5.1.1. Modeling for linear programming

Linear programming (LP) 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,\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.

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.1.1.1. Examples of linear programming problems

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 \end{matrix}\end{split}\]

The following part describes how to use MindOpt to build a model and solve the optimization problem. Examples are provided for different programming languages. You can input non-zero elements into the matrix in two ways:

  1. By row (constraint)

  2. By column (variable)

Note

  • When you input elements by row, you only need to input the column index and non-zero value of each non-zero element in a row.

  • When you input elements by column, you only need to input the column index and non-zero value of each non-zero element in a column.