Mixed-Integer Linear Programming (MILP)

The goal of a MILP is to minimize or maximize a single, linear objective function. This function is a weighted sum of decision variables, such as 3x + 2y - z. The linearity is a strict requirement; terms like x² or x*y are not permitted. This property ensures that the objective's contribution from each variable is constant and proportional, a key assumption that enables the use of powerful, convergent solution algorithms like branch-and-bound.

All restrictions on the decision variables must be expressed as linear equalities or inequalities. A typical constraint takes the form a₁x₁ + a₂x₂ ≤ b. This linearity defines a feasible region that is a convex polytope in the continuous space. The intersection of these linear constraints creates the search space where the optimal solution must reside, and the linearity guarantees that the optimal continuous solution will be at a vertex of this polytope.

The defining feature of MILP is that some decision variables are restricted to integer values. These are the 'integer' variables in 'Mixed-Integer'. Common restrictions include:

• Binary variables: x ∈ {0, 1}, used to model yes/no decisions like facility location or task assignment.
• General integers: y ∈ {0, 1, 2, ...}, used for counting discrete items like vehicles or batches. This integrality transforms the problem from a tractable Linear Program (LP) into a combinatorial one, making it NP-hard.

A MILP model explicitly partitions its decision variables into two distinct sets:

• Continuous variables: Can take any real value within bounds, often representing flow rates, temperatures, or percentages.
• Integer variables: Restricted to discrete values, representing structural or logical decisions. This 'mixed' nature allows a single model to capture both the high-level strategic choices (discrete) and the fine-grained operational quantities (continuous) of a system, such as deciding which warehouses to open (integer) and how much product to ship from each (continuous).

A standard MILP formulation assumes that all input parameters—such as costs, demands, and resource capacities—are known with certainty at the time of solving. The model does not inherently account for uncertainty or variability in the data. This contrasts with Stochastic Optimization or Robust Optimization, which explicitly incorporate data uncertainty. In a deterministic MILP, the output is a single, optimal action plan contingent on the exact data provided.

The addition of integer variables makes MILP a combinatorially explosive problem. It belongs to the class of NP-hard problems, meaning there is no known algorithm that can solve all instances in polynomial time. The computational effort can grow exponentially with the number of integer variables. Practical solvers use sophisticated techniques like the Simplex method for continuous relaxations, combined with branch-and-bound, cutting planes, and heuristics to close the optimality gap and find provably optimal solutions within a reasonable timeframe.

The continuous relaxation of MILP where all decision variables are allowed to take fractional values. LP problems are solvable in polynomial time using the Simplex Method or interior-point methods. In a MILP context, solving the LP relaxation provides a lower bound (for minimization) that is critical for the Branch and Bound algorithm. If the LP relaxation solution happens to satisfy integrality constraints, it is optimal for the MILP.

The most common exact algorithm for solving MILPs to global optimality. It systematically partitions the feasible region by branching on fractional integer variables, creating subproblems. For each subproblem, the LP relaxation is solved to compute a bound. Subtrees are pruned when their bound is worse than the incumbent best integer solution, or when the subproblem is infeasible. Modern solvers enhance this with cutting planes, heuristics, and presolve routines.

A complementary paradigm to MILP that excels when constraints are logical or combinatorial rather than purely linear. CP uses constraint propagation and systematic search to reduce variable domains. While MILP relies on a linear objective and convex relaxations, CP handles non-linear constraints like all-different or cumulative natively. Hybrid MILP/CP approaches are increasingly used for complex scheduling and routing problems.

When MILP problems become too large for exact solvers, heuristic methods find good, but not provably optimal, solutions quickly. Key approaches include:

• Genetic Algorithms: Evolve populations of solutions via crossover and mutation
• Simulated Annealing: Probabilistically escape local optima by accepting worse solutions
• Large Neighborhood Search: Destroy and repair portions of a solution iteratively These are often embedded within MILP solvers as primal heuristics to find feasible integer solutions early.

A canonical application domain for MILP. The VRP seeks optimal routes for a fleet of vehicles serving customers, minimizing total distance or cost. Standard MILP formulations use three-index or two-index vehicle flow models with subtour elimination constraints. Real-world variants add time windows (VRPTW), capacity limits (CVRP), and heterogeneous fleets. These problems are NP-hard, and MILP solvers are typically combined with column generation or decomposition for large instances.

Extends MILP to handle uncertainty in parameters such as demand, costs, or yields. A two-stage stochastic MILP formulates a recourse problem: first-stage decisions are made before uncertainty is revealed, and second-stage decisions adapt after. The deterministic equivalent is a large-scale MILP over multiple scenarios. This contrasts with Robust Optimization, which immunizes against worst-case realizations within an uncertainty set rather than optimizing expected value.