GLPK/Using GLPSOL

From Wikibooks, open books for an open world
Jump to navigation Jump to search

This page lists some tips and hints when using GLPSOL, the GLPK command-line solver.

Note that GLPSOL is built, by default, when GLPK is built. Hence GLPSOL should be generally present whenever GLPK is installed.


Usage[edit | edit source]

Usage:

glpsol [options...] filename

For example, using the options in their long-form:

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

Options[edit | edit source]

The following information is derived from the usage option --help.

General options:

  --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 basis factorization options:

  --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)

Options specific to the simplex solver:

  --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

Options specific to the interior-point solver:

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

Options specific to the MIP solver:

  --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

Options for CNF-SAT satisfiability problems:

 --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)

Compressed files[edit | edit source]

The size of output files can be reduced by appending the suffix .gz[1] This indicates gzip compression. For instance:

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

Similarly, GLPSOL will automatically decompress any file that it encounters that ends with the extension .gz.

Standard streams[edit | edit source]

GLPSOL supports the following three standard streams:

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

These are treated as special filenames by the GLPK I/O routines in a platform-independent manner. Hence the following command should work equally on Windows, Mac OS X, and Linux, delivering the solution report to the terminal instead of to a regular file:

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

Passing values via the command-line[edit | edit source]

If you need to pass a parameter value via the command-line, the following example shows how to do this using a shell script.

The shell script, either test.bat or test.sh, first creates a dynamic data file test.dat, which contains the required command-line value. The shell script then invokes GLPSOL with a hard-coded model name which, in this example, simply prints the value originally passed in from the command-line.

Step Microsoft Windows Linux and Mac OS X [2]
create a model file test.mod
param p;
printf "p = %f\n", p;
end;
create a shell script file 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
make that file executable  do nothing [4]
chmod u+x test.sh
run the shell script
test.bat 3.14159
./test.sh 3.14159

Observe that you can specify multiple data files within the shell script, for instance:

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

With a little more ingenuity, a whole raft of information could be passed to the shell script and the script itself could exercise some intelligence when making its internal calls (cf. GLPK/Scripting_plus_MathProg).

xglpsol bash script[edit | edit source]

The xglpsol bash script (which you can rename to suit your needs) offers a simplified interface to the GLPSOL command-line solver. For example the command:

$ xglpsol -dkrsw short

produces and runs the GLPSOL call:

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

It then saves the screen capture to short.grab and diff's that against the previous screen capture file.

This script enables the user to rapidly change and view the effects of different GLPSOL options. Other GLPSOL options could be easily added, for instance, those governing MIP behavior. The help message from xglpsol is shown for reference purposes.

             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

The bash source can be copied from the collapsed table below. xglpsol is licensed under a Creative Commons BY-SA.

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

Using encrypted models[edit | edit source]

Model files may contain confidential data which deserves protection via encryption. A model file can easily be encrypted using the GNU Privacy Guard.

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

To avoid writing the decrypted model to disk it can be passed via a pipe to 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;

Notes[edit | edit source]

  1. Given that GLPK was originally built with support for file compression.
  2. More generally, any POSIX-compliant operating system.
  3. If noclobber is set for your shell, replace > by >|.
  4. Windows uses the extension .bat to recognize an executable shell script.