跳转到内容

GLPK/使用 GLPSOL

Add links
来自华夏公益教科书，开放的书籍，为开放的世界

此页面列出了一些使用 GLPSOL（GLPK 命令行求解器）时的技巧和提示。

请注意，默认情况下，GLPSOL 在构建 GLPK 时就已构建。因此，只要安装了 GLPK，GLPSOL 通常都应该存在。


用法

[编辑 | 编辑源代码]

用法

glpsol [options...] filename

例如，使用其长格式的选项

glpsol --cuts --fpump --mipgap 0.001 --model problem.mod --data problem.dat

选项

[编辑 | 编辑源代码]

以下信息来自用法选项--help.

一般选项

  --mps             read LP/MIP problem in fixed MPS format
  --freemps         read LP/MIP problem in free MPS format (default)
  --lp              read LP/MIP problem in CPLEX LP format
  --glp             read LP/MIP problem in GLPK format
  --math            read LP/MIP model written in GNU MathProg modeling
                    language
  -m filename, --model filename
                    read model section and optional data section from
                    filename (same as --math)
  -d filename, --data filename
                    read data section from filename (for --math only);
                    if model file also has data section, it is ignored
  -y filename, --display filename
                    send display output to filename (for --math only);
                    by default the output is sent to terminal
  --seed value      initialize pseudo-random number generator used in
                    MathProg model with specified seed (any integer);
                    if seed value is ?, some random seed will be used
  --mincost         read min-cost flow problem in DIMACS format
  --maxflow         read maximum flow problem in DIMACS format
  --simplex         use simplex method (default)
  --interior        use interior point method (LP only)
  -r filename, --read filename
                    read solution from filename rather to find it with
                    the solver
  --min             minimization
  --max             maximization
  --scale           scale problem (default)
  --noscale         do not scale problem
  -o filename, --output filename
                    write solution to filename in printable format
  -w filename, --write filename
                    write solution to filename in plain text format
  --ranges filename
                    write sensitivity analysis report to filename in
                    printable format (simplex only)
  --tmlim nnn       limit solution time to nnn seconds
  --memlim nnn      limit available memory to nnn megabytes
  --check           do not solve problem, check input data only
  --name probname   change problem name to probname
  --wmps filename   write problem to filename in fixed MPS format
  --wfreemps filename
                    write problem to filename in free MPS format
  --wlp filename    write problem to filename in CPLEX LP format
  --wglp filename   write problem to filename in GLPK format
  --log filename    write copy of terminal output to filename
  -h, --help        display this help information and exit
  -v, --version     display program version and exit

LP 基因分解选项

  --luf             LU + Forrest-Tomlin update
                    (faster, less stable; default)
  --cbg             LU + Schur complement + Bartels-Golub update
                    (slower, more stable)
  --cgr             LU + Schur complement + Givens rotation update
                    (slower, more stable)

单纯形求解器特有的选项

  --primal          use primal simplex (default)
  --dual            use dual simplex
  --std             use standard initial basis of all slacks
  --adv             use advanced initial basis (default)
  --bib             use Bixby's initial basis
  --ini filename    use as initial basis previously saved with -w
                    (disables LP presolver)
  --steep           use steepest edge technique (default)
  --nosteep         use standard "textbook" pricing
  --relax           use Harris' two-pass ratio test (default)
  --norelax         use standard "textbook" ratio test
  --presol          use presolver (default; assumes --scale and --adv)
  --nopresol        do not use presolver
  --exact           use simplex method based on exact arithmetic
  --xcheck          check final basis using exact arithmetic

内点求解器特有的选项

  --nord            use natural (original) ordering
  --qmd             use quotient minimum degree ordering
  --amd             use approximate minimum degree ordering (default)
  --symamd          use approximate minimum degree ordering

MIP 求解器特有的选项

  --nomip           consider all integer variables as continuous
                    (allows solving MIP as pure LP)
  --first           branch on first integer variable
  --last            branch on last integer variable
  --mostf           branch on most fractional variable
  --drtom           branch using heuristic by Driebeck and Tomlin
                    (default)
  --pcost           branch using hybrid pseudocost heuristic (may be
                    useful for hard instances)
  --dfs             backtrack using depth first search
  --bfs             backtrack using breadth first search
  --bestp           backtrack using the best projection heuristic
  --bestb           backtrack using node with best local bound
                    (default)
  --intopt          use MIP presolver (default)
  --nointopt        do not use MIP presolver
  --binarize        replace general integer variables by binary ones
                    (assumes --intopt)
  --fpump           apply feasibility pump heuristic
  --gomory          generate Gomory's mixed integer cuts
  --mir             generate MIR (mixed integer rounding) cuts
  --cover           generate mixed cover cuts
  --clique          generate clique cuts
  --cuts            generate all cuts above
  --mipgap tol      set relative mip gap tolerance to tol

CNF-SAT 可满足性问题的选项

 --cnf filename     read CNF-SAT problem in DIMACS format from filename
 --wcnf filename    write CNF-SAT problem in DIMACS format to filename
 --minisat          solve CNF-SAT problem with glp_infeas1 solver
 --objbnd bound     add inequality bounds to 0-1 feasibility problem (assumes --minisat)

压缩文件

[编辑 | 编辑源代码]

通过追加后缀可以减小输出文件的大小.gz。 [1] 这表示gzip 压缩。例如

glpsol ... --wlp squash.lp.gz

类似地，GLPSOL 将自动解压缩它遇到的任何以扩展名结尾的文件.gz.

标准流

[编辑 | 编辑源代码]

GLPSOL 支持以下三个标准流

  • /dev/stdin
  • /dev/stdout
  • /dev/stderr

这些由 GLPK I/O 例程以平台无关的方式视为特殊文件名。因此，以下命令应该在 Windows、Mac OS X 和 Linux 上都能正常工作，将求解报告传递到终端而不是传递到普通文件

glpsol .. --output "/dev/stdout"

通过命令行传递值

[编辑 | 编辑源代码]

如果您需要通过命令行传递参数值，以下示例演示了如何使用shell 脚本 来执行此操作。

shell 脚本，要么是test.bat或者test.sh，首先创建一个动态数据文件test.dat，其中包含所需的命令行值。然后，shell 脚本调用 GLPSOL，使用一个硬编码的模型名称，在本例中，该名称只是简单地打印最初从命令行传递的值。

步骤 Microsoft Windows Linux 和 Mac OS X [2]
创建一个模型文件 test.mod 
param p;
printf "p = %f\n", p;
end;
创建一个 shell 脚本文件 test.bat 
echo data;param p := %1;end; > test.dat
glpsol.exe -m test.mod -d test.dat
test.sh [3] 
#!/bin/sh
echo data\;param p := $1\;end\; > test.dat
glpsol -m test.mod -d test.dat
使该文件可执行  什么也不做 [4] 
chmod u+x test.sh
运行 shell 脚本 
test.bat 3.14159
 
./test.sh 3.14159

请注意，您可以在 shell 脚本中指定多个数据文件，例如

glpsol -m test.mod -d one.dat -d two.dat -d three.dat

如果再稍微发挥点巧思，就可以将大量信息传递到 shell 脚本，脚本本身可以在进行内部调用时展现一定的智能（参见GLPK/Scripting_plus_MathProg）。

xglpsol bash 脚本

[编辑 | 编辑源代码]

该xglpsol bash 脚本（您可以根据需要将其重命名）为 GLPSOL 命令行求解器提供了一个简化的接口。例如，命令

$ xglpsol -dkrsw short

生成并运行 GLPSOL 调用

glpsol --scale --nopresol --nointopt --ranges "/dev/stdout" --output "/dev/stdout" --glp short.glpk

然后，它将屏幕截图保存到short.grab，并将其与以前的屏幕截图文件进行diff。

此脚本使用户能够快速更改和查看不同 GLPSOL 选项的效果。其他 GLPSOL 选项可以轻松添加，例如，控制 MIP 行为的选项。来自xglpsol的帮助消息仅供参考。

             usage: xglpsol                model[.ext]     basic GLPSOL run
                    xglpsol  --            model[.ext]     basic GLPSOL run (for convenience)
                    xglpsol  -acdklmrswy   model[.ext]     extended run
                    xglpsol  --help                        display this message and exit (takes priority)
       run options:   -a                   implies -lms
                      -c                   check model            --check
                      -l                   add back LP presolve   --nopresol | --presol
                      -m                   add back MIP presolve  --nointopt | --intopt
                      -s                   add back scaling       --noscale  | --scale
    output options:   -d                   diff with the last available capture (implies -k)
                      -k                   keep console output (with existing file backed up)
                      -r                   display sensitivity analysis (simplex only)  --ranges
                      -w                   display solution (includes KKT)              --output
                      -y                   dry run, simply print the GLPSOL call
        extensions: model.glpk             GLPK problem      --glp
                    model.lp               CPLEX LP problem  --lp
                    model.mod              MathProg model    --math
                    model.mps              free MPS problem  --freemps
           purpose: simplified interface to GLPK GLPSOL command-line solver
         hardcodes: GLPSOL utility             = glpsol
                    default extension          = .glpk
                    terminal capture extension = .grab
                    diff call                  = diff --side-by-side --suppress-common-lines --width=167

可以从下面折叠的表格中复制 bash 源代码。xglpsol是根据知识共享署名-相同方式共享许可授权的。

xglpsol.sh 
#! /bin/bash

#  LEGAL
#
#  Copyright: (c) 2011 Robbie Morrison. Some rights reserved.
#  License: this code is licensed under a Creative Commons BY-SA.
#  http://www.creativecommons.org/licenses/by-sa/3.0/
#  Version: $Id: xglpsol 6703 2011-05-07 07:56:57Z robbie $

#  OVERVIEW
#
#  This script provides a simplified interface to the
#  GLPK GLPSOL command-line solver.  It pumps out
#  GLPSOL command-lines, can diff recent output, and
#  generally facilitates experimentation.
#
#  The script was developed on Linux Ubuntu 10.04 using
#  Bash 4.1.5.  It should work on older versions of
#  Bash too.

# ---------------------------------
#  user modifiable
# ---------------------------------

EXTN="glpk"                             # assumed extension if no extension given

WIDTH=$(stty size | awk '{ print $2 }') # the 'diff' default is often 130 but my screen is wider
DIFF="diff --side-by-side --suppress-common-lines --width=$WIDTH"

# ---------------------------------
#  preamble
# ---------------------------------

GLPSOL="glpsol"                         # GLPSOL call
LOG="grab"                              # terminal capture extension

SCRIPT=$(basename "$0")

# script exit codes

E_SUCCESS=0
E_FAILURE=1
E_USAGE=2
E_GLPSOL_NOT_FOUND=3
E_FILE_NOT_FOUND=4
E_EXTN_NOT_SUPPORTED=5
E_OTHER=64

# ---------------------------------
#  display_help()
# ---------------------------------

function display_help
{
    cat << EOM

             usage: $SCRIPT                model[.ext]     basic GLPSOL run
                    $SCRIPT  --            model[.ext]     basic GLPSOL run (for convenience)
                    $SCRIPT  -acdklmrswy   model[.ext]     extended run
                    $SCRIPT  --help                        display this message and exit (takes priority)
       run options:   -a                   implies -lms
                      -c                   check model            --check
                      -l                   add back LP presolve   --nopresol | --presol
                      -m                   add back MIP presolve  --nointopt | --intopt
                      -s                   add back scaling       --noscale  | --scale
    output options:   -d                   diff with the last available capture (implies -k)
                      -k                   keep console output (with existing file backed up)
                      -r                   display sensitivity analysis (simplex only)  --ranges
                      -w                   display solution (includes KKT)              --output
                      -y                   dry run, simply print the GLPSOL call
        extensions: model.glpk             GLPK problem      --glp
                    model.lp               CPLEX LP problem  --lp
                    model.mod              MathProg model    --math
                    model.mps              free MPS problem  --freemps
           purpose: simplified interface to GLPK GLPSOL command-line solver
         hardcodes: GLPSOL utility             = $GLPSOL
                    default extension          = .$EXTN
                    terminal capture extension = .$LOG
                    diff call                  = $DIFF

EOM
}

# ---------------------------------
#  process long-form options
# ---------------------------------

case "$1" in
    --help|--hel|--he|--h|-help|-hel|-he|-h|"-?")
        display_help
        exit $E_SUCCESS
        ;;
esac

# ------------------------------
#  process short-form options
# ------------------------------

# capture command-line

cline=$(echo $SCRIPT $*)

# set the default flags

usageflag="0"
storeflag="0"
rangeflag="0"
writeflag="0"
sdiffflag="0"
dummyflag="0"

lppreflag="0"
mipreflag="0"
scaleflag="0"
checkflag="0"

# process options

while getopts ":-acdhklmrswy" option  # CAUTION: the leading : should be correct
do
    case "$option" in
        -)  :                          ;; # this codes for option "--" and do nothing is correct
        h)  usageflag="1"              ;;
        d)  sdiffflag="1"              ;;
        k)  storeflag="1"              ;;
        r)  rangeflag="1"              ;;
        w)  writeflag="1"              ;;
        y)  dummyflag="1"              ;;

        a)  lppreflag="1"; mipreflag="1"; scaleflag="1" ;;
        c)  checkflag="1"              ;;
        l)  lppreflag="1"              ;;
        m)  mipreflag="1"              ;;
        s)  scaleflag="1"              ;;

        *)
            echo "$SCRIPT: incorrect usage, try --help"
            exit $E_USAGE
            ;;
    esac
done
shift $(($OPTIND - 1))

#  the above decrements the argument pointer so it points to next
#  argument, hence $1 now references the first non-option supplied
#  on the command-line, in the event that substantive arguments
#  were given

# process help in multiple options

case "$usageflag" in
    1)
        display_help
        exit $E_SUCCESS
        ;;
esac

file="$1"

# rework the flags for some cases

case "$checkflag" in
    1) sdiffflag="0"                ;;
esac

case "$dummyflag" in
    1) sdiffflag="0"; storeflag="0" ;;
esac

case "$sdiffflag" in
    1) storeflag="1"                ;;
esac

# ---------------------------------
#  lead-up code
# ---------------------------------

# presume success

exitval=0

# confirm glpsol

test $(which "$GLPSOL") ||
{
    echo "$SCRIPT: GLPSOL not found: $GLPSOL"
    exit $E_GLPSOL_NOT_FOUND
}

# process filename

extn=${file##*.}                        # grab extension

test "$extn" == "$file" &&              # indicates no extension given
{
    extn="$EXTN"
    file="$file.$extn"
}

case "$extn" in
    glpk) fileopt="--glp"      ;;
    lp)   fileopt="--lp"       ;;
    mod)  fileopt="--math"     ;;
    mps)  fileopt="--freemps"  ;;
    *)
        echo "$SCRIPT: FATAL: model extension not supported: .$extn"
        exit $E_EXTN_NOT_SUPPORTED
        ;;
esac

stub=$(basename "$file" ".$extn")

# confirm model file

test -f "$file" ||
{
    echo "$SCRIPT: FATAL: input file not found: $file"
    exit $E_FILE_NOT_FOUND
}

# obtain some run-time details

lines=$(wc --lines "$file" | gawk '{ print $1 }')
tstamp=$(date "+%Z %z %a %d-%b-%Y %H:%M:%S")

# ---------------------------------
#  create GLPSOL call
# ---------------------------------

REDIRECT="/dev/stdout"                  # location of STDOUT
REDIRECT="\"$REDIRECT\""                # place in double-quotes

options=""

case "$checkflag" in
    0) :                                      ;;
    1) options="$options --check"             ;;
esac

case "$scaleflag" in
    0) options="$options --noscale"           ;;
    1) options="$options --scale"             ;;
esac

case "$lppreflag" in
    0) options="$options --nopresol"          ;;
    1) options="$options --presol"            ;;
esac

case "$mipreflag" in
    0) options="$options --nointopt"          ;;
    1) options="$options --intopt"            ;;
esac

case "$rangeflag" in
    0) :                                      ;;
    1) options="$options --ranges $REDIRECT"  ;;
esac

case "$writeflag" in
    0) :                                      ;;
    1) options="$options --output $REDIRECT"  ;;
esac

call="$GLPSOL$options $fileopt $file"

# ---------------------------------
#  call code
# ---------------------------------

test -f "$stub.$LOG" && mv --force "$stub.$LOG" "$stub.$LOG~"

{                                       # local block used to redirect output
    echo
    echo "  time    : $tstamp"
    echo "  cline   : $cline"
    echo "  model   : $file"
    echo "  lines   : $lines"
    echo "  call    : '$call'"
    echo
    case "$dummyflag" in
        0)
            eval "$call"
            exitval=$?                  # capture return
            ;;
        1)
            echo "  dry run, GLPSOL call shown above"
            ;;
    esac
    echo
    echo "  return  : $exitval"
    echo "  elapsed : $SECONDS"
    echo

} >> "$stub.$LOG"

cat "$stub.$LOG"

test "$storeflag" == "0" && rm --force "$stub.$LOG"

# ---------------------------------
#  diff code
# ---------------------------------

case "$sdiffflag" in
    1)
        test -f "$stub.$LOG" -a -f "$stub.$LOG~" &&
        {
            echo "  diff output : $stub.$LOG : $stub.$LOG~"
            echo
            $DIFF "$stub.$LOG" "$stub.$LOG~"
            echo
        }
        ;;
esac

# ---------------------------------
#  housekeeping
# ---------------------------------

exit $exitval

#  end of file

使用加密模型

[编辑 | 编辑源代码]

模型文件可能包含机密数据，需要通过加密进行保护。可以使用GNU Privacy Guard轻松加密模型文件。

gpg --output tsp.enc --encrypt --recipient user@example.com tsp.mod

为了避免将解密后的模型写入磁盘，可以通过管道将其传递给 glpsol。

gpg --decrypt tsp.enc | glpsol -m /dev/stdin

Set Xs;
Set Ys;
Param pcs {Ys, Xs};
Param pd {Xs};
Param ps {Ys};

Var vq{Ys, Xs} >= 0;

Minimize obj:
 Sum {I in Ys, j in Xs} pcs [i,j] * vq[i,j];

Subject to Ps {i in Ys}:
 Sum {j in Xs} Vq[i,j] <= ps [i];

Subject to Pd {j in Xs}:
 Sum {i in Ys} vq[i,j] = pd[j];

Solve;
End;

备注

[编辑 | 编辑源代码]
  1. ↑ 鉴于 GLPK 最初是构建了支持文件压缩的。
  2. ↑ 更一般地说，任何符合 POSIX 标准的操作系统。
  3. ↑ 如果您的 shell 设置了 noclobber，请将 > 替换为 >|。
  4. ↑ Windows 使用扩展名 .bat 来识别可执行的 shell 脚本。
检索自 "https://wikibooks.cn/w/index.php?title=GLPK/Using_GLPSOL&oldid=3840181"
华夏公益教科书