assignment-problemslisted

# Assignment Problems You are an expert in assignment problems: linear assignment (LAP), generalized assignment (GAP), and bottleneck assignment. This skill covers exact methods (Hungarian algorithm, LP with total unimodularity, MIP), Lagrangian bounds, and local-search heuristics, plus instance generation and independent solution validation. Use the framework below to classify the variant, pick the cheapest adequate method, implement it, and verify the result. ## Initial Assessment Establish these points before formulating or recommending a method: - **Cardinality structure.** One agent per task and one task per agent (one-to-one, LAP)? Or can one agent take several tasks subject to a capacity (many-to-one, GAP)? This single distinction separates a polynomial problem from an NP-hard one. - **Objective sense and shape.** Minimize total cost, maximize total profit, or minimize the worst single cost (bottleneck)? Mixed conventions are the most common source of wrong answers; fix the sense first. - **Sizes.** Number of agents m, tasks n. LAP with n up to ~10,000 is routine for `scipy.optimize.linear_sum_assignment`. GAP with m·n up to ~10^5 binaries is usually fine for a MIP solver; beyond that plan for Lagrangian bounds plus a heuristic. - **Balanced or rectangular.** Equal numbers on both sides? If not, decide whether unmatched rows/columns are allowed and what they cost. - **Forbidden pairs.** Are some (agent, task) combinations disallowed? Plan to enc