Mixed Integer Program¶

Definition¶

A mixed integer program (MIP) is an integer linear program containing both integer-restricted decision variables and continuous decision variables. Binary variables may be used for the discrete decisions.

Interpretation¶

A mixed integer program combines indivisible decisions, such as whether to buy a machine, with divisible quantities, such as how much to produce. A single model can thus select a discrete action and determine continuous quantities that depend on it, which is why the domain of each variable must be stated individually.

A feasible polygon cut into vertical segments at integer values of x1, since x2 may vary continuously; the MIP optimum (3, 1.75) and the LP optimum (3.5, 1.25) are marked.

Here only $x_1$ must be an integer, so the feasible set consists of vertical segments at $x_1=0,1,2,3$ $0, 1, 2, 3$ , each running up to the line $2x_1+2x_2=9.5$ $9.5$ . On the segment $x_1=3$ the variable $x_2$ can rise to $1.75$ , which gives the optimum $(3,1.75)$ with $z=12.5$ $12.5$ .

This value lies between the pure-integer optimum 11 and the LP optimum 13, and the same order holds for any maximization problem with finite optima: requiring integrality of fewer variables allows more points, so the mixed problem is a relaxation of the pure integer program, and the LP is a relaxation of both.

Integer linear programming supplies the integrality restrictions; a mixed model keeps them on some decisions only. A typical pattern pairs a binary variable with continuous quantities, as in $x_1+x_2\le100+50y$ from the Examples, where buying the machine ( $y =$ $y=1$ $1$ ) raises the production limit from 100 to 150.

A common slip is to declare every variable integer by accident. In the figure this would turn the problem into the pure integer program and lower the optimal value from $12.5$ to $11$ .

Key Results¶

An LP relaxation removes integrality only from the restricted variables.
Continuous variables should not accidentally be forced to integer values.
Logical modelling often introduces auxiliary binary variables alongside quantities.

Examples¶

The figure maximizes $3x_1+2x_2$ under $2x_1+2x_2\le9.5$ $9.5$ , $x_1\le3.5$ and $\boldsymbol{x}\ge0$ $0$ , with only $x_1$ integer. Its optimum $(3,1.75)$ has value 12.5, between the pure-integer value 11 and the continuous relaxation value 13.

$x_1+x_2\le100+50y$ combines continuous production with a binary machine-purchase decision.
Continuous job start times (as in the job sequencing model) can be combined with binary variables specifying which job comes first.

Prerequisites¶

Sources¶

OR Modelling · Week 2

Aliases: MIP, mixed integer linear program, MILP, mixed integer programming, mixed-integer linear programming

Last updated: 20 October 2026 03:02