Integer Linear Programming (ILP)

Linear constraints are mathematical inequalities or equalities that define the feasible region of solutions. They model the real-world limitations and requirements of the allocation problem.

• Form: a₁x₁ + a₂x₂ + ... + aₙxₙ ≤ b (or =, ≥).
• Common Types in Allocation:
  • Task Coverage: Each task must be assigned to exactly one agent: Σ x_{ij} = 1 for all tasks i.
  • Agent Capacity: An agent cannot exceed its maximum workload: Σ (Workload_i * x_{ij}) ≤ Capacity_j.
  • Precedence: Task k must be assigned before Task l can start.

Integrality constraints are the defining feature of ILP, requiring some or all decision variables to take on integer values (not fractional). This is crucial for modeling indivisible assignments.

• Binary Variables: The most common case for assignment: x ∈ {0,1}.
• Impact: This constraint transforms a computationally easier Linear Program (LP) into an NP-hard Integer Linear Program. The solver must search a combinatorial space of discrete solutions.
• Relaxation: A common technique is to solve the LP relaxation (ignoring integrality) first to obtain a bound, then use branch-and-bound algorithms to find the integer optimum.

The ILP solver (e.g., Gurobi, CPLEX, OR-Tools) is the algorithmic engine that finds the optimal assignment. The solution is the set of variable values that satisfy all constraints and optimize the objective.

• Optimal Solution: The best possible assignment according to the objective function.
• Feasible Solution: Any assignment that satisfies all constraints, but may not be optimal.
• Infeasible Model: A formulation where no assignment can satisfy all constraints simultaneously, indicating a flaw in the problem definition or overly restrictive limits.

An ILP model can be viewed as a highly structured Constraint Satisfaction Problem (CSP) with an optimization objective.

• Variables & Domains: ILP variables with integer domains map directly to CSP variables.
• Linear Constraints: These are the hard constraints of the CSP.
• Objective Function: The CSP lacks this; ILP adds it to select the best among many feasible solutions.
• Solving: ILP solvers use advanced techniques like branch-and-bound and cutting planes, which are more efficient for this class of linear problems than general CSP solvers.

The Linear Programming (LP) Relaxation of an ILP is formed by removing the integer constraints, allowing variables to take any real value within their bounds. Solving the LP relaxation is a fundamental step in most ILP solvers because it provides a lower bound (for minimization) on the optimal integer solution's value. The gap between the LP solution and the true integer optimum is called the integrality gap.

• Solver Role: Used within Branch-and-Bound algorithms to prune search trees. If the LP relaxation of a node is worse than the best-known integer solution, that branch is discarded.
• Special Case: Totally Unimodular Matrices: If the constraint matrix is totally unimodular, the LP relaxation naturally yields an integer solution, making the ILP solvable in polynomial time.

Branch and Bound is the dominant algorithmic paradigm for solving NP-hard ILPs and MILPs to optimality. It systematically explores the space of possible integer solutions by dividing the problem into smaller subproblems (branching) and eliminating subproblems that cannot contain a better solution than one already found (bounding).

• Branching: Selects an integer variable with a fractional value in the LP relaxation and creates two new subproblems, fixing the variable to floor and ceiling values.
• Bounding: Solves the LP relaxation for each subproblem. If its objective value is worse than the current best integer solution (the incumbent), the entire subtree is pruned.
• Modern Enhancements: Combined with cutting plane methods (Branch-and-Cut) and heuristic diving to find good incumbents early.

For large or complex ILPs where finding the provably optimal solution is computationally prohibitive, heuristics and metaheuristics provide good-quality, feasible solutions in reasonable time. These are approximate methods that trade optimality guarantees for speed.

• Constructive Heuristics: Greedy algorithms that build a solution step-by-step (e.g., assign each task to the agent with the lowest incremental cost).
• Local Search: Starts with a feasible solution and iteratively improves it by making small changes (e.g., swapping task assignments between two agents).
• Metaheuristics: High-level frameworks for guiding the search process:
  • Genetic Algorithms (GA): Evolve a population of candidate allocations using selection, crossover, and mutation.
  • Simulated Annealing: Allows occasional "worse" moves to escape local optima, with decreasing probability over time.
  • Tabu Search: Uses memory to avoid revisiting recently explored solutions.

The Assignment Problem is a classic, specialized ILP for optimally matching two equal-sized sets (e.g., n tasks to n agents) on a one-to-one basis to minimize total cost or maximize total benefit. It is modeled with binary decision variables x_ij and has the special property that its constraint matrix is totally unimodular, meaning its LP relaxation yields an integer solution. This makes it solvable in polynomial time using the Hungarian Algorithm (O(n³)).

• Standard Form: min Σ Σ c_ij * x_ij subject to Σ x_ij = 1 for all i (each task assigned), Σ x_ij = 1 for all j (each agent gets one task).
• Generalization: The Generalized Assignment Problem (GAP) allows multiple tasks per agent with resource capacity constraints, which is NP-hard.
• Use Case: Foundational for understanding the simplest form of optimal, centralized task allocation.