Mixed Integer Programming

293. Mixed Integer Programming

293.1. MIP (Mixed Integer Programming)

Optimizing (maximizing or minimizing) a linear objective function subject to linear equality or inequality constraints. Decision variables can take any continuous real or integer values

Minimize (or Maximize):

𝑐^{𝑇} 𝑥

Subject to:

$𝐴 𝑥 \leq 𝑏$
$𝑥_{𝑖} \in ℤ$ for some $𝑖$
$𝑥_{𝑗} \in ℝ$ for the remaining $𝑗$

Where:

$𝑥$ is the vector of decision variables
$𝑐$ is the vector of objective function coefficients
$𝐴$ is the constraint coefficient matrix
$𝑏$ is the vector of constraint right-hand side values
$𝑥_{𝑖}$ represents integer variables
$𝑥_{𝑗}$ represents continuous variables

Example

Objective Function

Maximize

𝑐^{𝑇} 𝑥

[\begin{matrix} 3 & 2 & - 5 & - 4 \end{matrix}] [\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \\ 𝑥_{3} \\ 𝑥_{4} \end{matrix}]

Constraints

𝐴 𝑥 \leq 𝑏

[\begin{matrix} 1 & 2 & 0 & 0 \\ 3 & 1 & 0 & 0 \\ 1 & 0 & - 5 & 0 \\ 0 & 1 & 0 & - 5 \end{matrix}] [\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \\ 𝑥_{3} \\ 𝑥_{4} \end{matrix}] \leq [\begin{matrix} 8 \\ 12 \\ 0 \\ 0 \end{matrix}]