5.2.1. Modeling for Mixed-Integer Linear Programming

A mixed-integer linear program (MILP) can be represented in the following mathematical form:

\[\begin{split}\begin{matrix} \min &-c^f &+& c^Tx \\ \mbox{s.t.} &l^r &\leq& Ax &\leq& u^r \\ & l^c &\leq &x &\leq &u^c \\ & & x_k \in \mathbb{Z}, & k \in [I] \end{matrix}\end{split}\]

where

• \(x \in \mathbb{R}^{n}\) is the decision variable,

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

• \(c^f \in \mathbb{R}\) is the constant term in the objective function,

• \(c \in \mathbb{R}^{n}\) is the linear coefficient in the objective function,

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

• \(l^r \in \mathbb{R}^{m}\) and \(u^r \in \mathbb{R}^{m}\) are the lower and upper bounds of the constraints,

• \(x_k \in \mathbb{Z},~k\in [I]\) denotes the integer constraints for part of the decision variable \(x\).

The steps to use MindOpt are as follows:

1. Create an optimization model;

2. Input the optimization problem and set algorithm parameters;

3. Solve the optimization problem and retrieve the optimal solutions.

Note

MindOpt only stores the non-zero elements in the constraint matrix \(A\). Therefore, we only need to input the positions and the values of the non-zero elements during the modeling process.

5.2.1.1. Example of Mixed-Integer Linear Programming

We consider the following mixed-integer linear program:

\[\begin{split}\begin{matrix} \min & 1 x_0 & + & 2 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 \in \mathbb{Z} \end{matrix}\end{split}\]

We will show how MindOpt models and solves the above program. The key difference comparing to the linear programs is setting the variable attribute to integer or binary when adding new variables.

We will provide example codes in different programming languages.