Skip to content

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 max⁡u∈RnJ(u)subject togi(u)≤0 (i=1,…,m),hj(u)=0 (j=1,…,p),uk integer (k∈I),\max_{u \in \mathbb{R}^n} J(u) \quad \text{subject to} \quad g_i(u) \le 0 \ (i = 1, \dots, m), \quad h_j(u) = 0 \ (j = 1, \dots, p), \quad u_k \text{ integer } (k \in I), with JJ, the gig_i, and the hjh_j continuously differentiable (twice, where second-order statements are made) and no convexity required. … The instance is smooth if II 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