Milp

Mixed-integer linear programming (MILP) is the class of optimization problems that seek to minimize or maximize a linear objective function subject to linear constraints, where some decision variables are required to take integer values. MILP combines continuous variables and integer variables, allowing models to represent discrete decisions such as on/off choices, counts, or allocations. A typical MILP can be written as: minimize c^T x + d^T z subject to A x + E z ≤ b, with x ≥ 0 and z ∈ Z^k, where some variables may be restricted to binary values (0 or 1).

MILP is NP-hard in general because the integer requirements introduce combinatorial complexity, even when the linear part is easy to solve. If all variables are continuous, the problem reduces to a linear program (LP), solvable in polynomial time. In practice, MILPs are solved by exploiting the LP relaxation to obtain bounds and guide a search over feasible integer assignments. Common exact methods include branch-and-bound, branch-and-cut (which adds cutting planes to tighten the relaxation), and branch-and-price for problems with a decomposable structure. Heuristic and metaheuristic approaches may provide good feasible solutions quickly when exact methods are too slow.

Applications of MILP span production planning, facility location, scheduling, routing and logistics, energy systems, and portfolio optimization. It is a standard tool in operations research and management science due to its ability to model a range of discrete and continuous decisions. Modeling languages such as AMPL, GAMS, Pyomo, and PuLP are commonly used, with solvers including CPLEX, Gurobi, SCIP, CBC, and GLPK.