| rev |
line source |
|
alpar@9
|
1 %* glpk02.tex *%
|
|
alpar@9
|
2
|
|
alpar@9
|
3 \chapter{Basic API Routines}
|
|
alpar@9
|
4
|
|
alpar@9
|
5 This chapter describes GLPK API routines intended for using in
|
|
alpar@9
|
6 application programs.
|
|
alpar@9
|
7
|
|
alpar@9
|
8 \subsubsection*{Library header}
|
|
alpar@9
|
9
|
|
alpar@9
|
10 All GLPK API data types and routines are defined in the header file
|
|
alpar@9
|
11 \verb|glpk.h|. It should be included in all source files which use
|
|
alpar@9
|
12 GLPK API, either directly or indirectly through some other header file
|
|
alpar@9
|
13 as follows:
|
|
alpar@9
|
14
|
|
alpar@9
|
15 \begin{verbatim}
|
|
alpar@9
|
16 #include <glpk.h>
|
|
alpar@9
|
17 \end{verbatim}
|
|
alpar@9
|
18
|
|
alpar@9
|
19 \subsubsection*{Error handling}
|
|
alpar@9
|
20
|
|
alpar@9
|
21 If some GLPK API routine detects erroneous or incorrect data passed by
|
|
alpar@9
|
22 the application program, it writes appropriate diagnostic messages to
|
|
alpar@9
|
23 the terminal and then abnormally terminates the application program.
|
|
alpar@9
|
24 In most practical cases this allows to simplify programming by avoiding
|
|
alpar@9
|
25 numerous checks of return codes. Thus, in order to prevent crashing the
|
|
alpar@9
|
26 application program should check all data, which are suspected to be
|
|
alpar@9
|
27 incorrect, before calling GLPK API routines.
|
|
alpar@9
|
28
|
|
alpar@9
|
29 Should note that this kind of error handling is used only in cases of
|
|
alpar@9
|
30 incorrect data passed by the application program. If, for example, the
|
|
alpar@9
|
31 application program calls some GLPK API routine to read data from an
|
|
alpar@9
|
32 input file and these data are incorrect, the GLPK API routine reports
|
|
alpar@9
|
33 about error in the usual way by means of the return code.
|
|
alpar@9
|
34
|
|
alpar@9
|
35 \subsubsection*{Thread safety}
|
|
alpar@9
|
36
|
|
alpar@9
|
37 Currently GLPK API routines are non-reentrant and therefore cannot be
|
|
alpar@9
|
38 used in multi-threaded programs.
|
|
alpar@9
|
39
|
|
alpar@9
|
40 \subsubsection*{Array indexing}
|
|
alpar@9
|
41
|
|
alpar@9
|
42 Normally all GLPK API routines start array indexing from 1, not from 0
|
|
alpar@9
|
43 (except the specially stipulated cases). This means, for example, that
|
|
alpar@9
|
44 if some vector $x$ of the length $n$ is passed as an array to some GLPK
|
|
alpar@9
|
45 API routine, the latter expects vector components to be placed in
|
|
alpar@9
|
46 locations \verb|x[1]|, \verb|x[2]|, \dots, \verb|x[n]|, and the location
|
|
alpar@9
|
47 \verb|x[0]| normally is not used.
|
|
alpar@9
|
48
|
|
alpar@9
|
49 In order to avoid indexing errors it is most convenient and most
|
|
alpar@9
|
50 reliable to declare the array \verb|x| as follows:
|
|
alpar@9
|
51
|
|
alpar@9
|
52 \begin{verbatim}
|
|
alpar@9
|
53 double x[1+n];
|
|
alpar@9
|
54 \end{verbatim}
|
|
alpar@9
|
55
|
|
alpar@9
|
56 \noindent
|
|
alpar@9
|
57 or to allocate it as follows:
|
|
alpar@9
|
58
|
|
alpar@9
|
59 \begin{verbatim}
|
|
alpar@9
|
60 double *x;
|
|
alpar@9
|
61 . . .
|
|
alpar@9
|
62 x = calloc(1+n, sizeof(double));
|
|
alpar@9
|
63 \end{verbatim}
|
|
alpar@9
|
64
|
|
alpar@9
|
65 \noindent
|
|
alpar@9
|
66 In both cases one extra location \verb|x[0]| is reserved that allows
|
|
alpar@9
|
67 passing the array to GLPK routines in a usual way.
|
|
alpar@9
|
68
|
|
alpar@9
|
69 \section{Problem object}
|
|
alpar@9
|
70
|
|
alpar@9
|
71 All GLPK API routines deal with so called {\it problem object}, which
|
|
alpar@9
|
72 is a program object of type \verb|glp_prob| and intended to represent
|
|
alpar@9
|
73 a particular LP or MIP instance.
|
|
alpar@9
|
74
|
|
alpar@9
|
75 The type \verb|glp_prob| is a data structure declared in the header
|
|
alpar@9
|
76 file \verb|glpk.h| as follows:
|
|
alpar@9
|
77
|
|
alpar@9
|
78 \begin{verbatim}
|
|
alpar@9
|
79 typedef struct { ... } glp_prob;
|
|
alpar@9
|
80 \end{verbatim}
|
|
alpar@9
|
81
|
|
alpar@9
|
82 Problem objects (i.e. program objects of the \verb|glp_prob| type) are
|
|
alpar@9
|
83 allocated and managed internally by the GLPK API routines. The
|
|
alpar@9
|
84 application program should never use any members of the \verb|glp_prob|
|
|
alpar@9
|
85 structure directly and should deal only with pointers to these objects
|
|
alpar@9
|
86 (that is, \verb|glp_prob *| values).
|
|
alpar@9
|
87
|
|
alpar@9
|
88 \pagebreak
|
|
alpar@9
|
89
|
|
alpar@9
|
90 The problem object consists of five segments, which are:
|
|
alpar@9
|
91
|
|
alpar@9
|
92 $\bullet$ problem segment,
|
|
alpar@9
|
93
|
|
alpar@9
|
94 $\bullet$ basis segment,
|
|
alpar@9
|
95
|
|
alpar@9
|
96 $\bullet$ interior point segment,
|
|
alpar@9
|
97
|
|
alpar@9
|
98 $\bullet$ MIP segment, and
|
|
alpar@9
|
99
|
|
alpar@9
|
100 $\bullet$ control parameters and statistics segment.
|
|
alpar@9
|
101
|
|
alpar@9
|
102 \subsubsection*{Problem segment}
|
|
alpar@9
|
103
|
|
alpar@9
|
104 The {\it problem segment} contains original LP/MIP data, which
|
|
alpar@9
|
105 corresponds to the problem formulation (1.1)---(1.3) (see Section
|
|
alpar@9
|
106 \ref{seclp}, page \pageref{seclp}). It includes the following
|
|
alpar@9
|
107 components:
|
|
alpar@9
|
108
|
|
alpar@9
|
109 $\bullet$ rows (auxiliary variables),
|
|
alpar@9
|
110
|
|
alpar@9
|
111 $\bullet$ columns (structural variables),
|
|
alpar@9
|
112
|
|
alpar@9
|
113 $\bullet$ objective function, and
|
|
alpar@9
|
114
|
|
alpar@9
|
115 $\bullet$ constraint matrix.
|
|
alpar@9
|
116
|
|
alpar@9
|
117 Rows and columns have the same set of the following attributes:
|
|
alpar@9
|
118
|
|
alpar@9
|
119 $\bullet$ ordinal number,
|
|
alpar@9
|
120
|
|
alpar@9
|
121 $\bullet$ symbolic name (1 up to 255 arbitrary graphic characters),
|
|
alpar@9
|
122
|
|
alpar@9
|
123 $\bullet$ type (free, lower bound, upper bound, double bound, fixed),
|
|
alpar@9
|
124
|
|
alpar@9
|
125 $\bullet$ numerical values of lower and upper bounds,
|
|
alpar@9
|
126
|
|
alpar@9
|
127 $\bullet$ scale factor.
|
|
alpar@9
|
128
|
|
alpar@9
|
129 {\it Ordinal numbers} are intended for referencing rows and columns.
|
|
alpar@9
|
130 Row ordinal numbers are integers $1, 2, \dots, m$, and column ordinal
|
|
alpar@9
|
131 numbers are integers $1, 2, \dots, n$, where $m$ and $n$ are,
|
|
alpar@9
|
132 respectively, the current number of rows and columns in the problem
|
|
alpar@9
|
133 object.
|
|
alpar@9
|
134
|
|
alpar@9
|
135 {\it Symbolic names} are intended for informational purposes. They also
|
|
alpar@9
|
136 can be used for referencing rows and columns.
|
|
alpar@9
|
137
|
|
alpar@9
|
138 {\it Types and bounds} of rows (auxiliary variables) and columns
|
|
alpar@9
|
139 (structural variables) are explained above (see Section \ref{seclp},
|
|
alpar@9
|
140 page \pageref{seclp}).
|
|
alpar@9
|
141
|
|
alpar@9
|
142 {\it Scale factors} are used internally for scaling rows and columns of
|
|
alpar@9
|
143 the constraint matrix.
|
|
alpar@9
|
144
|
|
alpar@9
|
145 Information about the {\it objective function} includes numerical
|
|
alpar@9
|
146 values of objective coefficients and a flag, which defines the
|
|
alpar@9
|
147 optimization direction (i.e. minimization or maximization).
|
|
alpar@9
|
148
|
|
alpar@9
|
149 The {\it constraint matrix} is a $m \times n$ rectangular matrix built
|
|
alpar@9
|
150 of constraint coefficients $a_{ij}$, which defines the system of linear
|
|
alpar@9
|
151 constraints (1.2) (see Section \ref{seclp}, page \pageref{seclp}). This
|
|
alpar@9
|
152 matrix is stored in the problem object in both row-wise and column-wise
|
|
alpar@9
|
153 sparse formats.
|
|
alpar@9
|
154
|
|
alpar@9
|
155 Once the problem object has been created, the application program can
|
|
alpar@9
|
156 access and modify any components of the problem segment in arbitrary
|
|
alpar@9
|
157 order.
|
|
alpar@9
|
158
|
|
alpar@9
|
159 \subsubsection*{Basis segment}
|
|
alpar@9
|
160
|
|
alpar@9
|
161 The {\it basis segment} of the problem object keeps information related
|
|
alpar@9
|
162 to the current basic solution. It includes:
|
|
alpar@9
|
163
|
|
alpar@9
|
164 $\bullet$ row and column statuses,
|
|
alpar@9
|
165
|
|
alpar@9
|
166 $\bullet$ basic solution statuses,
|
|
alpar@9
|
167
|
|
alpar@9
|
168 $\bullet$ factorization of the current basis matrix, and
|
|
alpar@9
|
169
|
|
alpar@9
|
170 $\bullet$ basic solution components.
|
|
alpar@9
|
171
|
|
alpar@9
|
172 The {\it row and column statuses} define which rows and columns are
|
|
alpar@9
|
173 basic and which are non-basic. These statuses may be assigned either by
|
|
alpar@9
|
174 the application program of by some API routines. Note that these
|
|
alpar@9
|
175 statuses are always defined independently on whether the corresponding
|
|
alpar@9
|
176 basis is valid or not.
|
|
alpar@9
|
177
|
|
alpar@9
|
178 The {\it basic solution statuses} include the {\it primal status} and
|
|
alpar@9
|
179 the {\it dual status}, which are set by the simplex-based solver once
|
|
alpar@9
|
180 the problem has been solved. The primal status shows whether a primal
|
|
alpar@9
|
181 basic solution is feasible, infeasible, or undefined. The dual status
|
|
alpar@9
|
182 shows the same for a dual basic solution.
|
|
alpar@9
|
183
|
|
alpar@9
|
184 The {\it factorization of the basis matrix} is some factorized form
|
|
alpar@9
|
185 (like LU-factorization) of the current basis matrix (defined by the
|
|
alpar@9
|
186 current row and column statuses). The factorization is used by the
|
|
alpar@9
|
187 simplex-based solver and kept when the solver terminates the search.
|
|
alpar@9
|
188 This feature allows efficiently reoptimizing the problem after some
|
|
alpar@9
|
189 modifications (for example, after changing some bounds or objective
|
|
alpar@9
|
190 coefficients). It also allows performing the post-optimal analysis (for
|
|
alpar@9
|
191 example, computing components of the simplex table, etc.).
|
|
alpar@9
|
192
|
|
alpar@9
|
193 The {\it basic solution components} include primal and dual values of
|
|
alpar@9
|
194 all auxiliary and structural variables for the most recently obtained
|
|
alpar@9
|
195 basic solution.
|
|
alpar@9
|
196
|
|
alpar@9
|
197 \subsubsection*{Interior point segment}
|
|
alpar@9
|
198
|
|
alpar@9
|
199 The {\it interior point segment} is automatically allocated after the
|
|
alpar@9
|
200 problem has been solved using the interior point solver. It contains
|
|
alpar@9
|
201 interior point solution components, which include the solution status,
|
|
alpar@9
|
202 and primal and dual values of all auxiliary and structural variables.
|
|
alpar@9
|
203
|
|
alpar@9
|
204 \subsubsection*{MIP segment}
|
|
alpar@9
|
205
|
|
alpar@9
|
206 The {\it MIP segment} is used only for MIP problems. This segment
|
|
alpar@9
|
207 includes:
|
|
alpar@9
|
208
|
|
alpar@9
|
209 $\bullet$ column kinds,
|
|
alpar@9
|
210
|
|
alpar@9
|
211 $\bullet$ MIP solution status, and
|
|
alpar@9
|
212
|
|
alpar@9
|
213 $\bullet$ MIP solution components.
|
|
alpar@9
|
214
|
|
alpar@9
|
215 The {\it column kinds} define which columns (i.e. structural variables)
|
|
alpar@9
|
216 are integer and which are continuous.
|
|
alpar@9
|
217
|
|
alpar@9
|
218 The {\it MIP solution status} is set by the MIP solver and shows whether
|
|
alpar@9
|
219 a MIP solution is integer optimal, integer feasible (non-optimal), or
|
|
alpar@9
|
220 undefined.
|
|
alpar@9
|
221
|
|
alpar@9
|
222 The {\it MIP solution components} are computed by the MIP solver and
|
|
alpar@9
|
223 include primal values of all auxiliary and structural variables for the
|
|
alpar@9
|
224 most recently obtained MIP solution.
|
|
alpar@9
|
225
|
|
alpar@9
|
226 Note that in case of MIP problem the basis segment corresponds to
|
|
alpar@9
|
227 the optimal solution of LP relaxation, which is also available to the
|
|
alpar@9
|
228 application program.
|
|
alpar@9
|
229
|
|
alpar@9
|
230 Currently the search tree is not kept in the MIP segment. Therefore if
|
|
alpar@9
|
231 the search has been terminated, it cannot be continued.
|
|
alpar@9
|
232
|
|
alpar@9
|
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
234
|
|
alpar@9
|
235 \newpage
|
|
alpar@9
|
236
|
|
alpar@9
|
237 \section{Problem creating and modifying routines}
|
|
alpar@9
|
238
|
|
alpar@9
|
239 \subsection{glp\_create\_prob---create problem object}
|
|
alpar@9
|
240
|
|
alpar@9
|
241 \subsubsection*{Synopsis}
|
|
alpar@9
|
242
|
|
alpar@9
|
243 \begin{verbatim}
|
|
alpar@9
|
244 glp_prob *glp_create_prob(void);
|
|
alpar@9
|
245 \end{verbatim}
|
|
alpar@9
|
246
|
|
alpar@9
|
247 \subsubsection*{Description}
|
|
alpar@9
|
248
|
|
alpar@9
|
249 The routine \verb|glp_create_prob| creates a new problem object, which
|
|
alpar@9
|
250 initially is ``empty'', i.e. has no rows and columns.
|
|
alpar@9
|
251
|
|
alpar@9
|
252 \subsubsection*{Returns}
|
|
alpar@9
|
253
|
|
alpar@9
|
254 The routine returns a pointer to the created object, which should be
|
|
alpar@9
|
255 used in any subsequent operations on this object.
|
|
alpar@9
|
256
|
|
alpar@9
|
257 \subsection{glp\_set\_prob\_name---assign (change) problem name}
|
|
alpar@9
|
258
|
|
alpar@9
|
259 \subsubsection*{Synopsis}
|
|
alpar@9
|
260
|
|
alpar@9
|
261 \begin{verbatim}
|
|
alpar@9
|
262 void glp_set_prob_name(glp_prob *lp, const char *name);
|
|
alpar@9
|
263 \end{verbatim}
|
|
alpar@9
|
264
|
|
alpar@9
|
265 \subsubsection*{Description}
|
|
alpar@9
|
266
|
|
alpar@9
|
267 The routine \verb|glp_set_prob_name| assigns a given symbolic
|
|
alpar@9
|
268 \verb|name| (1 up to 255 characters) to the specified problem object.
|
|
alpar@9
|
269
|
|
alpar@9
|
270 If the parameter \verb|name| is \verb|NULL| or empty string, the routine
|
|
alpar@9
|
271 erases an existing symbolic name of the problem object.
|
|
alpar@9
|
272
|
|
alpar@9
|
273 \subsection{glp\_set\_obj\_name---assign (change) objective function
|
|
alpar@9
|
274 name}
|
|
alpar@9
|
275
|
|
alpar@9
|
276 \subsubsection*{Synopsis}
|
|
alpar@9
|
277
|
|
alpar@9
|
278 \begin{verbatim}
|
|
alpar@9
|
279 void glp_set_obj_name(glp_prob *lp, const char *name);
|
|
alpar@9
|
280 \end{verbatim}
|
|
alpar@9
|
281
|
|
alpar@9
|
282 \subsubsection*{Description}
|
|
alpar@9
|
283
|
|
alpar@9
|
284 The routine \verb|glp_set_obj_name| assigns a given symbolic
|
|
alpar@9
|
285 \verb|name| (1 up to 255 characters) to the objective function of the
|
|
alpar@9
|
286 specified problem object.
|
|
alpar@9
|
287
|
|
alpar@9
|
288 If the parameter \verb|name| is \verb|NULL| or empty string, the routine
|
|
alpar@9
|
289 erases an existing symbolic name of the objective function.
|
|
alpar@9
|
290
|
|
alpar@9
|
291 \subsection{glp\_set\_obj\_dir---set (change) optimization direction\\
|
|
alpar@9
|
292 flag}
|
|
alpar@9
|
293
|
|
alpar@9
|
294 \subsubsection*{Synopsis}
|
|
alpar@9
|
295
|
|
alpar@9
|
296 \begin{verbatim}
|
|
alpar@9
|
297 void glp_set_obj_dir(glp_prob *lp, int dir);
|
|
alpar@9
|
298 \end{verbatim}
|
|
alpar@9
|
299
|
|
alpar@9
|
300 \subsubsection*{Description}
|
|
alpar@9
|
301
|
|
alpar@9
|
302 The routine \verb|glp_set_obj_dir| sets (changes) the optimization
|
|
alpar@9
|
303 direction flag (i.e. ``sense'' of the objective function) as specified
|
|
alpar@9
|
304 by the parameter \verb|dir|:
|
|
alpar@9
|
305
|
|
alpar@9
|
306 \begin{tabular}{@{}ll}
|
|
alpar@9
|
307 \verb|GLP_MIN| & minimization; \\
|
|
alpar@9
|
308 \verb|GLP_MAX| & maximization. \\
|
|
alpar@9
|
309 \end{tabular}
|
|
alpar@9
|
310
|
|
alpar@9
|
311 \noindent
|
|
alpar@9
|
312 (Note that by default the problem is minimization.)
|
|
alpar@9
|
313
|
|
alpar@9
|
314 \subsection{glp\_add\_rows---add new rows to problem object}
|
|
alpar@9
|
315
|
|
alpar@9
|
316 \subsubsection*{Synopsis}
|
|
alpar@9
|
317
|
|
alpar@9
|
318 \begin{verbatim}
|
|
alpar@9
|
319 int glp_add_rows(glp_prob *lp, int nrs);
|
|
alpar@9
|
320 \end{verbatim}
|
|
alpar@9
|
321
|
|
alpar@9
|
322 \subsubsection*{Description}
|
|
alpar@9
|
323
|
|
alpar@9
|
324 The routine \verb|glp_add_rows| adds \verb|nrs| rows (constraints) to
|
|
alpar@9
|
325 the specified problem object. New rows are always added to the end of
|
|
alpar@9
|
326 the row list, so the ordinal numbers of existing rows are not changed.
|
|
alpar@9
|
327
|
|
alpar@9
|
328 Being added each new row is initially free (unbounded) and has empty
|
|
alpar@9
|
329 list of the constraint coefficients.
|
|
alpar@9
|
330
|
|
alpar@9
|
331 \subsubsection*{Returns}
|
|
alpar@9
|
332
|
|
alpar@9
|
333 The routine \verb|glp_add_rows| returns the ordinal number of the first
|
|
alpar@9
|
334 new row added to the problem object.
|
|
alpar@9
|
335
|
|
alpar@9
|
336 \newpage
|
|
alpar@9
|
337
|
|
alpar@9
|
338 \subsection{glp\_add\_cols---add new columns to problem object}
|
|
alpar@9
|
339
|
|
alpar@9
|
340 \subsubsection*{Synopsis}
|
|
alpar@9
|
341
|
|
alpar@9
|
342 \begin{verbatim}
|
|
alpar@9
|
343 int glp_add_cols(glp_prob *lp, int ncs);
|
|
alpar@9
|
344 \end{verbatim}
|
|
alpar@9
|
345
|
|
alpar@9
|
346 \subsubsection*{Description}
|
|
alpar@9
|
347
|
|
alpar@9
|
348 The routine \verb|glp_add_cols| adds \verb|ncs| columns (structural
|
|
alpar@9
|
349 variables) to the specified problem object. New columns are always added
|
|
alpar@9
|
350 to the end of the column list, so the ordinal numbers of existing
|
|
alpar@9
|
351 columns are not changed.
|
|
alpar@9
|
352
|
|
alpar@9
|
353 Being added each new column is initially fixed at zero and has empty
|
|
alpar@9
|
354 list of the constraint coefficients.
|
|
alpar@9
|
355
|
|
alpar@9
|
356 \subsubsection*{Returns}
|
|
alpar@9
|
357
|
|
alpar@9
|
358 The routine \verb|glp_add_cols| returns the ordinal number of the first
|
|
alpar@9
|
359 new column added to the problem object.
|
|
alpar@9
|
360
|
|
alpar@9
|
361 \subsection{glp\_set\_row\_name---assign (change) row name}
|
|
alpar@9
|
362
|
|
alpar@9
|
363 \subsubsection*{Synopsis}
|
|
alpar@9
|
364
|
|
alpar@9
|
365 \begin{verbatim}
|
|
alpar@9
|
366 void glp_set_row_name(glp_prob *lp, int i, const char *name);
|
|
alpar@9
|
367 \end{verbatim}
|
|
alpar@9
|
368
|
|
alpar@9
|
369 \subsubsection*{Description}
|
|
alpar@9
|
370
|
|
alpar@9
|
371 The routine \verb|glp_set_row_name| assigns a given symbolic
|
|
alpar@9
|
372 \verb|name| (1 up to 255 characters) to \verb|i|-th row (auxiliary
|
|
alpar@9
|
373 variable) of the specified problem object.
|
|
alpar@9
|
374
|
|
alpar@9
|
375 If the parameter \verb|name| is \verb|NULL| or empty string, the routine
|
|
alpar@9
|
376 erases an existing name of $i$-th row.
|
|
alpar@9
|
377
|
|
alpar@9
|
378 \subsection{glp\_set\_col\_name---assign (change) column name}
|
|
alpar@9
|
379
|
|
alpar@9
|
380 \subsubsection*{Synopsis}
|
|
alpar@9
|
381
|
|
alpar@9
|
382 \begin{verbatim}
|
|
alpar@9
|
383 void glp_set_col_name(glp_prob *lp, int j, const char *name);
|
|
alpar@9
|
384 \end{verbatim}
|
|
alpar@9
|
385
|
|
alpar@9
|
386 \subsubsection*{Description}
|
|
alpar@9
|
387
|
|
alpar@9
|
388 The routine \verb|glp_set_col_name| assigns a given symbolic
|
|
alpar@9
|
389 \verb|name| (1 up to 255 characters) to \verb|j|-th column (structural
|
|
alpar@9
|
390 variable) of the specified problem object.
|
|
alpar@9
|
391
|
|
alpar@9
|
392 If the parameter \verb|name| is \verb|NULL| or empty string, the routine
|
|
alpar@9
|
393 erases an existing name of $j$-th column.
|
|
alpar@9
|
394
|
|
alpar@9
|
395 \subsection{glp\_set\_row\_bnds---set (change) row bounds}
|
|
alpar@9
|
396
|
|
alpar@9
|
397 \subsubsection*{Synopsis}
|
|
alpar@9
|
398
|
|
alpar@9
|
399 \begin{verbatim}
|
|
alpar@9
|
400 void glp_set_row_bnds(glp_prob *lp, int i, int type,
|
|
alpar@9
|
401 double lb, double ub);
|
|
alpar@9
|
402 \end{verbatim}
|
|
alpar@9
|
403
|
|
alpar@9
|
404 \subsubsection*{Description}
|
|
alpar@9
|
405
|
|
alpar@9
|
406 The routine \verb|glp_set_row_bnds| sets (changes) the type and bounds
|
|
alpar@9
|
407 of \verb|i|-th row (auxiliary variable) of the specified problem object.
|
|
alpar@9
|
408
|
|
alpar@9
|
409 The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
|
|
alpar@9
|
410 lower bound, and upper bound, respectively, as follows:
|
|
alpar@9
|
411
|
|
alpar@9
|
412 \begin{center}
|
|
alpar@9
|
413 \begin{tabular}{cr@{}c@{}ll}
|
|
alpar@9
|
414 Type & \multicolumn{3}{c}{Bounds} & Comment \\
|
|
alpar@9
|
415 \hline
|
|
alpar@9
|
416 \verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
|
|
alpar@9
|
417 & Free (unbounded) variable \\
|
|
alpar@9
|
418 \verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
|
|
alpar@9
|
419 & Variable with lower bound \\
|
|
alpar@9
|
420 \verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
|
|
alpar@9
|
421 & Variable with upper bound \\
|
|
alpar@9
|
422 \verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
|
|
alpar@9
|
423 & Double-bounded variable \\
|
|
alpar@9
|
424 \verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
|
|
alpar@9
|
425 & Fixed variable \\
|
|
alpar@9
|
426 \end{tabular}
|
|
alpar@9
|
427 \end{center}
|
|
alpar@9
|
428
|
|
alpar@9
|
429 \noindent
|
|
alpar@9
|
430 where $x$ is the auxiliary variable associated with $i$-th row.
|
|
alpar@9
|
431
|
|
alpar@9
|
432 If the row has no lower bound, the parameter \verb|lb| is ignored. If
|
|
alpar@9
|
433 the row has no upper bound, the parameter \verb|ub| is ignored. If the
|
|
alpar@9
|
434 row is an equality constraint (i.e. the corresponding auxiliary variable
|
|
alpar@9
|
435 is of fixed type), only the parameter \verb|lb| is used while the
|
|
alpar@9
|
436 parameter \verb|ub| is ignored.
|
|
alpar@9
|
437
|
|
alpar@9
|
438 Being added to the problem object each row is initially free, i.e. its
|
|
alpar@9
|
439 type is \verb|GLP_FR|.
|
|
alpar@9
|
440
|
|
alpar@9
|
441 \newpage
|
|
alpar@9
|
442
|
|
alpar@9
|
443 \subsection{glp\_set\_col\_bnds---set (change) column bounds}
|
|
alpar@9
|
444
|
|
alpar@9
|
445 \subsubsection*{Synopsis}
|
|
alpar@9
|
446
|
|
alpar@9
|
447 \begin{verbatim}
|
|
alpar@9
|
448 void glp_set_col_bnds(glp_prob *lp, int j, int type,
|
|
alpar@9
|
449 double lb, double ub);
|
|
alpar@9
|
450 \end{verbatim}
|
|
alpar@9
|
451
|
|
alpar@9
|
452 \subsubsection*{Description}
|
|
alpar@9
|
453
|
|
alpar@9
|
454 The routine \verb|glp_set_col_bnds| sets (changes) the type and bounds
|
|
alpar@9
|
455 of \verb|j|-th column (structural variable) of the specified problem
|
|
alpar@9
|
456 object.
|
|
alpar@9
|
457
|
|
alpar@9
|
458 The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
|
|
alpar@9
|
459 lower bound, and upper bound, respectively, as follows:
|
|
alpar@9
|
460
|
|
alpar@9
|
461 \begin{center}
|
|
alpar@9
|
462 \begin{tabular}{cr@{}c@{}ll}
|
|
alpar@9
|
463 Type & \multicolumn{3}{c}{Bounds} & Comment \\
|
|
alpar@9
|
464 \hline
|
|
alpar@9
|
465 \verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
|
|
alpar@9
|
466 & Free (unbounded) variable \\
|
|
alpar@9
|
467 \verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
|
|
alpar@9
|
468 & Variable with lower bound \\
|
|
alpar@9
|
469 \verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
|
|
alpar@9
|
470 & Variable with upper bound \\
|
|
alpar@9
|
471 \verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
|
|
alpar@9
|
472 & Double-bounded variable \\
|
|
alpar@9
|
473 \verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
|
|
alpar@9
|
474 & Fixed variable \\
|
|
alpar@9
|
475 \end{tabular}
|
|
alpar@9
|
476 \end{center}
|
|
alpar@9
|
477
|
|
alpar@9
|
478 \noindent
|
|
alpar@9
|
479 where $x$ is the structural variable associated with $j$-th column.
|
|
alpar@9
|
480
|
|
alpar@9
|
481 If the column has no lower bound, the parameter \verb|lb| is ignored.
|
|
alpar@9
|
482 If the column has no upper bound, the parameter \verb|ub| is ignored.
|
|
alpar@9
|
483 If the column is of fixed type, only the parameter \verb|lb| is used
|
|
alpar@9
|
484 while the parameter \verb|ub| is ignored.
|
|
alpar@9
|
485
|
|
alpar@9
|
486 Being added to the problem object each column is initially fixed at
|
|
alpar@9
|
487 zero, i.e. its type is \verb|GLP_FX| and both bounds are 0.
|
|
alpar@9
|
488
|
|
alpar@9
|
489 \subsection{glp\_set\_obj\_coef---set (change) objective coefficient
|
|
alpar@9
|
490 or constant term}
|
|
alpar@9
|
491
|
|
alpar@9
|
492 \subsubsection*{Synopsis}
|
|
alpar@9
|
493
|
|
alpar@9
|
494 \begin{verbatim}
|
|
alpar@9
|
495 void glp_set_obj_coef(glp_prob *lp, int j, double coef);
|
|
alpar@9
|
496 \end{verbatim}
|
|
alpar@9
|
497
|
|
alpar@9
|
498 \subsubsection*{Description}
|
|
alpar@9
|
499
|
|
alpar@9
|
500 The routine \verb|glp_set_obj_coef| sets (changes) the objective
|
|
alpar@9
|
501 coefficient at \verb|j|-th column (structural variable). A new value of
|
|
alpar@9
|
502 the objective coefficient is specified by the parameter \verb|coef|.
|
|
alpar@9
|
503
|
|
alpar@9
|
504 If the parameter \verb|j| is 0, the routine sets (changes) the constant
|
|
alpar@9
|
505 term (``shift'') of the objective function.
|
|
alpar@9
|
506
|
|
alpar@9
|
507 \subsection{glp\_set\_mat\_row---set (replace) row of the constraint
|
|
alpar@9
|
508 matrix}
|
|
alpar@9
|
509
|
|
alpar@9
|
510 \subsubsection*{Synopsis}
|
|
alpar@9
|
511
|
|
alpar@9
|
512 \begin{verbatim}
|
|
alpar@9
|
513 void glp_set_mat_row(glp_prob *lp, int i, int len,
|
|
alpar@9
|
514 const int ind[], const double val[]);
|
|
alpar@9
|
515 \end{verbatim}
|
|
alpar@9
|
516
|
|
alpar@9
|
517 \subsubsection*{Description}
|
|
alpar@9
|
518
|
|
alpar@9
|
519 The routine \verb|glp_set_mat_row| stores (replaces) the contents of
|
|
alpar@9
|
520 \verb|i|-th row of the constraint matrix of the specified problem
|
|
alpar@9
|
521 object.
|
|
alpar@9
|
522
|
|
alpar@9
|
523 Column indices and numerical values of new row elements must be placed
|
|
alpar@9
|
524 in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
|
|
alpar@9
|
525 \dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq n$
|
|
alpar@9
|
526 is the new length of $i$-th row, $n$ is the current number of columns in
|
|
alpar@9
|
527 the problem object. Elements with identical column indices are not
|
|
alpar@9
|
528 allowed. Zero elements are allowed, but they are not stored in the
|
|
alpar@9
|
529 constraint matrix.
|
|
alpar@9
|
530
|
|
alpar@9
|
531 If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
|
|
alpar@9
|
532 \verb|val| can be specified as \verb|NULL|.
|
|
alpar@9
|
533
|
|
alpar@9
|
534 \subsection{glp\_set\_mat\_col---set (replace) column of the
|
|
alpar@9
|
535 constr\-aint matrix}
|
|
alpar@9
|
536
|
|
alpar@9
|
537 \subsubsection*{Synopsis}
|
|
alpar@9
|
538
|
|
alpar@9
|
539 \begin{verbatim}
|
|
alpar@9
|
540 void glp_set_mat_col(glp_prob *lp, int j, int len,
|
|
alpar@9
|
541 const int ind[], const double val[]);
|
|
alpar@9
|
542 \end{verbatim}
|
|
alpar@9
|
543
|
|
alpar@9
|
544 \subsubsection*{Description}
|
|
alpar@9
|
545
|
|
alpar@9
|
546 The routine \verb|glp_set_mat_col| stores (replaces) the contents of
|
|
alpar@9
|
547 \verb|j|-th column of the constraint matrix of the specified problem
|
|
alpar@9
|
548 object.
|
|
alpar@9
|
549
|
|
alpar@9
|
550 Row indices and numerical values of new column elements must be placed
|
|
alpar@9
|
551 in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
|
|
alpar@9
|
552 \dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq m$
|
|
alpar@9
|
553 is the new length of $j$-th column, $m$ is the current number of rows in
|
|
alpar@9
|
554 the problem object. Elements with identical row indices are not allowed.
|
|
alpar@9
|
555 Zero elements are allowed, but they are not stored in the constraint
|
|
alpar@9
|
556 matrix.
|
|
alpar@9
|
557
|
|
alpar@9
|
558 If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
|
|
alpar@9
|
559 \verb|val| can be specified as \verb|NULL|.
|
|
alpar@9
|
560
|
|
alpar@9
|
561 \subsection{glp\_load\_matrix---load (replace) the whole constraint
|
|
alpar@9
|
562 matrix}
|
|
alpar@9
|
563
|
|
alpar@9
|
564 \subsubsection*{Synopsis}
|
|
alpar@9
|
565
|
|
alpar@9
|
566 \begin{verbatim}
|
|
alpar@9
|
567 void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
|
|
alpar@9
|
568 const int ja[], const double ar[]);
|
|
alpar@9
|
569 \end{verbatim}
|
|
alpar@9
|
570
|
|
alpar@9
|
571 \subsubsection*{Description}
|
|
alpar@9
|
572
|
|
alpar@9
|
573 The routine \verb|glp_load_matrix| loads the constraint matrix passed
|
|
alpar@9
|
574 in the arrays \verb|ia|, \verb|ja|, and \verb|ar| into the specified
|
|
alpar@9
|
575 problem object. Before loading the current contents of the constraint
|
|
alpar@9
|
576 matrix is destroyed.
|
|
alpar@9
|
577
|
|
alpar@9
|
578 Constraint coefficients (elements of the constraint matrix) must be
|
|
alpar@9
|
579 specified as triplets (\verb|ia[k]|, \verb|ja[k]|, \verb|ar[k]|) for
|
|
alpar@9
|
580 $k=1,\dots,ne$, where \verb|ia[k]| is the row index, \verb|ja[k]| is
|
|
alpar@9
|
581 the column index, and \verb|ar[k]| is a numeric value of corresponding
|
|
alpar@9
|
582 constraint coefficient. The parameter \verb|ne| specifies the total
|
|
alpar@9
|
583 number of (non-zero) elements in the matrix to be loaded. Coefficients
|
|
alpar@9
|
584 with identical indices are not allowed. Zero coefficients are allowed,
|
|
alpar@9
|
585 however, they are not stored in the constraint matrix.
|
|
alpar@9
|
586
|
|
alpar@9
|
587 If the parameter \verb|ne| is 0, the parameters \verb|ia|, \verb|ja|,
|
|
alpar@9
|
588 and/or \verb|ar| can be specified as \verb|NULL|.
|
|
alpar@9
|
589
|
|
alpar@9
|
590 \subsection{glp\_check\_dup---check for duplicate elements in sparse
|
|
alpar@9
|
591 matrix}
|
|
alpar@9
|
592
|
|
alpar@9
|
593 \subsubsection*{Synopsis}
|
|
alpar@9
|
594
|
|
alpar@9
|
595 \begin{verbatim}
|
|
alpar@9
|
596 int glp_check_dup(int m, int n, int ne, const int ia[],
|
|
alpar@9
|
597 const int ja[]);
|
|
alpar@9
|
598 \end{verbatim}
|
|
alpar@9
|
599
|
|
alpar@9
|
600 \subsubsection*{Description}
|
|
alpar@9
|
601
|
|
alpar@9
|
602 The routine \verb|glp_check_dup checks| for duplicate elements (that
|
|
alpar@9
|
603 is, elements with identical indices) in a sparse matrix specified in
|
|
alpar@9
|
604 the coordinate format.
|
|
alpar@9
|
605
|
|
alpar@9
|
606 The parameters $m$ and $n$ specifies, respectively, the number of rows
|
|
alpar@9
|
607 and columns in the matrix, $m\geq 0$, $n\geq 0$.
|
|
alpar@9
|
608
|
|
alpar@9
|
609 The parameter {\it ne} specifies the number of (structurally) non-zero
|
|
alpar@9
|
610 elements in the matrix, {\it ne} $\geq 0$.
|
|
alpar@9
|
611
|
|
alpar@9
|
612 Elements of the matrix are specified as doublets $(ia[k],ja[k])$ for
|
|
alpar@9
|
613 $k=1,\dots,ne$, where $ia[k]$ is a row index, $ja[k]$ is a column index.
|
|
alpar@9
|
614
|
|
alpar@9
|
615 The routine \verb|glp_check_dup| can be used prior to a call to the
|
|
alpar@9
|
616 routine \verb|glp_load_matrix| to check that the constraint matrix to
|
|
alpar@9
|
617 be loaded has no duplicate elements.
|
|
alpar@9
|
618
|
|
alpar@9
|
619 \subsubsection*{Returns}
|
|
alpar@9
|
620
|
|
alpar@9
|
621 The routine \verb|glp_check_dup| returns one of the following values:
|
|
alpar@9
|
622
|
|
alpar@9
|
623 \noindent
|
|
alpar@9
|
624 \begin{tabular}{@{}r@{\ }c@{\ }l@{}}
|
|
alpar@9
|
625 0&---&the matrix has no duplicate elements;\\
|
|
alpar@9
|
626 $-k$&---&indices $ia[k]$ or/and $ja[k]$ are out of range;\\
|
|
alpar@9
|
627 $+k$&---&element $(ia[k],ja[k])$ is duplicate.\\
|
|
alpar@9
|
628 \end{tabular}
|
|
alpar@9
|
629
|
|
alpar@9
|
630 \subsection{glp\_sort\_matrix---sort elements of the constraint matrix}
|
|
alpar@9
|
631
|
|
alpar@9
|
632 \subsubsection*{Synopsis}
|
|
alpar@9
|
633
|
|
alpar@9
|
634 \begin{verbatim}
|
|
alpar@9
|
635 void glp_sort_matrix(glp_prob *P);
|
|
alpar@9
|
636 \end{verbatim}
|
|
alpar@9
|
637
|
|
alpar@9
|
638 \subsubsection*{Description}
|
|
alpar@9
|
639
|
|
alpar@9
|
640 The routine \verb|glp_sort_matrix| sorts elements of the constraint
|
|
alpar@9
|
641 matrix rebuilding its row and column linked lists. On exit from the
|
|
alpar@9
|
642 routine the constraint matrix is not changed, however, elements in the
|
|
alpar@9
|
643 row linked lists become ordered by ascending column indices, and the
|
|
alpar@9
|
644 elements in the column linked lists become ordered by ascending row
|
|
alpar@9
|
645 indices.
|
|
alpar@9
|
646
|
|
alpar@9
|
647 \subsection{glp\_del\_rows---delete rows from problem object}
|
|
alpar@9
|
648
|
|
alpar@9
|
649 \subsubsection*{Synopsis}
|
|
alpar@9
|
650
|
|
alpar@9
|
651 \begin{verbatim}
|
|
alpar@9
|
652 void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
|
|
alpar@9
|
653 \end{verbatim}
|
|
alpar@9
|
654
|
|
alpar@9
|
655 \subsubsection*{Description}
|
|
alpar@9
|
656
|
|
alpar@9
|
657 The routine \verb|glp_del_rows| deletes rows from the specified problem
|
|
alpar@9
|
658 ob-\linebreak ject. Ordinal numbers of rows to be deleted should be
|
|
alpar@9
|
659 placed in locations \verb|num[1]|, \dots, \verb|num[nrs]|, where
|
|
alpar@9
|
660 ${\tt nrs}>0$.
|
|
alpar@9
|
661
|
|
alpar@9
|
662 Note that deleting rows involves changing ordinal numbers of other
|
|
alpar@9
|
663 rows remaining in the problem object. New ordinal numbers of the
|
|
alpar@9
|
664 remaining rows are assigned under the assumption that the original
|
|
alpar@9
|
665 order of rows is not changed. Let, for example, before deletion there
|
|
alpar@9
|
666 be five rows $a$, $b$, $c$, $d$, $e$ with ordinal numbers 1, 2, 3, 4, 5,
|
|
alpar@9
|
667 and let rows $b$ and $d$ have been deleted. Then after deletion the
|
|
alpar@9
|
668 remaining rows $a$, $c$, $e$ are assigned new oridinal numbers 1, 2, 3.
|
|
alpar@9
|
669
|
|
alpar@9
|
670 \subsection{glp\_del\_cols---delete columns from problem object}
|
|
alpar@9
|
671
|
|
alpar@9
|
672 \subsubsection*{Synopsis}
|
|
alpar@9
|
673
|
|
alpar@9
|
674 \begin{verbatim}
|
|
alpar@9
|
675 void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
|
|
alpar@9
|
676 \end{verbatim}
|
|
alpar@9
|
677
|
|
alpar@9
|
678 \subsubsection*{Description}
|
|
alpar@9
|
679
|
|
alpar@9
|
680 The routine \verb|glp_del_cols| deletes columns from the specified
|
|
alpar@9
|
681 problem object. Ordinal numbers of columns to be deleted should be
|
|
alpar@9
|
682 placed in locations \verb|num[1]|, \dots, \verb|num[ncs]|, where
|
|
alpar@9
|
683 ${\tt ncs}>0$.
|
|
alpar@9
|
684
|
|
alpar@9
|
685 Note that deleting columns involves changing ordinal numbers of other
|
|
alpar@9
|
686 columns remaining in the problem object. New ordinal numbers of the
|
|
alpar@9
|
687 remaining columns are assigned under the assumption that the original
|
|
alpar@9
|
688 order of columns is not changed. Let, for example, before deletion there
|
|
alpar@9
|
689 be six columns $p$, $q$, $r$, $s$, $t$, $u$ with ordinal numbers 1, 2,
|
|
alpar@9
|
690 3, 4, 5, 6, and let columns $p$, $q$, $s$ have been deleted. Then after
|
|
alpar@9
|
691 deletion the remaining columns $r$, $t$, $u$ are assigned new ordinal
|
|
alpar@9
|
692 numbers 1, 2, 3.
|
|
alpar@9
|
693
|
|
alpar@9
|
694 \subsection{glp\_copy\_prob---copy problem object content}
|
|
alpar@9
|
695
|
|
alpar@9
|
696 \subsubsection*{Synopsis}
|
|
alpar@9
|
697
|
|
alpar@9
|
698 \begin{verbatim}
|
|
alpar@9
|
699 void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
|
|
alpar@9
|
700 \end{verbatim}
|
|
alpar@9
|
701
|
|
alpar@9
|
702 \subsubsection*{Description}
|
|
alpar@9
|
703
|
|
alpar@9
|
704 The routine \verb|glp_copy_prob| copies the content of the problem
|
|
alpar@9
|
705 object \verb|prob| to the problem object \verb|dest|.
|
|
alpar@9
|
706
|
|
alpar@9
|
707 The parameter \verb|names| is a flag. If it is \verb|GLP_ON|,
|
|
alpar@9
|
708 the routine also copies all symbolic names; otherwise, if it is
|
|
alpar@9
|
709 \verb|GLP_OFF|, no symbolic names are copied.
|
|
alpar@9
|
710
|
|
alpar@9
|
711 \newpage
|
|
alpar@9
|
712
|
|
alpar@9
|
713 \subsection{glp\_erase\_prob---erase problem object content}
|
|
alpar@9
|
714
|
|
alpar@9
|
715 \subsubsection*{Synopsis}
|
|
alpar@9
|
716
|
|
alpar@9
|
717 \begin{verbatim}
|
|
alpar@9
|
718 void glp_erase_prob(glp_prob *lp);
|
|
alpar@9
|
719 \end{verbatim}
|
|
alpar@9
|
720
|
|
alpar@9
|
721 \subsubsection*{Description}
|
|
alpar@9
|
722
|
|
alpar@9
|
723 The routine \verb|glp_erase_prob| erases the content of the specified
|
|
alpar@9
|
724 problem object. The effect of this operation is the same as if the
|
|
alpar@9
|
725 problem object would be deleted with the routine \verb|glp_delete_prob|
|
|
alpar@9
|
726 and then created anew with the routine \verb|glp_create_prob|, with the
|
|
alpar@9
|
727 only exception that the handle (pointer) to the problem object remains
|
|
alpar@9
|
728 valid.
|
|
alpar@9
|
729
|
|
alpar@9
|
730 \subsection{glp\_delete\_prob---delete problem object}
|
|
alpar@9
|
731
|
|
alpar@9
|
732 \subsubsection*{Synopsis}
|
|
alpar@9
|
733
|
|
alpar@9
|
734 \begin{verbatim}
|
|
alpar@9
|
735 void glp_delete_prob(glp_prob *lp);
|
|
alpar@9
|
736 \end{verbatim}
|
|
alpar@9
|
737
|
|
alpar@9
|
738 \subsubsection*{Description}
|
|
alpar@9
|
739
|
|
alpar@9
|
740 The routine \verb|glp_delete_prob| deletes a problem object, which the
|
|
alpar@9
|
741 parameter \verb|lp| points to, freeing all the memory allocated to this
|
|
alpar@9
|
742 object.
|
|
alpar@9
|
743
|
|
alpar@9
|
744 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
745
|
|
alpar@9
|
746 \newpage
|
|
alpar@9
|
747
|
|
alpar@9
|
748 \section{Problem retrieving routines}
|
|
alpar@9
|
749
|
|
alpar@9
|
750 \subsection{glp\_get\_prob\_name---retrieve problem name}
|
|
alpar@9
|
751
|
|
alpar@9
|
752 \subsubsection*{Synopsis}
|
|
alpar@9
|
753
|
|
alpar@9
|
754 \begin{verbatim}
|
|
alpar@9
|
755 const char *glp_get_prob_name(glp_prob *lp);
|
|
alpar@9
|
756 \end{verbatim}
|
|
alpar@9
|
757
|
|
alpar@9
|
758 \subsubsection*{Returns}
|
|
alpar@9
|
759
|
|
alpar@9
|
760 The routine \verb|glp_get_prob_name| returns a pointer to an internal
|
|
alpar@9
|
761 buffer, which contains symbolic name of the problem. However, if the
|
|
alpar@9
|
762 problem has no assigned name, the routine returns \verb|NULL|.
|
|
alpar@9
|
763
|
|
alpar@9
|
764 \subsection{glp\_get\_obj\_name---retrieve objective function name}
|
|
alpar@9
|
765
|
|
alpar@9
|
766 \subsubsection*{Synopsis}
|
|
alpar@9
|
767
|
|
alpar@9
|
768 \begin{verbatim}
|
|
alpar@9
|
769 const char *glp_get_obj_name(glp_prob *lp);
|
|
alpar@9
|
770 \end{verbatim}
|
|
alpar@9
|
771
|
|
alpar@9
|
772 \subsubsection*{Returns}
|
|
alpar@9
|
773
|
|
alpar@9
|
774 The routine \verb|glp_get_obj_name| returns a pointer to an internal
|
|
alpar@9
|
775 buffer, which contains symbolic name assigned to the objective
|
|
alpar@9
|
776 function. However, if the objective function has no assigned name, the
|
|
alpar@9
|
777 routine returns \verb|NULL|.
|
|
alpar@9
|
778
|
|
alpar@9
|
779 \subsection{glp\_get\_obj\_dir---retrieve optimization direction flag}
|
|
alpar@9
|
780
|
|
alpar@9
|
781 \subsubsection*{Synopsis}
|
|
alpar@9
|
782
|
|
alpar@9
|
783 \begin{verbatim}
|
|
alpar@9
|
784 int glp_get_obj_dir(glp_prob *lp);
|
|
alpar@9
|
785 \end{verbatim}
|
|
alpar@9
|
786
|
|
alpar@9
|
787 \subsubsection*{Returns}
|
|
alpar@9
|
788
|
|
alpar@9
|
789 The routine \verb|glp_get_obj_dir| returns the optimization direction
|
|
alpar@9
|
790 flag (i.e. ``sense'' of the objective function):
|
|
alpar@9
|
791
|
|
alpar@9
|
792 \begin{tabular}{@{}ll}
|
|
alpar@9
|
793 \verb|GLP_MIN| & minimization; \\
|
|
alpar@9
|
794 \verb|GLP_MAX| & maximization. \\
|
|
alpar@9
|
795 \end{tabular}
|
|
alpar@9
|
796
|
|
alpar@9
|
797 \pagebreak
|
|
alpar@9
|
798
|
|
alpar@9
|
799 \subsection{glp\_get\_num\_rows---retrieve number of rows}
|
|
alpar@9
|
800
|
|
alpar@9
|
801 \subsubsection*{Synopsis}
|
|
alpar@9
|
802
|
|
alpar@9
|
803 \begin{verbatim}
|
|
alpar@9
|
804 int glp_get_num_rows(glp_prob *lp);
|
|
alpar@9
|
805 \end{verbatim}
|
|
alpar@9
|
806
|
|
alpar@9
|
807 \subsubsection*{Returns}
|
|
alpar@9
|
808
|
|
alpar@9
|
809 The routine \verb|glp_get_num_rows| returns the current number of rows
|
|
alpar@9
|
810 in the specified problem object.
|
|
alpar@9
|
811
|
|
alpar@9
|
812 \subsection{glp\_get\_num\_cols---retrieve number of columns}
|
|
alpar@9
|
813
|
|
alpar@9
|
814 \subsubsection*{Synopsis}
|
|
alpar@9
|
815
|
|
alpar@9
|
816 \begin{verbatim}
|
|
alpar@9
|
817 int glp_get_num_cols(glp_prob *lp);
|
|
alpar@9
|
818 \end{verbatim}
|
|
alpar@9
|
819
|
|
alpar@9
|
820 \subsubsection*{Returns}
|
|
alpar@9
|
821
|
|
alpar@9
|
822 The routine \verb|glp_get_num_cols| returns the current number of
|
|
alpar@9
|
823 columns the specified problem object.
|
|
alpar@9
|
824
|
|
alpar@9
|
825 \subsection{glp\_get\_row\_name---retrieve row name}
|
|
alpar@9
|
826
|
|
alpar@9
|
827 \subsubsection*{Synopsis}
|
|
alpar@9
|
828
|
|
alpar@9
|
829 \begin{verbatim}
|
|
alpar@9
|
830 const char *glp_get_row_name(glp_prob *lp, int i);
|
|
alpar@9
|
831 \end{verbatim}
|
|
alpar@9
|
832
|
|
alpar@9
|
833 \subsubsection*{Returns}
|
|
alpar@9
|
834
|
|
alpar@9
|
835 The routine \verb|glp_get_row_name| returns a pointer to an internal
|
|
alpar@9
|
836 buffer, which contains a symbolic name assigned to \verb|i|-th row.
|
|
alpar@9
|
837 However, if the row has no assigned name, the routine returns
|
|
alpar@9
|
838 \verb|NULL|.
|
|
alpar@9
|
839
|
|
alpar@9
|
840 \subsection{glp\_get\_col\_name---retrieve column name}
|
|
alpar@9
|
841
|
|
alpar@9
|
842 \subsubsection*{Synopsis}
|
|
alpar@9
|
843
|
|
alpar@9
|
844 \begin{verbatim}
|
|
alpar@9
|
845 const char *glp_get_col_name(glp_prob *lp, int j);
|
|
alpar@9
|
846 \end{verbatim}
|
|
alpar@9
|
847
|
|
alpar@9
|
848 \subsubsection*{Returns}
|
|
alpar@9
|
849
|
|
alpar@9
|
850 The routine \verb|glp_get_col_name| returns a pointer to an internal
|
|
alpar@9
|
851 buffer, which contains a symbolic name assigned to \verb|j|-th column.
|
|
alpar@9
|
852 However, if the column has no assigned name, the routine returns
|
|
alpar@9
|
853 \verb|NULL|.
|
|
alpar@9
|
854
|
|
alpar@9
|
855 \subsection{glp\_get\_row\_type---retrieve row type}
|
|
alpar@9
|
856
|
|
alpar@9
|
857 \subsubsection*{Synopsis}
|
|
alpar@9
|
858
|
|
alpar@9
|
859 \begin{verbatim}
|
|
alpar@9
|
860 int glp_get_row_type(glp_prob *lp, int i);
|
|
alpar@9
|
861 \end{verbatim}
|
|
alpar@9
|
862
|
|
alpar@9
|
863 \subsubsection*{Returns}
|
|
alpar@9
|
864
|
|
alpar@9
|
865 The routine \verb|glp_get_row_type| returns the type of \verb|i|-th
|
|
alpar@9
|
866 row, i.e. the type of corresponding auxiliary variable, as follows:
|
|
alpar@9
|
867
|
|
alpar@9
|
868 \begin{tabular}{@{}ll}
|
|
alpar@9
|
869 \verb|GLP_FR| & free (unbounded) variable; \\
|
|
alpar@9
|
870 \verb|GLP_LO| & variable with lower bound; \\
|
|
alpar@9
|
871 \verb|GLP_UP| & variable with upper bound; \\
|
|
alpar@9
|
872 \verb|GLP_DB| & double-bounded variable; \\
|
|
alpar@9
|
873 \verb|GLP_FX| & fixed variable. \\
|
|
alpar@9
|
874 \end{tabular}
|
|
alpar@9
|
875
|
|
alpar@9
|
876 \subsection{glp\_get\_row\_lb---retrieve row lower bound}
|
|
alpar@9
|
877
|
|
alpar@9
|
878 \subsubsection*{Synopsis}
|
|
alpar@9
|
879
|
|
alpar@9
|
880 \begin{verbatim}
|
|
alpar@9
|
881 double glp_get_row_lb(glp_prob *lp, int i);
|
|
alpar@9
|
882 \end{verbatim}
|
|
alpar@9
|
883
|
|
alpar@9
|
884 \subsubsection*{Returns}
|
|
alpar@9
|
885
|
|
alpar@9
|
886 The routine \verb|glp_get_row_lb| returns the lower bound of
|
|
alpar@9
|
887 \verb|i|-th row, i.e. the lower bound of corresponding auxiliary
|
|
alpar@9
|
888 variable. However, if the row has no lower bound, the routine returns
|
|
alpar@9
|
889 \verb|-DBL_MAX|.
|
|
alpar@9
|
890
|
|
alpar@9
|
891 \subsection{glp\_get\_row\_ub---retrieve row upper bound}
|
|
alpar@9
|
892
|
|
alpar@9
|
893 \subsubsection*{Synopsis}
|
|
alpar@9
|
894
|
|
alpar@9
|
895 \begin{verbatim}
|
|
alpar@9
|
896 double glp_get_row_ub(glp_prob *lp, int i);
|
|
alpar@9
|
897 \end{verbatim}
|
|
alpar@9
|
898
|
|
alpar@9
|
899 \subsubsection*{Returns}
|
|
alpar@9
|
900
|
|
alpar@9
|
901 The routine \verb|glp_get_row_ub| returns the upper bound of
|
|
alpar@9
|
902 \verb|i|-th row, i.e. the upper bound of corresponding auxiliary
|
|
alpar@9
|
903 variable. However, if the row has no upper bound, the routine returns
|
|
alpar@9
|
904 \verb|+DBL_MAX|.
|
|
alpar@9
|
905
|
|
alpar@9
|
906 \subsection{glp\_get\_col\_type---retrieve column type}
|
|
alpar@9
|
907
|
|
alpar@9
|
908 \subsubsection*{Synopsis}
|
|
alpar@9
|
909
|
|
alpar@9
|
910 \begin{verbatim}
|
|
alpar@9
|
911 int glp_get_col_type(glp_prob *lp, int j);
|
|
alpar@9
|
912 \end{verbatim}
|
|
alpar@9
|
913
|
|
alpar@9
|
914 \subsubsection*{Returns}
|
|
alpar@9
|
915
|
|
alpar@9
|
916 The routine \verb|glp_get_col_type| returns the type of \verb|j|-th
|
|
alpar@9
|
917 column, i.e. the type of corresponding structural variable, as follows:
|
|
alpar@9
|
918
|
|
alpar@9
|
919 \begin{tabular}{@{}ll}
|
|
alpar@9
|
920 \verb|GLP_FR| & free (unbounded) variable; \\
|
|
alpar@9
|
921 \verb|GLP_LO| & variable with lower bound; \\
|
|
alpar@9
|
922 \verb|GLP_UP| & variable with upper bound; \\
|
|
alpar@9
|
923 \verb|GLP_DB| & double-bounded variable; \\
|
|
alpar@9
|
924 \verb|GLP_FX| & fixed variable. \\
|
|
alpar@9
|
925 \end{tabular}
|
|
alpar@9
|
926
|
|
alpar@9
|
927 \subsection{glp\_get\_col\_lb---retrieve column lower bound}
|
|
alpar@9
|
928
|
|
alpar@9
|
929 \subsubsection*{Synopsis}
|
|
alpar@9
|
930
|
|
alpar@9
|
931 \begin{verbatim}
|
|
alpar@9
|
932 double glp_get_col_lb(glp_prob *lp, int j);
|
|
alpar@9
|
933 \end{verbatim}
|
|
alpar@9
|
934
|
|
alpar@9
|
935 \subsubsection*{Returns}
|
|
alpar@9
|
936
|
|
alpar@9
|
937 The routine \verb|glp_get_col_lb| returns the lower bound of
|
|
alpar@9
|
938 \verb|j|-th column, i.e. the lower bound of corresponding structural
|
|
alpar@9
|
939 variable. However, if the column has no lower bound, the routine returns
|
|
alpar@9
|
940 \verb|-DBL_MAX|.
|
|
alpar@9
|
941
|
|
alpar@9
|
942 \subsection{glp\_get\_col\_ub---retrieve column upper bound}
|
|
alpar@9
|
943
|
|
alpar@9
|
944 \subsubsection*{Synopsis}
|
|
alpar@9
|
945
|
|
alpar@9
|
946 \begin{verbatim}
|
|
alpar@9
|
947 double glp_get_col_ub(glp_prob *lp, int j);
|
|
alpar@9
|
948 \end{verbatim}
|
|
alpar@9
|
949
|
|
alpar@9
|
950 \subsubsection*{Returns}
|
|
alpar@9
|
951
|
|
alpar@9
|
952 The routine \verb|glp_get_col_ub| returns the upper bound of
|
|
alpar@9
|
953 \verb|j|-th column, i.e. the upper bound of corresponding structural
|
|
alpar@9
|
954 variable. However, if the column has no upper bound, the routine returns
|
|
alpar@9
|
955 \verb|+DBL_MAX|.
|
|
alpar@9
|
956
|
|
alpar@9
|
957 \subsection{glp\_get\_obj\_coef---retrieve objective coefficient or\\
|
|
alpar@9
|
958 constant term}
|
|
alpar@9
|
959
|
|
alpar@9
|
960 \subsubsection*{Synopsis}
|
|
alpar@9
|
961
|
|
alpar@9
|
962 \begin{verbatim}
|
|
alpar@9
|
963 double glp_get_obj_coef(glp_prob *lp, int j);
|
|
alpar@9
|
964 \end{verbatim}
|
|
alpar@9
|
965
|
|
alpar@9
|
966 \subsubsection*{Returns}
|
|
alpar@9
|
967
|
|
alpar@9
|
968 The routine \verb|glp_get_obj_coef| returns the objective coefficient
|
|
alpar@9
|
969 at \verb|j|-th structural variable (column).
|
|
alpar@9
|
970
|
|
alpar@9
|
971 If the parameter \verb|j| is 0, the routine returns the constant term
|
|
alpar@9
|
972 (``shift'') of the objective function.
|
|
alpar@9
|
973
|
|
alpar@9
|
974 \subsection{glp\_get\_num\_nz---retrieve number of constraint
|
|
alpar@9
|
975 coefficients}
|
|
alpar@9
|
976
|
|
alpar@9
|
977 \subsubsection*{Synopsis}
|
|
alpar@9
|
978
|
|
alpar@9
|
979 \begin{verbatim}
|
|
alpar@9
|
980 int glp_get_num_nz(glp_prob *lp);
|
|
alpar@9
|
981 \end{verbatim}
|
|
alpar@9
|
982
|
|
alpar@9
|
983 \subsubsection*{Returns}
|
|
alpar@9
|
984
|
|
alpar@9
|
985 The routine \verb|glp_get_num_nz| returns the number of non-zero
|
|
alpar@9
|
986 elements in the constraint matrix of the specified problem object.
|
|
alpar@9
|
987
|
|
alpar@9
|
988 \subsection{glp\_get\_mat\_row---retrieve row of the constraint
|
|
alpar@9
|
989 matrix}
|
|
alpar@9
|
990
|
|
alpar@9
|
991 \subsubsection*{Synopsis}
|
|
alpar@9
|
992
|
|
alpar@9
|
993 \begin{verbatim}
|
|
alpar@9
|
994 int glp_get_mat_row(glp_prob *lp, int i, int ind[],
|
|
alpar@9
|
995 double val[]);
|
|
alpar@9
|
996 \end{verbatim}
|
|
alpar@9
|
997
|
|
alpar@9
|
998 \subsubsection*{Description}
|
|
alpar@9
|
999
|
|
alpar@9
|
1000 The routine \verb|glp_get_mat_row| scans (non-zero) elements of
|
|
alpar@9
|
1001 \verb|i|-th row of the constraint matrix of the specified problem object
|
|
alpar@9
|
1002 and stores their column indices and numeric values to locations
|
|
alpar@9
|
1003 \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
|
|
alpar@9
|
1004 \verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is the
|
|
alpar@9
|
1005 number of elements in $i$-th row, $n$ is the number of columns.
|
|
alpar@9
|
1006
|
|
alpar@9
|
1007 The parameter \verb|ind| and/or \verb|val| can be specified as
|
|
alpar@9
|
1008 \verb|NULL|, in which case corresponding information is not stored.
|
|
alpar@9
|
1009
|
|
alpar@9
|
1010 \subsubsection*{Returns}
|
|
alpar@9
|
1011
|
|
alpar@9
|
1012 The routine \verb|glp_get_mat_row| returns the length \verb|len|, i.e.
|
|
alpar@9
|
1013 the number of (non-zero) elements in \verb|i|-th row.
|
|
alpar@9
|
1014
|
|
alpar@9
|
1015 \subsection{glp\_get\_mat\_col---retrieve column of the constraint\\
|
|
alpar@9
|
1016 matrix}
|
|
alpar@9
|
1017
|
|
alpar@9
|
1018 \subsubsection*{Synopsis}
|
|
alpar@9
|
1019
|
|
alpar@9
|
1020 \begin{verbatim}
|
|
alpar@9
|
1021 int glp_get_mat_col(glp_prob *lp, int j, int ind[],
|
|
alpar@9
|
1022 double val[]);
|
|
alpar@9
|
1023 \end{verbatim}
|
|
alpar@9
|
1024
|
|
alpar@9
|
1025 \subsubsection*{Description}
|
|
alpar@9
|
1026
|
|
alpar@9
|
1027 The routine \verb|glp_get_mat_col| scans (non-zero) elements of
|
|
alpar@9
|
1028 \verb|j|-th column of the constraint matrix of the specified problem
|
|
alpar@9
|
1029 object and stores their row indices and numeric values to locations
|
|
alpar@9
|
1030 \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
|
|
alpar@9
|
1031 \verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is the
|
|
alpar@9
|
1032 number of elements in $j$-th column, $m$ is the number of rows.
|
|
alpar@9
|
1033
|
|
alpar@9
|
1034 The parameter \verb|ind| and/or \verb|val| can be specified as
|
|
alpar@9
|
1035 \verb|NULL|, in which case corresponding information is not stored.
|
|
alpar@9
|
1036
|
|
alpar@9
|
1037 \subsubsection*{Returns}
|
|
alpar@9
|
1038
|
|
alpar@9
|
1039 The routine \verb|glp_get_mat_col| returns the length \verb|len|, i.e.
|
|
alpar@9
|
1040 the number of (non-zero) elements in \verb|j|-th column.
|
|
alpar@9
|
1041
|
|
alpar@9
|
1042 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
1043
|
|
alpar@9
|
1044 \newpage
|
|
alpar@9
|
1045
|
|
alpar@9
|
1046 \section{Row and column searching routines}
|
|
alpar@9
|
1047
|
|
alpar@9
|
1048 \subsection{glp\_create\_index---create the name index}
|
|
alpar@9
|
1049
|
|
alpar@9
|
1050 \subsubsection*{Synopsis}
|
|
alpar@9
|
1051
|
|
alpar@9
|
1052 \begin{verbatim}
|
|
alpar@9
|
1053 void glp_create_index(glp_prob *lp);
|
|
alpar@9
|
1054 \end{verbatim}
|
|
alpar@9
|
1055
|
|
alpar@9
|
1056 \subsubsection*{Description}
|
|
alpar@9
|
1057
|
|
alpar@9
|
1058 The routine \verb|glp_create_index| creates the name index for the
|
|
alpar@9
|
1059 specified problem object. The name index is an auxiliary data structure,
|
|
alpar@9
|
1060 which is intended to quickly (i.e. for logarithmic time) find rows and
|
|
alpar@9
|
1061 columns by their names.
|
|
alpar@9
|
1062
|
|
alpar@9
|
1063 This routine can be called at any time. If the name index already
|
|
alpar@9
|
1064 exists, the routine does nothing.
|
|
alpar@9
|
1065
|
|
alpar@9
|
1066 \subsection{glp\_find\_row---find row by its name}
|
|
alpar@9
|
1067
|
|
alpar@9
|
1068 \subsubsection*{Synopsis}
|
|
alpar@9
|
1069
|
|
alpar@9
|
1070 \begin{verbatim}
|
|
alpar@9
|
1071 int glp_find_row(glp_prob *lp, const char *name);
|
|
alpar@9
|
1072 \end{verbatim}
|
|
alpar@9
|
1073
|
|
alpar@9
|
1074 \subsubsection*{Returns}
|
|
alpar@9
|
1075
|
|
alpar@9
|
1076 The routine \verb|glp_find_row| returns the ordinal number of a row,
|
|
alpar@9
|
1077 which is assigned (by the routine \verb|glp_set_row_name|) the specified
|
|
alpar@9
|
1078 symbolic \verb|name|. If no such row exists, the routine returns 0.
|
|
alpar@9
|
1079
|
|
alpar@9
|
1080 \subsection{glp\_find\_col---find column by its name}
|
|
alpar@9
|
1081
|
|
alpar@9
|
1082 \subsubsection*{Synopsis}
|
|
alpar@9
|
1083
|
|
alpar@9
|
1084 \begin{verbatim}
|
|
alpar@9
|
1085 int glp_find_col(glp_prob *lp, const char *name);
|
|
alpar@9
|
1086 \end{verbatim}
|
|
alpar@9
|
1087
|
|
alpar@9
|
1088 \subsubsection*{Returns}
|
|
alpar@9
|
1089
|
|
alpar@9
|
1090 The routine \verb|glp_find_col| returns the ordinal number of a column,
|
|
alpar@9
|
1091 which is assigned (by the routine \verb|glp_set_col_name|) the specified
|
|
alpar@9
|
1092 symbolic \verb|name|. If no such column exists, the routine returns 0.
|
|
alpar@9
|
1093
|
|
alpar@9
|
1094 \subsection{glp\_delete\_index---delete the name index}
|
|
alpar@9
|
1095
|
|
alpar@9
|
1096 \subsubsection*{Synopsis}
|
|
alpar@9
|
1097
|
|
alpar@9
|
1098 \begin{verbatim}
|
|
alpar@9
|
1099 void glp_delete_index(glp_prob *lp);
|
|
alpar@9
|
1100 \end{verbatim}
|
|
alpar@9
|
1101
|
|
alpar@9
|
1102 \subsubsection*{Description}
|
|
alpar@9
|
1103
|
|
alpar@9
|
1104 The routine \verb|glp_delete_index| deletes the name index previously
|
|
alpar@9
|
1105 created by the routine \verb|glp_create_index| and frees the memory
|
|
alpar@9
|
1106 allocated to this auxiliary data structure.
|
|
alpar@9
|
1107
|
|
alpar@9
|
1108 This routine can be called at any time. If the name index does not
|
|
alpar@9
|
1109 exist, the routine does nothing.
|
|
alpar@9
|
1110
|
|
alpar@9
|
1111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
1112
|
|
alpar@9
|
1113 \newpage
|
|
alpar@9
|
1114
|
|
alpar@9
|
1115 \section{Problem scaling routines}
|
|
alpar@9
|
1116
|
|
alpar@9
|
1117 \subsection{Background}
|
|
alpar@9
|
1118
|
|
alpar@9
|
1119 In GLPK the {\it scaling} means a linear transformation applied to the
|
|
alpar@9
|
1120 constraint matrix to improve its numerical properties.\footnote{In many
|
|
alpar@9
|
1121 cases a proper scaling allows making the constraint matrix to be better
|
|
alpar@9
|
1122 conditioned, i.e. decreasing its condition number, that makes
|
|
alpar@9
|
1123 computations numerically more stable.}
|
|
alpar@9
|
1124
|
|
alpar@9
|
1125 The main equality is the following:
|
|
alpar@9
|
1126 $$\widetilde{A}=RAS,\eqno(2.1)$$
|
|
alpar@9
|
1127 where $A=(a_{ij})$ is the original constraint matrix, $R=(r_{ii})>0$ is
|
|
alpar@9
|
1128 a diagonal matrix used to scale rows (constraints), $S=(s_{jj})>0$ is a
|
|
alpar@9
|
1129 diagonal matrix used to scale columns (variables), $\widetilde{A}$ is
|
|
alpar@9
|
1130 the scaled constraint matrix.
|
|
alpar@9
|
1131
|
|
alpar@9
|
1132 From (2.1) it follows that in the {\it scaled} problem instance each
|
|
alpar@9
|
1133 original constraint coefficient $a_{ij}$ is replaced by corresponding
|
|
alpar@9
|
1134 scaled constraint coefficient:
|
|
alpar@9
|
1135 $$\widetilde{a}_{ij}=r_{ii}a_{ij}s_{jj}.\eqno(2.2)$$
|
|
alpar@9
|
1136
|
|
alpar@9
|
1137 Note that the scaling is performed internally and therefore
|
|
alpar@9
|
1138 transparently to the user. This means that on API level the user always
|
|
alpar@9
|
1139 deal with unscaled data.
|
|
alpar@9
|
1140
|
|
alpar@9
|
1141 Scale factors $r_{ii}$ and $s_{jj}$ can be set or changed at any time
|
|
alpar@9
|
1142 either directly by the application program in a problem specific way
|
|
alpar@9
|
1143 (with the routines \verb|glp_set_rii| and \verb|glp_set_sjj|), or by
|
|
alpar@9
|
1144 some API routines intended for automatic scaling.
|
|
alpar@9
|
1145
|
|
alpar@9
|
1146 \subsection{glp\_set\_rii---set (change) row scale factor}
|
|
alpar@9
|
1147
|
|
alpar@9
|
1148 \subsubsection*{Synopsis}
|
|
alpar@9
|
1149
|
|
alpar@9
|
1150 \begin{verbatim}
|
|
alpar@9
|
1151 void glp_set_rii(glp_prob *lp, int i, double rii);
|
|
alpar@9
|
1152 \end{verbatim}
|
|
alpar@9
|
1153
|
|
alpar@9
|
1154 \subsubsection*{Description}
|
|
alpar@9
|
1155
|
|
alpar@9
|
1156 The routine \verb|glp_set_rii| sets (changes) the scale factor $r_{ii}$
|
|
alpar@9
|
1157 for $i$-th row of the specified problem object.
|
|
alpar@9
|
1158
|
|
alpar@9
|
1159 \subsection{glp\_set\_sjj---set (change) column scale factor}
|
|
alpar@9
|
1160
|
|
alpar@9
|
1161 \subsubsection*{Synopsis}
|
|
alpar@9
|
1162
|
|
alpar@9
|
1163 \begin{verbatim}
|
|
alpar@9
|
1164 void glp_set_sjj(glp_prob *lp, int j, double sjj);
|
|
alpar@9
|
1165 \end{verbatim}
|
|
alpar@9
|
1166
|
|
alpar@9
|
1167 \subsubsection*{Description}
|
|
alpar@9
|
1168
|
|
alpar@9
|
1169 The routine \verb|glp_set_sjj| sets (changes) the scale factor $s_{jj}$
|
|
alpar@9
|
1170 for $j$-th column of the specified problem object.
|
|
alpar@9
|
1171
|
|
alpar@9
|
1172 \subsection{glp\_get\_rii---retrieve row scale factor}
|
|
alpar@9
|
1173
|
|
alpar@9
|
1174 \subsubsection*{Synopsis}
|
|
alpar@9
|
1175
|
|
alpar@9
|
1176 \begin{verbatim}
|
|
alpar@9
|
1177 double glp_get_rii(glp_prob *lp, int i);
|
|
alpar@9
|
1178 \end{verbatim}
|
|
alpar@9
|
1179
|
|
alpar@9
|
1180 \subsubsection*{Returns}
|
|
alpar@9
|
1181
|
|
alpar@9
|
1182 The routine \verb|glp_get_rii| returns current scale factor $r_{ii}$ for
|
|
alpar@9
|
1183 $i$-th row of the specified problem object.
|
|
alpar@9
|
1184
|
|
alpar@9
|
1185 \subsection{glp\_get\_sjj---retrieve column scale factor}
|
|
alpar@9
|
1186
|
|
alpar@9
|
1187 \subsubsection*{Synopsis}
|
|
alpar@9
|
1188
|
|
alpar@9
|
1189 \begin{verbatim}
|
|
alpar@9
|
1190 double glp_get_sjj(glp_prob *lp, int j);
|
|
alpar@9
|
1191 \end{verbatim}
|
|
alpar@9
|
1192
|
|
alpar@9
|
1193 \subsubsection*{Returns}
|
|
alpar@9
|
1194
|
|
alpar@9
|
1195 The routine \verb|glp_get_sjj| returns current scale factor $s_{jj}$ for
|
|
alpar@9
|
1196 $j$-th column of the specified problem object.
|
|
alpar@9
|
1197
|
|
alpar@9
|
1198 \subsection{glp\_scale\_prob---scale problem data}
|
|
alpar@9
|
1199
|
|
alpar@9
|
1200 \subsubsection*{Synopsis}
|
|
alpar@9
|
1201
|
|
alpar@9
|
1202 \begin{verbatim}
|
|
alpar@9
|
1203 void glp_scale_prob(glp_prob *lp, int flags);
|
|
alpar@9
|
1204 \end{verbatim}
|
|
alpar@9
|
1205
|
|
alpar@9
|
1206 \subsubsection*{Description}
|
|
alpar@9
|
1207
|
|
alpar@9
|
1208 The routine \verb|glp_scale_prob| performs automatic scaling of problem
|
|
alpar@9
|
1209 data for the specified problem object.
|
|
alpar@9
|
1210
|
|
alpar@9
|
1211 The parameter \verb|flags| specifies scaling options used by the
|
|
alpar@9
|
1212 routine. The options can be combined with the bitwise OR operator and
|
|
alpar@9
|
1213 may be the following:
|
|
alpar@9
|
1214
|
|
alpar@9
|
1215 \begin{tabular}{@{}ll}
|
|
alpar@9
|
1216 \verb|GLP_SF_GM| & perform geometric mean scaling;\\
|
|
alpar@9
|
1217 \verb|GLP_SF_EQ| & perform equilibration scaling;\\
|
|
alpar@9
|
1218 \verb|GLP_SF_2N| & round scale factors to nearest power of two;\\
|
|
alpar@9
|
1219 \verb|GLP_SF_SKIP| & skip scaling, if the problem is well scaled.\\
|
|
alpar@9
|
1220 \end{tabular}
|
|
alpar@9
|
1221
|
|
alpar@9
|
1222 The parameter \verb|flags| may be specified as \verb|GLP_SF_AUTO|, in
|
|
alpar@9
|
1223 which case the routine chooses the scaling options automatically.
|
|
alpar@9
|
1224
|
|
alpar@9
|
1225 \subsection{glp\_unscale\_prob---unscale problem data}
|
|
alpar@9
|
1226
|
|
alpar@9
|
1227 \subsubsection*{Synopsis}
|
|
alpar@9
|
1228
|
|
alpar@9
|
1229 \begin{verbatim}
|
|
alpar@9
|
1230 void glp_unscale_prob(glp_prob *lp);
|
|
alpar@9
|
1231 \end{verbatim}
|
|
alpar@9
|
1232
|
|
alpar@9
|
1233 The routine \verb|glp_unscale_prob| performs unscaling of problem data
|
|
alpar@9
|
1234 for the specified problem object.
|
|
alpar@9
|
1235
|
|
alpar@9
|
1236 ``Unscaling'' means replacing the current scaling matrices $R$ and $S$
|
|
alpar@9
|
1237 by unity matrices that cancels the scaling effect.
|
|
alpar@9
|
1238
|
|
alpar@9
|
1239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
1240
|
|
alpar@9
|
1241 \newpage
|
|
alpar@9
|
1242
|
|
alpar@9
|
1243 \section{LP basis constructing routines}
|
|
alpar@9
|
1244
|
|
alpar@9
|
1245 \subsection{Background}
|
|
alpar@9
|
1246
|
|
alpar@9
|
1247 To start the search the simplex method needs a valid initial basis. In
|
|
alpar@9
|
1248 GLPK the basis is completely defined by a set of {\it statuses} assigned
|
|
alpar@9
|
1249 to {\it all} (auxiliary and structural) variables, where the status may
|
|
alpar@9
|
1250 be one of the following:
|
|
alpar@9
|
1251
|
|
alpar@9
|
1252 \begin{tabular}{@{}ll}
|
|
alpar@9
|
1253 \verb|GLP_BS| & basic variable;\\
|
|
alpar@9
|
1254 \verb|GLP_NL| & non-basic variable having active lower bound;\\
|
|
alpar@9
|
1255 \verb|GLP_NU| & non-basic variable having active upper bound;\\
|
|
alpar@9
|
1256 \verb|GLP_NF| & non-basic free variable;\\
|
|
alpar@9
|
1257 \verb|GLP_NS| & non-basic fixed variable.\\
|
|
alpar@9
|
1258 \end{tabular}
|
|
alpar@9
|
1259
|
|
alpar@9
|
1260 The basis is {\it valid}, if the basis matrix, which is a matrix built
|
|
alpar@9
|
1261 of columns of the augmented constraint matrix $(I\:|-A)$ corresponding
|
|
alpar@9
|
1262 to basic variables, is non-singular. This, in particular, means that
|
|
alpar@9
|
1263 the number of basic variables must be the same as the number of rows in
|
|
alpar@9
|
1264 the problem object. (For more details see Section \ref{lpbasis}, page
|
|
alpar@9
|
1265 \pageref{lpbasis}.)
|
|
alpar@9
|
1266
|
|
alpar@9
|
1267 Any initial basis may be constructed (or restored) with the API
|
|
alpar@9
|
1268 routines \verb|glp_set_row_stat| and \verb|glp_set_col_stat| by
|
|
alpar@9
|
1269 assigning appropriate statuses to auxiliary and structural variables.
|
|
alpar@9
|
1270 Another way to construct an initial basis is to use API routines like
|
|
alpar@9
|
1271 \verb|glp_adv_basis|, which implement so called
|
|
alpar@9
|
1272 {\it crashing}.\footnote{This term is from early linear programming
|
|
alpar@9
|
1273 systems and means a heuristic to construct a valid initial basis.} Note
|
|
alpar@9
|
1274 that on normal exit the simplex solver remains the basis valid, so in
|
|
alpar@9
|
1275 case of reoptimization there is no need to construct an initial basis
|
|
alpar@9
|
1276 from scratch.
|
|
alpar@9
|
1277
|
|
alpar@9
|
1278 \subsection{glp\_set\_row\_stat---set (change) row status}
|
|
alpar@9
|
1279
|
|
alpar@9
|
1280 \subsubsection*{Synopsis}
|
|
alpar@9
|
1281
|
|
alpar@9
|
1282 \begin{verbatim}
|
|
alpar@9
|
1283 void glp_set_row_stat(glp_prob *lp, int i, int stat);
|
|
alpar@9
|
1284 \end{verbatim}
|
|
alpar@9
|
1285
|
|
alpar@9
|
1286 \subsubsection*{Description}
|
|
alpar@9
|
1287
|
|
alpar@9
|
1288 The routine \verb|glp_set_row_stat| sets (changes) the current status
|
|
alpar@9
|
1289 of \verb|i|-th row (auxiliary variable) as specified by the parameter
|
|
alpar@9
|
1290 \verb|stat|:
|
|
alpar@9
|
1291
|
|
alpar@9
|
1292 \begin{tabular}{@{}lp{104.2mm}@{}}
|
|
alpar@9
|
1293 \verb|GLP_BS| & make the row basic (make the constraint inactive); \\
|
|
alpar@9
|
1294 \verb|GLP_NL| & make the row non-basic (make the constraint active); \\
|
|
alpar@9
|
1295 \end{tabular}
|
|
alpar@9
|
1296
|
|
alpar@9
|
1297 \newpage
|
|
alpar@9
|
1298
|
|
alpar@9
|
1299 \begin{tabular}{@{}lp{104.2mm}@{}}
|
|
alpar@9
|
1300 \verb|GLP_NU| & make the row non-basic and set it to the upper bound;
|
|
alpar@9
|
1301 if the row is not double-bounded, this status is equivalent to
|
|
alpar@9
|
1302 \verb|GLP_NL| (only in the case of this routine); \\
|
|
alpar@9
|
1303 \verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
|
|
alpar@9
|
1304 routine); \\
|
|
alpar@9
|
1305 \verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
|
|
alpar@9
|
1306 routine). \\
|
|
alpar@9
|
1307 \end{tabular}
|
|
alpar@9
|
1308
|
|
alpar@9
|
1309 \subsection{glp\_set\_col\_stat---set (change) column status}
|
|
alpar@9
|
1310
|
|
alpar@9
|
1311 \subsubsection*{Synopsis}
|
|
alpar@9
|
1312
|
|
alpar@9
|
1313 \begin{verbatim}
|
|
alpar@9
|
1314 void glp_set_col_stat(glp_prob *lp, int j, int stat);
|
|
alpar@9
|
1315 \end{verbatim}
|
|
alpar@9
|
1316
|
|
alpar@9
|
1317 \subsubsection*{Description}
|
|
alpar@9
|
1318
|
|
alpar@9
|
1319 The routine \verb|glp_set_col_stat sets| (changes) the current status
|
|
alpar@9
|
1320 of \verb|j|-th column (structural variable) as specified by the
|
|
alpar@9
|
1321 parameter \verb|stat|:
|
|
alpar@9
|
1322
|
|
alpar@9
|
1323 \begin{tabular}{@{}lp{104.2mm}@{}}
|
|
alpar@9
|
1324 \verb|GLP_BS| & make the column basic; \\
|
|
alpar@9
|
1325 \verb|GLP_NL| & make the column non-basic; \\
|
|
alpar@9
|
1326 \verb|GLP_NU| & make the column non-basic and set it to the upper
|
|
alpar@9
|
1327 bound; if the column is not double-bounded, this status is equivalent
|
|
alpar@9
|
1328 to \verb|GLP_NL| (only in the case of this routine); \\
|
|
alpar@9
|
1329 \verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
|
|
alpar@9
|
1330 routine); \\
|
|
alpar@9
|
1331 \verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
|
|
alpar@9
|
1332 routine).
|
|
alpar@9
|
1333 \end{tabular}
|
|
alpar@9
|
1334
|
|
alpar@9
|
1335 \subsection{glp\_std\_basis---construct standard initial LP basis}
|
|
alpar@9
|
1336
|
|
alpar@9
|
1337 \subsubsection*{Synopsis}
|
|
alpar@9
|
1338
|
|
alpar@9
|
1339 \begin{verbatim}
|
|
alpar@9
|
1340 void glp_std_basis(glp_prob *lp);
|
|
alpar@9
|
1341 \end{verbatim}
|
|
alpar@9
|
1342
|
|
alpar@9
|
1343 \subsubsection*{Description}
|
|
alpar@9
|
1344
|
|
alpar@9
|
1345 The routine \verb|glp_std_basis| constructs the ``standard'' (trivial)
|
|
alpar@9
|
1346 initial LP basis for the specified problem object.
|
|
alpar@9
|
1347
|
|
alpar@9
|
1348 In the ``standard'' LP basis all auxiliary variables (rows) are basic,
|
|
alpar@9
|
1349 and all structural variables (columns) are non-basic (so the
|
|
alpar@9
|
1350 corresponding basis matrix is unity).
|
|
alpar@9
|
1351
|
|
alpar@9
|
1352 \newpage
|
|
alpar@9
|
1353
|
|
alpar@9
|
1354 \subsection{glp\_adv\_basis---construct advanced initial LP basis}
|
|
alpar@9
|
1355
|
|
alpar@9
|
1356 \subsubsection*{Synopsis}
|
|
alpar@9
|
1357
|
|
alpar@9
|
1358 \begin{verbatim}
|
|
alpar@9
|
1359 void glp_adv_basis(glp_prob *lp, int flags);
|
|
alpar@9
|
1360 \end{verbatim}
|
|
alpar@9
|
1361
|
|
alpar@9
|
1362 \subsubsection*{Description}
|
|
alpar@9
|
1363
|
|
alpar@9
|
1364 The routine \verb|glp_adv_basis| constructs an advanced initial LP
|
|
alpar@9
|
1365 basis for the specified problem object.
|
|
alpar@9
|
1366
|
|
alpar@9
|
1367 The parameter \verb|flags| is reserved for use in the future and must
|
|
alpar@9
|
1368 be specified as zero.
|
|
alpar@9
|
1369
|
|
alpar@9
|
1370 In order to construct the advanced initial LP basis the routine does
|
|
alpar@9
|
1371 the following:
|
|
alpar@9
|
1372
|
|
alpar@9
|
1373 1) includes in the basis all non-fixed auxiliary variables;
|
|
alpar@9
|
1374
|
|
alpar@9
|
1375 2) includes in the basis as many non-fixed structural variables as
|
|
alpar@9
|
1376 possible keeping the triangular form of the basis matrix;
|
|
alpar@9
|
1377
|
|
alpar@9
|
1378 3) includes in the basis appropriate (fixed) auxiliary variables to
|
|
alpar@9
|
1379 complete the basis.
|
|
alpar@9
|
1380
|
|
alpar@9
|
1381 As a result the initial LP basis has as few fixed variables as possible
|
|
alpar@9
|
1382 and the corresponding basis matrix is triangular.
|
|
alpar@9
|
1383
|
|
alpar@9
|
1384 \subsection{glp\_cpx\_basis---construct Bixby's initial LP basis}
|
|
alpar@9
|
1385
|
|
alpar@9
|
1386 \subsubsection*{Synopsis}
|
|
alpar@9
|
1387
|
|
alpar@9
|
1388 \begin{verbatim}
|
|
alpar@9
|
1389 void glp_cpx_basis(glp_prob *lp);
|
|
alpar@9
|
1390 \end{verbatim}
|
|
alpar@9
|
1391
|
|
alpar@9
|
1392 \subsubsection*{Description}
|
|
alpar@9
|
1393
|
|
alpar@9
|
1394 The routine \verb|glp_cpx_basis| constructs an initial basis for the
|
|
alpar@9
|
1395 specified problem object with the algorithm proposed by
|
|
alpar@9
|
1396 R.~Bixby.\footnote{Robert E. Bixby, ``Implementing the Simplex Method:
|
|
alpar@9
|
1397 The Initial Basis.'' ORSA Journal on Computing, Vol. 4, No. 3, 1992,
|
|
alpar@9
|
1398 pp. 267-84.}
|
|
alpar@9
|
1399
|
|
alpar@9
|
1400 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
1401
|
|
alpar@9
|
1402 \newpage
|
|
alpar@9
|
1403
|
|
alpar@9
|
1404 \section{Simplex method routines}
|
|
alpar@9
|
1405
|
|
alpar@9
|
1406 The {\it simplex method} is a well known efficient numerical procedure
|
|
alpar@9
|
1407 to solve LP problems.
|
|
alpar@9
|
1408
|
|
alpar@9
|
1409 On each iteration the simplex method transforms the original system of
|
|
alpar@9
|
1410 equaility constraints (1.2) resolving them through different sets of
|
|
alpar@9
|
1411 variables to an equivalent system called {\it the simplex table} (or
|
|
alpar@9
|
1412 sometimes {\it the simplex tableau}), which has the following form:
|
|
alpar@9
|
1413 $$
|
|
alpar@9
|
1414 \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
|
|
alpar@9
|
1415 z&=&d_1(x_N)_1&+&d_2(x_N)_2&+ \dots +&d_n(x_N)_n \\
|
|
alpar@9
|
1416 (x_B)_1&=&\xi_{11}(x_N)_1& +& \xi_{12}(x_N)_2& + \dots +&
|
|
alpar@9
|
1417 \xi_{1n}(x_N)_n \\
|
|
alpar@9
|
1418 (x_B)_2&=& \xi_{21}(x_N)_1& +& \xi_{22}(x_N)_2& + \dots +&
|
|
alpar@9
|
1419 \xi_{2n}(x_N)_n \\
|
|
alpar@9
|
1420 \multicolumn{7}{c}
|
|
alpar@9
|
1421 {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
|
|
alpar@9
|
1422 (x_B)_m&=&\xi_{m1}(x_N)_1& +& \xi_{m2}(x_N)_2& + \dots +&
|
|
alpar@9
|
1423 \xi_{mn}(x_N)_n \\
|
|
alpar@9
|
1424 \end{array} \eqno (2.3)
|
|
alpar@9
|
1425 $$
|
|
alpar@9
|
1426 where: $(x_B)_1, (x_B)_2, \dots, (x_B)_m$ are basic variables;
|
|
alpar@9
|
1427 $(x_N)_1, (x_N)_2, \dots, (x_N)_n$ are non-basic variables;
|
|
alpar@9
|
1428 $d_1, d_2, \dots, d_n$ are reduced costs;
|
|
alpar@9
|
1429 $\xi_{11}, \xi_{12}, \dots, \xi_{mn}$ are coefficients of the
|
|
alpar@9
|
1430 simplex table. (May note that the original LP problem (1.1)---(1.3) also
|
|
alpar@9
|
1431 has the form of a simplex table, where all equalities are resolved
|
|
alpar@9
|
1432 through auxiliary variables.)
|
|
alpar@9
|
1433
|
|
alpar@9
|
1434 From the linear programming theory it is known that if an optimal
|
|
alpar@9
|
1435 solution of the LP problem (1.1)---(1.3) exists, it can always be
|
|
alpar@9
|
1436 written in the form (2.3), where non-basic variables are set on their
|
|
alpar@9
|
1437 bounds while values of the objective function and basic variables are
|
|
alpar@9
|
1438 determined by the corresponding equalities of the simplex table.
|
|
alpar@9
|
1439
|
|
alpar@9
|
1440 A set of values of all basic and non-basic variables determined by the
|
|
alpar@9
|
1441 simplex table is called {\it basic solution}. If all basic variables are
|
|
alpar@9
|
1442 within their bounds, the basic solution is called {\it (primal)
|
|
alpar@9
|
1443 feasible}, otherwise it is called {\it (primal) infeasible}. A feasible
|
|
alpar@9
|
1444 basic solution, which provides a smallest (in case of minimization) or
|
|
alpar@9
|
1445 a largest (in case of maximization) value of the objective function is
|
|
alpar@9
|
1446 called {\it optimal}. Therefore, for solving LP problem the simplex
|
|
alpar@9
|
1447 method tries to find its optimal basic solution.
|
|
alpar@9
|
1448
|
|
alpar@9
|
1449 Primal feasibility of some basic solution may be stated by simple
|
|
alpar@9
|
1450 checking if all basic variables are within their bounds. Basic solution
|
|
alpar@9
|
1451 is optimal if additionally the following optimality conditions are
|
|
alpar@9
|
1452 satisfied for all non-basic variables:
|
|
alpar@9
|
1453 \begin{center}
|
|
alpar@9
|
1454 \begin{tabular}{lcc}
|
|
alpar@9
|
1455 Status of $(x_N)_j$ & Minimization & Maximization \\
|
|
alpar@9
|
1456 \hline
|
|
alpar@9
|
1457 $(x_N)_j$ is free & $d_j = 0$ & $d_j = 0$ \\
|
|
alpar@9
|
1458 $(x_N)_j$ is on its lower bound & $d_j \geq 0$ & $d_j \leq 0$ \\
|
|
alpar@9
|
1459 $(x_N)_j$ is on its upper bound & $d_j \leq 0$ & $d_j \geq 0$ \\
|
|
alpar@9
|
1460 \end{tabular}
|
|
alpar@9
|
1461 \end{center}
|
|
alpar@9
|
1462 In other words, basic solution is optimal if there is no non-basic
|
|
alpar@9
|
1463 variable, which changing in the feasible direction (i.e. increasing if
|
|
alpar@9
|
1464 it is free or on its lower bound, or decreasing if it is free or on its
|
|
alpar@9
|
1465 upper bound) can improve (i.e. decrease in case of minimization or
|
|
alpar@9
|
1466 increase in case of maximization) the objective function.
|
|
alpar@9
|
1467
|
|
alpar@9
|
1468 If all non-basic variables satisfy to the optimality conditions shown
|
|
alpar@9
|
1469 above (independently on whether basic variables are within their bounds
|
|
alpar@9
|
1470 or not), the basic solution is called {\it dual feasible}, otherwise it
|
|
alpar@9
|
1471 is called {\it dual infeasible}.
|
|
alpar@9
|
1472
|
|
alpar@9
|
1473 It may happen that some LP problem has no primal feasible solution due
|
|
alpar@9
|
1474 to incorrect formulation---this means that its constraints conflict
|
|
alpar@9
|
1475 with each other. It also may happen that some LP problem has unbounded
|
|
alpar@9
|
1476 solution again due to incorrect formulation---this means that some
|
|
alpar@9
|
1477 non-basic variable can improve the objective function, i.e. the
|
|
alpar@9
|
1478 optimality conditions are violated, and at the same time this variable
|
|
alpar@9
|
1479 can infinitely change in the feasible direction meeting no resistance
|
|
alpar@9
|
1480 from basic variables. (May note that in the latter case the LP problem
|
|
alpar@9
|
1481 has no dual feasible solution.)
|
|
alpar@9
|
1482
|
|
alpar@9
|
1483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
1484
|
|
alpar@9
|
1485 \subsection{glp\_simplex---solve LP problem with the primal or dual
|
|
alpar@9
|
1486 simplex method}
|
|
alpar@9
|
1487
|
|
alpar@9
|
1488 \subsubsection*{Synopsis}
|
|
alpar@9
|
1489
|
|
alpar@9
|
1490 \begin{verbatim}
|
|
alpar@9
|
1491 int glp_simplex(glp_prob *lp, const glp_smcp *parm);
|
|
alpar@9
|
1492 \end{verbatim}
|
|
alpar@9
|
1493
|
|
alpar@9
|
1494 \subsubsection*{Description}
|
|
alpar@9
|
1495
|
|
alpar@9
|
1496 The routine \verb|glp_simplex| is a driver to the LP solver based on
|
|
alpar@9
|
1497 the simplex method. This routine retrieves problem data from the
|
|
alpar@9
|
1498 specified problem object, calls the solver to solve the problem
|
|
alpar@9
|
1499 instance, and stores results of computations back into the problem
|
|
alpar@9
|
1500 object.
|
|
alpar@9
|
1501
|
|
alpar@9
|
1502 The simplex solver has a set of control parameters. Values of the
|
|
alpar@9
|
1503 control parameters can be passed in the structure \verb|glp_smcp|,
|
|
alpar@9
|
1504 which the parameter \verb|parm| points to. For detailed description of
|
|
alpar@9
|
1505 this structure see paragraph ``Control parameters'' below.
|
|
alpar@9
|
1506 Before specifying some control parameters the application program
|
|
alpar@9
|
1507 should initialize the structure \verb|glp_smcp| by default values of
|
|
alpar@9
|
1508 all control parameters using the routine \verb|glp_init_smcp| (see the
|
|
alpar@9
|
1509 next subsection). This is needed for backward compatibility, because in
|
|
alpar@9
|
1510 the future there may appear new members in the structure
|
|
alpar@9
|
1511 \verb|glp_smcp|.
|
|
alpar@9
|
1512
|
|
alpar@9
|
1513 The parameter \verb|parm| can be specified as \verb|NULL|, in which
|
|
alpar@9
|
1514 case the solver uses default settings.
|
|
alpar@9
|
1515
|
|
alpar@9
|
1516 \subsubsection*{Returns}
|
|
alpar@9
|
1517
|
|
alpar@9
|
1518 \def\arraystretch{1}
|
|
alpar@9
|
1519
|
|
alpar@9
|
1520 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
|
|
alpar@9
|
1521 0 & The LP problem instance has been successfully solved. (This code
|
|
alpar@9
|
1522 does {\it not} necessarily mean that the solver has found optimal
|
|
alpar@9
|
1523 solution. It only means that the solution process was successful.) \\
|
|
alpar@9
|
1524 \verb|GLP_EBADB| & Unable to start the search, because the initial basis
|
|
alpar@9
|
1525 specified in the problem object is invalid---the number of basic
|
|
alpar@9
|
1526 (auxiliary and structural) variables is not the same as the number of
|
|
alpar@9
|
1527 rows in the problem object.\\
|
|
alpar@9
|
1528 \verb|GLP_ESING| & Unable to start the search, because the basis matrix
|
|
alpar@9
|
1529 corresponding to the initial basis is singular within the working
|
|
alpar@9
|
1530 precision.\\
|
|
alpar@9
|
1531 \verb|GLP_ECOND| & Unable to start the search, because the basis matrix
|
|
alpar@9
|
1532 corresponding to the initial basis is ill-conditioned, i.e. its
|
|
alpar@9
|
1533 condition number is too large.\\
|
|
alpar@9
|
1534 \verb|GLP_EBOUND| & Unable to start the search, because some
|
|
alpar@9
|
1535 double-bounded (auxiliary or structural) variables have incorrect
|
|
alpar@9
|
1536 bounds.\\
|
|
alpar@9
|
1537 \verb|GLP_EFAIL| & The search was prematurely terminated due to the
|
|
alpar@9
|
1538 solver failure.\\
|
|
alpar@9
|
1539 \verb|GLP_EOBJLL| & The search was prematurely terminated, because the
|
|
alpar@9
|
1540 objective function being maximized has reached its lower limit and
|
|
alpar@9
|
1541 continues decreasing (the dual simplex only).\\
|
|
alpar@9
|
1542 \verb|GLP_EOBJUL| & The search was prematurely terminated, because the
|
|
alpar@9
|
1543 objective function being minimized has reached its upper limit and
|
|
alpar@9
|
1544 continues increasing (the dual simplex only).\\
|
|
alpar@9
|
1545 \verb|GLP_EITLIM| & The search was prematurely terminated, because the
|
|
alpar@9
|
1546 simplex iteration limit has been exceeded.\\
|
|
alpar@9
|
1547 \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
|
|
alpar@9
|
1548 time limit has been exceeded.\\
|
|
alpar@9
|
1549 \verb|GLP_ENOPFS| & The LP problem instance has no primal feasible
|
|
alpar@9
|
1550 solution (only if the LP presolver is used).\\
|
|
alpar@9
|
1551 \verb|GLP_ENODFS| & The LP problem instance has no dual feasible
|
|
alpar@9
|
1552 solution (only if the LP presolver is used).\\
|
|
alpar@9
|
1553 \end{tabular}
|
|
alpar@9
|
1554
|
|
alpar@9
|
1555 \subsubsection*{Built-in LP presolver}
|
|
alpar@9
|
1556
|
|
alpar@9
|
1557 The simplex solver has {\it built-in LP presolver}. It is a subprogram
|
|
alpar@9
|
1558 that transforms the original LP problem specified in the problem object
|
|
alpar@9
|
1559 to an equivalent LP problem, which may be easier for solving with the
|
|
alpar@9
|
1560 simplex method than the original one. This is attained mainly due to
|
|
alpar@9
|
1561 reducing the problem size and improving its numeric properties (for
|
|
alpar@9
|
1562 example, by removing some inactive constraints or by fixing some
|
|
alpar@9
|
1563 non-basic variables). Once the transformed LP problem has been solved,
|
|
alpar@9
|
1564 the presolver transforms its basic solution back to the corresponding
|
|
alpar@9
|
1565 basic solution of the original problem.
|
|
alpar@9
|
1566
|
|
alpar@9
|
1567 Presolving is an optional feature of the routine \verb|glp_simplex|,
|
|
alpar@9
|
1568 and by default it is disabled. In order to enable the LP presolver the
|
|
alpar@9
|
1569 control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
|
|
alpar@9
|
1570 paragraph ``Control parameters'' below). Presolving may be used when
|
|
alpar@9
|
1571 the problem instance is solved for the first time. However, on
|
|
alpar@9
|
1572 performing re-optimization the presolver should be disabled.
|
|
alpar@9
|
1573
|
|
alpar@9
|
1574 The presolving procedure is transparent to the API user in the sense
|
|
alpar@9
|
1575 that all necessary processing is performed internally, and a basic
|
|
alpar@9
|
1576 solution of the original problem recovered by the presolver is the same
|
|
alpar@9
|
1577 as if it were computed directly, i.e. without presolving.
|
|
alpar@9
|
1578
|
|
alpar@9
|
1579 Note that the presolver is able to recover only optimal solutions. If
|
|
alpar@9
|
1580 a computed solution is infeasible or non-optimal, the corresponding
|
|
alpar@9
|
1581 solution of the original problem cannot be recovered and therefore
|
|
alpar@9
|
1582 remains undefined. If you need to know a basic solution even if it is
|
|
alpar@9
|
1583 infeasible or non-optimal, the presolver should be disabled.
|
|
alpar@9
|
1584
|
|
alpar@9
|
1585 \subsubsection*{Terminal output}
|
|
alpar@9
|
1586
|
|
alpar@9
|
1587 Solving large problem instances may take a long time, so the solver
|
|
alpar@9
|
1588 reports some information about the current basic solution, which is sent
|
|
alpar@9
|
1589 to the terminal. This information has the following format:
|
|
alpar@9
|
1590
|
|
alpar@9
|
1591 \begin{verbatim}
|
|
alpar@9
|
1592 nnn: obj = xxx infeas = yyy (ddd)
|
|
alpar@9
|
1593 \end{verbatim}
|
|
alpar@9
|
1594
|
|
alpar@9
|
1595 \noindent
|
|
alpar@9
|
1596 where: `\verb|nnn|' is the iteration number, `\verb|xxx|' is the
|
|
alpar@9
|
1597 current value of the objective function (it is is unscaled and has
|
|
alpar@9
|
1598 correct sign); `\verb|yyy|' is the current sum of primal or dual
|
|
alpar@9
|
1599 infeasibilities (it is scaled and therefore may be used only for visual
|
|
alpar@9
|
1600 estimating), `\verb|ddd|' is the current number of fixed basic
|
|
alpar@9
|
1601 variables.
|
|
alpar@9
|
1602
|
|
alpar@9
|
1603 The symbol preceding the iteration number indicates which phase of the
|
|
alpar@9
|
1604 simplex method is in effect:
|
|
alpar@9
|
1605
|
|
alpar@9
|
1606 {\it Blank} means that the solver is searching for primal feasible
|
|
alpar@9
|
1607 solution using the primal simplex or for dual feasible solution using
|
|
alpar@9
|
1608 the dual simplex;
|
|
alpar@9
|
1609
|
|
alpar@9
|
1610 {\it Asterisk} (\verb|*|) means that the solver is searching for
|
|
alpar@9
|
1611 optimal solution using the primal simplex;
|
|
alpar@9
|
1612
|
|
alpar@9
|
1613 {\it Vertical dash} (\verb/|/) means that the solver is searching for
|
|
alpar@9
|
1614 optimal solution using the dual simplex.
|
|
alpar@9
|
1615
|
|
alpar@9
|
1616 \subsubsection*{Control parameters}
|
|
alpar@9
|
1617
|
|
alpar@9
|
1618 This paragraph describes all control parameters currently used in the
|
|
alpar@9
|
1619 simplex solver. Symbolic names of control parameters are names of
|
|
alpar@9
|
1620 corresponding members in the structure \verb|glp_smcp|.
|
|
alpar@9
|
1621
|
|
alpar@9
|
1622 \medskip
|
|
alpar@9
|
1623
|
|
alpar@9
|
1624 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1625 \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
|
|
alpar@9
|
1626 \\
|
|
alpar@9
|
1627 &Message level for terminal output:\\
|
|
alpar@9
|
1628 &\verb|GLP_MSG_OFF|---no output;\\
|
|
alpar@9
|
1629 &\verb|GLP_MSG_ERR|---error and warning messages only;\\
|
|
alpar@9
|
1630 &\verb|GLP_MSG_ON |---normal output;\\
|
|
alpar@9
|
1631 &\verb|GLP_MSG_ALL|---full output (including informational messages).
|
|
alpar@9
|
1632 \\
|
|
alpar@9
|
1633 \end{tabular}
|
|
alpar@9
|
1634
|
|
alpar@9
|
1635 \medskip
|
|
alpar@9
|
1636
|
|
alpar@9
|
1637 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1638 \multicolumn{2}{@{}l}{{\tt int meth} (default: {\tt GLP\_PRIMAL})}
|
|
alpar@9
|
1639 \\
|
|
alpar@9
|
1640 &Simplex method option:\\
|
|
alpar@9
|
1641 &\verb|GLP_PRIMAL|---use two-phase primal simplex;\\
|
|
alpar@9
|
1642 &\verb|GLP_DUAL |---use two-phase dual simplex;\\
|
|
alpar@9
|
1643 &\verb|GLP_DUALP |---use two-phase dual simplex, and if it fails,
|
|
alpar@9
|
1644 switch to the\\
|
|
alpar@9
|
1645 &\verb| |$\:$ primal simplex.\\
|
|
alpar@9
|
1646 \end{tabular}
|
|
alpar@9
|
1647
|
|
alpar@9
|
1648 \medskip
|
|
alpar@9
|
1649
|
|
alpar@9
|
1650 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1651 \multicolumn{2}{@{}l}{{\tt int pricing} (default: {\tt GLP\_PT\_PSE})}
|
|
alpar@9
|
1652 \\
|
|
alpar@9
|
1653 &Pricing technique:\\
|
|
alpar@9
|
1654 &\verb|GLP_PT_STD|---standard (textbook);\\
|
|
alpar@9
|
1655 &\verb|GLP_PT_PSE|---projected steepest edge.\\
|
|
alpar@9
|
1656 \end{tabular}
|
|
alpar@9
|
1657
|
|
alpar@9
|
1658 \medskip
|
|
alpar@9
|
1659
|
|
alpar@9
|
1660 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1661 \multicolumn{2}{@{}l}{{\tt int r\_test} (default: {\tt GLP\_RT\_HAR})}
|
|
alpar@9
|
1662 \\
|
|
alpar@9
|
1663 &Ratio test technique:\\
|
|
alpar@9
|
1664 &\verb|GLP_RT_STD|---standard (textbook);\\
|
|
alpar@9
|
1665 &\verb|GLP_RT_HAR|---Harris' two-pass ratio test.\\
|
|
alpar@9
|
1666 \end{tabular}
|
|
alpar@9
|
1667
|
|
alpar@9
|
1668 \medskip
|
|
alpar@9
|
1669
|
|
alpar@9
|
1670 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1671 \multicolumn{2}{@{}l}{{\tt double tol\_bnd} (default: {\tt 1e-7})}
|
|
alpar@9
|
1672 \\
|
|
alpar@9
|
1673 &Tolerance used to check if the basic solution is primal feasible.
|
|
alpar@9
|
1674 (Do not change this parameter without detailed understanding its
|
|
alpar@9
|
1675 purpose.)\\
|
|
alpar@9
|
1676 \end{tabular}
|
|
alpar@9
|
1677
|
|
alpar@9
|
1678 \medskip
|
|
alpar@9
|
1679
|
|
alpar@9
|
1680 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1681 \multicolumn{2}{@{}l}{{\tt double tol\_dj} (default: {\tt 1e-7})}
|
|
alpar@9
|
1682 \\
|
|
alpar@9
|
1683 &Tolerance used to check if the basic solution is dual feasible.
|
|
alpar@9
|
1684 (Do not change this parameter without detailed understanding its
|
|
alpar@9
|
1685 purpose.)\\
|
|
alpar@9
|
1686 \end{tabular}
|
|
alpar@9
|
1687
|
|
alpar@9
|
1688 \medskip
|
|
alpar@9
|
1689
|
|
alpar@9
|
1690 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1691 \multicolumn{2}{@{}l}{{\tt double tol\_piv} (default: {\tt 1e-10})}
|
|
alpar@9
|
1692 \\
|
|
alpar@9
|
1693 &Tolerance used to choose eligble pivotal elements of the simplex table.
|
|
alpar@9
|
1694 (Do not change this parameter without detailed understanding its
|
|
alpar@9
|
1695 purpose.)\\
|
|
alpar@9
|
1696 \end{tabular}
|
|
alpar@9
|
1697
|
|
alpar@9
|
1698 \medskip
|
|
alpar@9
|
1699
|
|
alpar@9
|
1700 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1701 \multicolumn{2}{@{}l}{{\tt double obj\_ll} (default: {\tt -DBL\_MAX})}
|
|
alpar@9
|
1702 \\
|
|
alpar@9
|
1703 &Lower limit of the objective function. If the objective function
|
|
alpar@9
|
1704 reaches this limit and continues decreasing, the solver terminates the
|
|
alpar@9
|
1705 search. (Used in the dual simplex only.)\\
|
|
alpar@9
|
1706 \end{tabular}
|
|
alpar@9
|
1707
|
|
alpar@9
|
1708 \medskip
|
|
alpar@9
|
1709
|
|
alpar@9
|
1710 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1711 \multicolumn{2}{@{}l}{{\tt double obj\_ul} (default: {\tt +DBL\_MAX})}
|
|
alpar@9
|
1712 \\
|
|
alpar@9
|
1713 &Upper limit of the objective function. If the objective function
|
|
alpar@9
|
1714 reaches this limit and continues increasing, the solver terminates the
|
|
alpar@9
|
1715 search. (Used in the dual simplex only.)\\
|
|
alpar@9
|
1716 \end{tabular}
|
|
alpar@9
|
1717
|
|
alpar@9
|
1718 \medskip
|
|
alpar@9
|
1719
|
|
alpar@9
|
1720 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1721 \multicolumn{2}{@{}l}{{\tt int it\_lim} (default: {\tt INT\_MAX})}
|
|
alpar@9
|
1722 \\
|
|
alpar@9
|
1723 &Simplex iteration limit.\\
|
|
alpar@9
|
1724 \end{tabular}
|
|
alpar@9
|
1725
|
|
alpar@9
|
1726 \medskip
|
|
alpar@9
|
1727
|
|
alpar@9
|
1728 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1729 \multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}
|
|
alpar@9
|
1730 \\
|
|
alpar@9
|
1731 &Searching time limit, in milliseconds.\\
|
|
alpar@9
|
1732 \end{tabular}
|
|
alpar@9
|
1733
|
|
alpar@9
|
1734 \medskip
|
|
alpar@9
|
1735
|
|
alpar@9
|
1736 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1737 \multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 500})}
|
|
alpar@9
|
1738 \\
|
|
alpar@9
|
1739 &Output frequency, in iterations. This parameter specifies how
|
|
alpar@9
|
1740 frequently the solver sends information about the solution process to
|
|
alpar@9
|
1741 the terminal.\\
|
|
alpar@9
|
1742 \end{tabular}
|
|
alpar@9
|
1743
|
|
alpar@9
|
1744 \medskip
|
|
alpar@9
|
1745
|
|
alpar@9
|
1746 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1747 \multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 0})}
|
|
alpar@9
|
1748 \\
|
|
alpar@9
|
1749 &Output delay, in milliseconds. This parameter specifies how long the
|
|
alpar@9
|
1750 solver should delay sending information about the solution process to
|
|
alpar@9
|
1751 the terminal.\\
|
|
alpar@9
|
1752 \end{tabular}
|
|
alpar@9
|
1753
|
|
alpar@9
|
1754 \medskip
|
|
alpar@9
|
1755
|
|
alpar@9
|
1756 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
1757 \multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}
|
|
alpar@9
|
1758 \\
|
|
alpar@9
|
1759 &LP presolver option:\\
|
|
alpar@9
|
1760 &\verb|GLP_ON |---enable using the LP presolver;\\
|
|
alpar@9
|
1761 &\verb|GLP_OFF|---disable using the LP presolver.\\
|
|
alpar@9
|
1762 \end{tabular}
|
|
alpar@9
|
1763
|
|
alpar@9
|
1764 \subsubsection*{Example 1}
|
|
alpar@9
|
1765
|
|
alpar@9
|
1766 The following main program reads LP problem instance in fixed MPS
|
|
alpar@9
|
1767 format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
|
|
alpar@9
|
1768 format can be found in the Netlib LP collection; see
|
|
alpar@9
|
1769 {\tt ftp://ftp.netlib.org/lp/data/}.} constructs an advanced initial
|
|
alpar@9
|
1770 basis, solves the instance with the primal simplex method (by default),
|
|
alpar@9
|
1771 and writes the solution to file \verb|25fv47.txt|.
|
|
alpar@9
|
1772
|
|
alpar@9
|
1773 \newpage
|
|
alpar@9
|
1774
|
|
alpar@9
|
1775 \begin{footnotesize}
|
|
alpar@9
|
1776 \begin{verbatim}
|
|
alpar@9
|
1777 /* spxsamp1.c */
|
|
alpar@9
|
1778
|
|
alpar@9
|
1779 #include <stdio.h>
|
|
alpar@9
|
1780 #include <stdlib.h>
|
|
alpar@9
|
1781 #include <glpk.h>
|
|
alpar@9
|
1782
|
|
alpar@9
|
1783 int main(void)
|
|
alpar@9
|
1784 { glp_prob *P;
|
|
alpar@9
|
1785 P = glp_create_prob();
|
|
alpar@9
|
1786 glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
|
|
alpar@9
|
1787 glp_adv_basis(P, 0);
|
|
alpar@9
|
1788 glp_simplex(P, NULL);
|
|
alpar@9
|
1789 glp_print_sol(P, "25fv47.txt");
|
|
alpar@9
|
1790 glp_delete_prob(P);
|
|
alpar@9
|
1791 return 0;
|
|
alpar@9
|
1792 }
|
|
alpar@9
|
1793
|
|
alpar@9
|
1794 /* eof */
|
|
alpar@9
|
1795 \end{verbatim}
|
|
alpar@9
|
1796 \end{footnotesize}
|
|
alpar@9
|
1797
|
|
alpar@9
|
1798 \noindent
|
|
alpar@9
|
1799 Below here is shown the terminal output from this example program.
|
|
alpar@9
|
1800
|
|
alpar@9
|
1801 \begin{footnotesize}
|
|
alpar@9
|
1802 \begin{verbatim}
|
|
alpar@9
|
1803 Reading problem data from `25fv47.mps'...
|
|
alpar@9
|
1804 Problem: 25FV47
|
|
alpar@9
|
1805 Objective: R0000
|
|
alpar@9
|
1806 822 rows, 1571 columns, 11127 non-zeros
|
|
alpar@9
|
1807 6919 records were read
|
|
alpar@9
|
1808 Crashing...
|
|
alpar@9
|
1809 Size of triangular part = 799
|
|
alpar@9
|
1810 0: obj = 1.627307307e+04 infeas = 5.194e+04 (23)
|
|
alpar@9
|
1811 200: obj = 1.474901610e+04 infeas = 1.233e+04 (19)
|
|
alpar@9
|
1812 400: obj = 1.343909995e+04 infeas = 3.648e+03 (13)
|
|
alpar@9
|
1813 600: obj = 1.756052217e+04 infeas = 4.179e+02 (7)
|
|
alpar@9
|
1814 * 775: obj = 1.789251591e+04 infeas = 4.982e-14 (1)
|
|
alpar@9
|
1815 * 800: obj = 1.663354510e+04 infeas = 2.857e-14 (1)
|
|
alpar@9
|
1816 * 1000: obj = 1.024935068e+04 infeas = 1.958e-12 (1)
|
|
alpar@9
|
1817 * 1200: obj = 7.860174791e+03 infeas = 2.810e-29 (1)
|
|
alpar@9
|
1818 * 1400: obj = 6.642378184e+03 infeas = 2.036e-16 (1)
|
|
alpar@9
|
1819 * 1600: obj = 6.037014568e+03 infeas = 0.000e+00 (1)
|
|
alpar@9
|
1820 * 1800: obj = 5.662171307e+03 infeas = 6.447e-15 (1)
|
|
alpar@9
|
1821 * 2000: obj = 5.528146165e+03 infeas = 9.764e-13 (1)
|
|
alpar@9
|
1822 * 2125: obj = 5.501845888e+03 infeas = 0.000e+00 (1)
|
|
alpar@9
|
1823 OPTIMAL SOLUTION FOUND
|
|
alpar@9
|
1824 Writing basic solution to `25fv47.txt'...
|
|
alpar@9
|
1825 \end{verbatim}
|
|
alpar@9
|
1826 \end{footnotesize}
|
|
alpar@9
|
1827
|
|
alpar@9
|
1828 \newpage
|
|
alpar@9
|
1829
|
|
alpar@9
|
1830 \subsubsection*{Example 2}
|
|
alpar@9
|
1831
|
|
alpar@9
|
1832 The following main program solves the same LP problem instance as in
|
|
alpar@9
|
1833 Example 1 above, however, it uses the dual simplex method, which starts
|
|
alpar@9
|
1834 from the standard initial basis.
|
|
alpar@9
|
1835
|
|
alpar@9
|
1836 \begin{footnotesize}
|
|
alpar@9
|
1837 \begin{verbatim}
|
|
alpar@9
|
1838 /* spxsamp2.c */
|
|
alpar@9
|
1839
|
|
alpar@9
|
1840 #include <stdio.h>
|
|
alpar@9
|
1841 #include <stdlib.h>
|
|
alpar@9
|
1842 #include <glpk.h>
|
|
alpar@9
|
1843
|
|
alpar@9
|
1844 int main(void)
|
|
alpar@9
|
1845 { glp_prob *P;
|
|
alpar@9
|
1846 glp_smcp parm;
|
|
alpar@9
|
1847 P = glp_create_prob();
|
|
alpar@9
|
1848 glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
|
|
alpar@9
|
1849 glp_init_smcp(&parm);
|
|
alpar@9
|
1850 parm.meth = GLP_DUAL;
|
|
alpar@9
|
1851 glp_simplex(P, &parm);
|
|
alpar@9
|
1852 glp_print_sol(P, "25fv47.txt");
|
|
alpar@9
|
1853 glp_delete_prob(P);
|
|
alpar@9
|
1854 return 0;
|
|
alpar@9
|
1855 }
|
|
alpar@9
|
1856
|
|
alpar@9
|
1857 /* eof */
|
|
alpar@9
|
1858 \end{verbatim}
|
|
alpar@9
|
1859 \end{footnotesize}
|
|
alpar@9
|
1860
|
|
alpar@9
|
1861 \noindent
|
|
alpar@9
|
1862 Below here is shown the terminal output from this example program.
|
|
alpar@9
|
1863
|
|
alpar@9
|
1864 \begin{footnotesize}
|
|
alpar@9
|
1865 \begin{verbatim}
|
|
alpar@9
|
1866 Reading problem data from `25fv47.mps'...
|
|
alpar@9
|
1867 Problem: 25FV47
|
|
alpar@9
|
1868 Objective: R0000
|
|
alpar@9
|
1869 822 rows, 1571 columns, 11127 non-zeros
|
|
alpar@9
|
1870 6919 records were read
|
|
alpar@9
|
1871 0: infeas = 1.223e+03 (516)
|
|
alpar@9
|
1872 200: infeas = 7.000e+00 (471)
|
|
alpar@9
|
1873 240: infeas = 1.106e-14 (461)
|
|
alpar@9
|
1874 | 400: obj = -5.394267152e+03 infeas = 5.571e-16 (391)
|
|
alpar@9
|
1875 | 600: obj = -4.586395752e+03 infeas = 1.389e-15 (340)
|
|
alpar@9
|
1876 | 800: obj = -4.158268146e+03 infeas = 1.640e-15 (264)
|
|
alpar@9
|
1877 | 1000: obj = -3.725320045e+03 infeas = 5.181e-15 (245)
|
|
alpar@9
|
1878 | 1200: obj = -3.104802163e+03 infeas = 1.019e-14 (210)
|
|
alpar@9
|
1879 | 1400: obj = -2.584190499e+03 infeas = 8.865e-15 (178)
|
|
alpar@9
|
1880 | 1600: obj = -2.073852927e+03 infeas = 7.867e-15 (142)
|
|
alpar@9
|
1881 | 1800: obj = -1.164037407e+03 infeas = 8.792e-15 (109)
|
|
alpar@9
|
1882 | 2000: obj = -4.370590250e+02 infeas = 2.591e-14 (85)
|
|
alpar@9
|
1883 | 2200: obj = 1.068240144e+03 infeas = 1.025e-13 (70)
|
|
alpar@9
|
1884 | 2400: obj = 1.607481126e+03 infeas = 3.272e-14 (67)
|
|
alpar@9
|
1885 | 2600: obj = 3.038230551e+03 infeas = 4.850e-14 (52)
|
|
alpar@9
|
1886 | 2800: obj = 4.316238187e+03 infeas = 2.622e-14 (36)
|
|
alpar@9
|
1887 | 3000: obj = 5.443842629e+03 infeas = 3.976e-15 (11)
|
|
alpar@9
|
1888 | 3060: obj = 5.501845888e+03 infeas = 8.806e-15 (2)
|
|
alpar@9
|
1889 OPTIMAL SOLUTION FOUND
|
|
alpar@9
|
1890 Writing basic solution to `25fv47.txt'...
|
|
alpar@9
|
1891 \end{verbatim}
|
|
alpar@9
|
1892 \end{footnotesize}
|
|
alpar@9
|
1893
|
|
alpar@9
|
1894 \subsection{glp\_exact---solve LP problem in exact arithmetic}
|
|
alpar@9
|
1895
|
|
alpar@9
|
1896 \subsubsection*{Synopsis}
|
|
alpar@9
|
1897
|
|
alpar@9
|
1898 \begin{verbatim}
|
|
alpar@9
|
1899 int glp_exact(glp_prob *lp, const glp_smcp *parm);
|
|
alpar@9
|
1900 \end{verbatim}
|
|
alpar@9
|
1901
|
|
alpar@9
|
1902 \subsubsection*{Description}
|
|
alpar@9
|
1903
|
|
alpar@9
|
1904 The routine \verb|glp_exact| is a tentative implementation of the
|
|
alpar@9
|
1905 primal two-phase simplex method based on exact (rational) arithmetic.
|
|
alpar@9
|
1906 It is similar to the routine \verb|glp_simplex|, however, for all
|
|
alpar@9
|
1907 internal computations it uses arithmetic of rational numbers, which is
|
|
alpar@9
|
1908 exact in mathematical sense, i.e. free of round-off errors unlike
|
|
alpar@9
|
1909 floating-point arithmetic.
|
|
alpar@9
|
1910
|
|
alpar@9
|
1911 Note that the routine \verb|glp_exact| uses only two control parameters
|
|
alpar@9
|
1912 passed in the structure \verb|glp_smcp|, namely, \verb|it_lim| and
|
|
alpar@9
|
1913 \verb|tm_lim|.
|
|
alpar@9
|
1914
|
|
alpar@9
|
1915 \subsubsection*{Returns}
|
|
alpar@9
|
1916
|
|
alpar@9
|
1917 \def\arraystretch{1}
|
|
alpar@9
|
1918
|
|
alpar@9
|
1919 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
|
|
alpar@9
|
1920 0 & The LP problem instance has been successfully solved. (This code
|
|
alpar@9
|
1921 does {\it not} necessarily mean that the solver has found optimal
|
|
alpar@9
|
1922 solution. It only means that the solution process was successful.) \\
|
|
alpar@9
|
1923 \verb|GLP_EBADB| & Unable to start the search, because the initial basis
|
|
alpar@9
|
1924 specified in the problem object is invalid---the number of basic
|
|
alpar@9
|
1925 (auxiliary and structural) variables is not the same as the number of
|
|
alpar@9
|
1926 rows in the problem object.\\
|
|
alpar@9
|
1927 \verb|GLP_ESING| & Unable to start the search, because the basis matrix
|
|
alpar@9
|
1928 corresponding to the initial basis is exactly singular.\\
|
|
alpar@9
|
1929 \verb|GLP_EBOUND| & Unable to start the search, because some
|
|
alpar@9
|
1930 double-bounded (auxiliary or structural) variables have incorrect
|
|
alpar@9
|
1931 bounds.\\
|
|
alpar@9
|
1932 \verb|GLP_EFAIL| & The problem instance has no rows/columns.\\
|
|
alpar@9
|
1933 \verb|GLP_EITLIM| & The search was prematurely terminated, because the
|
|
alpar@9
|
1934 simplex iteration limit has been exceeded.\\
|
|
alpar@9
|
1935 \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
|
|
alpar@9
|
1936 time limit has been exceeded.\\
|
|
alpar@9
|
1937 \end{tabular}
|
|
alpar@9
|
1938
|
|
alpar@9
|
1939 \subsubsection*{Comments}
|
|
alpar@9
|
1940
|
|
alpar@9
|
1941 Computations in exact arithmetic are very time consuming, so solving
|
|
alpar@9
|
1942 LP problem with the routine \verb|glp_exact| from the very beginning is
|
|
alpar@9
|
1943 not a good idea. It is much better at first to find an optimal basis
|
|
alpar@9
|
1944 with the routine \verb|glp_simplex| and only then to call
|
|
alpar@9
|
1945 \verb|glp_exact|, in which case only a few simplex iterations need to
|
|
alpar@9
|
1946 be performed in exact arithmetic.
|
|
alpar@9
|
1947
|
|
alpar@9
|
1948 \subsection{glp\_init\_smcp---initialize simplex solver control
|
|
alpar@9
|
1949 parameters}
|
|
alpar@9
|
1950
|
|
alpar@9
|
1951 \subsubsection*{Synopsis}
|
|
alpar@9
|
1952
|
|
alpar@9
|
1953 \begin{verbatim}
|
|
alpar@9
|
1954 int glp_init_smcp(glp_smcp *parm);
|
|
alpar@9
|
1955 \end{verbatim}
|
|
alpar@9
|
1956
|
|
alpar@9
|
1957 \subsubsection*{Description}
|
|
alpar@9
|
1958
|
|
alpar@9
|
1959 The routine \verb|glp_init_smcp| initializes control parameters, which
|
|
alpar@9
|
1960 are used by the simplex solver, with default values.
|
|
alpar@9
|
1961
|
|
alpar@9
|
1962 Default values of the control parameters are stored in a \verb|glp_smcp|
|
|
alpar@9
|
1963 structure, which the parameter \verb|parm| points to.
|
|
alpar@9
|
1964
|
|
alpar@9
|
1965 \subsection{glp\_get\_status---determine generic status of basic
|
|
alpar@9
|
1966 solution}
|
|
alpar@9
|
1967
|
|
alpar@9
|
1968 \subsubsection*{Synopsis}
|
|
alpar@9
|
1969
|
|
alpar@9
|
1970 \begin{verbatim}
|
|
alpar@9
|
1971 int glp_get_status(glp_prob *lp);
|
|
alpar@9
|
1972 \end{verbatim}
|
|
alpar@9
|
1973
|
|
alpar@9
|
1974 \subsubsection*{Returns}
|
|
alpar@9
|
1975
|
|
alpar@9
|
1976 The routine \verb|glp_get_status| reports the generic status of the
|
|
alpar@9
|
1977 current basic solution for the specified problem object as follows:
|
|
alpar@9
|
1978
|
|
alpar@9
|
1979 \begin{tabular}{@{}ll}
|
|
alpar@9
|
1980 \verb|GLP_OPT| & solution is optimal; \\
|
|
alpar@9
|
1981 \verb|GLP_FEAS| & solution is feasible; \\
|
|
alpar@9
|
1982 \verb|GLP_INFEAS| & solution is infeasible; \\
|
|
alpar@9
|
1983 \verb|GLP_NOFEAS| & problem has no feasible solution; \\
|
|
alpar@9
|
1984 \verb|GLP_UNBND| & problem has unbounded solution; \\
|
|
alpar@9
|
1985 \verb|GLP_UNDEF| & solution is undefined. \\
|
|
alpar@9
|
1986 \end{tabular}
|
|
alpar@9
|
1987
|
|
alpar@9
|
1988 More detailed information about the status of basic solution can be
|
|
alpar@9
|
1989 retrieved with the routines \verb|glp_get_prim_stat| and
|
|
alpar@9
|
1990 \verb|glp_get_dual_stat|.
|
|
alpar@9
|
1991
|
|
alpar@9
|
1992 \newpage
|
|
alpar@9
|
1993
|
|
alpar@9
|
1994 \subsection{glp\_get\_prim\_stat---retrieve status of primal basic
|
|
alpar@9
|
1995 solution}
|
|
alpar@9
|
1996
|
|
alpar@9
|
1997 \subsubsection*{Synopsis}
|
|
alpar@9
|
1998
|
|
alpar@9
|
1999 \begin{verbatim}
|
|
alpar@9
|
2000 int glp_get_prim_stat(glp_prob *lp);
|
|
alpar@9
|
2001 \end{verbatim}
|
|
alpar@9
|
2002
|
|
alpar@9
|
2003 \subsubsection*{Returns}
|
|
alpar@9
|
2004
|
|
alpar@9
|
2005 The routine \verb|glp_get_prim_stat| reports the status of the primal
|
|
alpar@9
|
2006 basic solution for the specified problem object as follows:
|
|
alpar@9
|
2007
|
|
alpar@9
|
2008 \begin{tabular}{@{}ll}
|
|
alpar@9
|
2009 \verb|GLP_UNDEF| & primal solution is undefined; \\
|
|
alpar@9
|
2010 \verb|GLP_FEAS| & primal solution is feasible; \\
|
|
alpar@9
|
2011 \verb|GLP_INFEAS| & primal solution is infeasible; \\
|
|
alpar@9
|
2012 \verb|GLP_NOFEAS| & no primal feasible solution exists. \\
|
|
alpar@9
|
2013 \end{tabular}
|
|
alpar@9
|
2014
|
|
alpar@9
|
2015 \subsection{glp\_get\_dual\_stat---retrieve status of dual basic
|
|
alpar@9
|
2016 solution}
|
|
alpar@9
|
2017
|
|
alpar@9
|
2018 \subsubsection*{Synopsis}
|
|
alpar@9
|
2019
|
|
alpar@9
|
2020 \begin{verbatim}
|
|
alpar@9
|
2021 int glp_get_dual_stat(glp_prob *lp);
|
|
alpar@9
|
2022 \end{verbatim}
|
|
alpar@9
|
2023
|
|
alpar@9
|
2024 \subsubsection*{Returns}
|
|
alpar@9
|
2025
|
|
alpar@9
|
2026 The routine \verb|glp_get_dual_stat| reports the status of the dual
|
|
alpar@9
|
2027 basic solution for the specified problem object as follows:
|
|
alpar@9
|
2028
|
|
alpar@9
|
2029 \begin{tabular}{@{}ll}
|
|
alpar@9
|
2030 \verb|GLP_UNDEF| & dual solution is undefined; \\
|
|
alpar@9
|
2031 \verb|GLP_FEAS| & dual solution is feasible; \\
|
|
alpar@9
|
2032 \verb|GLP_INFEAS| & dual solution is infeasible; \\
|
|
alpar@9
|
2033 \verb|GLP_NOFEAS| & no dual feasible solution exists. \\
|
|
alpar@9
|
2034 \end{tabular}
|
|
alpar@9
|
2035
|
|
alpar@9
|
2036 \subsection{glp\_get\_obj\_val---retrieve objective value}
|
|
alpar@9
|
2037
|
|
alpar@9
|
2038 \subsubsection*{Synopsis}
|
|
alpar@9
|
2039
|
|
alpar@9
|
2040 \begin{verbatim}
|
|
alpar@9
|
2041 double glp_get_obj_val(glp_prob *lp);
|
|
alpar@9
|
2042 \end{verbatim}
|
|
alpar@9
|
2043
|
|
alpar@9
|
2044 \subsubsection*{Returns}
|
|
alpar@9
|
2045
|
|
alpar@9
|
2046 The routine \verb|glp_get_obj_val| returns current value of the
|
|
alpar@9
|
2047 objective function.
|
|
alpar@9
|
2048
|
|
alpar@9
|
2049 \subsection{glp\_get\_row\_stat---retrieve row status}
|
|
alpar@9
|
2050
|
|
alpar@9
|
2051 \subsubsection*{Synopsis}
|
|
alpar@9
|
2052
|
|
alpar@9
|
2053 \begin{verbatim}
|
|
alpar@9
|
2054 int glp_get_row_stat(glp_prob *lp, int i);
|
|
alpar@9
|
2055 \end{verbatim}
|
|
alpar@9
|
2056
|
|
alpar@9
|
2057 \subsubsection*{Returns}
|
|
alpar@9
|
2058
|
|
alpar@9
|
2059 The routine \verb|glp_get_row_stat| returns current status assigned to
|
|
alpar@9
|
2060 the auxiliary variable associated with \verb|i|-th row as follows:
|
|
alpar@9
|
2061
|
|
alpar@9
|
2062 \begin{tabular}{@{}ll}
|
|
alpar@9
|
2063 \verb|GLP_BS| & basic variable; \\
|
|
alpar@9
|
2064 \verb|GLP_NL| & non-basic variable on its lower bound; \\
|
|
alpar@9
|
2065 \verb|GLP_NU| & non-basic variable on its upper bound; \\
|
|
alpar@9
|
2066 \verb|GLP_NF| & non-basic free (unbounded) variable; \\
|
|
alpar@9
|
2067 \verb|GLP_NS| & non-basic fixed variable. \\
|
|
alpar@9
|
2068 \end{tabular}
|
|
alpar@9
|
2069
|
|
alpar@9
|
2070 \subsection{glp\_get\_row\_prim---retrieve row primal value}
|
|
alpar@9
|
2071
|
|
alpar@9
|
2072 \subsubsection*{Synopsis}
|
|
alpar@9
|
2073
|
|
alpar@9
|
2074 \begin{verbatim}
|
|
alpar@9
|
2075 double glp_get_row_prim(glp_prob *lp, int i);
|
|
alpar@9
|
2076 \end{verbatim}
|
|
alpar@9
|
2077
|
|
alpar@9
|
2078 \subsubsection*{Returns}
|
|
alpar@9
|
2079
|
|
alpar@9
|
2080 The routine \verb|glp_get_row_prim| returns primal value of the
|
|
alpar@9
|
2081 auxiliary variable associated with \verb|i|-th row.
|
|
alpar@9
|
2082
|
|
alpar@9
|
2083 \subsection{glp\_get\_row\_dual---retrieve row dual value}
|
|
alpar@9
|
2084
|
|
alpar@9
|
2085 \subsubsection*{Synopsis}
|
|
alpar@9
|
2086
|
|
alpar@9
|
2087 \begin{verbatim}
|
|
alpar@9
|
2088 double glp_get_row_dual(glp_prob *lp, int i);
|
|
alpar@9
|
2089 \end{verbatim}
|
|
alpar@9
|
2090
|
|
alpar@9
|
2091 \subsubsection*{Returns}
|
|
alpar@9
|
2092
|
|
alpar@9
|
2093 The routine \verb|glp_get_row_dual| returns dual value (i.e. reduced
|
|
alpar@9
|
2094 cost) of the auxiliary variable associated with \verb|i|-th row.
|
|
alpar@9
|
2095
|
|
alpar@9
|
2096 \newpage
|
|
alpar@9
|
2097
|
|
alpar@9
|
2098 \subsection{glp\_get\_col\_stat---retrieve column status}
|
|
alpar@9
|
2099
|
|
alpar@9
|
2100 \subsubsection*{Synopsis}
|
|
alpar@9
|
2101
|
|
alpar@9
|
2102 \begin{verbatim}
|
|
alpar@9
|
2103 int glp_get_col_stat(glp_prob *lp, int j);
|
|
alpar@9
|
2104 \end{verbatim}
|
|
alpar@9
|
2105
|
|
alpar@9
|
2106 \subsubsection*{Returns}
|
|
alpar@9
|
2107
|
|
alpar@9
|
2108 The routine \verb|glp_get_col_stat| returns current status assigned to
|
|
alpar@9
|
2109 the structural variable associated with \verb|j|-th column as follows:
|
|
alpar@9
|
2110
|
|
alpar@9
|
2111 \begin{tabular}{@{}ll}
|
|
alpar@9
|
2112 \verb|GLP_BS| & basic variable; \\
|
|
alpar@9
|
2113 \verb|GLP_NL| & non-basic variable on its lower bound; \\
|
|
alpar@9
|
2114 \verb|GLP_NU| & non-basic variable on its upper bound; \\
|
|
alpar@9
|
2115 \verb|GLP_NF| & non-basic free (unbounded) variable; \\
|
|
alpar@9
|
2116 \verb|GLP_NS| & non-basic fixed variable. \\
|
|
alpar@9
|
2117 \end{tabular}
|
|
alpar@9
|
2118
|
|
alpar@9
|
2119 \subsection{glp\_get\_col\_prim---retrieve column primal value}
|
|
alpar@9
|
2120
|
|
alpar@9
|
2121 \subsubsection*{Synopsis}
|
|
alpar@9
|
2122
|
|
alpar@9
|
2123 \begin{verbatim}
|
|
alpar@9
|
2124 double glp_get_col_prim(glp_prob *lp, int j);
|
|
alpar@9
|
2125 \end{verbatim}
|
|
alpar@9
|
2126
|
|
alpar@9
|
2127 \subsubsection*{Returns}
|
|
alpar@9
|
2128
|
|
alpar@9
|
2129 The routine \verb|glp_get_col_prim| returns primal value of the
|
|
alpar@9
|
2130 structural variable associated with \verb|j|-th column.
|
|
alpar@9
|
2131
|
|
alpar@9
|
2132 \subsection{glp\_get\_col\_dual---retrieve column dual value}
|
|
alpar@9
|
2133
|
|
alpar@9
|
2134 \subsubsection*{Synopsis}
|
|
alpar@9
|
2135
|
|
alpar@9
|
2136 \begin{verbatim}
|
|
alpar@9
|
2137 double glp_get_col_dual(glp_prob *lp, int j);
|
|
alpar@9
|
2138 \end{verbatim}
|
|
alpar@9
|
2139
|
|
alpar@9
|
2140 \subsubsection*{Returns}
|
|
alpar@9
|
2141
|
|
alpar@9
|
2142 The routine \verb|glp_get_col_dual| returns dual value (i.e. reduced
|
|
alpar@9
|
2143 cost) of the structural variable associated with \verb|j|-th column.
|
|
alpar@9
|
2144
|
|
alpar@9
|
2145 \newpage
|
|
alpar@9
|
2146
|
|
alpar@9
|
2147 \subsection{glp\_get\_unbnd\_ray---determine variable causing\\
|
|
alpar@9
|
2148 unboundedness}
|
|
alpar@9
|
2149
|
|
alpar@9
|
2150 \subsubsection*{Synopsis}
|
|
alpar@9
|
2151
|
|
alpar@9
|
2152 \begin{verbatim}
|
|
alpar@9
|
2153 int glp_get_unbnd_ray(glp_prob *lp);
|
|
alpar@9
|
2154 \end{verbatim}
|
|
alpar@9
|
2155
|
|
alpar@9
|
2156 \subsubsection*{Returns}
|
|
alpar@9
|
2157
|
|
alpar@9
|
2158 The routine \verb|glp_get_unbnd_ray| returns the number $k$ of
|
|
alpar@9
|
2159 a variable, which causes primal or dual unboundedness.
|
|
alpar@9
|
2160 If $1\leq k\leq m$, it is $k$-th auxiliary variable, and if
|
|
alpar@9
|
2161 $m+1\leq k\leq m+n$, it is $(k-m)$-th structural variable, where $m$ is
|
|
alpar@9
|
2162 the number of rows, $n$ is the number of columns in the problem object.
|
|
alpar@9
|
2163 If such variable is not defined, the routine returns 0.
|
|
alpar@9
|
2164
|
|
alpar@9
|
2165 \subsubsection*{Comments}
|
|
alpar@9
|
2166
|
|
alpar@9
|
2167 If it is not exactly known which version of the simplex solver
|
|
alpar@9
|
2168 detected unboundedness, i.e. whether the unboundedness is primal or
|
|
alpar@9
|
2169 dual, it is sufficient to check the status of the variable
|
|
alpar@9
|
2170 with the routine \verb|glp_get_row_stat| or \verb|glp_get_col_stat|.
|
|
alpar@9
|
2171 If the variable is non-basic, the unboundedness is primal, otherwise,
|
|
alpar@9
|
2172 if the variable is basic, the unboundedness is dual (the latter case
|
|
alpar@9
|
2173 means that the problem has no primal feasible dolution).
|
|
alpar@9
|
2174
|
|
alpar@9
|
2175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
2176
|
|
alpar@9
|
2177 \newpage
|
|
alpar@9
|
2178
|
|
alpar@9
|
2179 \section{Interior-point method routines}
|
|
alpar@9
|
2180
|
|
alpar@9
|
2181 {\it Interior-point methods} (also known as {\it barrier methods}) are
|
|
alpar@9
|
2182 more modern and powerful numerical methods for large-scale linear
|
|
alpar@9
|
2183 programming. Such methods are especially efficient for very sparse LP
|
|
alpar@9
|
2184 problems and allow solving such problems much faster than the simplex
|
|
alpar@9
|
2185 method.
|
|
alpar@9
|
2186
|
|
alpar@9
|
2187 In brief, the GLPK interior-point solver works as follows.
|
|
alpar@9
|
2188
|
|
alpar@9
|
2189 At first, the solver transforms the original LP to a {\it working} LP
|
|
alpar@9
|
2190 in the standard format:
|
|
alpar@9
|
2191
|
|
alpar@9
|
2192 \medskip
|
|
alpar@9
|
2193
|
|
alpar@9
|
2194 \noindent
|
|
alpar@9
|
2195 \hspace{.5in} minimize
|
|
alpar@9
|
2196 $$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (2.4)$$
|
|
alpar@9
|
2197 \hspace{.5in} subject to linear constraints
|
|
alpar@9
|
2198 $$
|
|
alpar@9
|
2199 \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}l}
|
|
alpar@9
|
2200 a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n}&=&b_1 \\
|
|
alpar@9
|
2201 a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n}&=&b_2 \\
|
|
alpar@9
|
2202 \multicolumn{7}{c}
|
|
alpar@9
|
2203 {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
|
|
alpar@9
|
2204 a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n}&=&b_m \\
|
|
alpar@9
|
2205 \end{array} \eqno (2.5)
|
|
alpar@9
|
2206 $$
|
|
alpar@9
|
2207 \hspace{.5in} and non-negative variables
|
|
alpar@9
|
2208 $$x_1\geq 0,\ \ x_2\geq 0,\ \ \dots,\ \ x_n\geq 0 \eqno(2.6)$$
|
|
alpar@9
|
2209 where: $z$ is the objective function; $x_1$, \dots, $x_n$ are variables;
|
|
alpar@9
|
2210 $c_1$, \dots, $c_n$ are objective coefficients; $c_0$ is a constant term
|
|
alpar@9
|
2211 of the objective function;\linebreak $a_{11}$, \dots, $a_{mn}$ are
|
|
alpar@9
|
2212 constraint coefficients; $b_1$, \dots, $b_m$ are right-hand sides.
|
|
alpar@9
|
2213
|
|
alpar@9
|
2214 Using vector and matrix notations the working LP (2.4)---(2.6) can be
|
|
alpar@9
|
2215 written as follows:
|
|
alpar@9
|
2216 $$z=c^Tx+c_0\ \rightarrow\ \min,\eqno(2.7)$$
|
|
alpar@9
|
2217 $$Ax=b,\eqno(2.8)$$
|
|
alpar@9
|
2218 $$x\geq 0,\eqno(2.9)$$
|
|
alpar@9
|
2219 where: $x=(x_j)$ is $n$-vector of variables, $c=(c_j)$ is $n$-vector of
|
|
alpar@9
|
2220 objective coefficients, $A=(a_{ij})$ is $m\times n$-matrix of
|
|
alpar@9
|
2221 constraint coefficients, and $b=(b_i)$ is $m$-vector of right-hand
|
|
alpar@9
|
2222 sides.
|
|
alpar@9
|
2223
|
|
alpar@9
|
2224 Karush--Kuhn--Tucker optimality conditions for LP (2.7)---(2.9) are the
|
|
alpar@9
|
2225 following:
|
|
alpar@9
|
2226
|
|
alpar@9
|
2227 \newpage
|
|
alpar@9
|
2228
|
|
alpar@9
|
2229 $$Ax=b,\eqno(2.10)$$
|
|
alpar@9
|
2230 $$A^T\pi+\lambda=c,\eqno(2.11)$$
|
|
alpar@9
|
2231 $$\lambda^Tx=0,\eqno(2.12)$$
|
|
alpar@9
|
2232 $$x\geq 0,\ \ \lambda\geq 0,\eqno(2.13)$$
|
|
alpar@9
|
2233 where: $\pi$ is $m$-vector of Lagrange multipliers (dual variables) for
|
|
alpar@9
|
2234 equality constraints (2.8), $\lambda$ is $n$-vector of Lagrange
|
|
alpar@9
|
2235 multipliers (dual variables) for non-negativity constraints (2.9),
|
|
alpar@9
|
2236 (2.10) is the primal feasibility condition, (2.11) is the dual
|
|
alpar@9
|
2237 feasibility condition, (2.12) is the primal-dual complementarity
|
|
alpar@9
|
2238 condition, and (2.13) is the non-negativity conditions.
|
|
alpar@9
|
2239
|
|
alpar@9
|
2240 The main idea of the primal-dual interior-point method is based on
|
|
alpar@9
|
2241 finding a point in the primal-dual space (i.e. in the space of all
|
|
alpar@9
|
2242 primal and dual variables $x$, $\pi$, and $\lambda$), which satisfies
|
|
alpar@9
|
2243 to all optimality conditions (2.10)---(2.13). Obviously, $x$-component
|
|
alpar@9
|
2244 of such point then provides an optimal solution to the working LP
|
|
alpar@9
|
2245 (2.7)---(2.9).
|
|
alpar@9
|
2246
|
|
alpar@9
|
2247 To find the optimal point $(x^*,\pi^*,\lambda^*)$ the interior-point
|
|
alpar@9
|
2248 method attempts to solve the system of equations (2.10)---(2.12), which
|
|
alpar@9
|
2249 is closed in the sense that the number of variables $x_j$, $\pi_i$, and
|
|
alpar@9
|
2250 $\lambda_j$ and the number equations are the same and equal to $m+2n$.
|
|
alpar@9
|
2251 Due to condition (2.12) this system of equations is non-linear, so it
|
|
alpar@9
|
2252 can be solved with a version of {\it Newton's method} provided with
|
|
alpar@9
|
2253 additional rules to keep the current point within the positive orthant
|
|
alpar@9
|
2254 as required by the non-negativity conditions (2.13).
|
|
alpar@9
|
2255
|
|
alpar@9
|
2256 Finally, once the optimal point $(x^*,\pi^*,\lambda^*)$ has been found,
|
|
alpar@9
|
2257 the solver performs inverse transformations to recover corresponding
|
|
alpar@9
|
2258 solution to the original LP passed to the solver from the application
|
|
alpar@9
|
2259 program.
|
|
alpar@9
|
2260
|
|
alpar@9
|
2261 \subsection{glp\_interior---solve LP problem with the interior-point
|
|
alpar@9
|
2262 method}
|
|
alpar@9
|
2263
|
|
alpar@9
|
2264 \subsubsection*{Synopsis}
|
|
alpar@9
|
2265
|
|
alpar@9
|
2266 \begin{verbatim}
|
|
alpar@9
|
2267 int glp_interior(glp_prob *P, const glp_iptcp *parm);
|
|
alpar@9
|
2268 \end{verbatim}
|
|
alpar@9
|
2269
|
|
alpar@9
|
2270 \subsubsection*{Description}
|
|
alpar@9
|
2271
|
|
alpar@9
|
2272 The routine \verb|glp_interior| is a driver to the LP solver based on
|
|
alpar@9
|
2273 the primal-dual interior-point method. This routine retrieves problem
|
|
alpar@9
|
2274 data from the specified problem object, calls the solver to solve the
|
|
alpar@9
|
2275 problem instance, and stores results of computations back into the
|
|
alpar@9
|
2276 problem object.
|
|
alpar@9
|
2277
|
|
alpar@9
|
2278 The interior-point solver has a set of control parameters. Values of
|
|
alpar@9
|
2279 the control parameters can be passed in the structure \verb|glp_iptcp|,
|
|
alpar@9
|
2280 which the parameter \verb|parm| points to. For detailed description of
|
|
alpar@9
|
2281 this structure see paragraph ``Control parameters'' below. Before
|
|
alpar@9
|
2282 specifying some control parameters the application program should
|
|
alpar@9
|
2283 initialize the structure \verb|glp_iptcp| by default values of all
|
|
alpar@9
|
2284 control parameters using the routine \verb|glp_init_iptcp| (see the
|
|
alpar@9
|
2285 next subsection). This is needed for backward compatibility, because in
|
|
alpar@9
|
2286 the future there may appear new members in the structure
|
|
alpar@9
|
2287 \verb|glp_iptcp|.
|
|
alpar@9
|
2288
|
|
alpar@9
|
2289 The parameter \verb|parm| can be specified as \verb|NULL|, in which
|
|
alpar@9
|
2290 case the solver uses default settings.
|
|
alpar@9
|
2291
|
|
alpar@9
|
2292 \subsubsection*{Returns}
|
|
alpar@9
|
2293
|
|
alpar@9
|
2294 \def\arraystretch{1}
|
|
alpar@9
|
2295
|
|
alpar@9
|
2296 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
|
|
alpar@9
|
2297 0 & The LP problem instance has been successfully solved. (This code
|
|
alpar@9
|
2298 does {\it not} necessarily mean that the solver has found optimal
|
|
alpar@9
|
2299 solution. It only means that the solution process was successful.) \\
|
|
alpar@9
|
2300 \verb|GLP_EFAIL| & The problem has no rows/columns.\\
|
|
alpar@9
|
2301 \verb|GLP_ENOCVG| & Very slow convergence or divergence.\\
|
|
alpar@9
|
2302 \verb|GLP_EITLIM| & Iteration limit exceeded.\\
|
|
alpar@9
|
2303 \verb|GLP_EINSTAB| & Numerical instability on solving Newtonian
|
|
alpar@9
|
2304 system.\\
|
|
alpar@9
|
2305 \end{tabular}
|
|
alpar@9
|
2306
|
|
alpar@9
|
2307 \subsubsection*{Comments}
|
|
alpar@9
|
2308
|
|
alpar@9
|
2309 The routine \verb|glp_interior| implements an easy version of
|
|
alpar@9
|
2310 the primal-dual interior-point method based on Mehrotra's
|
|
alpar@9
|
2311 technique.\footnote{S. Mehrotra. On the implementation of a primal-dual
|
|
alpar@9
|
2312 interior point method. SIAM J. on Optim., 2(4), pp. 575-601, 1992.}
|
|
alpar@9
|
2313
|
|
alpar@9
|
2314 Note that currently the GLPK interior-point solver does not include
|
|
alpar@9
|
2315 many important features, in particular:
|
|
alpar@9
|
2316
|
|
alpar@9
|
2317 $\bullet$ it is not able to process dense columns. Thus, if the
|
|
alpar@9
|
2318 constraint matrix of the LP problem has dense columns, the solving
|
|
alpar@9
|
2319 process may be inefficient;
|
|
alpar@9
|
2320
|
|
alpar@9
|
2321 $\bullet$ it has no features against numerical instability. For some
|
|
alpar@9
|
2322 LP problems premature termination may happen if the matrix $ADA^T$
|
|
alpar@9
|
2323 becomes singular or ill-conditioned;
|
|
alpar@9
|
2324
|
|
alpar@9
|
2325 $\bullet$ it is not able to identify the optimal basis, which
|
|
alpar@9
|
2326 corresponds to the interior-point solution found.
|
|
alpar@9
|
2327
|
|
alpar@9
|
2328 \newpage
|
|
alpar@9
|
2329
|
|
alpar@9
|
2330 \subsubsection*{Terminal output}
|
|
alpar@9
|
2331
|
|
alpar@9
|
2332 Solving large LP problems may take a long time, so the solver reports
|
|
alpar@9
|
2333 some information about every interior-point iteration,\footnote{Unlike
|
|
alpar@9
|
2334 the simplex method the interior point method usually needs 30---50
|
|
alpar@9
|
2335 iterations (independently on the problem size) in order to find an
|
|
alpar@9
|
2336 optimal solution.} which is sent to the terminal. This information has
|
|
alpar@9
|
2337 the following format:
|
|
alpar@9
|
2338
|
|
alpar@9
|
2339 \begin{verbatim}
|
|
alpar@9
|
2340 nnn: obj = fff; rpi = ppp; rdi = ddd; gap = ggg
|
|
alpar@9
|
2341 \end{verbatim}
|
|
alpar@9
|
2342
|
|
alpar@9
|
2343 \noindent where: \verb|nnn| is iteration number, \verb|fff| is the
|
|
alpar@9
|
2344 current value of the objective function (in the case of maximization it
|
|
alpar@9
|
2345 has wrong sign), \verb|ppp| is the current relative primal
|
|
alpar@9
|
2346 infeasibility (cf. (2.10)):
|
|
alpar@9
|
2347 $$\frac{\|Ax^{(k)}-b\|}{1+\|b\|},\eqno(2.14)$$
|
|
alpar@9
|
2348 \verb|ddd| is the current relative dual infeasibility (cf. (2.11)):
|
|
alpar@9
|
2349 $$\frac{\|A^T\pi^{(k)}+\lambda^{(k)}-c\|}{1+\|c\|},\eqno(2.15)$$
|
|
alpar@9
|
2350 \verb|ggg| is the current primal-dual gap (cf. (2.12)):
|
|
alpar@9
|
2351 $$\frac{|c^Tx^{(k)}-b^T\pi^{(k)}|}{1+|c^Tx^{(k)}|},\eqno(2.16)$$
|
|
alpar@9
|
2352 and $[x^{(k)},\pi^{(k)},\lambda^{(k)}]$ is the current point on $k$-th
|
|
alpar@9
|
2353 iteration, $k=0,1,2,\dots$\ . Note that all solution components are
|
|
alpar@9
|
2354 internally scaled, so information sent to the terminal is suitable only
|
|
alpar@9
|
2355 for visual inspection.
|
|
alpar@9
|
2356
|
|
alpar@9
|
2357 \subsubsection*{Control parameters}
|
|
alpar@9
|
2358
|
|
alpar@9
|
2359 This paragraph describes all control parameters currently used in the
|
|
alpar@9
|
2360 interior-point solver. Symbolic names of control parameters are names of
|
|
alpar@9
|
2361 corresponding members in the structure \verb|glp_iptcp|.
|
|
alpar@9
|
2362
|
|
alpar@9
|
2363 \medskip
|
|
alpar@9
|
2364
|
|
alpar@9
|
2365 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2366 \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
|
|
alpar@9
|
2367 \\
|
|
alpar@9
|
2368 &Message level for terminal output:\\
|
|
alpar@9
|
2369 &\verb|GLP_MSG_OFF|---no output;\\
|
|
alpar@9
|
2370 &\verb|GLP_MSG_ERR|---error and warning messages only;\\
|
|
alpar@9
|
2371 &\verb|GLP_MSG_ON |---normal output;\\
|
|
alpar@9
|
2372 &\verb|GLP_MSG_ALL|---full output (including informational messages).
|
|
alpar@9
|
2373 \\
|
|
alpar@9
|
2374 \end{tabular}
|
|
alpar@9
|
2375
|
|
alpar@9
|
2376 \medskip
|
|
alpar@9
|
2377
|
|
alpar@9
|
2378 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2379 \multicolumn{2}{@{}l}{{\tt int ord\_alg} (default: {\tt GLP\_ORD\_AMD})}
|
|
alpar@9
|
2380 \\
|
|
alpar@9
|
2381 &Ordering algorithm used prior to Cholesky factorization:\\
|
|
alpar@9
|
2382 &\verb|GLP_ORD_NONE |---use natural (original) ordering;\\
|
|
alpar@9
|
2383 &\verb|GLP_ORD_QMD |---quotient minimum degree (QMD);\\
|
|
alpar@9
|
2384 &\verb|GLP_ORD_AMD |---approximate minimum degree (AMD);\\
|
|
alpar@9
|
2385 &\verb|GLP_ORD_SYMAMD|---approximate minimum degree (SYMAMD).\\
|
|
alpar@9
|
2386 \end{tabular}
|
|
alpar@9
|
2387
|
|
alpar@9
|
2388 \subsubsection*{Example}
|
|
alpar@9
|
2389
|
|
alpar@9
|
2390 The following main program reads LP problem instance in fixed MPS
|
|
alpar@9
|
2391 format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
|
|
alpar@9
|
2392 format can be found in the Netlib LP collection; see
|
|
alpar@9
|
2393 {\tt ftp://ftp.netlib.org/lp/data/}.} solves it with the interior-point
|
|
alpar@9
|
2394 solver, and writes the solution to file \verb|25fv47.txt|.
|
|
alpar@9
|
2395
|
|
alpar@9
|
2396 \begin{footnotesize}
|
|
alpar@9
|
2397 \begin{verbatim}
|
|
alpar@9
|
2398 /* iptsamp.c */
|
|
alpar@9
|
2399
|
|
alpar@9
|
2400 #include <stdio.h>
|
|
alpar@9
|
2401 #include <stdlib.h>
|
|
alpar@9
|
2402 #include <glpk.h>
|
|
alpar@9
|
2403
|
|
alpar@9
|
2404 int main(void)
|
|
alpar@9
|
2405 { glp_prob *P;
|
|
alpar@9
|
2406 P = glp_create_prob();
|
|
alpar@9
|
2407 glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
|
|
alpar@9
|
2408 glp_interior(P, NULL);
|
|
alpar@9
|
2409 glp_print_ipt(P, "25fv47.txt");
|
|
alpar@9
|
2410 glp_delete_prob(P);
|
|
alpar@9
|
2411 return 0;
|
|
alpar@9
|
2412 }
|
|
alpar@9
|
2413
|
|
alpar@9
|
2414 /* eof */
|
|
alpar@9
|
2415 \end{verbatim}
|
|
alpar@9
|
2416 \end{footnotesize}
|
|
alpar@9
|
2417
|
|
alpar@9
|
2418 \noindent
|
|
alpar@9
|
2419 Below here is shown the terminal output from this example program.
|
|
alpar@9
|
2420
|
|
alpar@9
|
2421 \begin{footnotesize}
|
|
alpar@9
|
2422 \begin{verbatim}
|
|
alpar@9
|
2423 Reading problem data from `25fv47.mps'...
|
|
alpar@9
|
2424 Problem: 25FV47
|
|
alpar@9
|
2425 Objective: R0000
|
|
alpar@9
|
2426 822 rows, 1571 columns, 11127 non-zeros
|
|
alpar@9
|
2427 6919 records were read
|
|
alpar@9
|
2428 Original LP has 822 row(s), 1571 column(s), and 11127 non-zero(s)
|
|
alpar@9
|
2429 Working LP has 821 row(s), 1876 column(s), and 10705 non-zero(s)
|
|
alpar@9
|
2430 Matrix A has 10705 non-zeros
|
|
alpar@9
|
2431 Matrix S = A*A' has 11895 non-zeros (upper triangle)
|
|
alpar@9
|
2432 Minimal degree ordering...
|
|
alpar@9
|
2433 Computing Cholesky factorization S = L'*L...
|
|
alpar@9
|
2434 Matrix L has 35411 non-zeros
|
|
alpar@9
|
2435 Guessing initial point...
|
|
alpar@9
|
2436 Optimization begins...
|
|
alpar@9
|
2437 0: obj = 1.823377629e+05; rpi = 1.3e+01; rdi = 1.4e+01; gap = 9.3e-01
|
|
alpar@9
|
2438 1: obj = 9.260045192e+04; rpi = 5.3e+00; rdi = 5.6e+00; gap = 6.8e+00
|
|
alpar@9
|
2439 2: obj = 3.596999742e+04; rpi = 1.5e+00; rdi = 1.2e+00; gap = 1.8e+01
|
|
alpar@9
|
2440 3: obj = 1.989627568e+04; rpi = 4.7e-01; rdi = 3.0e-01; gap = 1.9e+01
|
|
alpar@9
|
2441 4: obj = 1.430215557e+04; rpi = 1.1e-01; rdi = 8.6e-02; gap = 1.4e+01
|
|
alpar@9
|
2442 5: obj = 1.155716505e+04; rpi = 2.3e-02; rdi = 2.4e-02; gap = 6.8e+00
|
|
alpar@9
|
2443 6: obj = 9.660273208e+03; rpi = 6.7e-03; rdi = 4.6e-03; gap = 3.9e+00
|
|
alpar@9
|
2444 7: obj = 8.694348283e+03; rpi = 3.7e-03; rdi = 1.7e-03; gap = 2.0e+00
|
|
alpar@9
|
2445 8: obj = 8.019543639e+03; rpi = 2.4e-03; rdi = 3.9e-04; gap = 1.0e+00
|
|
alpar@9
|
2446 9: obj = 7.122676293e+03; rpi = 1.2e-03; rdi = 1.5e-04; gap = 6.6e-01
|
|
alpar@9
|
2447 10: obj = 6.514534518e+03; rpi = 6.1e-04; rdi = 4.3e-05; gap = 4.1e-01
|
|
alpar@9
|
2448 11: obj = 6.361572203e+03; rpi = 4.8e-04; rdi = 2.2e-05; gap = 3.0e-01
|
|
alpar@9
|
2449 12: obj = 6.203355508e+03; rpi = 3.2e-04; rdi = 1.7e-05; gap = 2.6e-01
|
|
alpar@9
|
2450 13: obj = 6.032943411e+03; rpi = 2.0e-04; rdi = 9.3e-06; gap = 2.1e-01
|
|
alpar@9
|
2451 14: obj = 5.796553021e+03; rpi = 9.8e-05; rdi = 3.2e-06; gap = 1.0e-01
|
|
alpar@9
|
2452 15: obj = 5.667032431e+03; rpi = 4.4e-05; rdi = 1.1e-06; gap = 5.6e-02
|
|
alpar@9
|
2453 16: obj = 5.613911867e+03; rpi = 2.5e-05; rdi = 4.1e-07; gap = 3.5e-02
|
|
alpar@9
|
2454 17: obj = 5.560572626e+03; rpi = 9.9e-06; rdi = 2.3e-07; gap = 2.1e-02
|
|
alpar@9
|
2455 18: obj = 5.537276001e+03; rpi = 5.5e-06; rdi = 8.4e-08; gap = 1.1e-02
|
|
alpar@9
|
2456 19: obj = 5.522746942e+03; rpi = 2.2e-06; rdi = 4.0e-08; gap = 6.7e-03
|
|
alpar@9
|
2457 20: obj = 5.509956679e+03; rpi = 7.5e-07; rdi = 1.8e-08; gap = 2.9e-03
|
|
alpar@9
|
2458 21: obj = 5.504571733e+03; rpi = 1.6e-07; rdi = 5.8e-09; gap = 1.1e-03
|
|
alpar@9
|
2459 22: obj = 5.502576367e+03; rpi = 3.4e-08; rdi = 1.0e-09; gap = 2.5e-04
|
|
alpar@9
|
2460 23: obj = 5.502057119e+03; rpi = 8.1e-09; rdi = 3.0e-10; gap = 7.7e-05
|
|
alpar@9
|
2461 24: obj = 5.501885996e+03; rpi = 9.4e-10; rdi = 1.2e-10; gap = 2.4e-05
|
|
alpar@9
|
2462 25: obj = 5.501852464e+03; rpi = 1.4e-10; rdi = 1.2e-11; gap = 3.0e-06
|
|
alpar@9
|
2463 26: obj = 5.501846549e+03; rpi = 1.4e-11; rdi = 1.2e-12; gap = 3.0e-07
|
|
alpar@9
|
2464 27: obj = 5.501845954e+03; rpi = 1.4e-12; rdi = 1.2e-13; gap = 3.0e-08
|
|
alpar@9
|
2465 28: obj = 5.501845895e+03; rpi = 1.5e-13; rdi = 1.2e-14; gap = 3.0e-09
|
|
alpar@9
|
2466 OPTIMAL SOLUTION FOUND
|
|
alpar@9
|
2467 Writing interior-point solution to `25fv47.txt'...
|
|
alpar@9
|
2468 \end{verbatim}
|
|
alpar@9
|
2469 \end{footnotesize}
|
|
alpar@9
|
2470
|
|
alpar@9
|
2471 \subsection{glp\_init\_iptcp---initialize interior-point solver control
|
|
alpar@9
|
2472 parameters}
|
|
alpar@9
|
2473
|
|
alpar@9
|
2474 \subsubsection*{Synopsis}
|
|
alpar@9
|
2475
|
|
alpar@9
|
2476 \begin{verbatim}
|
|
alpar@9
|
2477 int glp_init_iptcp(glp_iptcp *parm);
|
|
alpar@9
|
2478 \end{verbatim}
|
|
alpar@9
|
2479
|
|
alpar@9
|
2480 \subsubsection*{Description}
|
|
alpar@9
|
2481
|
|
alpar@9
|
2482 The routine \verb|glp_init_iptcp| initializes control parameters, which
|
|
alpar@9
|
2483 are used by the interior-point solver, with default values.
|
|
alpar@9
|
2484
|
|
alpar@9
|
2485 Default values of the control parameters are stored in the structure
|
|
alpar@9
|
2486 \verb|glp_iptcp|, which the parameter \verb|parm| points to.
|
|
alpar@9
|
2487
|
|
alpar@9
|
2488 \subsection{glp\_ipt\_status---determine solution status}
|
|
alpar@9
|
2489
|
|
alpar@9
|
2490 \subsubsection*{Synopsis}
|
|
alpar@9
|
2491
|
|
alpar@9
|
2492 \begin{verbatim}
|
|
alpar@9
|
2493 int glp_ipt_status(glp_prob *lp);
|
|
alpar@9
|
2494 \end{verbatim}
|
|
alpar@9
|
2495
|
|
alpar@9
|
2496 \subsubsection*{Returns}
|
|
alpar@9
|
2497
|
|
alpar@9
|
2498 The routine \verb|glp_ipt_status| reports the status of a solution
|
|
alpar@9
|
2499 found by the interior-point solver as follows:
|
|
alpar@9
|
2500
|
|
alpar@9
|
2501 \begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
|
|
alpar@9
|
2502 \verb|GLP_UNDEF| & interior-point solution is undefined. \\
|
|
alpar@9
|
2503 \verb|GLP_OPT| & interior-point solution is optimal. \\
|
|
alpar@9
|
2504 \verb|GLP_INFEAS|& interior-point solution is infeasible. \\
|
|
alpar@9
|
2505 \verb|GLP_NOFEAS|& no feasible primal-dual solution exists.\\
|
|
alpar@9
|
2506 \end{tabular}
|
|
alpar@9
|
2507
|
|
alpar@9
|
2508 \subsection{glp\_ipt\_obj\_val---retrieve objective value}
|
|
alpar@9
|
2509
|
|
alpar@9
|
2510 \subsubsection*{Synopsis}
|
|
alpar@9
|
2511
|
|
alpar@9
|
2512 \begin{verbatim}
|
|
alpar@9
|
2513 double glp_ipt_obj_val(glp_prob *lp);
|
|
alpar@9
|
2514 \end{verbatim}
|
|
alpar@9
|
2515
|
|
alpar@9
|
2516 \subsubsection*{Returns}
|
|
alpar@9
|
2517
|
|
alpar@9
|
2518 The routine \verb|glp_ipt_obj_val| returns value of the objective
|
|
alpar@9
|
2519 function for interior-point solution.
|
|
alpar@9
|
2520
|
|
alpar@9
|
2521 \subsection{glp\_ipt\_row\_prim---retrieve row primal value}
|
|
alpar@9
|
2522
|
|
alpar@9
|
2523 \subsubsection*{Synopsis}
|
|
alpar@9
|
2524
|
|
alpar@9
|
2525 \begin{verbatim}
|
|
alpar@9
|
2526 double glp_ipt_row_prim(glp_prob *lp, int i);
|
|
alpar@9
|
2527 \end{verbatim}
|
|
alpar@9
|
2528
|
|
alpar@9
|
2529 \subsubsection*{Returns}
|
|
alpar@9
|
2530
|
|
alpar@9
|
2531 The routine \verb|glp_ipt_row_prim| returns primal value of the
|
|
alpar@9
|
2532 auxiliary variable associated with \verb|i|-th row.
|
|
alpar@9
|
2533
|
|
alpar@9
|
2534 \newpage
|
|
alpar@9
|
2535
|
|
alpar@9
|
2536 \subsection{glp\_ipt\_row\_dual---retrieve row dual value}
|
|
alpar@9
|
2537
|
|
alpar@9
|
2538 \subsubsection*{Synopsis}
|
|
alpar@9
|
2539
|
|
alpar@9
|
2540 \begin{verbatim}
|
|
alpar@9
|
2541 double glp_ipt_row_dual(glp_prob *lp, int i);
|
|
alpar@9
|
2542 \end{verbatim}
|
|
alpar@9
|
2543
|
|
alpar@9
|
2544 \subsubsection*{Returns}
|
|
alpar@9
|
2545
|
|
alpar@9
|
2546 The routine \verb|glp_ipt_row_dual| returns dual value (i.e. reduced
|
|
alpar@9
|
2547 cost) of the auxiliary variable associated with \verb|i|-th row.
|
|
alpar@9
|
2548
|
|
alpar@9
|
2549 \subsection{glp\_ipt\_col\_prim---retrieve column primal value}
|
|
alpar@9
|
2550
|
|
alpar@9
|
2551 \subsubsection*{Synopsis}
|
|
alpar@9
|
2552
|
|
alpar@9
|
2553 \begin{verbatim}
|
|
alpar@9
|
2554 double glp_ipt_col_prim(glp_prob *lp, int j);
|
|
alpar@9
|
2555 \end{verbatim}
|
|
alpar@9
|
2556
|
|
alpar@9
|
2557 \subsubsection*{Returns}
|
|
alpar@9
|
2558
|
|
alpar@9
|
2559 The routine \verb|glp_ipt_col_prim| returns primal value of the
|
|
alpar@9
|
2560 structural variable associated with \verb|j|-th column.
|
|
alpar@9
|
2561
|
|
alpar@9
|
2562 \subsection{glp\_ipt\_col\_dual---retrieve column dual value}
|
|
alpar@9
|
2563
|
|
alpar@9
|
2564 \subsubsection*{Synopsis}
|
|
alpar@9
|
2565
|
|
alpar@9
|
2566 \begin{verbatim}
|
|
alpar@9
|
2567 double glp_ipt_col_dual(glp_prob *lp, int j);
|
|
alpar@9
|
2568 \end{verbatim}
|
|
alpar@9
|
2569
|
|
alpar@9
|
2570 \subsubsection*{Returns}
|
|
alpar@9
|
2571
|
|
alpar@9
|
2572 The routine \verb|glp_ipt_col_dual| returns dual value (i.e. reduced
|
|
alpar@9
|
2573 cost) of the structural variable associated with \verb|j|-th column.
|
|
alpar@9
|
2574
|
|
alpar@9
|
2575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
2576
|
|
alpar@9
|
2577 \newpage
|
|
alpar@9
|
2578
|
|
alpar@9
|
2579 \section{Mixed integer programming routines}
|
|
alpar@9
|
2580
|
|
alpar@9
|
2581 \subsection{glp\_set\_col\_kind---set (change) column kind}
|
|
alpar@9
|
2582
|
|
alpar@9
|
2583 \subsubsection*{Synopsis}
|
|
alpar@9
|
2584
|
|
alpar@9
|
2585 \begin{verbatim}
|
|
alpar@9
|
2586 void glp_set_col_kind(glp_prob *mip, int j, int kind);
|
|
alpar@9
|
2587 \end{verbatim}
|
|
alpar@9
|
2588
|
|
alpar@9
|
2589 \subsubsection*{Description}
|
|
alpar@9
|
2590
|
|
alpar@9
|
2591 The routine \verb|glp_set_col_kind| sets (changes) the kind of
|
|
alpar@9
|
2592 \verb|j|-th column (structural variable) as specified by the parameter
|
|
alpar@9
|
2593 \verb|kind|:
|
|
alpar@9
|
2594
|
|
alpar@9
|
2595 \begin{tabular}{@{}ll}
|
|
alpar@9
|
2596 \verb|GLP_CV| & continuous variable; \\
|
|
alpar@9
|
2597 \verb|GLP_IV| & integer variable; \\
|
|
alpar@9
|
2598 \verb|GLP_BV| & binary variable. \\
|
|
alpar@9
|
2599 \end{tabular}
|
|
alpar@9
|
2600
|
|
alpar@9
|
2601 %If a column is set to \verb|GLP_IV|, its bounds must be exact integer
|
|
alpar@9
|
2602 %numbers with no tolerance, such that the condition
|
|
alpar@9
|
2603 %\verb|bnd == floor(bnd)| would hold.
|
|
alpar@9
|
2604
|
|
alpar@9
|
2605 Setting a column to \verb|GLP_BV| has the same effect as if it were
|
|
alpar@9
|
2606 set to \verb|GLP_IV|, its lower bound were set 0, and its upper bound
|
|
alpar@9
|
2607 were set to 1.
|
|
alpar@9
|
2608
|
|
alpar@9
|
2609 \subsection{glp\_get\_col\_kind---retrieve column kind}
|
|
alpar@9
|
2610
|
|
alpar@9
|
2611 \subsubsection*{Synopsis}
|
|
alpar@9
|
2612
|
|
alpar@9
|
2613 \begin{verbatim}
|
|
alpar@9
|
2614 int glp_get_col_kind(glp_prob *mip, int j);
|
|
alpar@9
|
2615 \end{verbatim}
|
|
alpar@9
|
2616
|
|
alpar@9
|
2617 \subsubsection*{Returns}
|
|
alpar@9
|
2618
|
|
alpar@9
|
2619 The routine \verb|glp_get_col_kind| returns the kind of \verb|j|-th
|
|
alpar@9
|
2620 column (structural variable) as follows:
|
|
alpar@9
|
2621
|
|
alpar@9
|
2622 \begin{tabular}{@{}ll}
|
|
alpar@9
|
2623 \verb|GLP_CV| & continuous variable; \\
|
|
alpar@9
|
2624 \verb|GLP_IV| & integer variable; \\
|
|
alpar@9
|
2625 \verb|GLP_BV| & binary variable. \\
|
|
alpar@9
|
2626 \end{tabular}
|
|
alpar@9
|
2627
|
|
alpar@9
|
2628 \subsection{glp\_get\_num\_int---retrieve number of integer columns}
|
|
alpar@9
|
2629
|
|
alpar@9
|
2630 \subsubsection*{Synopsis}
|
|
alpar@9
|
2631
|
|
alpar@9
|
2632 \begin{verbatim}
|
|
alpar@9
|
2633 int glp_get_num_int(glp_prob *mip);
|
|
alpar@9
|
2634 \end{verbatim}
|
|
alpar@9
|
2635
|
|
alpar@9
|
2636 \subsubsection*{Returns}
|
|
alpar@9
|
2637
|
|
alpar@9
|
2638 The routine \verb|glp_get_num_int| returns the number of columns
|
|
alpar@9
|
2639 (structural variables), which are marked as integer. Note that this
|
|
alpar@9
|
2640 number {\it does} include binary columns.
|
|
alpar@9
|
2641
|
|
alpar@9
|
2642 \subsection{glp\_get\_num\_bin---retrieve number of binary columns}
|
|
alpar@9
|
2643
|
|
alpar@9
|
2644 \subsubsection*{Synopsis}
|
|
alpar@9
|
2645
|
|
alpar@9
|
2646 \begin{verbatim}
|
|
alpar@9
|
2647 int glp_get_num_bin(glp_prob *mip);
|
|
alpar@9
|
2648 \end{verbatim}
|
|
alpar@9
|
2649
|
|
alpar@9
|
2650 \subsubsection*{Returns}
|
|
alpar@9
|
2651
|
|
alpar@9
|
2652 The routine \verb|glp_get_num_bin| returns the number of columns
|
|
alpar@9
|
2653 (structural variables), which are marked as integer and whose lower
|
|
alpar@9
|
2654 bound is zero and upper bound is one.
|
|
alpar@9
|
2655
|
|
alpar@9
|
2656 \subsection{glp\_intopt---solve MIP problem with the branch-and-cut
|
|
alpar@9
|
2657 method}
|
|
alpar@9
|
2658
|
|
alpar@9
|
2659 \subsubsection*{Synopsis}
|
|
alpar@9
|
2660
|
|
alpar@9
|
2661 \begin{verbatim}
|
|
alpar@9
|
2662 int glp_intopt(glp_prob *mip, const glp_iocp *parm);
|
|
alpar@9
|
2663 \end{verbatim}
|
|
alpar@9
|
2664
|
|
alpar@9
|
2665 \subsubsection*{Description}
|
|
alpar@9
|
2666
|
|
alpar@9
|
2667 The routine \verb|glp_intopt| is a driver to the MIP solver based on
|
|
alpar@9
|
2668 the branch-and-cut method, which is a hybrid of branch-and-bound and
|
|
alpar@9
|
2669 cutting plane methods.
|
|
alpar@9
|
2670
|
|
alpar@9
|
2671 If the presolver is disabled (see paragraph ``Control parameters''
|
|
alpar@9
|
2672 below), on entry to the routine \verb|glp_intopt| the problem object,
|
|
alpar@9
|
2673 which the parameter \verb|mip| points to, should contain optimal
|
|
alpar@9
|
2674 solution to LP relaxation (it can be obtained, for example, with the
|
|
alpar@9
|
2675 routine \verb|glp_simplex|). Otherwise, if the presolver is enabled, it
|
|
alpar@9
|
2676 is not necessary.
|
|
alpar@9
|
2677
|
|
alpar@9
|
2678 The MIP solver has a set of control parameters. Values of the control
|
|
alpar@9
|
2679 parameters can be passed in the structure \verb|glp_iocp|, which the
|
|
alpar@9
|
2680 parameter \verb|parm| points to. For detailed description of this
|
|
alpar@9
|
2681 structure see paragraph ``Control parameters'' below. Before specifying
|
|
alpar@9
|
2682 some control parameters the application program should initialize the
|
|
alpar@9
|
2683 structure \verb|glp_iocp| by default values of all control parameters
|
|
alpar@9
|
2684 using the routine \verb|glp_init_iocp| (see the next subsection). This
|
|
alpar@9
|
2685 is needed for backward compatibility, because in the future there may
|
|
alpar@9
|
2686 appear new members in the structure \verb|glp_iocp|.
|
|
alpar@9
|
2687
|
|
alpar@9
|
2688 The parameter \verb|parm| can be specified as \verb|NULL|, in which case
|
|
alpar@9
|
2689 the solver uses default settings.
|
|
alpar@9
|
2690
|
|
alpar@9
|
2691 Note that the GLPK branch-and-cut solver is not perfect, so it is unable
|
|
alpar@9
|
2692 to solve hard or very large scale MIP instances for a reasonable time.
|
|
alpar@9
|
2693
|
|
alpar@9
|
2694 \subsubsection*{Returns}
|
|
alpar@9
|
2695
|
|
alpar@9
|
2696 \def\arraystretch{1}
|
|
alpar@9
|
2697
|
|
alpar@9
|
2698 \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
|
|
alpar@9
|
2699 0 & The MIP problem instance has been successfully solved. (This code
|
|
alpar@9
|
2700 does {\it not} necessarily mean that the solver has found optimal
|
|
alpar@9
|
2701 solution. It only means that the solution process was successful.) \\
|
|
alpar@9
|
2702 \verb|GLP_EBOUND| & Unable to start the search, because some
|
|
alpar@9
|
2703 double-bounded variables have incorrect bounds or some integer variables
|
|
alpar@9
|
2704 have non-integer (fractional) bounds.\\
|
|
alpar@9
|
2705 \verb|GLP_EROOT| & Unable to start the search, because optimal basis for
|
|
alpar@9
|
2706 initial LP relaxation is not provided. (This code may appear only if the
|
|
alpar@9
|
2707 presolver is disabled.)\\
|
|
alpar@9
|
2708 \verb|GLP_ENOPFS| & Unable to start the search, because LP relaxation
|
|
alpar@9
|
2709 of the MIP problem instance has no primal feasible solution. (This code
|
|
alpar@9
|
2710 may appear only if the presolver is enabled.)\\
|
|
alpar@9
|
2711 \verb|GLP_ENODFS| & Unable to start the search, because LP relaxation
|
|
alpar@9
|
2712 of the MIP problem instance has no dual feasible solution. In other
|
|
alpar@9
|
2713 word, this code means that if the LP relaxation has at least one primal
|
|
alpar@9
|
2714 feasible solution, its optimal solution is unbounded, so if the MIP
|
|
alpar@9
|
2715 problem has at least one integer feasible solution, its (integer)
|
|
alpar@9
|
2716 optimal solution is also unbounded. (This code may appear only if the
|
|
alpar@9
|
2717 presolver is enabled.)\\
|
|
alpar@9
|
2718 \verb|GLP_EFAIL| & The search was prematurely terminated due to the
|
|
alpar@9
|
2719 solver failure.\\
|
|
alpar@9
|
2720 \verb|GLP_EMIPGAP| & The search was prematurely terminated, because the
|
|
alpar@9
|
2721 relative mip gap tolerance has been reached.\\
|
|
alpar@9
|
2722 \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
|
|
alpar@9
|
2723 time limit has been exceeded.\\
|
|
alpar@9
|
2724 \verb|GLP_ESTOP| & The search was prematurely terminated by application.
|
|
alpar@9
|
2725 (This code may appear only if the advanced solver interface is used.)\\
|
|
alpar@9
|
2726 \end{tabular}
|
|
alpar@9
|
2727
|
|
alpar@9
|
2728 \subsubsection*{Built-in MIP presolver}
|
|
alpar@9
|
2729
|
|
alpar@9
|
2730 The branch-and-cut solver has {\it built-in MIP presolver}. It is
|
|
alpar@9
|
2731 a subprogram that transforms the original MIP problem specified in the
|
|
alpar@9
|
2732 problem object to an equivalent MIP problem, which may be easier for
|
|
alpar@9
|
2733 solving with the branch-and-cut method than the original one. For
|
|
alpar@9
|
2734 example, the presolver can remove redundant constraints and variables,
|
|
alpar@9
|
2735 whose optimal values are known, perform bound and coefficient reduction,
|
|
alpar@9
|
2736 etc. Once the transformed MIP problem has been solved, the presolver
|
|
alpar@9
|
2737 transforms its solution back to corresponding solution of the original
|
|
alpar@9
|
2738 problem.
|
|
alpar@9
|
2739
|
|
alpar@9
|
2740 Presolving is an optional feature of the routine \verb|glp_intopt|, and
|
|
alpar@9
|
2741 by default it is disabled. In order to enable the MIP presolver, the
|
|
alpar@9
|
2742 control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
|
|
alpar@9
|
2743 paragraph ``Control parameters'' below).
|
|
alpar@9
|
2744
|
|
alpar@9
|
2745 \subsubsection*{Advanced solver interface}
|
|
alpar@9
|
2746
|
|
alpar@9
|
2747 The routine \verb|glp_intopt| allows the user to control the
|
|
alpar@9
|
2748 branch-and-cut search by passing to the solver a user-defined callback
|
|
alpar@9
|
2749 routine. For more details see Chapter ``Branch-and-Cut API Routines''.
|
|
alpar@9
|
2750
|
|
alpar@9
|
2751 \subsubsection*{Terminal output}
|
|
alpar@9
|
2752
|
|
alpar@9
|
2753 Solving a MIP problem may take a long time, so the solver reports some
|
|
alpar@9
|
2754 information about best known solutions, which is sent to the terminal.
|
|
alpar@9
|
2755 This information has the following format:
|
|
alpar@9
|
2756
|
|
alpar@9
|
2757 \begin{verbatim}
|
|
alpar@9
|
2758 +nnn: mip = xxx <rho> yyy gap (ppp; qqq)
|
|
alpar@9
|
2759 \end{verbatim}
|
|
alpar@9
|
2760
|
|
alpar@9
|
2761 \noindent
|
|
alpar@9
|
2762 where: `\verb|nnn|' is the simplex iteration number; `\verb|xxx|' is a
|
|
alpar@9
|
2763 value of the objective function for the best known integer feasible
|
|
alpar@9
|
2764 solution (if no integer feasible solution has been found yet,
|
|
alpar@9
|
2765 `\verb|xxx|' is the text `\verb|not found yet|'); `\verb|rho|' is the
|
|
alpar@9
|
2766 string `\verb|>=|' (in case of minimization) or `\verb|<=|' (in case of
|
|
alpar@9
|
2767 maximization); `\verb|yyy|' is a global bound for exact integer optimum
|
|
alpar@9
|
2768 (i.e. the exact integer optimum is always in the range from `\verb|xxx|'
|
|
alpar@9
|
2769 to `\verb|yyy|'); `\verb|gap|' is the relative mip gap, in percents,
|
|
alpar@9
|
2770 computed as $gap=|xxx-yyy|/(|xxx|+{\tt DBL\_EPSILON})\cdot 100\%$ (if
|
|
alpar@9
|
2771 $gap$ is greater than $999.9\%$, it is not printed); `\verb|ppp|' is the
|
|
alpar@9
|
2772 number of subproblems in the active list, `\verb|qqq|' is the number of
|
|
alpar@9
|
2773 subproblems which have been already fathomed and therefore removed from
|
|
alpar@9
|
2774 the branch-and-bound search tree.
|
|
alpar@9
|
2775
|
|
alpar@9
|
2776 \subsubsection{Control parameters}
|
|
alpar@9
|
2777
|
|
alpar@9
|
2778 This paragraph describes all control parameters currently used in the
|
|
alpar@9
|
2779 MIP solver. Symbolic names of control parameters are names of
|
|
alpar@9
|
2780 corresponding members in the structure \verb|glp_iocp|.
|
|
alpar@9
|
2781
|
|
alpar@9
|
2782 \medskip
|
|
alpar@9
|
2783
|
|
alpar@9
|
2784 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2785 \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
|
|
alpar@9
|
2786 \\
|
|
alpar@9
|
2787 &Message level for terminal output:\\
|
|
alpar@9
|
2788 &\verb|GLP_MSG_OFF|---no output;\\
|
|
alpar@9
|
2789 &\verb|GLP_MSG_ERR|---error and warning messages only;\\
|
|
alpar@9
|
2790 &\verb|GLP_MSG_ON |---normal output;\\
|
|
alpar@9
|
2791 &\verb|GLP_MSG_ALL|---full output (including informational messages).
|
|
alpar@9
|
2792 \\
|
|
alpar@9
|
2793 \end{tabular}
|
|
alpar@9
|
2794
|
|
alpar@9
|
2795 \medskip
|
|
alpar@9
|
2796
|
|
alpar@9
|
2797 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2798 \multicolumn{2}{@{}l}{{\tt int br\_tech} (default: {\tt GLP\_BR\_DTH})}
|
|
alpar@9
|
2799 \\
|
|
alpar@9
|
2800 &Branching technique option:\\
|
|
alpar@9
|
2801 &\verb|GLP_BR_FFV|---first fractional variable;\\
|
|
alpar@9
|
2802 &\verb|GLP_BR_LFV|---last fractional variable;\\
|
|
alpar@9
|
2803 &\verb|GLP_BR_MFV|---most fractional variable;\\
|
|
alpar@9
|
2804 &\verb|GLP_BR_DTH|---heuristic by Driebeck and Tomlin;\\
|
|
alpar@9
|
2805 &\verb|GLP_BR_PCH|---hybrid pseudocost heuristic.\\
|
|
alpar@9
|
2806 \end{tabular}
|
|
alpar@9
|
2807
|
|
alpar@9
|
2808 \medskip
|
|
alpar@9
|
2809
|
|
alpar@9
|
2810 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2811 \multicolumn{2}{@{}l}{{\tt int bt\_tech} (default: {\tt GLP\_BT\_BLB})}
|
|
alpar@9
|
2812 \\
|
|
alpar@9
|
2813 &Backtracking technique option:\\
|
|
alpar@9
|
2814 &\verb|GLP_BT_DFS|---depth first search;\\
|
|
alpar@9
|
2815 &\verb|GLP_BT_BFS|---breadth first search;\\
|
|
alpar@9
|
2816 &\verb|GLP_BT_BLB|---best local bound;\\
|
|
alpar@9
|
2817 &\verb|GLP_BT_BPH|---best projection heuristic.\\
|
|
alpar@9
|
2818 \end{tabular}
|
|
alpar@9
|
2819
|
|
alpar@9
|
2820 \medskip
|
|
alpar@9
|
2821
|
|
alpar@9
|
2822 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2823 \multicolumn{2}{@{}l}{{\tt int pp\_tech} (default: {\tt GLP\_PP\_ALL})}
|
|
alpar@9
|
2824 \\
|
|
alpar@9
|
2825 &Preprocessing technique option:\\
|
|
alpar@9
|
2826 &\verb|GLP_PP_NONE|---disable preprocessing;\\
|
|
alpar@9
|
2827 &\verb|GLP_PP_ROOT|---perform preprocessing only on the root level;\\
|
|
alpar@9
|
2828 &\verb|GLP_PP_ALL |---perform preprocessing on all levels.\\
|
|
alpar@9
|
2829 \end{tabular}
|
|
alpar@9
|
2830
|
|
alpar@9
|
2831 \medskip
|
|
alpar@9
|
2832
|
|
alpar@9
|
2833 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2834 \multicolumn{2}{@{}l}{{\tt int fp\_heur} (default: {\tt GLP\_OFF})}
|
|
alpar@9
|
2835 \\
|
|
alpar@9
|
2836 &Feasibility pump heuristic option:\\
|
|
alpar@9
|
2837 &\verb|GLP_ON |---enable applying the feasibility pump heuristic;\\
|
|
alpar@9
|
2838 &\verb|GLP_OFF|---disable applying the feasibility pump heuristic.\\
|
|
alpar@9
|
2839 \end{tabular}
|
|
alpar@9
|
2840
|
|
alpar@9
|
2841 \medskip
|
|
alpar@9
|
2842
|
|
alpar@9
|
2843 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2844 \multicolumn{2}{@{}l}{{\tt int gmi\_cuts} (default: {\tt GLP\_OFF})}\\
|
|
alpar@9
|
2845 &Gomory's mixed integer cut option:\\
|
|
alpar@9
|
2846 &\verb|GLP_ON |---enable generating Gomory's cuts;\\
|
|
alpar@9
|
2847 &\verb|GLP_OFF|---disable generating Gomory's cuts.\\
|
|
alpar@9
|
2848 \end{tabular}
|
|
alpar@9
|
2849
|
|
alpar@9
|
2850 \medskip
|
|
alpar@9
|
2851
|
|
alpar@9
|
2852 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2853 \multicolumn{2}{@{}l}{{\tt int mir\_cuts} (default: {\tt GLP\_OFF})}\\
|
|
alpar@9
|
2854 &Mixed integer rounding (MIR) cut option:\\
|
|
alpar@9
|
2855 &\verb|GLP_ON |---enable generating MIR cuts;\\
|
|
alpar@9
|
2856 &\verb|GLP_OFF|---disable generating MIR cuts.\\
|
|
alpar@9
|
2857 \end{tabular}
|
|
alpar@9
|
2858
|
|
alpar@9
|
2859 \medskip
|
|
alpar@9
|
2860
|
|
alpar@9
|
2861 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2862 \multicolumn{2}{@{}l}{{\tt int cov\_cuts} (default: {\tt GLP\_OFF})}\\
|
|
alpar@9
|
2863 &Mixed cover cut option:\\
|
|
alpar@9
|
2864 &\verb|GLP_ON |---enable generating mixed cover cuts;\\
|
|
alpar@9
|
2865 &\verb|GLP_OFF|---disable generating mixed cover cuts.\\
|
|
alpar@9
|
2866 \end{tabular}
|
|
alpar@9
|
2867
|
|
alpar@9
|
2868 \medskip
|
|
alpar@9
|
2869
|
|
alpar@9
|
2870 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2871 \multicolumn{2}{@{}l}{{\tt int clq\_cuts} (default: {\tt GLP\_OFF})}\\
|
|
alpar@9
|
2872 &Clique cut option:\\
|
|
alpar@9
|
2873 &\verb|GLP_ON |---enable generating clique cuts;\\
|
|
alpar@9
|
2874 &\verb|GLP_OFF|---disable generating clique cuts.\\
|
|
alpar@9
|
2875 \end{tabular}
|
|
alpar@9
|
2876
|
|
alpar@9
|
2877 \medskip
|
|
alpar@9
|
2878
|
|
alpar@9
|
2879 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2880 \multicolumn{2}{@{}l}{{\tt double tol\_int} (default: {\tt 1e-5})}\\
|
|
alpar@9
|
2881 &Absolute tolerance used to check if optimal solution to the current LP
|
|
alpar@9
|
2882 relaxation is integer feasible. (Do not change this parameter without
|
|
alpar@9
|
2883 detailed understanding its purpose.)\\
|
|
alpar@9
|
2884 \end{tabular}
|
|
alpar@9
|
2885
|
|
alpar@9
|
2886 \medskip
|
|
alpar@9
|
2887
|
|
alpar@9
|
2888 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2889 \multicolumn{2}{@{}l}{{\tt double tol\_obj} (default: {\tt 1e-7})}\\
|
|
alpar@9
|
2890 &Relative tolerance used to check if the objective value in optimal
|
|
alpar@9
|
2891 solution to the current LP relaxation is not better than in the best
|
|
alpar@9
|
2892 known integer feasible solution. (Do not change this parameter without
|
|
alpar@9
|
2893 detailed understanding its purpose.)\\
|
|
alpar@9
|
2894 \end{tabular}
|
|
alpar@9
|
2895
|
|
alpar@9
|
2896 \medskip
|
|
alpar@9
|
2897
|
|
alpar@9
|
2898 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2899 \multicolumn{2}{@{}l}{{\tt double mip\_gap} (default: {\tt 0.0})}\\
|
|
alpar@9
|
2900 &The relative mip gap tolerance. If the relative mip gap for currently
|
|
alpar@9
|
2901 known best integer feasible solution falls below this tolerance, the
|
|
alpar@9
|
2902 solver terminates the search. This allows obtainig suboptimal integer
|
|
alpar@9
|
2903 feasible solutions if solving the problem to optimality takes too long
|
|
alpar@9
|
2904 time.\\
|
|
alpar@9
|
2905 \end{tabular}
|
|
alpar@9
|
2906
|
|
alpar@9
|
2907 \medskip
|
|
alpar@9
|
2908
|
|
alpar@9
|
2909 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2910 \multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}\\
|
|
alpar@9
|
2911 &Searching time limit, in milliseconds.\\
|
|
alpar@9
|
2912 \end{tabular}
|
|
alpar@9
|
2913
|
|
alpar@9
|
2914 \medskip
|
|
alpar@9
|
2915
|
|
alpar@9
|
2916 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2917 \multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 5000})}\\
|
|
alpar@9
|
2918 &Output frequency, in milliseconds. This parameter specifies how
|
|
alpar@9
|
2919 frequently the solver sends information about the solution process to
|
|
alpar@9
|
2920 the terminal.\\
|
|
alpar@9
|
2921 \end{tabular}
|
|
alpar@9
|
2922
|
|
alpar@9
|
2923 \medskip
|
|
alpar@9
|
2924
|
|
alpar@9
|
2925 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2926 \multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 10000})}\\
|
|
alpar@9
|
2927 &Output delay, in milliseconds. This parameter specifies how long the
|
|
alpar@9
|
2928 solver should delay sending information about solution of the current
|
|
alpar@9
|
2929 LP relaxation with the simplex method to the terminal.\\
|
|
alpar@9
|
2930 \end{tabular}
|
|
alpar@9
|
2931
|
|
alpar@9
|
2932 \medskip
|
|
alpar@9
|
2933
|
|
alpar@9
|
2934 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2935 \multicolumn{2}{@{}l}
|
|
alpar@9
|
2936 {{\tt void (*cb\_func)(glp\_tree *tree, void *info)}
|
|
alpar@9
|
2937 (default: {\tt NULL})}\\
|
|
alpar@9
|
2938 &Entry point to the user-defined callback routine. \verb|NULL| means
|
|
alpar@9
|
2939 the advanced solver interface is not used. For more details see Chapter
|
|
alpar@9
|
2940 ``Branch-and-Cut API Routines''.\\
|
|
alpar@9
|
2941 \end{tabular}
|
|
alpar@9
|
2942
|
|
alpar@9
|
2943 \medskip
|
|
alpar@9
|
2944
|
|
alpar@9
|
2945 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2946 \multicolumn{2}{@{}l}{{\tt void *cb\_info} (default: {\tt NULL})}\\
|
|
alpar@9
|
2947 &Transit pointer passed to the routine \verb|cb_func| (see above).\\
|
|
alpar@9
|
2948 \end{tabular}
|
|
alpar@9
|
2949
|
|
alpar@9
|
2950 \medskip
|
|
alpar@9
|
2951
|
|
alpar@9
|
2952 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2953 \multicolumn{2}{@{}l}{{\tt int cb\_size} (default: {\tt 0})}\\
|
|
alpar@9
|
2954 &The number of extra (up to 256) bytes allocated for each node of the
|
|
alpar@9
|
2955 branch-and-bound tree to store application-specific data. On creating
|
|
alpar@9
|
2956 a node these bytes are initialized by binary zeros.\\
|
|
alpar@9
|
2957 \end{tabular}
|
|
alpar@9
|
2958
|
|
alpar@9
|
2959 \medskip
|
|
alpar@9
|
2960
|
|
alpar@9
|
2961 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2962 \multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}\\
|
|
alpar@9
|
2963 &MIP presolver option:\\
|
|
alpar@9
|
2964 &\verb|GLP_ON |---enable using the MIP presolver;\\
|
|
alpar@9
|
2965 &\verb|GLP_OFF|---disable using the MIP presolver.\\
|
|
alpar@9
|
2966 \end{tabular}
|
|
alpar@9
|
2967
|
|
alpar@9
|
2968 \medskip
|
|
alpar@9
|
2969
|
|
alpar@9
|
2970 \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
|
|
alpar@9
|
2971 \multicolumn{2}{@{}l}{{\tt int binarize} (default: {\tt GLP\_OFF})}\\
|
|
alpar@9
|
2972 &Binarization option (used only if the presolver is enabled):\\
|
|
alpar@9
|
2973 &\verb|GLP_ON |---replace general integer variables by binary ones;\\
|
|
alpar@9
|
2974 &\verb|GLP_OFF|---do not use binarization.\\
|
|
alpar@9
|
2975 \end{tabular}
|
|
alpar@9
|
2976
|
|
alpar@9
|
2977 \subsection{glp\_init\_iocp---initialize integer optimizer control
|
|
alpar@9
|
2978 parameters}
|
|
alpar@9
|
2979
|
|
alpar@9
|
2980 \subsubsection*{Synopsis}
|
|
alpar@9
|
2981
|
|
alpar@9
|
2982 \begin{verbatim}
|
|
alpar@9
|
2983 void glp_init_iocp(glp_iocp *parm);
|
|
alpar@9
|
2984 \end{verbatim}
|
|
alpar@9
|
2985
|
|
alpar@9
|
2986 \subsubsection*{Description}
|
|
alpar@9
|
2987
|
|
alpar@9
|
2988 The routine \verb|glp_init_iocp| initializes control parameters, which
|
|
alpar@9
|
2989 are used by the branch-and-cut solver, with default values.
|
|
alpar@9
|
2990
|
|
alpar@9
|
2991 Default values of the control parameters are stored in a \verb|glp_iocp|
|
|
alpar@9
|
2992 structure, which the parameter \verb|parm| points to.
|
|
alpar@9
|
2993
|
|
alpar@9
|
2994 \subsection{glp\_mip\_status---determine status of MIP solution}
|
|
alpar@9
|
2995
|
|
alpar@9
|
2996 \subsubsection*{Synopsis}
|
|
alpar@9
|
2997
|
|
alpar@9
|
2998 \begin{verbatim}
|
|
alpar@9
|
2999 int glp_mip_status(glp_prob *mip);
|
|
alpar@9
|
3000 \end{verbatim}
|
|
alpar@9
|
3001
|
|
alpar@9
|
3002 \subsubsection*{Returns}
|
|
alpar@9
|
3003
|
|
alpar@9
|
3004 The routine \verb|glp_mip_status| reports the status of a MIP solution
|
|
alpar@9
|
3005 found by the MIP solver as follows:
|
|
alpar@9
|
3006
|
|
alpar@9
|
3007 \smallskip
|
|
alpar@9
|
3008
|
|
alpar@9
|
3009 \begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
|
|
alpar@9
|
3010 \verb|GLP_UNDEF| & MIP solution is undefined. \\
|
|
alpar@9
|
3011 \verb|GLP_OPT| & MIP solution is integer optimal. \\
|
|
alpar@9
|
3012 \verb|GLP_FEAS| & MIP solution is integer feasible, however, its
|
|
alpar@9
|
3013 optimality (or non-optimality) has not been proven, perhaps due to
|
|
alpar@9
|
3014 premature termination of the search. \\
|
|
alpar@9
|
3015 \end{tabular}
|
|
alpar@9
|
3016
|
|
alpar@9
|
3017 \begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
|
|
alpar@9
|
3018 \verb|GLP_NOFEAS| & problem has no integer feasible solution (proven by
|
|
alpar@9
|
3019 the solver). \\
|
|
alpar@9
|
3020 \end{tabular}
|
|
alpar@9
|
3021
|
|
alpar@9
|
3022 \subsection{glp\_mip\_obj\_val---retrieve objective value}
|
|
alpar@9
|
3023
|
|
alpar@9
|
3024 \subsubsection*{Synopsis}
|
|
alpar@9
|
3025
|
|
alpar@9
|
3026 \begin{verbatim}
|
|
alpar@9
|
3027 double glp_mip_obj_val(glp_prob *mip);
|
|
alpar@9
|
3028 \end{verbatim}
|
|
alpar@9
|
3029
|
|
alpar@9
|
3030 \subsubsection*{Returns}
|
|
alpar@9
|
3031
|
|
alpar@9
|
3032 The routine \verb|glp_mip_obj_val| returns value of the objective
|
|
alpar@9
|
3033 function for MIP solution.
|
|
alpar@9
|
3034
|
|
alpar@9
|
3035 \subsection{glp\_mip\_row\_val---retrieve row value}
|
|
alpar@9
|
3036
|
|
alpar@9
|
3037 \subsubsection*{Synopsis}
|
|
alpar@9
|
3038
|
|
alpar@9
|
3039 \begin{verbatim}
|
|
alpar@9
|
3040 double glp_mip_row_val(glp_prob *mip, int i);
|
|
alpar@9
|
3041 \end{verbatim}
|
|
alpar@9
|
3042
|
|
alpar@9
|
3043 \subsubsection*{Returns}
|
|
alpar@9
|
3044
|
|
alpar@9
|
3045 The routine \verb|glp_mip_row_val| returns value of the auxiliary
|
|
alpar@9
|
3046 variable associated with \verb|i|-th row for MIP solution.
|
|
alpar@9
|
3047
|
|
alpar@9
|
3048 \subsection{glp\_mip\_col\_val---retrieve column value}
|
|
alpar@9
|
3049
|
|
alpar@9
|
3050 \subsubsection*{Synopsis}
|
|
alpar@9
|
3051
|
|
alpar@9
|
3052 \begin{verbatim}
|
|
alpar@9
|
3053 double glp_mip_col_val(glp_prob *mip, int j);
|
|
alpar@9
|
3054 \end{verbatim}
|
|
alpar@9
|
3055
|
|
alpar@9
|
3056 \subsubsection*{Returns}
|
|
alpar@9
|
3057
|
|
alpar@9
|
3058 The routine \verb|glp_mip_col_val| returns value of the structural
|
|
alpar@9
|
3059 variable associated with \verb|j|-th column for MIP solution.
|
|
alpar@9
|
3060
|
|
alpar@9
|
3061 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
alpar@9
|
3062
|
|
alpar@9
|
3063 \newpage
|
|
alpar@9
|
3064
|
|
alpar@9
|
3065 \section{Additional routines}
|
|
alpar@9
|
3066
|
|
alpar@9
|
3067 \subsection{lpx\_check\_kkt---check Karush-Kuhn-Tucker optimality
|
|
alpar@9
|
3068 conditions}
|
|
alpar@9
|
3069
|
|
alpar@9
|
3070 \subsubsection*{Synopsis}
|
|
alpar@9
|
3071
|
|
alpar@9
|
3072 \begin{verbatim}
|
|
alpar@9
|
3073 void lpx_check_kkt(glp_prob *lp, int scaled, LPXKKT *kkt);
|
|
alpar@9
|
3074 \end{verbatim}
|
|
alpar@9
|
3075
|
|
alpar@9
|
3076 \subsubsection*{Description}
|
|
alpar@9
|
3077
|
|
alpar@9
|
3078 The routine \verb|lpx_check_kkt| checks Karush-Kuhn-Tucker optimality
|
|
alpar@9
|
3079 conditions for basic solution. It is assumed that both primal and dual
|
|
alpar@9
|
3080 components of basic solution are valid.
|
|
alpar@9
|
3081
|
|
alpar@9
|
3082 If the parameter \verb|scaled| is zero, the optimality conditions are
|
|
alpar@9
|
3083 checked for the original, unscaled LP problem. Otherwise, if the
|
|
alpar@9
|
3084 parameter \verb|scaled| is non-zero, the routine checks the conditions
|
|
alpar@9
|
3085 for an internally scaled LP problem.
|
|
alpar@9
|
3086
|
|
alpar@9
|
3087 The parameter \verb|kkt| is a pointer to the structure \verb|LPXKKT|,
|
|
alpar@9
|
3088 to which the routine stores results of the check. Members of this
|
|
alpar@9
|
3089 structure are shown in the table below.
|
|
alpar@9
|
3090
|
|
alpar@9
|
3091 \begin{table}[h]
|
|
alpar@9
|
3092 \begin{center}
|
|
alpar@9
|
3093 \begin{tabular}{@{}c|l|l@{}}
|
|
alpar@9
|
3094 Condition & Member & Comment \\
|
|
alpar@9
|
3095 \hline
|
|
alpar@9
|
3096 (KKT.PE) & \verb|pe_ae_max| &
|
|
alpar@9
|
3097 Largest absolute error \\
|
|
alpar@9
|
3098 & \verb|pe_ae_row| &
|
|
alpar@9
|
3099 Number of row with largest absolute error \\
|
|
alpar@9
|
3100 & \verb|pe_re_max| &
|
|
alpar@9
|
3101 Largest relative error \\
|
|
alpar@9
|
3102 & \verb|pe_re_row| &
|
|
alpar@9
|
3103 Number of row with largest relative error \\
|
|
alpar@9
|
3104 & \verb|pe_quality| &
|
|
alpar@9
|
3105 Quality of primal solution \\
|
|
alpar@9
|
3106 \hline
|
|
alpar@9
|
3107 (KKT.PB) & \verb|pb_ae_max| &
|
|
alpar@9
|
3108 Largest absolute error \\
|
|
alpar@9
|
3109 & \verb|pb_ae_ind| &
|
|
alpar@9
|
3110 Number of variable with largest absolute error \\
|
|
alpar@9
|
3111 & \verb|pb_re_max| &
|
|
alpar@9
|
3112 Largest relative error \\
|
|
alpar@9
|
3113 & \verb|pb_re_ind| &
|
|
alpar@9
|
3114 Number of variable with largest relative error \\
|
|
alpar@9
|
3115 & \verb|pb_quality| &
|
|
alpar@9
|
3116 Quality of primal feasibility \\
|
|
alpar@9
|
3117 \hline
|
|
alpar@9
|
3118 (KKT.DE) & \verb|de_ae_max| &
|
|
alpar@9
|
3119 Largest absolute error \\
|
|
alpar@9
|
3120 & \verb|de_ae_col| &
|
|
alpar@9
|
3121 Number of column with largest absolute error \\
|
|
alpar@9
|
3122 & \verb|de_re_max| &
|
|
alpar@9
|
3123 Largest relative error \\
|
|
alpar@9
|
3124 & \verb|de_re_col| &
|
|
alpar@9
|
3125 Number of column with largest relative error \\
|
|
alpar@9
|
3126 & \verb|de_quality| &
|
|
alpar@9
|
3127 Quality of dual solution \\
|
|
alpar@9
|
3128 \hline
|
|
alpar@9
|
3129 (KKT.DB) & \verb|db_ae_max| &
|
|
alpar@9
|
3130 Largest absolute error \\
|
|
alpar@9
|
3131 & \verb|db_ae_ind| &
|
|
alpar@9
|
3132 Number of variable with largest absolute error \\
|
|
alpar@9
|
3133 & \verb|db_re_max| &
|
|
alpar@9
|
3134 Largest relative error \\
|
|
alpar@9
|
3135 & \verb|db_re_ind| &
|
|
alpar@9
|
3136 Number of variable with largest relative error \\
|
|
alpar@9
|
3137 & \verb|db_quality| &
|
|
alpar@9
|
3138 Quality of dual feasibility \\
|
|
alpar@9
|
3139 \end{tabular}
|
|
alpar@9
|
3140 \end{center}
|
|
alpar@9
|
3141 \end{table}
|
|
alpar@9
|
3142
|
|
alpar@9
|
3143 The routine performs all computations using only components of the
|
|
alpar@9
|
3144 given LP problem and the current basic solution.
|
|
alpar@9
|
3145
|
|
alpar@9
|
3146 \subsubsection*{Background}
|
|
alpar@9
|
3147
|
|
alpar@9
|
3148 The first condition checked by the routine is:
|
|
alpar@9
|
3149 $$x_R - A x_S = 0, \eqno{\rm (KKT.PE)}$$
|
|
alpar@9
|
3150 where $x_R$ is the subvector of auxiliary variables (rows), $x_S$ is the
|
|
alpar@9
|
3151 subvector of structural variables (columns), $A$ is the constraint
|
|
alpar@9
|
3152 matrix. This condition expresses the requirement that all primal
|
|
alpar@9
|
3153 variables must satisfy to the system of equality constraints of the
|
|
alpar@9
|
3154 original LP problem. In case of exact arithmetic this condition would be
|
|
alpar@9
|
3155 satisfied for any basic solution; however, in case of inexact
|
|
alpar@9
|
3156 (floating-point) arithmetic, this condition shows how accurate the
|
|
alpar@9
|
3157 primal basic solution is, that depends on accuracy of a representation
|
|
alpar@9
|
3158 of the basis matrix used by the simplex method routines.
|
|
alpar@9
|
3159
|
|
alpar@9
|
3160 The second condition checked by the routine is:
|
|
alpar@9
|
3161 $$l_k \leq x_k \leq u_k {\rm \ \ \ for\ all}\ k=1,\dots,m+n,
|
|
alpar@9
|
3162 \eqno{\rm (KKT.PB)}$$
|
|
alpar@9
|
3163 where $x_k$ is auxiliary ($1\leq k\leq m$) or structural
|
|
alpar@9
|
3164 ($m+1\leq k\leq m+n$) variable, $l_k$ and $u_k$ are, respectively,
|
|
alpar@9
|
3165 lower and upper bounds of the variable $x_k$ (including cases of
|
|
alpar@9
|
3166 infinite bounds). This condition expresses the requirement that all
|
|
alpar@9
|
3167 primal variables must satisfy to bound constraints of the original LP
|
|
alpar@9
|
3168 problem. Since in case of basic solution all non-basic variables are
|
|
alpar@9
|
3169 placed on their bounds, actually the condition (KKT.PB) needs to be
|
|
alpar@9
|
3170 checked for basic variables only. If the primal basic solution has
|
|
alpar@9
|
3171 sufficient accuracy, this condition shows primal feasibility of the
|
|
alpar@9
|
3172 solution.
|
|
alpar@9
|
3173
|
|
alpar@9
|
3174 The third condition checked by the routine is:
|
|
alpar@9
|
3175 $${\rm grad}\;Z = c = (\tilde{A})^T \pi + d,$$
|
|
alpar@9
|
3176 where $Z$ is the objective function, $c$ is the vector of objective
|
|
alpar@9
|
3177 coefficients, $(\tilde{A})^T$ is a matrix transposed to the expanded
|
|
alpar@9
|
3178 constraint matrix $\tilde{A} = (I|-A)$, $\pi$ is a vector of Lagrange
|
|
alpar@9
|
3179 multipliers that correspond to equality constraints of the original LP
|
|
alpar@9
|
3180 problem, $d$ is a vector of Lagrange multipliers that correspond to
|
|
alpar@9
|
3181 bound constraints for all (auxiliary and structural) variables of the
|
|
alpar@9
|
3182 original LP problem. Geometrically the third condition expresses the
|
|
alpar@9
|
3183 requirement that the gradient of the objective function must belong to
|
|
alpar@9
|
3184 the orthogonal complement of a linear subspace defined by the equality
|
|
alpar@9
|
3185 and active bound constraints, i.e. that the gradient must be a linear
|
|
alpar@9
|
3186 combination of normals to the constraint planes, where Lagrange
|
|
alpar@9
|
3187 multipliers $\pi$ and $d$ are coefficients of that linear combination.
|
|
alpar@9
|
3188
|
|
alpar@9
|
3189 To eliminate the vector $\pi$ the third condition can be rewritten as:
|
|
alpar@9
|
3190 $$
|
|
alpar@9
|
3191 \left(\begin{array}{@{}c@{}}I \\ -A^T\end{array}\right) \pi =
|
|
alpar@9
|
3192 \left(\begin{array}{@{}c@{}}d_R \\ d_S\end{array}\right) +
|
|
alpar@9
|
3193 \left(\begin{array}{@{}c@{}}c_R \\ c_S\end{array}\right),
|
|
alpar@9
|
3194 $$
|
|
alpar@9
|
3195 or, equivalently:
|
|
alpar@9
|
3196 $$
|
|
alpar@9
|
3197 \begin{array}{r@{}c@{}c}
|
|
alpar@9
|
3198 \pi + d_R&\ =\ &c_R, \\
|
|
alpar@9
|
3199 -A^T\pi + d_S&\ =\ &c_S. \\
|
|
alpar@9
|
3200 \end{array}
|
|
alpar@9
|
3201 $$
|
|
alpar@9
|
3202 Then substituting the vector $\pi$ from the first equation into the
|
|
alpar@9
|
3203 second one we have:
|
|
alpar@9
|
3204 $$A^T (d_R - c_R) + (d_S - c_S) = 0, \eqno{\rm (KKT.DE)}$$
|
|
alpar@9
|
3205 where $d_R$ is the subvector of reduced costs of auxiliary variables
|
|
alpar@9
|
3206 (rows), $d_S$ is the subvector of reduced costs of structural variables
|
|
alpar@9
|
3207 (columns), $c_R$ and $c_S$ are subvectors of objective coefficients at,
|
|
alpar@9
|
3208 respectively, auxiliary and structural variables, $A^T$ is a matrix
|
|
alpar@9
|
3209 transposed to the constraint matrix of the original LP problem. In case
|
|
alpar@9
|
3210 of exact arithmetic this condition would be satisfied for any basic
|
|
alpar@9
|
3211 solution; however, in case of inexact (floating-point) arithmetic, this
|
|
alpar@9
|
3212 condition shows how accurate the dual basic solution is, that depends on
|
|
alpar@9
|
3213 accuracy of a representation of the basis matrix used by the simplex
|
|
alpar@9
|
3214 method routines.
|
|
alpar@9
|
3215
|
|
alpar@9
|
3216 The last, fourth condition checked by the routine is (KKT.DB):
|
|
alpar@9
|
3217
|
|
alpar@9
|
3218 \medskip
|
|
alpar@9
|
3219
|
|
alpar@9
|
3220 \begin{tabular}{r@{}c@{}ll}
|
|
alpar@9
|
3221 &$\ d_k\ $& $=0,$&if $x_k$ is basic or free non-basic variable \\
|
|
alpar@9
|
3222 $0\leq$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic on its lower
|
|
alpar@9
|
3223 (minimization) \\
|
|
alpar@9
|
3224 &&&or upper (maximization) bound \\
|
|
alpar@9
|
3225 $-\infty<$&$\ d_k\ $&$\leq 0$&if $x_k$ is non-basic on its upper
|
|
alpar@9
|
3226 (minimization) \\
|
|
alpar@9
|
3227 &&&or lower (maximization) bound \\
|
|
alpar@9
|
3228 $-\infty<$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic fixed variable \\
|
|
alpar@9
|
3229 \end{tabular}
|
|
alpar@9
|
3230
|
|
alpar@9
|
3231 \medskip
|
|
alpar@9
|
3232
|
|
alpar@9
|
3233 \noindent
|
|
alpar@9
|
3234 for all $k=1,\dots,m+n$, where $d_k$ is a reduced cost (Lagrange
|
|
alpar@9
|
3235 multiplier) of auxiliary ($1\leq k\leq m$) or structural
|
|
alpar@9
|
3236 ($m+1\leq k\leq m+n$) variable $x_k$. Geometrically this condition
|
|
alpar@9
|
3237 expresses the requirement that constraints of the original problem must
|
|
alpar@9
|
3238 "hold" the point preventing its movement along the anti-gradient (in
|
|
alpar@9
|
3239 case of minimization) or the gradient (in case of maximization) of the
|
|
alpar@9
|
3240 objective function. Since in case of basic solution reduced costs of
|
|
alpar@9
|
3241 all basic variables are placed on their (zero) bounds, actually the
|
|
alpar@9
|
3242 condition (KKT.DB) needs to be checked for non-basic variables only.
|
|
alpar@9
|
3243 If the dual basic solution has sufficient accuracy, this condition shows
|
|
alpar@9
|
3244 dual feasibility of the solution.
|
|
alpar@9
|
3245
|
|
alpar@9
|
3246 Should note that the complete set of Karush-Kuhn-Tucker optimality
|
|
alpar@9
|
3247 conditions also includes the fifth, so called complementary slackness
|
|
alpar@9
|
3248 condition, which expresses the requirement that at least either a primal
|
|
alpar@9
|
3249 variable $x_k$ or its dual counterpart $d_k$ must be on its bound for
|
|
alpar@9
|
3250 all $k=1,\dots,m+n$. However, being always satisfied by definition for
|
|
alpar@9
|
3251 any basic solution that condition is not checked by the routine.
|
|
alpar@9
|
3252
|
|
alpar@9
|
3253 To check the first condition (KKT.PE) the routine computes a vector of
|
|
alpar@9
|
3254 residuals:
|
|
alpar@9
|
3255 $$g = x_R - A x_S,$$
|
|
alpar@9
|
3256 determines component of this vector that correspond to largest absolute
|
|
alpar@9
|
3257 and relative errors:
|
|
alpar@9
|
3258
|
|
alpar@9
|
3259 \medskip
|
|
alpar@9
|
3260
|
|
alpar@9
|
3261 \hspace{30mm}
|
|
alpar@9
|
3262 \verb|pe_ae_max| $\displaystyle{= \max_{1\leq i\leq m}|g_i|}$,
|
|
alpar@9
|
3263
|
|
alpar@9
|
3264 \medskip
|
|
alpar@9
|
3265
|
|
alpar@9
|
3266 \hspace{30mm}
|
|
alpar@9
|
3267 \verb|pe_re_max| $\displaystyle{= \max_{1\leq i\leq m}
|
|
alpar@9
|
3268 \frac{|g_i|}{1+|(x_R)_i|}}$,
|
|
alpar@9
|
3269
|
|
alpar@9
|
3270 \medskip
|
|
alpar@9
|
3271
|
|
alpar@9
|
3272 \noindent
|
|
alpar@9
|
3273 and stores these quantities and corresponding row indices to the
|
|
alpar@9
|
3274 structure \verb|LPXKKT|.
|
|
alpar@9
|
3275
|
|
alpar@9
|
3276 To check the second condition (KKT.PB) the routine computes a vector
|
|
alpar@9
|
3277 of residuals:
|
|
alpar@9
|
3278 $$
|
|
alpar@9
|
3279 h_k = \left\{
|
|
alpar@9
|
3280 \begin{array}{ll}
|
|
alpar@9
|
3281 0, & {\rm if}\ l_k \leq x_k \leq u_k \\
|
|
alpar@9
|
3282 x_k - l_k, & {\rm if}\ x_k < l_k \\
|
|
alpar@9
|
3283 x_k - u_k, & {\rm if}\ x_k > u_k \\
|
|
alpar@9
|
3284 \end{array}
|
|
alpar@9
|
3285 \right.
|
|
alpar@9
|
3286 $$
|
|
alpar@9
|
3287 for all $k=1,\dots,m+n$, determines components of this vector that
|
|
alpar@9
|
3288 correspond to largest absolute and relative errors:
|
|
alpar@9
|
3289
|
|
alpar@9
|
3290 \medskip
|
|
alpar@9
|
3291
|
|
alpar@9
|
3292 \hspace{30mm}
|
|
alpar@9
|
3293 \verb|pb_ae_max| $\displaystyle{= \max_{1\leq k \leq m+n}|h_k|}$,
|
|
alpar@9
|
3294
|
|
alpar@9
|
3295 \medskip
|
|
alpar@9
|
3296
|
|
alpar@9
|
3297 \hspace{30mm}
|
|
alpar@9
|
3298 \verb|pb_re_max| $\displaystyle{= \max_{1\leq k \leq m+n}
|
|
alpar@9
|
3299 \frac{|h_k|}{1+|x_k|}}$,
|
|
alpar@9
|
3300
|
|
alpar@9
|
3301 \medskip
|
|
alpar@9
|
3302
|
|
alpar@9
|
3303 \noindent
|
|
alpar@9
|
3304 and stores these quantities and corresponding variable indices to the
|
|
alpar@9
|
3305 structure \verb|LPXKKT|.
|
|
alpar@9
|
3306
|
|
alpar@9
|
3307 To check the third condition (KKT.DE) the routine computes a vector of
|
|
alpar@9
|
3308 residuals:
|
|
alpar@9
|
3309 $$u = A^T (d_R - c_R) + (d_S - c_S),$$
|
|
alpar@9
|
3310 determines components of this vector that correspond to largest
|
|
alpar@9
|
3311 absolute and relative errors:
|
|
alpar@9
|
3312
|
|
alpar@9
|
3313 \medskip
|
|
alpar@9
|
3314
|
|
alpar@9
|
3315 \hspace{30mm}
|
|
alpar@9
|
3316 \verb|de_ae_max| $\displaystyle{= \max_{1\leq j\leq n}|u_j|}$,
|
|
alpar@9
|
3317
|
|
alpar@9
|
3318 \medskip
|
|
alpar@9
|
3319
|
|
alpar@9
|
3320 \hspace{30mm}
|
|
alpar@9
|
3321 \verb|de_re_max| $\displaystyle{= \max_{1\leq j\leq n}
|
|
alpar@9
|
3322 \frac{|u_j|}{1+|(d_S)_j - (c_S)_j|}}$,
|
|
alpar@9
|
3323
|
|
alpar@9
|
3324 \medskip
|
|
alpar@9
|
3325
|
|
alpar@9
|
3326 \noindent
|
|
alpar@9
|
3327 and stores these quantities and corresponding column indices to the
|
|
alpar@9
|
3328 structure \verb|LPXKKT|.
|
|
alpar@9
|
3329
|
|
alpar@9
|
3330 To check the fourth condition (KKT.DB) the routine computes a vector
|
|
alpar@9
|
3331 of residuals:
|
|
alpar@9
|
3332
|
|
alpar@9
|
3333 $$
|
|
alpar@9
|
3334 v_k = \left\{
|
|
alpar@9
|
3335 \begin{array}{ll}
|
|
alpar@9
|
3336 0, & {\rm if}\ d_k\ {\rm has\ correct\ sign} \\
|
|
alpar@9
|
3337 d_k, & {\rm if}\ d_k\ {\rm has\ wrong\ sign} \\
|
|
alpar@9
|
3338 \end{array}
|
|
alpar@9
|
3339 \right.
|
|
alpar@9
|
3340 $$
|
|
alpar@9
|
3341 for all $k=1,\dots,m+n$, determines components of this vector that
|
|
alpar@9
|
3342 correspond to largest absolute and relative errors:
|
|
alpar@9
|
3343
|
|
alpar@9
|
3344 \medskip
|
|
alpar@9
|
3345
|
|
alpar@9
|
3346 \hspace{30mm}
|
|
alpar@9
|
3347 \verb|db_ae_max| $\displaystyle{= \max_{1\leq k\leq m+n}|v_k|}$,
|
|
alpar@9
|
3348
|
|
alpar@9
|
3349 \medskip
|
|
alpar@9
|
3350
|
|
alpar@9
|
3351 \hspace{30mm}
|
|
alpar@9
|
3352 \verb|db_re_max| $\displaystyle{= \max_{1\leq k\leq m+n}
|
|
alpar@9
|
3353 \frac{|v_k|}{1+|d_k - c_k|}}$,
|
|
alpar@9
|
3354
|
|
alpar@9
|
3355 \medskip
|
|
alpar@9
|
3356
|
|
alpar@9
|
3357 \noindent
|
|
alpar@9
|
3358 and stores these quantities and corresponding variable indices to the
|
|
alpar@9
|
3359 structure \verb|LPXKKT|.
|
|
alpar@9
|
3360
|
|
alpar@9
|
3361 Using the relative errors for all the four conditions listed above the
|
|
alpar@9
|
3362 routine
|
|
alpar@9
|
3363 \verb|lpx_check_kkt| also estimates a "quality" of the basic solution
|
|
alpar@9
|
3364 from the standpoint of these conditions and stores corresponding
|
|
alpar@9
|
3365 quality indicators to the structure \verb|LPXKKT|:
|
|
alpar@9
|
3366
|
|
alpar@9
|
3367 \verb|pe_quality|---quality of primal solution;
|
|
alpar@9
|
3368
|
|
alpar@9
|
3369 \verb|pb_quality|---quality of primal feasibility;
|
|
alpar@9
|
3370
|
|
alpar@9
|
3371 \verb|de_quality|---quality of dual solution;
|
|
alpar@9
|
3372
|
|
alpar@9
|
3373 \verb|db_quality|---quality of dual feasibility.
|
|
alpar@9
|
3374
|
|
alpar@9
|
3375 Each of these indicators is assigned to one of the following four
|
|
alpar@9
|
3376 values:
|
|
alpar@9
|
3377
|
|
alpar@9
|
3378 \verb|'H'| means high quality,
|
|
alpar@9
|
3379
|
|
alpar@9
|
3380 \verb|'M'| means medium quality,
|
|
alpar@9
|
3381
|
|
alpar@9
|
3382 \verb|'L'| means low quality, or
|
|
alpar@9
|
3383
|
|
alpar@9
|
3384 \verb|'?'| means wrong or infeasible solution.
|
|
alpar@9
|
3385
|
|
alpar@9
|
3386 If all the indicators show high or medium quality (for an internally
|
|
alpar@9
|
3387 scaled LP problem, i.e. when the parameter \verb|scaled| in a call to
|
|
alpar@9
|
3388 the routine \verb|lpx_check_kkt| is non-zero), the user can be sure that
|
|
alpar@9
|
3389 the obtained basic solution is quite accurate.
|
|
alpar@9
|
3390
|
|
alpar@9
|
3391 If some of the indicators show low quality, the solution can still be
|
|
alpar@9
|
3392 considered as relevant, though an additional analysis is needed
|
|
alpar@9
|
3393 depending on which indicator shows low quality.
|
|
alpar@9
|
3394
|
|
alpar@9
|
3395 If the indicator \verb|pe_quality| is assigned to \verb|'?'|, the
|
|
alpar@9
|
3396 primal solution is wrong. If the indicator \verb|de_quality| is assigned
|
|
alpar@9
|
3397 to \verb|'?'|, the dual solution is wrong.
|
|
alpar@9
|
3398
|
|
alpar@9
|
3399 If the indicator \verb|db_quality| is assigned to \verb|'?'| while
|
|
alpar@9
|
3400 other indicators show a good quality, this means that the current
|
|
alpar@9
|
3401 basic solution being primal feasible is not dual feasible. Similarly,
|
|
alpar@9
|
3402 if the indicator \verb|pb_quality| is assigned to \verb|'?'| while
|
|
alpar@9
|
3403 other indicators are not, this means that the current basic solution
|
|
alpar@9
|
3404 being dual feasible is not primal feasible.
|
|
alpar@9
|
3405
|
|
alpar@9
|
3406 %* eof *%
|
