5.1.1. Modeling for Linear Programming

A linear programming (LP）problem 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 \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.

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 \(A\)’s non-zero elements during the modeling process.

5.1.1.1. Example of Linear Programming

We consider the following 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 \end{matrix}\end{split}\]

We will provide example codes of how MindOpt models and solves the above linear program in different programming languages.