MILPs

Mixed-integer linear programs (MILPs) are a class of mathematical optimization problems in which the objective and all constraints are linear, and some decision variables are restricted to take integer values. A standard MILP can be written as minimize c^T x subject to Ax ≤ b, x ≥ 0, with x_j ∈ Z for a subset of indices j in I. If the integer variables are only binary, the problem is a 0-1 MILP; if integers can take larger values, it is a general MILP. The remaining variables are continuous.

MILPs combine continuous and discrete decisions, making them more expressive than linear programs (LPs) while retaining a linear structure. Common formulations include production levels, facility locations, scheduling decisions, and yes/no choices. In many cases, the problem is linear in all relevant quantities but the integrality constraints capture essential decision traits such as on/off, reachability, or capacity steps.

Solving MILPs typically relies on specialized algorithms that extend linear programming techniques. A common approach is to solve the LP relaxation (ignoring integrality) to obtain a bound, then use branch-and-bound or branch-and-cut to enforce integrality. Cutting planes, heuristics, and problem decompositions are often used to tighten relaxations or find feasible good solutions quickly. The field has mature software, and modern solvers can handle large-scale MILPs efficiently in many practical applications.

Applications of MILPs span supply chain, manufacturing, energy systems, finance, transportation, and scheduling. A classic example is the knapsack problem, where binary variables select items to maximize value subject to a weight constraint. Toolkits include Gurobi, CPLEX, CBC, MOSEK, and SCIP.