Integer Linear Programming (ILP)

The objective function is a linear expression that defines the goal of the optimization, which the solver must either maximize or minimize. It quantifies the total cost, profit, or utility of a given assignment.

• Form: Typically Z = c₁x₁ + c₂x₂ + ... + cₙxₙ, where cᵢ are coefficients (e.g., cost, time) and xᵢ are decision variables.
• Purpose: Provides a single metric to evaluate and compare different task allocation plans.
• Example: In a task allocation problem, this could be Minimize Total_Cost = Σ (Cost_of_Agent_i_for_Task_j * Assign_i_j).

Decision variables represent the choices the solver can make. In task allocation, these are typically binary (0/1) variables that indicate whether a specific task is assigned to a particular agent.

• Integer Requirement: For classic assignment, variables are binary integers (e.g., x_{ij} ∈ {0,1}).
• Semantics: x_{ij} = 1 means "Task i is assigned to Agent j."
• Role: The solver's job is to find the optimal set of variables (the assignment) that satisfies all constraints while optimizing the objective.

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.

A Constraint Satisfaction Problem (CSP) is a mathematical formalism used to model decision problems by defining a set of variables, their possible domains, and a set of constraints that specify allowable combinations of values. In task allocation, variables represent task-agent assignments, domains are the agents available for each task, and constraints encode hard rules like agent capabilities or mutual exclusivity. While ILP optimizes a linear objective, a CSP solver focuses on finding any feasible assignment that satisfies all constraints, making it suitable for feasibility checks before optimization.

• Key Difference from ILP: CSPs seek satisfaction; ILP seeks optimal satisfaction with a numeric objective.
• Common Solvers: Backtracking search with constraint propagation (e.g., arc-consistency).
• Use Case: Verifying if a task allocation respecting all agent skill requirements is even possible.

Mixed-Integer Linear Programming (MILP) is a direct generalization of Integer Linear Programming where only some decision variables are required to be integers, while others can be continuous. This hybrid formulation is exceptionally powerful for modeling real-world allocation problems that combine discrete choices (e.g., "assign agent A to task 1: yes/no") with continuous quantities (e.g., "allocate 3.5 hours of agent B's time").

• Mathematical Form: min cᵀx + dᵀy subject to Ax + By ≤ b, with x integer and y continuous.
• Advantage: Provides modeling flexibility for problems with both discrete assignment and resource rationing.
• Solver Impact: MILPs are also NP-hard, but modern solvers like Gurobi and CPLEX use advanced branch-and-cut algorithms.

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.