DCT Lexicon · Optimization
Mixed-integer programming (MILP)
An optimization problem in which some decisions are whole numbers (in or out, which quarter); branch-and-bound solves it, and the gap between the best plan found and the largest open bound certifies how far from best the answer can be.
Drafted for the author's approval from Vol. II, Definition 4.1 and Theorem 4.4
In depth
In the book
A nonlinear enterprise optimization (NEO) problem is an instance with , the , and the continuously differentiable (twice, where second-order statements are made) and no convexity required. … The instance is smooth if is empty and mixed-integer otherwise; integer coordinates range over finite sets.
Vol. II, Definition 4.1 (Nonlinear Enterprise Optimization Problem), verbatim
The certificate
A certificate at every stage. The incumbent’s value is at most the best value, and the best value is at most the larger of the incumbent’s value and the largest bound of an open node; their difference is a valid optimality gap.
Vol. II, Theorem 4.4(i) (Branch-and-Bound Theorem), verbatim
Intuition
Many transformation decisions are lumpy: a project is in or out, starts in one quarter or another, a tranche is released whole. An integer program searches those combinations and, at every stage, can say how much better than its current best plan any plan could still be.
Drafted for the author's approval
Common misreading
A common mistake is to round a relaxation’s answer, or to report a plan without its gap.
Vol. II, LOS 4.5, verbatim
How AXIOM uses it
Optimize chooses which initiatives to include and when to start them with a mixed-integer program whose floor is a sample-average chance constraint: designed on 400 paths with HiGHS, certified on 100,000 fresh paths. Its result is optimal within the stated gap on the design paths, and statistical on the fresh ones.
Drafted for the author's approval, from AXIOM's method passport "Optimize: include and start"
In the book: Vol. II, Ch. 4: Nonlinear and Mixed-Integer Enterprise Optimization · Vol. II, Ch. 9: Stochastic Enterprise Optimization
Related: Optimal (with solver evidence) · Linear program (joint consistency) · General Enterprise Optimization Problem
V2.Def.4.1 · V2.Thm.4.4 · V2.Tab.4.3 · V2.Thm.9.3


