跳轉到內容

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://wikibook.tw/w/index.php?title=GLPK/Using_GLPSOL&oldid=3840181"
華夏公益教科書