Math——运筹优化开源求解器-GLPK的使用

本文介绍各种运筹优化开源求解器-GLPK的使用

  • GLPK是一款完全开源免费的运筹优化求解器，可以任意商用

Ubuntu安装GLPK

  • 据说Ubuntu安装较为方便，所以建议首选Ubuntu

  • 在网站下载文件：https://ftp.gnu.org/gnu/glpk/

    • 可以下载任意版本，建议选最新

  • 安装命令

    1
    2
    3
    4
    tar -xzvf glpk-xxx.tar.gz
    ./configure
    make
    sudo make install

  • 安装后直接执行可能出现错误

    1
    error while loading shared libraries: libglpk.so.36:...

  • 解决方案（原始解决方案地址）：

    1
    https://github.com/rstudio/renv/issues/1881

Ubuntu下GLPK的使用

  • 下列式子参考了：线性规划工具　GLPK 的安装及基本使用

  • 创建问题描述文件glpkDemo.mod

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /* Variables */
    var x1 >= 0;
    var x2 >= 0;
    var x3 >= 0;

    /* Object function */
    maximize z: 3*x1 + x2 +2*x3;

    /* Constrains */
    s.t. con1: x1 + x2 + 3*x3 <= 30;
    s.t. con2: 2*x1 +2*x2 + 5*x3 <= 24;
    s.t. con3: 4*x1 + x2 + 2*x3 <= 36;

    end;

  • 执行命令解决问题

    1
    glpsol -m glpkDemo.mod -o ./output/glpkDemo.sol

  • 输出文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    Problem:    glpkDemo
    Rows:       4
    Columns:    3
    Non-zeros:  12
    Status:     OPTIMAL
    Objective:  z = 28 (MAXimum)

       No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
    ------ ------------ -- ------------- ------------- ------------- -------------
         1 z            B             28                             
         2 a            B             12                          30 
         3 b            NU            24                          24      0.166667 
         4 c            NU            36                          36      0.666667 

       No. Column name  St   Activity     Lower bound   Upper bound    Marginal
    ------ ------------ -- ------------- ------------- ------------- -------------
         1 x1           B              8             0               
         2 x2           B              4             0               
         3 x3           NL             0             0                   -0.166667 

    Karush-Kuhn-Tucker optimality conditions:

    KKT.PE: max.abs.err = 0.00e+00 on row 0
            max.rel.err = 0.00e+00 on row 0
            High quality

    KKT.PB: max.abs.err = 0.00e+00 on row 0
            max.rel.err = 0.00e+00 on row 0
            High quality

    KKT.DE: max.abs.err = 2.22e-16 on column 1
            max.rel.err = 3.17e-17 on column 1
            High quality

    KKT.DB: max.abs.err = 0.00e+00 on row 0
            max.rel.err = 0.00e+00 on row 0
            High quality

    End of output

  • Activity这一列就是想要的解

  • 其他输出项如何理解？

自动化生成问题

  • 使用shell或者Python自动生成.mod文件，然后自然解析.sol文件，实现自动化测试参数