mathematics//optimization//combinatorial optimization//integer linear programming
Integer linear programming is the class of optimization problems with a linear cost, linear constraints and decision variables restricted to integers, often to 0 or 1; it is the modelling language of industrial scheduling, vehicle routing, the daily commitment of power plants and fleet allocation, solved by mature commercial and open solvers. When some variables are continuous and others integer it is called mixed-integer (MILP), which is the common case.
Integer linear programming is the class of optimization problems with a linear cost, linear constraints and decision variables restricted to integers, often to 0 or 1; it is the modelling language of industrial scheduling, vehicle routing, the daily commitment of power plants and fleet allocation, solved by mature commercial and open solvers. When some variables are continuous and others integer it is called mixed-integer (MILP), which is the common case.
minx c⊤xsubject toAx≤b,x∈{0,1}n\min_{x}\; c^{\top}x \quad\text{subject to}\quad Ax\le b,\qquad x\in\{0,1\}^nxminc⊤xsubject toAx≤b,x∈{0,1}n
Each xix_ixi is a yes or no decision (this robot takes this order, this generator runs tomorrow), ccc holds what each decision costs, and the rows of Ax≤bAx\le bAx≤b say what must hold: capacities, each task done once, a robot in one place at a time. The binary variables make modelling flexible (a fixed cost paid only if a site is opened, a logical if this then that), and they also make the problem hard: nnn binaries have 2n2^n2n combinations, more than 101810^{18}1018 at n=60n=60n=60.
The formulation is the craft. Solvers relax the integers to continuous values, solve that linear program for a bound, and search with branch and bound; a model whose relaxation sits close to the integer optimum solves in seconds, while a logically equivalent model with a loose relaxation can run for days.
Nonlinear problems are often brought into this form. The book's resource-to-target assignment, whose objective multiplies probabilities, can be rewritten with one binary per target and number of agents sent there, turning the product into a lookup of precomputed values and the problem into an integer program a solver finishes in seconds or minutes for tens of agents (weapon-target assignment).
The solvers are the product of decades of engineering: Gurobi and CPLEX commercially, HiGHS, SCIP, CBC and OR-Tools in the open. They report the optimality gap as they go, so a run can be stopped with a known quality. Grid operators solve unit commitment (which generators to start tomorrow, under ramp and reserve limits) as a mixed-integer program every day, and an MPC with on and off decisions becomes one at every step.
Time is the cost to watch. A plan computed overnight can wait for the solver; a dispatch loop of a few seconds needs a time limit, a fallback heuristic and the knowledge that NP-hardness makes the solve time of tomorrow's instance unpredictable from today's.