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

---

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

---

1. 项目场景

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

min ⁡    c 1 x 1 + c 2 x 2 + ⋯ + c n x n s.t.   a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 … a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m x 1 , x 2 , … , x n ≥ 0 min  c1x1+c2x2+⋯+cnxns.t.  a11x1+a12x2+⋯+a1nxn=b1a21x1+a22x2+⋯+a2nxn=b2…am1x1+am2x2+⋯+amnxn=bmx1,x2,…,xn≥0

min  s.t.  ​c1​x1​+c2​x2​+⋯+cn​xn​a11​x1​+a12​x2​+⋯+a1n​xn​=b1​a21​x1​+a22​x2​+⋯+a2n​xn​=b2​…am1​x1​+am2​x2​+⋯+amn​xn​=bm​x1​,x2​,…,xn​≥0​

或者写成如下形式：

min ⁡   c x   s.t.  { A x = b x ≽ 0 \min\ \bf{cx}\ \ \textrm{s.t.}\ \left\{Ax=bx≽0

\right. min cx  s.t. {Ax=bx≽0​

并且 $\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$

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

max ⁡ 5 x 1 + 10 x 2 s.t. 8 x 1 + 8 x 2 ≤ 160 4 x 1 + 12 x 2 ≤ 180 x 1 ≤ 15 x 1 , x 2 ≥ 0 max5x1+10x2s.t.8x1+8x2≤1604x1+12x2≤180x1≤15x1,x2≥0

maxs.t.​5x1​+10x2​8x1​+8x2​≤1604x1​+12x2​≤180x1​≤15x1​,x2​≥0​

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

min ⁡ − 5 x 1 − 10 x 2 s.t. 8 x 1 + 8 x 2 + x 3 = 160 4 x 1 + 12 x 2 + x 4 = 180 x 1 + x 5 = 15 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 min−5x1−10x2s.t.8x1+8x2+x3=1604x1+12x2+x4=180x1+x5=15x1,x2,x3,x4,x5≥0

mins.t.​−5x1​−10x2​8x1​+8x2​+x3​=1604x1​+12x2​+x4​=180x1​+x5​=15x1​,x2​,x3​,x4​,x5​≥0​

接着输入文件 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
1
2
3
4
5

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

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

---

4. 如何构建模型

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

sudo apt install build-essential cmake make
1

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

cd LinprogSolver4C && cmake CMakeLists.txt
1

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

make
1

---

5. 如何使用

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

./linprog data.txt # any data paths
1

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

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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

0 - optimal

1 - terminated by maxIter

2 - infeasible

---

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