Mixed-Integer Linear Programming (MILP)

The goal of a MILP model is to maximize or minimize a single, linear objective function. This function is a weighted sum of the decision variables, where each variable's contribution is directly proportional to its value. For example, a logistics model might minimize total_cost = 5*x1 + 3*x2 + 10*y1, where x represents continuous mileage and y represents a binary decision to dispatch a vehicle. This linearity ensures the objective landscape is a convex polyhedron, a property exploited by solvers.

All restrictions on the decision variables must be expressed as linear equalities or inequalities. A constraint like 2*x + 3*y <= 100 is valid, representing a resource limit. This linearity defines a feasible region that is a convex polytope. Key constraint types include:

• Resource capacity: Total demand assigned to a vehicle cannot exceed its weight limit.
• Flow conservation: The number of vehicles entering a node must equal the number leaving.
• Logical conditions: A binary variable y can force a continuous variable x to zero via x <= M*y, where M is a large constant.

The defining characteristic of MILP is that some decision variables are restricted to integer values. This is what makes the problem hard (NP-hard) but also what gives it immense modeling power. Common integer variable types include:

• Binary variables (0 or 1): Model yes/no decisions like opening a warehouse, assigning a driver to a route, or establishing a precedence relationship.
• General integer variables: Represent discrete, countable items like the number of pallets to load or the number of stops on a route. Without integrality, the model is a simple Linear Program (LP), solvable in polynomial time. The addition of integers introduces combinatorial complexity.

MILP problems are solved using the Branch-and-Bound algorithm, an exact tree-search method. The process works by:

• Relaxation: First, the integer constraints are removed, and the resulting LP is solved quickly. This provides a lower bound (for minimization) on the optimal cost.
• Branching: If a variable x that must be an integer has a fractional value in the LP solution, say x = 3.7, the problem is split into two new subproblems: one with x <= 3 and another with x >= 4.
• Bounding & Pruning: If the LP solution for a branch is worse than the best known integer solution, that entire branch is discarded. This systematic search guarantees a globally optimal solution is found.

Unlike heuristic or metaheuristic methods which provide good but unverified solutions, a MILP solver provides a provably globally optimal solution and a MIP gap that quantifies solution quality. The MIP gap is the relative difference between the best found integer solution and the best remaining theoretical bound. A gap of 0.0% proves optimality. For large, complex problems, solvers can be stopped early with a guarantee like 'this solution is within 1.5% of the true optimum.' This mathematical rigor is critical for high-stakes strategic decisions like network design or capital allocation.

A key architectural principle is the strict separation between the mathematical model and the solver engine. The model is a declarative description of the problem—variables, objective, and constraints—written in a modeling language or API. The solver (e.g., Gurobi, CPLEX, OR-Tools) is the algorithmic engine that processes this model. This separation allows:

• Solver interchangeability: The same model can be solved by different engines without rewriting the logic.
• Algorithmic advances: Improvements in solver heuristics, cutting planes, and presolve routines automatically benefit all existing models without modification.

The continuous relaxation of a MILP, formed by temporarily dropping the integrality constraints on integer variables. Solving this relaxation yields a lower bound (for minimization) on the optimal MILP objective. The solution to the LP relaxation is the starting point for Branch and Bound. If the relaxed solution happens to satisfy integrality, it is provably optimal for the original MILP.

Linear inequalities added to the MILP formulation that cut off fractional solutions from the LP relaxation without eliminating any feasible integer solutions. Cuts tighten the relaxation, improving the lower bound and accelerating convergence. Common families include Gomory cuts, clique cuts, and cover cuts. Modern solvers generate hundreds of cuts dynamically during the solve process.