C++内点法求解大规模线性规划问题——对标MATLAB中linprog函数

---

项目资源链接如下：https://download.csdn.net/download/weixin_46584887/86406561

---

1. 项目场景

对于如下大规模线性规划问题：

$$\begin{array}{rl}\min & c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n\\ \text{s.t.}& a_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=b_1\\ & a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=b_2\\ & \dots \\ & a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n=b_m\\ & x_1,x_2,\dots ,x_n\ge 0\end{array}$$

或者写成如下形式：

$$\min \mathbf{cx}\text{s.t.}\{\begin{array}{l}\mathbf{Ax}=\mathbf{b}\\ \mathbf{x}\succcurlyeq 0\end{array}$$

并且 $\mathbf{A}\in {\mathbf{R}}_{\mathbf{m}\times \mathbf{n}},\mathbf{x}\in {\mathbf{R}}_{\mathbf{n}\times 1},\mathbf{b}\in {\mathbf{R}}_{\mathbf{m}\times 1}$.

---

2. 约束的规范化

• 对于缺乏非负约束的变量 $x_i$，我们做出如下转化 ：

  • $x_i=x_{i1}-x_{i2}$

  • $x_{i1}\ge 0,x_{i2}\ge 0$

• 对于不等式约束，我们也需要将其松弛为等式约束:

  • ${\sum }_{j=0}^n{a}_{ij}{x}_j\le b_i$ 或者 ${\sum }_{j=0}^n{a}_{ij}{x}_j\ge b_i$

  • $x_{n+i}\pm {\sum }_{j=0}^n{a}_{ij}{x}_j=b_i,x_{n+i}\ge 0$

---

3. 输入格式

代码从文本文件中读取数据(data.txt):

• 该文本文件的第一行包含两个整数, m and n, 分别代表约束个数与变量个数
• 第二行的 n 个元素代表目标函数中变量前的系数 $c_i$
• 接下来 m 行每行包括 n + 1 个元素, 每行的前 n 个元素代表变量前的系数 $a_{ij}$,，最后一个元素代表 $b_i$

举个例子，对于如下线性规划问题:

$$\begin{array}{rl}\max & 5x_1+10x_2\\ \text{s.t.}& 8x_1+8x_2\le 160\\ & 4x_1+12x_2\le 180\\ & x_1\le 15\\ & x_1,x_2\ge 0\end{array}$$

我们首先要将其转换为如下形式:

$$\begin{array}{rl}\min & -5x_1-10x_2\\ \text{s.t.}& 8x_1+8x_2+x_3=160\\ & 4x_1+12x_2+x_4=180\\ & x_1+x_5=15\\ & x_1,x_2,x_3,x_4,x_5\ge 0\end{array}$$

接着输入文件 data.txt 中的内容应如下:

3 5
-5 -10 0 0 0
8 8 1 0 0 160
4 12 0 1 0 180
1 0 0 0 1 15

应注意的是，在上述情况下获得的求解结果不是特别精确。对于小规模模型的求解，我们可以尝试使用一些整数规划解算器，例如 Google 的 OR-Tools，或者使用单纯形法来求解。

对于大规模线性规划问题（包括整数和浮点数），代码的求解精度是不错的。

---

4. 如何构建模型

确保你的电脑中有这些编译工具，以 Ubuntu 为例:

sudo apt install build-essential cmake make

接着进入项目目录，执行如下命令：

cd LinprogSolver4C && cmake CMakeLists.txt

可以看见目录中生成了 Makefile 文件，你可以使用 make 工具获得可执行文件:

make

---

5. 如何使用

在目录中构建出可执行文件之后，其用法如下：

./linprog data.txt # any data paths

在终端中可以得到如下输出:

1

LP problem:
 Iter  Residual        Mu    Alphax    Alphas
    0  2.70e-01  1.54e+00       ---       ---
    1  1.24e-03  6.01e-02  1.00e+00  1.00e+00
    2  7.97e-08  3.86e-06  1.00e+00  1.00e+00
    3  3.99e-12  1.93e-10  1.00e+00  1.00e+00
    4  2.06e-16  9.66e-15  1.00e+00  1.00e+00

----------------------------

Optx:
    1       7.5
    2        12
    3   2.4e-14
    4   2.6e-14
    5       7.5

----------------------------

linprog Terminated. Status : 0
[Iters: 4] [Time: 2.82e-03s]

第一行输出的整数含义如下:

0 - optimal

1 - terminated by maxIter

2 - infeasible

---

GitHub地址：https://github.com/ZhiQiangFeng