5.2.1. Mixed Integer Linear Programming

Mixed Integer Linear Programming (MILP) problems can be described by using the following mathematical model:

\[\begin{split}\min \quad&-c^f + c^Tx \\ \mbox{s.t.} \quad&l^r \leq Ax \leq u^r, \\ & l^c \leq x \leq u^c, \\ & partial\ x \in \mathbb{Z}^{n}\end{split}\]
In the preceding model:

  • \(x \in \mathbb{R}^{n}\) is a decision variable.

  • \(l^c \in \mathbb{R}^{n}\) and \(u^c \in \mathbb{R}^{n}\) are the lower bound and upper bound of \(x\).

  • \(c^f \in \mathbb{R}\) is a constant in the target function.

  • \(c \in \mathbb{R}^{n}\) is a coefficient in the target function.

  • \(A \in \mathbb{R}^{m \times n}\) is a constraint matrix.

  • \(l^r \in \mathbb{R}^{m}\) and \(u^r \in \mathbb{R}^{m}\) are the lower bound and upper bound of a constraint.

  • \(partial\ x \in \mathbb{Z}^{n}\) means the variables are integer.

The procedure of using MindOpt is as follows:

  1. Create an optimization model.

  2. Input an optimization problem and set algorithm parameters.

  3. Solve the problem and obtain the solution.

Note

MindOpt stores only non-zero elements in the constraint matrix \(A\) . Therefore, you only need to input the row/column index and non-zero value of each non-zero element in the constraint matrix.

5.2.1.1. Examples of MILP problems

Mixed Integer Linear Programming problem:

\[\begin{split}\begin{matrix} \min & 1 x_0 & + & 1 x_1 & + & 1 x_2 & + & 1 x_3 \\ \mbox{s.t.} & 1 x_0 & + & 1 x_1 & + & 2 x_2 & + & 3 x_3 & \geq & 1 \\ & 1 x_0 & & & - & 1 x_2 & + & 6 x_3 & = & 1 \end{matrix}\end{split}\]
\[\begin{split}\begin{matrix} 0 & \leq & x_0 & \leq & 10 \\ 0 & \leq & x_1 & \leq & \infty \\ 0 & \leq & x_2 & \leq & \infty \\ 0 & \leq & x_3 & \leq & \infty \\ & & x_0、x_1、x_2 \ are\ integer \end{matrix}\end{split}\]

The following part describes how to use MindOpt to build a model and solve the optimization problem.

Mixed Integer Linear Programming (MILP) differs from linear programming (LP) in the input of variables. For the modeling of integer constraints, the is_integer parameter should be set to True when adding the variables.

You can input non-zero elements into the constraint matrix in two ways:

  1. By row (constraint)

  2. By column (variable)

For more information, see Modeling for linear programming.

Examples are provided for different programming languages.