|
alpar@1
|
1 |
%* glpk10.tex *%
|
|
alpar@1
|
2 |
|
|
alpar@1
|
3 |
\chapter{Stand-alone LP/MIP Solver}
|
|
alpar@1
|
4 |
\label{chaglpsol}
|
|
alpar@1
|
5 |
|
|
alpar@1
|
6 |
The GLPK package includes the program \verb|glpsol|, which is a
|
|
alpar@1
|
7 |
stand-alone LP/MIP solver. This program can be invoked from the command
|
|
alpar@1
|
8 |
line of from the shell to read LP/MIP problem data in any format
|
|
alpar@1
|
9 |
supported by GLPK, solve the problem, and write the problem solution
|
|
alpar@1
|
10 |
obtained to an output text file.
|
|
alpar@1
|
11 |
|
|
alpar@1
|
12 |
\subsubsection*{Usage}
|
|
alpar@1
|
13 |
|
|
alpar@1
|
14 |
\noindent
|
|
alpar@1
|
15 |
\verb|glpsol| [{\it options\dots}] [{\it filename}]
|
|
alpar@1
|
16 |
|
|
alpar@1
|
17 |
\subsubsection*{General options}
|
|
alpar@1
|
18 |
|
|
alpar@1
|
19 |
\noindent
|
|
alpar@1
|
20 |
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
|
|
alpar@1
|
21 |
\verb|--mps| & read LP/MIP problem in fixed MPS format \\
|
|
alpar@1
|
22 |
\verb|--freemps| & read LP/MIP problem in free MPS format (default)\\
|
|
alpar@1
|
23 |
\verb|--lp| & read LP/MIP problem in CPLEX LP format \\
|
|
alpar@1
|
24 |
\verb|--glp| & read LP/MIP problem in GLPK format \\
|
|
alpar@1
|
25 |
\verb|--math| & read LP/MIP model written in GNU MathProg modeling
|
|
alpar@1
|
26 |
language \\
|
|
alpar@1
|
27 |
\multicolumn{2}{@{}l}{{\tt -m} {\it filename}, {\tt --model}
|
|
alpar@1
|
28 |
{\it filename}} \\
|
|
alpar@1
|
29 |
& read model section and optional data section from
|
|
alpar@1
|
30 |
{\it filename} (the same as \verb|--math|) \\
|
|
alpar@1
|
31 |
\multicolumn{2}{@{}l}{{\tt -d} {\it filename}, {\tt --data}
|
|
alpar@1
|
32 |
{\it filename}} \\
|
|
alpar@1
|
33 |
& read data section from {\it filename}
|
|
alpar@1
|
34 |
(for \verb|--math| only); if model file also has
|
|
alpar@1
|
35 |
data section, that section is ignored \\
|
|
alpar@1
|
36 |
\multicolumn{2}{@{}l}{{\tt -y} {\it filename}, {\tt --display}
|
|
alpar@1
|
37 |
{\it filename}} \\
|
|
alpar@1
|
38 |
& send display output to {\it filename}
|
|
alpar@1
|
39 |
(for \verb|--math| only); by default the output is
|
|
alpar@1
|
40 |
sent to \verb|stdout| \\
|
|
alpar@1
|
41 |
\end{tabular}
|
|
alpar@1
|
42 |
|
|
alpar@1
|
43 |
\noindent
|
|
alpar@1
|
44 |
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
|
|
alpar@1
|
45 |
\verb|--seed| {\it value}
|
|
alpar@1
|
46 |
& initialize pseudo-random number generator used in
|
|
alpar@1
|
47 |
MathProg model with specified seed (any integer);
|
|
alpar@1
|
48 |
if the seed value is specified as \verb|?|
|
|
alpar@1
|
49 |
(question mark), some random seed will be used\\
|
|
alpar@1
|
50 |
\verb|--mincost| & read min-cost flow problem in DIMACS format\\
|
|
alpar@1
|
51 |
\verb|--maxflow| & read maximum flow problem in DIMACS format\\
|
|
alpar@1
|
52 |
\verb|--simplex| & use simplex method (default) \\
|
|
alpar@1
|
53 |
\verb|--interior| & use interior point method (for pure LP only) \\
|
|
alpar@1
|
54 |
\multicolumn{2}{@{}l}{{\tt -r} {\it filename}, {\tt --read}
|
|
alpar@1
|
55 |
{\it filename}} \\
|
|
alpar@1
|
56 |
& read solution from {\it filename} rather to find
|
|
alpar@1
|
57 |
it with the solver \\
|
|
alpar@1
|
58 |
\verb|--min| & minimization \\
|
|
alpar@1
|
59 |
\verb|--max| & maximization \\
|
|
alpar@1
|
60 |
\verb|--scale| & scale problem (default) \\
|
|
alpar@1
|
61 |
\verb|--noscale| & do not scale problem \\
|
|
alpar@1
|
62 |
\multicolumn{2}{@{}l}{{\tt -o} {\it filename}, {\tt --output}
|
|
alpar@1
|
63 |
{\it filename}} \\
|
|
alpar@1
|
64 |
& write solution to {\it filename} in printable
|
|
alpar@1
|
65 |
format \\
|
|
alpar@1
|
66 |
\multicolumn{2}{@{}l}{{\tt -w} {\it filename}, {\tt --write}
|
|
alpar@1
|
67 |
{\it filename}} \\
|
|
alpar@1
|
68 |
& write solution to {\it filename} in plain text
|
|
alpar@1
|
69 |
format \\
|
|
alpar@1
|
70 |
\multicolumn{2}{@{}l}{{\tt --ranges} {\it filename}} \\
|
|
alpar@1
|
71 |
& write sensitivity analysis report to {\it filename}
|
|
alpar@1
|
72 |
in printable format (simplex only) \\
|
|
alpar@1
|
73 |
\verb|--tmlim| {\it nnn}
|
|
alpar@1
|
74 |
& limit solution time to {\it nnn} seconds
|
|
alpar@1
|
75 |
(\verb|--tmlim 0| allows obtaining solution at
|
|
alpar@1
|
76 |
initial point) \\
|
|
alpar@1
|
77 |
\verb|--memlim| {\it nnn}
|
|
alpar@1
|
78 |
& limit available memory to {\it nnn} megabytes \\
|
|
alpar@1
|
79 |
\verb|--check| & do not solve problem, check input data only \\
|
|
alpar@1
|
80 |
\verb|--name| {\it probname}
|
|
alpar@1
|
81 |
& change problem name to {\it probname} \\
|
|
alpar@1
|
82 |
\verb|--wmps| {\it filename}
|
|
alpar@1
|
83 |
& write problem to {\it filename} in fixed MPS
|
|
alpar@1
|
84 |
format \\
|
|
alpar@1
|
85 |
\multicolumn{2}{@{}l}{{\tt --wfreemps} {\it filename}} \\
|
|
alpar@1
|
86 |
& write problem to {\it filename} in free MPS
|
|
alpar@1
|
87 |
format \\
|
|
alpar@1
|
88 |
\verb|--wlp| {\it filename}
|
|
alpar@1
|
89 |
& write problem to {\it filename} in CPLEX LP
|
|
alpar@1
|
90 |
format \\
|
|
alpar@1
|
91 |
\verb|--wglp| {\it filename}
|
|
alpar@1
|
92 |
& write problem to {\it filename} in GLPK format \\
|
|
alpar@1
|
93 |
\verb|--log| {\it filename}
|
|
alpar@1
|
94 |
& write copy of terminal output to {\it filename} \\
|
|
alpar@1
|
95 |
\verb|-h|, \verb|--help|
|
|
alpar@1
|
96 |
& display this help information and exit \\
|
|
alpar@1
|
97 |
\verb|-v|, \verb|--version|
|
|
alpar@1
|
98 |
& display program version and exit \\
|
|
alpar@1
|
99 |
\end{tabular}
|
|
alpar@1
|
100 |
|
|
alpar@1
|
101 |
\subsection*{LP basis factorization options}
|
|
alpar@1
|
102 |
|
|
alpar@1
|
103 |
\noindent
|
|
alpar@1
|
104 |
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
|
|
alpar@1
|
105 |
\verb|--luf| & LU + Forrest--Tomlin update \\
|
|
alpar@1
|
106 |
& (faster, less stable; default) \\
|
|
alpar@1
|
107 |
\verb|--cbg| & LU + Schur complement + Bartels--Golub update \\
|
|
alpar@1
|
108 |
& (slower, more stable) \\
|
|
alpar@1
|
109 |
\verb|--cgr| & LU + Schur complement + Givens rotation update \\
|
|
alpar@1
|
110 |
& (slower, more stable) \\
|
|
alpar@1
|
111 |
\end{tabular}
|
|
alpar@1
|
112 |
|
|
alpar@1
|
113 |
\subsubsection*{Options specific to the simplex solver}
|
|
alpar@1
|
114 |
|
|
alpar@1
|
115 |
\noindent
|
|
alpar@1
|
116 |
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
|
|
alpar@1
|
117 |
\verb|--primal| & use primal simplex (default) \\
|
|
alpar@1
|
118 |
\verb|--dual| & use dual simplex \\
|
|
alpar@1
|
119 |
\verb|--std| & use standard initial basis of all slacks \\
|
|
alpar@1
|
120 |
\verb|--adv| & use advanced initial basis (default) \\
|
|
alpar@1
|
121 |
\verb|--bib| & use Bixby's initial basis\\
|
|
alpar@1
|
122 |
\verb|--ini| {\it filename}
|
|
alpar@1
|
123 |
& use as initial basis previously saved with
|
|
alpar@1
|
124 |
\verb|-w| \\
|
|
alpar@1
|
125 |
& (disables LP presolver) \\
|
|
alpar@1
|
126 |
\verb|--steep| & use steepest edge technique (default) \\
|
|
alpar@1
|
127 |
\verb|--nosteep| & use standard ``textbook'' pricing \\
|
|
alpar@1
|
128 |
\verb|--relax| & use Harris' two-pass ratio test (default) \\
|
|
alpar@1
|
129 |
\verb|--norelax| & use standard ``textbook'' ratio test \\
|
|
alpar@1
|
130 |
\verb|--presol| & use LP presolver (default; assumes \verb|--scale|
|
|
alpar@1
|
131 |
and \verb|--adv|) \\
|
|
alpar@1
|
132 |
\verb|--nopresol| & do not use LP presolver \\
|
|
alpar@1
|
133 |
\verb|--exact| & use simplex method based on exact arithmetic \\
|
|
alpar@1
|
134 |
\verb|--xcheck| & check final basis using exact arithmetic \\
|
|
alpar@1
|
135 |
\end{tabular}
|
|
alpar@1
|
136 |
|
|
alpar@1
|
137 |
\subsubsection*{Options specific to the interior-point solver}
|
|
alpar@1
|
138 |
|
|
alpar@1
|
139 |
\noindent
|
|
alpar@1
|
140 |
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
|
|
alpar@1
|
141 |
\verb|--nord| & use natural (original) ordering \\
|
|
alpar@1
|
142 |
\verb|--qmd| & use quotient minimum degree ordering \\
|
|
alpar@1
|
143 |
\verb|--amd| & use approximate minimum degree ordering (default)\\
|
|
alpar@1
|
144 |
\verb|--symamd| & use approximate minimum degree ordering \\
|
|
alpar@1
|
145 |
\end{tabular}
|
|
alpar@1
|
146 |
|
|
alpar@1
|
147 |
\subsubsection*{Options specific to the MIP solver}
|
|
alpar@1
|
148 |
|
|
alpar@1
|
149 |
\noindent
|
|
alpar@1
|
150 |
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
|
|
alpar@1
|
151 |
\verb|--nomip| & consider all integer variables as continuous
|
|
alpar@1
|
152 |
(allows solving MIP as pure LP) \\
|
|
alpar@1
|
153 |
\verb|--first| & branch on first integer variable \\
|
|
alpar@1
|
154 |
\verb|--last| & branch on last integer variable \\
|
|
alpar@1
|
155 |
\verb|--mostf| & branch on most fractional variable \\
|
|
alpar@1
|
156 |
\end{tabular}
|
|
alpar@1
|
157 |
|
|
alpar@1
|
158 |
\noindent
|
|
alpar@1
|
159 |
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
|
|
alpar@1
|
160 |
\verb|--drtom| & branch using heuristic by Driebeck and Tomlin
|
|
alpar@1
|
161 |
(default) \\
|
|
alpar@1
|
162 |
\verb|--pcost| & branch using hybrid pseudocost heuristic (may be
|
|
alpar@1
|
163 |
useful for hard instances) \\
|
|
alpar@1
|
164 |
\verb|--dfs| & backtrack using depth first search \\
|
|
alpar@1
|
165 |
\verb|--bfs| & backtrack using breadth first search \\
|
|
alpar@1
|
166 |
\verb|--bestp| & backtrack using the best projection heuristic
|
|
alpar@1
|
167 |
(default) \\
|
|
alpar@1
|
168 |
\verb|--bestb| & backtrack using node with best local bound \\
|
|
alpar@1
|
169 |
\verb|--intopt| & use MIP presolver (default)\\
|
|
alpar@1
|
170 |
\verb|--nointopt| & do not use MIP presolver\\
|
|
alpar@1
|
171 |
\verb|--binarize| & replace general integer variables by binary ones
|
|
alpar@1
|
172 |
(assumes \verb|--intopt|)\\
|
|
alpar@1
|
173 |
\verb|--fpump| & apply feasibility pump heuristic\\
|
|
alpar@1
|
174 |
\verb|--gomory| & generate Gomory's mixed integer cuts\\
|
|
alpar@1
|
175 |
\verb|--mir| & generate MIR (mixed integer rounding) cuts\\
|
|
alpar@1
|
176 |
\verb|--cover| & generate mixed cover cuts\\
|
|
alpar@1
|
177 |
\verb|--clique| & generate clique cuts\\
|
|
alpar@1
|
178 |
\verb|--cuts| & generate cuts of all classes above (assumes
|
|
alpar@1
|
179 |
\verb|--intopt|)\\
|
|
alpar@1
|
180 |
\verb|--mipgap| {\it tol}
|
|
alpar@1
|
181 |
& set relative mip gap tolerance to {\it tol}\\
|
|
alpar@1
|
182 |
\end{tabular}
|
|
alpar@1
|
183 |
|
|
alpar@1
|
184 |
\bigskip
|
|
alpar@1
|
185 |
|
|
alpar@1
|
186 |
\noindent
|
|
alpar@1
|
187 |
For description of the MPS format see Appendix \ref{champs},
|
|
alpar@1
|
188 |
page \pageref{champs}.
|
|
alpar@1
|
189 |
|
|
alpar@1
|
190 |
\bigskip
|
|
alpar@1
|
191 |
|
|
alpar@1
|
192 |
\noindent
|
|
alpar@1
|
193 |
For description of the CPLEX LP format see Appendix \ref{chacplex},
|
|
alpar@1
|
194 |
page \pageref{chacplex}.
|
|
alpar@1
|
195 |
|
|
alpar@1
|
196 |
\bigskip
|
|
alpar@1
|
197 |
|
|
alpar@1
|
198 |
\noindent
|
|
alpar@1
|
199 |
For description of the modeling language see the document ``Modeling
|
|
alpar@1
|
200 |
Language GNU MathProg: Language Reference'' included in the GLPK
|
|
alpar@1
|
201 |
distribution.
|
|
alpar@1
|
202 |
|
|
alpar@1
|
203 |
\bigskip
|
|
alpar@1
|
204 |
|
|
alpar@1
|
205 |
\noindent
|
|
alpar@1
|
206 |
For description of the DIMACS min-cost flow problem format and DIMACS
|
|
alpar@1
|
207 |
maximum flow problem format see the document ``GLPK: Graph and Network
|
|
alpar@1
|
208 |
Routines'' included in the GLPK distribution.
|
|
alpar@1
|
209 |
|
|
alpar@1
|
210 |
%* eof *%
|