lemon-project-template-glpk
view deps/glpk/src/glpk.h @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line source
1 /* glpk.h */
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 *
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
9 * E-mail: <mao@gnu.org>.
10 *
11 * GLPK is free software: you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation, either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
19 * License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
23 ***********************************************************************/
25 #ifndef GLPK_H
26 #define GLPK_H
28 #include <stdarg.h>
29 #include <stddef.h>
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
35 /* library version numbers: */
36 #define GLP_MAJOR_VERSION 4
37 #define GLP_MINOR_VERSION 47
39 #ifndef GLP_PROB_DEFINED
40 #define GLP_PROB_DEFINED
41 typedef struct { double _opaque_prob[100]; } glp_prob;
42 /* LP/MIP problem object */
43 #endif
45 /* optimization direction flag: */
46 #define GLP_MIN 1 /* minimization */
47 #define GLP_MAX 2 /* maximization */
49 /* kind of structural variable: */
50 #define GLP_CV 1 /* continuous variable */
51 #define GLP_IV 2 /* integer variable */
52 #define GLP_BV 3 /* binary variable */
54 /* type of auxiliary/structural variable: */
55 #define GLP_FR 1 /* free variable */
56 #define GLP_LO 2 /* variable with lower bound */
57 #define GLP_UP 3 /* variable with upper bound */
58 #define GLP_DB 4 /* double-bounded variable */
59 #define GLP_FX 5 /* fixed variable */
61 /* status of auxiliary/structural variable: */
62 #define GLP_BS 1 /* basic variable */
63 #define GLP_NL 2 /* non-basic variable on lower bound */
64 #define GLP_NU 3 /* non-basic variable on upper bound */
65 #define GLP_NF 4 /* non-basic free variable */
66 #define GLP_NS 5 /* non-basic fixed variable */
68 /* scaling options: */
69 #define GLP_SF_GM 0x01 /* perform geometric mean scaling */
70 #define GLP_SF_EQ 0x10 /* perform equilibration scaling */
71 #define GLP_SF_2N 0x20 /* round scale factors to power of two */
72 #define GLP_SF_SKIP 0x40 /* skip if problem is well scaled */
73 #define GLP_SF_AUTO 0x80 /* choose scaling options automatically */
75 /* solution indicator: */
76 #define GLP_SOL 1 /* basic solution */
77 #define GLP_IPT 2 /* interior-point solution */
78 #define GLP_MIP 3 /* mixed integer solution */
80 /* solution status: */
81 #define GLP_UNDEF 1 /* solution is undefined */
82 #define GLP_FEAS 2 /* solution is feasible */
83 #define GLP_INFEAS 3 /* solution is infeasible */
84 #define GLP_NOFEAS 4 /* no feasible solution exists */
85 #define GLP_OPT 5 /* solution is optimal */
86 #define GLP_UNBND 6 /* solution is unbounded */
88 typedef struct
89 { /* basis factorization control parameters */
90 int msg_lev; /* (reserved) */
91 int type; /* factorization type: */
92 #define GLP_BF_FT 1 /* LUF + Forrest-Tomlin */
93 #define GLP_BF_BG 2 /* LUF + Schur compl. + Bartels-Golub */
94 #define GLP_BF_GR 3 /* LUF + Schur compl. + Givens rotation */
95 int lu_size; /* luf.sv_size */
96 double piv_tol; /* luf.piv_tol */
97 int piv_lim; /* luf.piv_lim */
98 int suhl; /* luf.suhl */
99 double eps_tol; /* luf.eps_tol */
100 double max_gro; /* luf.max_gro */
101 int nfs_max; /* fhv.hh_max */
102 double upd_tol; /* fhv.upd_tol */
103 int nrs_max; /* lpf.n_max */
104 int rs_size; /* lpf.v_size */
105 double foo_bar[38]; /* (reserved) */
106 } glp_bfcp;
108 typedef struct
109 { /* simplex method control parameters */
110 int msg_lev; /* message level: */
111 #define GLP_MSG_OFF 0 /* no output */
112 #define GLP_MSG_ERR 1 /* warning and error messages only */
113 #define GLP_MSG_ON 2 /* normal output */
114 #define GLP_MSG_ALL 3 /* full output */
115 #define GLP_MSG_DBG 4 /* debug output */
116 int meth; /* simplex method option: */
117 #define GLP_PRIMAL 1 /* use primal simplex */
118 #define GLP_DUALP 2 /* use dual; if it fails, use primal */
119 #define GLP_DUAL 3 /* use dual simplex */
120 int pricing; /* pricing technique: */
121 #define GLP_PT_STD 0x11 /* standard (Dantzig rule) */
122 #define GLP_PT_PSE 0x22 /* projected steepest edge */
123 int r_test; /* ratio test technique: */
124 #define GLP_RT_STD 0x11 /* standard (textbook) */
125 #define GLP_RT_HAR 0x22 /* two-pass Harris' ratio test */
126 double tol_bnd; /* spx.tol_bnd */
127 double tol_dj; /* spx.tol_dj */
128 double tol_piv; /* spx.tol_piv */
129 double obj_ll; /* spx.obj_ll */
130 double obj_ul; /* spx.obj_ul */
131 int it_lim; /* spx.it_lim */
132 int tm_lim; /* spx.tm_lim (milliseconds) */
133 int out_frq; /* spx.out_frq */
134 int out_dly; /* spx.out_dly (milliseconds) */
135 int presolve; /* enable/disable using LP presolver */
136 double foo_bar[36]; /* (reserved) */
137 } glp_smcp;
139 typedef struct
140 { /* interior-point solver control parameters */
141 int msg_lev; /* message level (see glp_smcp) */
142 int ord_alg; /* ordering algorithm: */
143 #define GLP_ORD_NONE 0 /* natural (original) ordering */
144 #define GLP_ORD_QMD 1 /* quotient minimum degree (QMD) */
145 #define GLP_ORD_AMD 2 /* approx. minimum degree (AMD) */
146 #define GLP_ORD_SYMAMD 3 /* approx. minimum degree (SYMAMD) */
147 double foo_bar[48]; /* (reserved) */
148 } glp_iptcp;
150 #ifndef GLP_TREE_DEFINED
151 #define GLP_TREE_DEFINED
152 typedef struct { double _opaque_tree[100]; } glp_tree;
153 /* branch-and-bound tree */
154 #endif
156 typedef struct
157 { /* integer optimizer control parameters */
158 int msg_lev; /* message level (see glp_smcp) */
159 int br_tech; /* branching technique: */
160 #define GLP_BR_FFV 1 /* first fractional variable */
161 #define GLP_BR_LFV 2 /* last fractional variable */
162 #define GLP_BR_MFV 3 /* most fractional variable */
163 #define GLP_BR_DTH 4 /* heuristic by Driebeck and Tomlin */
164 #define GLP_BR_PCH 5 /* hybrid pseudocost heuristic */
165 int bt_tech; /* backtracking technique: */
166 #define GLP_BT_DFS 1 /* depth first search */
167 #define GLP_BT_BFS 2 /* breadth first search */
168 #define GLP_BT_BLB 3 /* best local bound */
169 #define GLP_BT_BPH 4 /* best projection heuristic */
170 double tol_int; /* mip.tol_int */
171 double tol_obj; /* mip.tol_obj */
172 int tm_lim; /* mip.tm_lim (milliseconds) */
173 int out_frq; /* mip.out_frq (milliseconds) */
174 int out_dly; /* mip.out_dly (milliseconds) */
175 void (*cb_func)(glp_tree *T, void *info);
176 /* mip.cb_func */
177 void *cb_info; /* mip.cb_info */
178 int cb_size; /* mip.cb_size */
179 int pp_tech; /* preprocessing technique: */
180 #define GLP_PP_NONE 0 /* disable preprocessing */
181 #define GLP_PP_ROOT 1 /* preprocessing only on root level */
182 #define GLP_PP_ALL 2 /* preprocessing on all levels */
183 double mip_gap; /* relative MIP gap tolerance */
184 int mir_cuts; /* MIR cuts (GLP_ON/GLP_OFF) */
185 int gmi_cuts; /* Gomory's cuts (GLP_ON/GLP_OFF) */
186 int cov_cuts; /* cover cuts (GLP_ON/GLP_OFF) */
187 int clq_cuts; /* clique cuts (GLP_ON/GLP_OFF) */
188 int presolve; /* enable/disable using MIP presolver */
189 int binarize; /* try to binarize integer variables */
190 int fp_heur; /* feasibility pump heuristic */
191 #if 1 /* 28/V-2010 */
192 int alien; /* use alien solver */
193 #endif
194 double foo_bar[29]; /* (reserved) */
195 } glp_iocp;
197 typedef struct
198 { /* additional row attributes */
199 int level;
200 /* subproblem level at which the row was added */
201 int origin;
202 /* row origin flag: */
203 #define GLP_RF_REG 0 /* regular constraint */
204 #define GLP_RF_LAZY 1 /* "lazy" constraint */
205 #define GLP_RF_CUT 2 /* cutting plane constraint */
206 int klass;
207 /* row class descriptor: */
208 #define GLP_RF_GMI 1 /* Gomory's mixed integer cut */
209 #define GLP_RF_MIR 2 /* mixed integer rounding cut */
210 #define GLP_RF_COV 3 /* mixed cover cut */
211 #define GLP_RF_CLQ 4 /* clique cut */
212 double foo_bar[7];
213 /* (reserved) */
214 } glp_attr;
216 /* enable/disable flag: */
217 #define GLP_ON 1 /* enable something */
218 #define GLP_OFF 0 /* disable something */
220 /* reason codes: */
221 #define GLP_IROWGEN 0x01 /* request for row generation */
222 #define GLP_IBINGO 0x02 /* better integer solution found */
223 #define GLP_IHEUR 0x03 /* request for heuristic solution */
224 #define GLP_ICUTGEN 0x04 /* request for cut generation */
225 #define GLP_IBRANCH 0x05 /* request for branching */
226 #define GLP_ISELECT 0x06 /* request for subproblem selection */
227 #define GLP_IPREPRO 0x07 /* request for preprocessing */
229 /* branch selection indicator: */
230 #define GLP_NO_BRNCH 0 /* select no branch */
231 #define GLP_DN_BRNCH 1 /* select down-branch */
232 #define GLP_UP_BRNCH 2 /* select up-branch */
234 /* return codes: */
235 #define GLP_EBADB 0x01 /* invalid basis */
236 #define GLP_ESING 0x02 /* singular matrix */
237 #define GLP_ECOND 0x03 /* ill-conditioned matrix */
238 #define GLP_EBOUND 0x04 /* invalid bounds */
239 #define GLP_EFAIL 0x05 /* solver failed */
240 #define GLP_EOBJLL 0x06 /* objective lower limit reached */
241 #define GLP_EOBJUL 0x07 /* objective upper limit reached */
242 #define GLP_EITLIM 0x08 /* iteration limit exceeded */
243 #define GLP_ETMLIM 0x09 /* time limit exceeded */
244 #define GLP_ENOPFS 0x0A /* no primal feasible solution */
245 #define GLP_ENODFS 0x0B /* no dual feasible solution */
246 #define GLP_EROOT 0x0C /* root LP optimum not provided */
247 #define GLP_ESTOP 0x0D /* search terminated by application */
248 #define GLP_EMIPGAP 0x0E /* relative mip gap tolerance reached */
249 #define GLP_ENOFEAS 0x0F /* no primal/dual feasible solution */
250 #define GLP_ENOCVG 0x10 /* no convergence */
251 #define GLP_EINSTAB 0x11 /* numerical instability */
252 #define GLP_EDATA 0x12 /* invalid data */
253 #define GLP_ERANGE 0x13 /* result out of range */
255 /* condition indicator: */
256 #define GLP_KKT_PE 1 /* primal equalities */
257 #define GLP_KKT_PB 2 /* primal bounds */
258 #define GLP_KKT_DE 3 /* dual equalities */
259 #define GLP_KKT_DB 4 /* dual bounds */
260 #define GLP_KKT_CS 5 /* complementary slackness */
262 /* MPS file format: */
263 #define GLP_MPS_DECK 1 /* fixed (ancient) */
264 #define GLP_MPS_FILE 2 /* free (modern) */
266 typedef struct
267 { /* MPS format control parameters */
268 int blank;
269 /* character code to replace blanks in symbolic names */
270 char *obj_name;
271 /* objective row name */
272 double tol_mps;
273 /* zero tolerance for MPS data */
274 double foo_bar[17];
275 /* (reserved for use in the future) */
276 } glp_mpscp;
278 typedef struct
279 { /* CPLEX LP format control parameters */
280 double foo_bar[20];
281 /* (reserved for use in the future) */
282 } glp_cpxcp;
284 #ifndef GLP_TRAN_DEFINED
285 #define GLP_TRAN_DEFINED
286 typedef struct { double _opaque_tran[100]; } glp_tran;
287 /* MathProg translator workspace */
288 #endif
290 glp_prob *glp_create_prob(void);
291 /* create problem object */
293 void glp_set_prob_name(glp_prob *P, const char *name);
294 /* assign (change) problem name */
296 void glp_set_obj_name(glp_prob *P, const char *name);
297 /* assign (change) objective function name */
299 void glp_set_obj_dir(glp_prob *P, int dir);
300 /* set (change) optimization direction flag */
302 int glp_add_rows(glp_prob *P, int nrs);
303 /* add new rows to problem object */
305 int glp_add_cols(glp_prob *P, int ncs);
306 /* add new columns to problem object */
308 void glp_set_row_name(glp_prob *P, int i, const char *name);
309 /* assign (change) row name */
311 void glp_set_col_name(glp_prob *P, int j, const char *name);
312 /* assign (change) column name */
314 void glp_set_row_bnds(glp_prob *P, int i, int type, double lb,
315 double ub);
316 /* set (change) row bounds */
318 void glp_set_col_bnds(glp_prob *P, int j, int type, double lb,
319 double ub);
320 /* set (change) column bounds */
322 void glp_set_obj_coef(glp_prob *P, int j, double coef);
323 /* set (change) obj. coefficient or constant term */
325 void glp_set_mat_row(glp_prob *P, int i, int len, const int ind[],
326 const double val[]);
327 /* set (replace) row of the constraint matrix */
329 void glp_set_mat_col(glp_prob *P, int j, int len, const int ind[],
330 const double val[]);
331 /* set (replace) column of the constraint matrix */
333 void glp_load_matrix(glp_prob *P, int ne, const int ia[],
334 const int ja[], const double ar[]);
335 /* load (replace) the whole constraint matrix */
337 int glp_check_dup(int m, int n, int ne, const int ia[], const int ja[]);
338 /* check for duplicate elements in sparse matrix */
340 void glp_sort_matrix(glp_prob *P);
341 /* sort elements of the constraint matrix */
343 void glp_del_rows(glp_prob *P, int nrs, const int num[]);
344 /* delete specified rows from problem object */
346 void glp_del_cols(glp_prob *P, int ncs, const int num[]);
347 /* delete specified columns from problem object */
349 void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
350 /* copy problem object content */
352 void glp_erase_prob(glp_prob *P);
353 /* erase problem object content */
355 void glp_delete_prob(glp_prob *P);
356 /* delete problem object */
358 const char *glp_get_prob_name(glp_prob *P);
359 /* retrieve problem name */
361 const char *glp_get_obj_name(glp_prob *P);
362 /* retrieve objective function name */
364 int glp_get_obj_dir(glp_prob *P);
365 /* retrieve optimization direction flag */
367 int glp_get_num_rows(glp_prob *P);
368 /* retrieve number of rows */
370 int glp_get_num_cols(glp_prob *P);
371 /* retrieve number of columns */
373 const char *glp_get_row_name(glp_prob *P, int i);
374 /* retrieve row name */
376 const char *glp_get_col_name(glp_prob *P, int j);
377 /* retrieve column name */
379 int glp_get_row_type(glp_prob *P, int i);
380 /* retrieve row type */
382 double glp_get_row_lb(glp_prob *P, int i);
383 /* retrieve row lower bound */
385 double glp_get_row_ub(glp_prob *P, int i);
386 /* retrieve row upper bound */
388 int glp_get_col_type(glp_prob *P, int j);
389 /* retrieve column type */
391 double glp_get_col_lb(glp_prob *P, int j);
392 /* retrieve column lower bound */
394 double glp_get_col_ub(glp_prob *P, int j);
395 /* retrieve column upper bound */
397 double glp_get_obj_coef(glp_prob *P, int j);
398 /* retrieve obj. coefficient or constant term */
400 int glp_get_num_nz(glp_prob *P);
401 /* retrieve number of constraint coefficients */
403 int glp_get_mat_row(glp_prob *P, int i, int ind[], double val[]);
404 /* retrieve row of the constraint matrix */
406 int glp_get_mat_col(glp_prob *P, int j, int ind[], double val[]);
407 /* retrieve column of the constraint matrix */
409 void glp_create_index(glp_prob *P);
410 /* create the name index */
412 int glp_find_row(glp_prob *P, const char *name);
413 /* find row by its name */
415 int glp_find_col(glp_prob *P, const char *name);
416 /* find column by its name */
418 void glp_delete_index(glp_prob *P);
419 /* delete the name index */
421 void glp_set_rii(glp_prob *P, int i, double rii);
422 /* set (change) row scale factor */
424 void glp_set_sjj(glp_prob *P, int j, double sjj);
425 /* set (change) column scale factor */
427 double glp_get_rii(glp_prob *P, int i);
428 /* retrieve row scale factor */
430 double glp_get_sjj(glp_prob *P, int j);
431 /* retrieve column scale factor */
433 void glp_scale_prob(glp_prob *P, int flags);
434 /* scale problem data */
436 void glp_unscale_prob(glp_prob *P);
437 /* unscale problem data */
439 void glp_set_row_stat(glp_prob *P, int i, int stat);
440 /* set (change) row status */
442 void glp_set_col_stat(glp_prob *P, int j, int stat);
443 /* set (change) column status */
445 void glp_std_basis(glp_prob *P);
446 /* construct standard initial LP basis */
448 void glp_adv_basis(glp_prob *P, int flags);
449 /* construct advanced initial LP basis */
451 void glp_cpx_basis(glp_prob *P);
452 /* construct Bixby's initial LP basis */
454 int glp_simplex(glp_prob *P, const glp_smcp *parm);
455 /* solve LP problem with the simplex method */
457 int glp_exact(glp_prob *P, const glp_smcp *parm);
458 /* solve LP problem in exact arithmetic */
460 void glp_init_smcp(glp_smcp *parm);
461 /* initialize simplex method control parameters */
463 int glp_get_status(glp_prob *P);
464 /* retrieve generic status of basic solution */
466 int glp_get_prim_stat(glp_prob *P);
467 /* retrieve status of primal basic solution */
469 int glp_get_dual_stat(glp_prob *P);
470 /* retrieve status of dual basic solution */
472 double glp_get_obj_val(glp_prob *P);
473 /* retrieve objective value (basic solution) */
475 int glp_get_row_stat(glp_prob *P, int i);
476 /* retrieve row status */
478 double glp_get_row_prim(glp_prob *P, int i);
479 /* retrieve row primal value (basic solution) */
481 double glp_get_row_dual(glp_prob *P, int i);
482 /* retrieve row dual value (basic solution) */
484 int glp_get_col_stat(glp_prob *P, int j);
485 /* retrieve column status */
487 double glp_get_col_prim(glp_prob *P, int j);
488 /* retrieve column primal value (basic solution) */
490 double glp_get_col_dual(glp_prob *P, int j);
491 /* retrieve column dual value (basic solution) */
493 int glp_get_unbnd_ray(glp_prob *P);
494 /* determine variable causing unboundedness */
496 int glp_interior(glp_prob *P, const glp_iptcp *parm);
497 /* solve LP problem with the interior-point method */
499 void glp_init_iptcp(glp_iptcp *parm);
500 /* initialize interior-point solver control parameters */
502 int glp_ipt_status(glp_prob *P);
503 /* retrieve status of interior-point solution */
505 double glp_ipt_obj_val(glp_prob *P);
506 /* retrieve objective value (interior point) */
508 double glp_ipt_row_prim(glp_prob *P, int i);
509 /* retrieve row primal value (interior point) */
511 double glp_ipt_row_dual(glp_prob *P, int i);
512 /* retrieve row dual value (interior point) */
514 double glp_ipt_col_prim(glp_prob *P, int j);
515 /* retrieve column primal value (interior point) */
517 double glp_ipt_col_dual(glp_prob *P, int j);
518 /* retrieve column dual value (interior point) */
520 void glp_set_col_kind(glp_prob *P, int j, int kind);
521 /* set (change) column kind */
523 int glp_get_col_kind(glp_prob *P, int j);
524 /* retrieve column kind */
526 int glp_get_num_int(glp_prob *P);
527 /* retrieve number of integer columns */
529 int glp_get_num_bin(glp_prob *P);
530 /* retrieve number of binary columns */
532 int glp_intopt(glp_prob *P, const glp_iocp *parm);
533 /* solve MIP problem with the branch-and-bound method */
535 void glp_init_iocp(glp_iocp *parm);
536 /* initialize integer optimizer control parameters */
538 int glp_mip_status(glp_prob *P);
539 /* retrieve status of MIP solution */
541 double glp_mip_obj_val(glp_prob *P);
542 /* retrieve objective value (MIP solution) */
544 double glp_mip_row_val(glp_prob *P, int i);
545 /* retrieve row value (MIP solution) */
547 double glp_mip_col_val(glp_prob *P, int j);
548 /* retrieve column value (MIP solution) */
550 int glp_print_sol(glp_prob *P, const char *fname);
551 /* write basic solution in printable format */
553 int glp_read_sol(glp_prob *P, const char *fname);
554 /* read basic solution from text file */
556 int glp_write_sol(glp_prob *P, const char *fname);
557 /* write basic solution to text file */
559 int glp_print_ranges(glp_prob *P, int len, const int list[],
560 int flags, const char *fname);
561 /* print sensitivity analysis report */
563 int glp_print_ipt(glp_prob *P, const char *fname);
564 /* write interior-point solution in printable format */
566 int glp_read_ipt(glp_prob *P, const char *fname);
567 /* read interior-point solution from text file */
569 int glp_write_ipt(glp_prob *P, const char *fname);
570 /* write interior-point solution to text file */
572 int glp_print_mip(glp_prob *P, const char *fname);
573 /* write MIP solution in printable format */
575 int glp_read_mip(glp_prob *P, const char *fname);
576 /* read MIP solution from text file */
578 int glp_write_mip(glp_prob *P, const char *fname);
579 /* write MIP solution to text file */
581 int glp_bf_exists(glp_prob *P);
582 /* check if the basis factorization exists */
584 int glp_factorize(glp_prob *P);
585 /* compute the basis factorization */
587 int glp_bf_updated(glp_prob *P);
588 /* check if the basis factorization has been updated */
590 void glp_get_bfcp(glp_prob *P, glp_bfcp *parm);
591 /* retrieve basis factorization control parameters */
593 void glp_set_bfcp(glp_prob *P, const glp_bfcp *parm);
594 /* change basis factorization control parameters */
596 int glp_get_bhead(glp_prob *P, int k);
597 /* retrieve the basis header information */
599 int glp_get_row_bind(glp_prob *P, int i);
600 /* retrieve row index in the basis header */
602 int glp_get_col_bind(glp_prob *P, int j);
603 /* retrieve column index in the basis header */
605 void glp_ftran(glp_prob *P, double x[]);
606 /* perform forward transformation (solve system B*x = b) */
608 void glp_btran(glp_prob *P, double x[]);
609 /* perform backward transformation (solve system B'*x = b) */
611 int glp_warm_up(glp_prob *P);
612 /* "warm up" LP basis */
614 int glp_eval_tab_row(glp_prob *P, int k, int ind[], double val[]);
615 /* compute row of the simplex tableau */
617 int glp_eval_tab_col(glp_prob *P, int k, int ind[], double val[]);
618 /* compute column of the simplex tableau */
620 int glp_transform_row(glp_prob *P, int len, int ind[], double val[]);
621 /* transform explicitly specified row */
623 int glp_transform_col(glp_prob *P, int len, int ind[], double val[]);
624 /* transform explicitly specified column */
626 int glp_prim_rtest(glp_prob *P, int len, const int ind[],
627 const double val[], int dir, double eps);
628 /* perform primal ratio test */
630 int glp_dual_rtest(glp_prob *P, int len, const int ind[],
631 const double val[], int dir, double eps);
632 /* perform dual ratio test */
634 void glp_analyze_bound(glp_prob *P, int k, double *value1, int *var1,
635 double *value2, int *var2);
636 /* analyze active bound of non-basic variable */
638 void glp_analyze_coef(glp_prob *P, int k, double *coef1, int *var1,
639 double *value1, double *coef2, int *var2, double *value2);
640 /* analyze objective coefficient at basic variable */
642 int glp_ios_reason(glp_tree *T);
643 /* determine reason for calling the callback routine */
645 glp_prob *glp_ios_get_prob(glp_tree *T);
646 /* access the problem object */
648 void glp_ios_tree_size(glp_tree *T, int *a_cnt, int *n_cnt,
649 int *t_cnt);
650 /* determine size of the branch-and-bound tree */
652 int glp_ios_curr_node(glp_tree *T);
653 /* determine current active subproblem */
655 int glp_ios_next_node(glp_tree *T, int p);
656 /* determine next active subproblem */
658 int glp_ios_prev_node(glp_tree *T, int p);
659 /* determine previous active subproblem */
661 int glp_ios_up_node(glp_tree *T, int p);
662 /* determine parent subproblem */
664 int glp_ios_node_level(glp_tree *T, int p);
665 /* determine subproblem level */
667 double glp_ios_node_bound(glp_tree *T, int p);
668 /* determine subproblem local bound */
670 int glp_ios_best_node(glp_tree *T);
671 /* find active subproblem with best local bound */
673 double glp_ios_mip_gap(glp_tree *T);
674 /* compute relative MIP gap */
676 void *glp_ios_node_data(glp_tree *T, int p);
677 /* access subproblem application-specific data */
679 void glp_ios_row_attr(glp_tree *T, int i, glp_attr *attr);
680 /* retrieve additional row attributes */
682 int glp_ios_pool_size(glp_tree *T);
683 /* determine current size of the cut pool */
685 int glp_ios_add_row(glp_tree *T,
686 const char *name, int klass, int flags, int len, const int ind[],
687 const double val[], int type, double rhs);
688 /* add row (constraint) to the cut pool */
690 void glp_ios_del_row(glp_tree *T, int i);
691 /* remove row (constraint) from the cut pool */
693 void glp_ios_clear_pool(glp_tree *T);
694 /* remove all rows (constraints) from the cut pool */
696 int glp_ios_can_branch(glp_tree *T, int j);
697 /* check if can branch upon specified variable */
699 void glp_ios_branch_upon(glp_tree *T, int j, int sel);
700 /* choose variable to branch upon */
702 void glp_ios_select_node(glp_tree *T, int p);
703 /* select subproblem to continue the search */
705 int glp_ios_heur_sol(glp_tree *T, const double x[]);
706 /* provide solution found by heuristic */
708 void glp_ios_terminate(glp_tree *T);
709 /* terminate the solution process */
711 void glp_init_mpscp(glp_mpscp *parm);
712 /* initialize MPS format control parameters */
714 int glp_read_mps(glp_prob *P, int fmt, const glp_mpscp *parm,
715 const char *fname);
716 /* read problem data in MPS format */
718 int glp_write_mps(glp_prob *P, int fmt, const glp_mpscp *parm,
719 const char *fname);
720 /* write problem data in MPS format */
722 void glp_init_cpxcp(glp_cpxcp *parm);
723 /* initialize CPLEX LP format control parameters */
725 int glp_read_lp(glp_prob *P, const glp_cpxcp *parm, const char *fname);
726 /* read problem data in CPLEX LP format */
728 int glp_write_lp(glp_prob *P, const glp_cpxcp *parm, const char *fname);
729 /* write problem data in CPLEX LP format */
731 int glp_read_prob(glp_prob *P, int flags, const char *fname);
732 /* read problem data in GLPK format */
734 int glp_write_prob(glp_prob *P, int flags, const char *fname);
735 /* write problem data in GLPK format */
737 glp_tran *glp_mpl_alloc_wksp(void);
738 /* allocate the MathProg translator workspace */
740 int glp_mpl_read_model(glp_tran *tran, const char *fname, int skip);
741 /* read and translate model section */
743 int glp_mpl_read_data(glp_tran *tran, const char *fname);
744 /* read and translate data section */
746 int glp_mpl_generate(glp_tran *tran, const char *fname);
747 /* generate the model */
749 void glp_mpl_build_prob(glp_tran *tran, glp_prob *prob);
750 /* build LP/MIP problem instance from the model */
752 int glp_mpl_postsolve(glp_tran *tran, glp_prob *prob, int sol);
753 /* postsolve the model */
755 void glp_mpl_free_wksp(glp_tran *tran);
756 /* free the MathProg translator workspace */
758 int glp_main(int argc, const char *argv[]);
759 /* stand-alone LP/MIP solver */
761 /**********************************************************************/
763 int glp_read_cnfsat(glp_prob *P, const char *fname);
764 /* read CNF-SAT problem data in DIMACS format */
766 int glp_check_cnfsat(glp_prob *P);
767 /* check for CNF-SAT problem instance */
769 int glp_write_cnfsat(glp_prob *P, const char *fname);
770 /* write CNF-SAT problem data in DIMACS format */
772 int glp_minisat1(glp_prob *P);
773 /* solve CNF-SAT problem with MiniSat solver */
775 int glp_intfeas1(glp_prob *P, int use_bound, int obj_bound);
776 /* solve integer feasibility problem */
778 /**********************************************************************/
780 #ifndef GLP_LONG_DEFINED
781 #define GLP_LONG_DEFINED
782 typedef struct { int lo, hi; } glp_long;
783 /* long integer data type */
784 #endif
786 int glp_init_env(void);
787 /* initialize GLPK environment */
789 const char *glp_version(void);
790 /* determine library version */
792 int glp_free_env(void);
793 /* free GLPK environment */
795 void glp_printf(const char *fmt, ...);
796 /* write formatted output to terminal */
798 void glp_vprintf(const char *fmt, va_list arg);
799 /* write formatted output to terminal */
801 int glp_term_out(int flag);
802 /* enable/disable terminal output */
804 void glp_term_hook(int (*func)(void *info, const char *s), void *info);
805 /* install hook to intercept terminal output */
807 int glp_open_tee(const char *fname);
808 /* start copying terminal output to text file */
810 int glp_close_tee(void);
811 /* stop copying terminal output to text file */
813 #ifndef GLP_ERROR_DEFINED
814 #define GLP_ERROR_DEFINED
815 typedef void (*_glp_error)(const char *fmt, ...);
816 #endif
818 #define glp_error glp_error_(__FILE__, __LINE__)
819 _glp_error glp_error_(const char *file, int line);
820 /* display error message and terminate execution */
822 #define glp_assert(expr) \
823 ((void)((expr) || (glp_assert_(#expr, __FILE__, __LINE__), 1)))
824 void glp_assert_(const char *expr, const char *file, int line);
825 /* check for logical condition */
827 void glp_error_hook(void (*func)(void *info), void *info);
828 /* install hook to intercept abnormal termination */
830 void *glp_malloc(int size);
831 /* allocate memory block */
833 void *glp_calloc(int n, int size);
834 /* allocate memory block */
836 void glp_free(void *ptr);
837 /* free memory block */
839 void glp_mem_limit(int limit);
840 /* set memory usage limit */
842 void glp_mem_usage(int *count, int *cpeak, glp_long *total,
843 glp_long *tpeak);
844 /* get memory usage information */
846 glp_long glp_time(void);
847 /* determine current universal time */
849 double glp_difftime(glp_long t1, glp_long t0);
850 /* compute difference between two time values */
852 /**********************************************************************/
854 #ifndef GLP_DATA_DEFINED
855 #define GLP_DATA_DEFINED
856 typedef struct { double _opaque_data[100]; } glp_data;
857 /* plain data file */
858 #endif
860 glp_data *glp_sdf_open_file(const char *fname);
861 /* open plain data file */
863 void glp_sdf_set_jump(glp_data *data, void *jump);
864 /* set up error handling */
866 void glp_sdf_error(glp_data *data, const char *fmt, ...);
867 /* print error message */
869 void glp_sdf_warning(glp_data *data, const char *fmt, ...);
870 /* print warning message */
872 int glp_sdf_read_int(glp_data *data);
873 /* read integer number */
875 double glp_sdf_read_num(glp_data *data);
876 /* read floating-point number */
878 const char *glp_sdf_read_item(glp_data *data);
879 /* read data item */
881 const char *glp_sdf_read_text(glp_data *data);
882 /* read text until end of line */
884 int glp_sdf_line(glp_data *data);
885 /* determine current line number */
887 void glp_sdf_close_file(glp_data *data);
888 /* close plain data file */
890 /**********************************************************************/
892 typedef struct _glp_graph glp_graph;
893 typedef struct _glp_vertex glp_vertex;
894 typedef struct _glp_arc glp_arc;
896 struct _glp_graph
897 { /* graph descriptor */
898 void *pool; /* DMP *pool; */
899 /* memory pool to store graph components */
900 char *name;
901 /* graph name (1 to 255 chars); NULL means no name is assigned
902 to the graph */
903 int nv_max;
904 /* length of the vertex list (enlarged automatically) */
905 int nv;
906 /* number of vertices in the graph, 0 <= nv <= nv_max */
907 int na;
908 /* number of arcs in the graph, na >= 0 */
909 glp_vertex **v; /* glp_vertex *v[1+nv_max]; */
910 /* v[i], 1 <= i <= nv, is a pointer to i-th vertex */
911 void *index; /* AVL *index; */
912 /* vertex index to find vertices by their names; NULL means the
913 index does not exist */
914 int v_size;
915 /* size of data associated with each vertex (0 to 256 bytes) */
916 int a_size;
917 /* size of data associated with each arc (0 to 256 bytes) */
918 };
920 struct _glp_vertex
921 { /* vertex descriptor */
922 int i;
923 /* vertex ordinal number, 1 <= i <= nv */
924 char *name;
925 /* vertex name (1 to 255 chars); NULL means no name is assigned
926 to the vertex */
927 void *entry; /* AVLNODE *entry; */
928 /* pointer to corresponding entry in the vertex index; NULL means
929 that either the index does not exist or the vertex has no name
930 assigned */
931 void *data;
932 /* pointer to data associated with the vertex */
933 void *temp;
934 /* working pointer */
935 glp_arc *in;
936 /* pointer to the (unordered) list of incoming arcs */
937 glp_arc *out;
938 /* pointer to the (unordered) list of outgoing arcs */
939 };
941 struct _glp_arc
942 { /* arc descriptor */
943 glp_vertex *tail;
944 /* pointer to the tail endpoint */
945 glp_vertex *head;
946 /* pointer to the head endpoint */
947 void *data;
948 /* pointer to data associated with the arc */
949 void *temp;
950 /* working pointer */
951 glp_arc *t_prev;
952 /* pointer to previous arc having the same tail endpoint */
953 glp_arc *t_next;
954 /* pointer to next arc having the same tail endpoint */
955 glp_arc *h_prev;
956 /* pointer to previous arc having the same head endpoint */
957 glp_arc *h_next;
958 /* pointer to next arc having the same head endpoint */
959 };
961 glp_graph *glp_create_graph(int v_size, int a_size);
962 /* create graph */
964 void glp_set_graph_name(glp_graph *G, const char *name);
965 /* assign (change) graph name */
967 int glp_add_vertices(glp_graph *G, int nadd);
968 /* add new vertices to graph */
970 void glp_set_vertex_name(glp_graph *G, int i, const char *name);
971 /* assign (change) vertex name */
973 glp_arc *glp_add_arc(glp_graph *G, int i, int j);
974 /* add new arc to graph */
976 void glp_del_vertices(glp_graph *G, int ndel, const int num[]);
977 /* delete vertices from graph */
979 void glp_del_arc(glp_graph *G, glp_arc *a);
980 /* delete arc from graph */
982 void glp_erase_graph(glp_graph *G, int v_size, int a_size);
983 /* erase graph content */
985 void glp_delete_graph(glp_graph *G);
986 /* delete graph */
988 void glp_create_v_index(glp_graph *G);
989 /* create vertex name index */
991 int glp_find_vertex(glp_graph *G, const char *name);
992 /* find vertex by its name */
994 void glp_delete_v_index(glp_graph *G);
995 /* delete vertex name index */
997 int glp_read_graph(glp_graph *G, const char *fname);
998 /* read graph from plain text file */
1000 int glp_write_graph(glp_graph *G, const char *fname);
1001 /* write graph to plain text file */
1003 void glp_mincost_lp(glp_prob *P, glp_graph *G, int names, int v_rhs,
1004 int a_low, int a_cap, int a_cost);
1005 /* convert minimum cost flow problem to LP */
1007 int glp_mincost_okalg(glp_graph *G, int v_rhs, int a_low, int a_cap,
1008 int a_cost, double *sol, int a_x, int v_pi);
1009 /* find minimum-cost flow with out-of-kilter algorithm */
1011 void glp_maxflow_lp(glp_prob *P, glp_graph *G, int names, int s,
1012 int t, int a_cap);
1013 /* convert maximum flow problem to LP */
1015 int glp_maxflow_ffalg(glp_graph *G, int s, int t, int a_cap,
1016 double *sol, int a_x, int v_cut);
1017 /* find maximal flow with Ford-Fulkerson algorithm */
1019 int glp_check_asnprob(glp_graph *G, int v_set);
1020 /* check correctness of assignment problem data */
1022 /* assignment problem formulation: */
1023 #define GLP_ASN_MIN 1 /* perfect matching (minimization) */
1024 #define GLP_ASN_MAX 2 /* perfect matching (maximization) */
1025 #define GLP_ASN_MMP 3 /* maximum matching */
1027 int glp_asnprob_lp(glp_prob *P, int form, glp_graph *G, int names,
1028 int v_set, int a_cost);
1029 /* convert assignment problem to LP */
1031 int glp_asnprob_okalg(int form, glp_graph *G, int v_set, int a_cost,
1032 double *sol, int a_x);
1033 /* solve assignment problem with out-of-kilter algorithm */
1035 int glp_asnprob_hall(glp_graph *G, int v_set, int a_x);
1036 /* find bipartite matching of maximum cardinality */
1038 double glp_cpp(glp_graph *G, int v_t, int v_es, int v_ls);
1039 /* solve critical path problem */
1041 int glp_read_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
1042 int a_cost, const char *fname);
1043 /* read min-cost flow problem data in DIMACS format */
1045 int glp_write_mincost(glp_graph *G, int v_rhs, int a_low, int a_cap,
1046 int a_cost, const char *fname);
1047 /* write min-cost flow problem data in DIMACS format */
1049 int glp_read_maxflow(glp_graph *G, int *s, int *t, int a_cap,
1050 const char *fname);
1051 /* read maximum flow problem data in DIMACS format */
1053 int glp_write_maxflow(glp_graph *G, int s, int t, int a_cap,
1054 const char *fname);
1055 /* write maximum flow problem data in DIMACS format */
1057 int glp_read_asnprob(glp_graph *G, int v_set, int a_cost, const char
1058 *fname);
1059 /* read assignment problem data in DIMACS format */
1061 int glp_write_asnprob(glp_graph *G, int v_set, int a_cost, const char
1062 *fname);
1063 /* write assignment problem data in DIMACS format */
1065 int glp_read_ccdata(glp_graph *G, int v_wgt, const char *fname);
1066 /* read graph in DIMACS clique/coloring format */
1068 int glp_write_ccdata(glp_graph *G, int v_wgt, const char *fname);
1069 /* write graph in DIMACS clique/coloring format */
1071 int glp_netgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
1072 const int parm[1+15]);
1073 /* Klingman's network problem generator */
1075 int glp_gridgen(glp_graph *G, int v_rhs, int a_cap, int a_cost,
1076 const int parm[1+14]);
1077 /* grid-like network problem generator */
1079 int glp_rmfgen(glp_graph *G, int *s, int *t, int a_cap,
1080 const int parm[1+5]);
1081 /* Goldfarb's maximum flow problem generator */
1083 int glp_weak_comp(glp_graph *G, int v_num);
1084 /* find all weakly connected components of graph */
1086 int glp_strong_comp(glp_graph *G, int v_num);
1087 /* find all strongly connected components of graph */
1089 int glp_top_sort(glp_graph *G, int v_num);
1090 /* topological sorting of acyclic digraph */
1092 int glp_wclique_exact(glp_graph *G, int v_wgt, double *sol, int v_set);
1093 /* find maximum weight clique with exact algorithm */
1095 /***********************************************************************
1096 * NOTE: All symbols defined below are obsolete and kept here only for
1097 * backward compatibility.
1098 ***********************************************************************/
1100 #define LPX glp_prob
1102 /* problem class: */
1103 #define LPX_LP 100 /* linear programming (LP) */
1104 #define LPX_MIP 101 /* mixed integer programming (MIP) */
1106 /* type of auxiliary/structural variable: */
1107 #define LPX_FR 110 /* free variable */
1108 #define LPX_LO 111 /* variable with lower bound */
1109 #define LPX_UP 112 /* variable with upper bound */
1110 #define LPX_DB 113 /* double-bounded variable */
1111 #define LPX_FX 114 /* fixed variable */
1113 /* optimization direction flag: */
1114 #define LPX_MIN 120 /* minimization */
1115 #define LPX_MAX 121 /* maximization */
1117 /* status of primal basic solution: */
1118 #define LPX_P_UNDEF 132 /* primal solution is undefined */
1119 #define LPX_P_FEAS 133 /* solution is primal feasible */
1120 #define LPX_P_INFEAS 134 /* solution is primal infeasible */
1121 #define LPX_P_NOFEAS 135 /* no primal feasible solution exists */
1123 /* status of dual basic solution: */
1124 #define LPX_D_UNDEF 136 /* dual solution is undefined */
1125 #define LPX_D_FEAS 137 /* solution is dual feasible */
1126 #define LPX_D_INFEAS 138 /* solution is dual infeasible */
1127 #define LPX_D_NOFEAS 139 /* no dual feasible solution exists */
1129 /* status of auxiliary/structural variable: */
1130 #define LPX_BS 140 /* basic variable */
1131 #define LPX_NL 141 /* non-basic variable on lower bound */
1132 #define LPX_NU 142 /* non-basic variable on upper bound */
1133 #define LPX_NF 143 /* non-basic free variable */
1134 #define LPX_NS 144 /* non-basic fixed variable */
1136 /* status of interior-point solution: */
1137 #define LPX_T_UNDEF 150 /* interior solution is undefined */
1138 #define LPX_T_OPT 151 /* interior solution is optimal */
1140 /* kind of structural variable: */
1141 #define LPX_CV 160 /* continuous variable */
1142 #define LPX_IV 161 /* integer variable */
1144 /* status of integer solution: */
1145 #define LPX_I_UNDEF 170 /* integer solution is undefined */
1146 #define LPX_I_OPT 171 /* integer solution is optimal */
1147 #define LPX_I_FEAS 172 /* integer solution is feasible */
1148 #define LPX_I_NOFEAS 173 /* no integer solution exists */
1150 /* status codes reported by the routine lpx_get_status: */
1151 #define LPX_OPT 180 /* optimal */
1152 #define LPX_FEAS 181 /* feasible */
1153 #define LPX_INFEAS 182 /* infeasible */
1154 #define LPX_NOFEAS 183 /* no feasible */
1155 #define LPX_UNBND 184 /* unbounded */
1156 #define LPX_UNDEF 185 /* undefined */
1158 /* exit codes returned by solver routines: */
1159 #define LPX_E_OK 200 /* success */
1160 #define LPX_E_EMPTY 201 /* empty problem */
1161 #define LPX_E_BADB 202 /* invalid initial basis */
1162 #define LPX_E_INFEAS 203 /* infeasible initial solution */
1163 #define LPX_E_FAULT 204 /* unable to start the search */
1164 #define LPX_E_OBJLL 205 /* objective lower limit reached */
1165 #define LPX_E_OBJUL 206 /* objective upper limit reached */
1166 #define LPX_E_ITLIM 207 /* iterations limit exhausted */
1167 #define LPX_E_TMLIM 208 /* time limit exhausted */
1168 #define LPX_E_NOFEAS 209 /* no feasible solution */
1169 #define LPX_E_INSTAB 210 /* numerical instability */
1170 #define LPX_E_SING 211 /* problems with basis matrix */
1171 #define LPX_E_NOCONV 212 /* no convergence (interior) */
1172 #define LPX_E_NOPFS 213 /* no primal feas. sol. (LP presolver) */
1173 #define LPX_E_NODFS 214 /* no dual feas. sol. (LP presolver) */
1174 #define LPX_E_MIPGAP 215 /* relative mip gap tolerance reached */
1176 /* control parameter identifiers: */
1177 #define LPX_K_MSGLEV 300 /* lp->msg_lev */
1178 #define LPX_K_SCALE 301 /* lp->scale */
1179 #define LPX_K_DUAL 302 /* lp->dual */
1180 #define LPX_K_PRICE 303 /* lp->price */
1181 #define LPX_K_RELAX 304 /* lp->relax */
1182 #define LPX_K_TOLBND 305 /* lp->tol_bnd */
1183 #define LPX_K_TOLDJ 306 /* lp->tol_dj */
1184 #define LPX_K_TOLPIV 307 /* lp->tol_piv */
1185 #define LPX_K_ROUND 308 /* lp->round */
1186 #define LPX_K_OBJLL 309 /* lp->obj_ll */
1187 #define LPX_K_OBJUL 310 /* lp->obj_ul */
1188 #define LPX_K_ITLIM 311 /* lp->it_lim */
1189 #define LPX_K_ITCNT 312 /* lp->it_cnt */
1190 #define LPX_K_TMLIM 313 /* lp->tm_lim */
1191 #define LPX_K_OUTFRQ 314 /* lp->out_frq */
1192 #define LPX_K_OUTDLY 315 /* lp->out_dly */
1193 #define LPX_K_BRANCH 316 /* lp->branch */
1194 #define LPX_K_BTRACK 317 /* lp->btrack */
1195 #define LPX_K_TOLINT 318 /* lp->tol_int */
1196 #define LPX_K_TOLOBJ 319 /* lp->tol_obj */
1197 #define LPX_K_MPSINFO 320 /* lp->mps_info */
1198 #define LPX_K_MPSOBJ 321 /* lp->mps_obj */
1199 #define LPX_K_MPSORIG 322 /* lp->mps_orig */
1200 #define LPX_K_MPSWIDE 323 /* lp->mps_wide */
1201 #define LPX_K_MPSFREE 324 /* lp->mps_free */
1202 #define LPX_K_MPSSKIP 325 /* lp->mps_skip */
1203 #define LPX_K_LPTORIG 326 /* lp->lpt_orig */
1204 #define LPX_K_PRESOL 327 /* lp->presol */
1205 #define LPX_K_BINARIZE 328 /* lp->binarize */
1206 #define LPX_K_USECUTS 329 /* lp->use_cuts */
1207 #define LPX_K_BFTYPE 330 /* lp->bfcp->type */
1208 #define LPX_K_MIPGAP 331 /* lp->mip_gap */
1210 #define LPX_C_COVER 0x01 /* mixed cover cuts */
1211 #define LPX_C_CLIQUE 0x02 /* clique cuts */
1212 #define LPX_C_GOMORY 0x04 /* Gomory's mixed integer cuts */
1213 #define LPX_C_MIR 0x08 /* mixed integer rounding cuts */
1214 #define LPX_C_ALL 0xFF /* all cuts */
1216 typedef struct
1217 { /* this structure contains results reported by the routines which
1218 checks Karush-Kuhn-Tucker conditions (for details see comments
1219 to those routines) */
1220 /*--------------------------------------------------------------*/
1221 /* xR - A * xS = 0 (KKT.PE) */
1222 double pe_ae_max;
1223 /* largest absolute error */
1224 int pe_ae_row;
1225 /* number of row with largest absolute error */
1226 double pe_re_max;
1227 /* largest relative error */
1228 int pe_re_row;
1229 /* number of row with largest relative error */
1230 int pe_quality;
1231 /* quality of primal solution:
1232 'H' - high
1233 'M' - medium
1234 'L' - low
1235 '?' - primal solution is wrong */
1236 /*--------------------------------------------------------------*/
1237 /* l[k] <= x[k] <= u[k] (KKT.PB) */
1238 double pb_ae_max;
1239 /* largest absolute error */
1240 int pb_ae_ind;
1241 /* number of variable with largest absolute error */
1242 double pb_re_max;
1243 /* largest relative error */
1244 int pb_re_ind;
1245 /* number of variable with largest relative error */
1246 int pb_quality;
1247 /* quality of primal feasibility:
1248 'H' - high
1249 'M' - medium
1250 'L' - low
1251 '?' - primal solution is infeasible */
1252 /*--------------------------------------------------------------*/
1253 /* A' * (dR - cR) + (dS - cS) = 0 (KKT.DE) */
1254 double de_ae_max;
1255 /* largest absolute error */
1256 int de_ae_col;
1257 /* number of column with largest absolute error */
1258 double de_re_max;
1259 /* largest relative error */
1260 int de_re_col;
1261 /* number of column with largest relative error */
1262 int de_quality;
1263 /* quality of dual solution:
1264 'H' - high
1265 'M' - medium
1266 'L' - low
1267 '?' - dual solution is wrong */
1268 /*--------------------------------------------------------------*/
1269 /* d[k] >= 0 or d[k] <= 0 (KKT.DB) */
1270 double db_ae_max;
1271 /* largest absolute error */
1272 int db_ae_ind;
1273 /* number of variable with largest absolute error */
1274 double db_re_max;
1275 /* largest relative error */
1276 int db_re_ind;
1277 /* number of variable with largest relative error */
1278 int db_quality;
1279 /* quality of dual feasibility:
1280 'H' - high
1281 'M' - medium
1282 'L' - low
1283 '?' - dual solution is infeasible */
1284 /*--------------------------------------------------------------*/
1285 /* (x[k] - bound of x[k]) * d[k] = 0 (KKT.CS) */
1286 double cs_ae_max;
1287 /* largest absolute error */
1288 int cs_ae_ind;
1289 /* number of variable with largest absolute error */
1290 double cs_re_max;
1291 /* largest relative error */
1292 int cs_re_ind;
1293 /* number of variable with largest relative error */
1294 int cs_quality;
1295 /* quality of complementary slackness:
1296 'H' - high
1297 'M' - medium
1298 'L' - low
1299 '?' - primal and dual solutions are not complementary */
1300 } LPXKKT;
1302 #define lpx_create_prob _glp_lpx_create_prob
1303 LPX *lpx_create_prob(void);
1304 /* create problem object */
1306 #define lpx_set_prob_name _glp_lpx_set_prob_name
1307 void lpx_set_prob_name(LPX *lp, const char *name);
1308 /* assign (change) problem name */
1310 #define lpx_set_obj_name _glp_lpx_set_obj_name
1311 void lpx_set_obj_name(LPX *lp, const char *name);
1312 /* assign (change) objective function name */
1314 #define lpx_set_obj_dir _glp_lpx_set_obj_dir
1315 void lpx_set_obj_dir(LPX *lp, int dir);
1316 /* set (change) optimization direction flag */
1318 #define lpx_add_rows _glp_lpx_add_rows
1319 int lpx_add_rows(LPX *lp, int nrs);
1320 /* add new rows to problem object */
1322 #define lpx_add_cols _glp_lpx_add_cols
1323 int lpx_add_cols(LPX *lp, int ncs);
1324 /* add new columns to problem object */
1326 #define lpx_set_row_name _glp_lpx_set_row_name
1327 void lpx_set_row_name(LPX *lp, int i, const char *name);
1328 /* assign (change) row name */
1330 #define lpx_set_col_name _glp_lpx_set_col_name
1331 void lpx_set_col_name(LPX *lp, int j, const char *name);
1332 /* assign (change) column name */
1334 #define lpx_set_row_bnds _glp_lpx_set_row_bnds
1335 void lpx_set_row_bnds(LPX *lp, int i, int type, double lb, double ub);
1336 /* set (change) row bounds */
1338 #define lpx_set_col_bnds _glp_lpx_set_col_bnds
1339 void lpx_set_col_bnds(LPX *lp, int j, int type, double lb, double ub);
1340 /* set (change) column bounds */
1342 #define lpx_set_obj_coef _glp_lpx_set_obj_coef
1343 void lpx_set_obj_coef(glp_prob *lp, int j, double coef);
1344 /* set (change) obj. coefficient or constant term */
1346 #define lpx_set_mat_row _glp_lpx_set_mat_row
1347 void lpx_set_mat_row(LPX *lp, int i, int len, const int ind[],
1348 const double val[]);
1349 /* set (replace) row of the constraint matrix */
1351 #define lpx_set_mat_col _glp_lpx_set_mat_col
1352 void lpx_set_mat_col(LPX *lp, int j, int len, const int ind[],
1353 const double val[]);
1354 /* set (replace) column of the constraint matrix */
1356 #define lpx_load_matrix _glp_lpx_load_matrix
1357 void lpx_load_matrix(LPX *lp, int ne, const int ia[], const int ja[],
1358 const double ar[]);
1359 /* load (replace) the whole constraint matrix */
1361 #define lpx_del_rows _glp_lpx_del_rows
1362 void lpx_del_rows(LPX *lp, int nrs, const int num[]);
1363 /* delete specified rows from problem object */
1365 #define lpx_del_cols _glp_lpx_del_cols
1366 void lpx_del_cols(LPX *lp, int ncs, const int num[]);
1367 /* delete specified columns from problem object */
1369 #define lpx_delete_prob _glp_lpx_delete_prob
1370 void lpx_delete_prob(LPX *lp);
1371 /* delete problem object */
1373 #define lpx_get_prob_name _glp_lpx_get_prob_name
1374 const char *lpx_get_prob_name(LPX *lp);
1375 /* retrieve problem name */
1377 #define lpx_get_obj_name _glp_lpx_get_obj_name
1378 const char *lpx_get_obj_name(LPX *lp);
1379 /* retrieve objective function name */
1381 #define lpx_get_obj_dir _glp_lpx_get_obj_dir
1382 int lpx_get_obj_dir(LPX *lp);
1383 /* retrieve optimization direction flag */
1385 #define lpx_get_num_rows _glp_lpx_get_num_rows
1386 int lpx_get_num_rows(LPX *lp);
1387 /* retrieve number of rows */
1389 #define lpx_get_num_cols _glp_lpx_get_num_cols
1390 int lpx_get_num_cols(LPX *lp);
1391 /* retrieve number of columns */
1393 #define lpx_get_row_name _glp_lpx_get_row_name
1394 const char *lpx_get_row_name(LPX *lp, int i);
1395 /* retrieve row name */
1397 #define lpx_get_col_name _glp_lpx_get_col_name
1398 const char *lpx_get_col_name(LPX *lp, int j);
1399 /* retrieve column name */
1401 #define lpx_get_row_type _glp_lpx_get_row_type
1402 int lpx_get_row_type(LPX *lp, int i);
1403 /* retrieve row type */
1405 #define lpx_get_row_lb _glp_lpx_get_row_lb
1406 double lpx_get_row_lb(LPX *lp, int i);
1407 /* retrieve row lower bound */
1409 #define lpx_get_row_ub _glp_lpx_get_row_ub
1410 double lpx_get_row_ub(LPX *lp, int i);
1411 /* retrieve row upper bound */
1413 #define lpx_get_row_bnds _glp_lpx_get_row_bnds
1414 void lpx_get_row_bnds(LPX *lp, int i, int *typx, double *lb,
1415 double *ub);
1416 /* retrieve row bounds */
1418 #define lpx_get_col_type _glp_lpx_get_col_type
1419 int lpx_get_col_type(LPX *lp, int j);
1420 /* retrieve column type */
1422 #define lpx_get_col_lb _glp_lpx_get_col_lb
1423 double lpx_get_col_lb(LPX *lp, int j);
1424 /* retrieve column lower bound */
1426 #define lpx_get_col_ub _glp_lpx_get_col_ub
1427 double lpx_get_col_ub(LPX *lp, int j);
1428 /* retrieve column upper bound */
1430 #define lpx_get_col_bnds _glp_lpx_get_col_bnds
1431 void lpx_get_col_bnds(LPX *lp, int j, int *typx, double *lb,
1432 double *ub);
1433 /* retrieve column bounds */
1435 #define lpx_get_obj_coef _glp_lpx_get_obj_coef
1436 double lpx_get_obj_coef(LPX *lp, int j);
1437 /* retrieve obj. coefficient or constant term */
1439 #define lpx_get_num_nz _glp_lpx_get_num_nz
1440 int lpx_get_num_nz(LPX *lp);
1441 /* retrieve number of constraint coefficients */
1443 #define lpx_get_mat_row _glp_lpx_get_mat_row
1444 int lpx_get_mat_row(LPX *lp, int i, int ind[], double val[]);
1445 /* retrieve row of the constraint matrix */
1447 #define lpx_get_mat_col _glp_lpx_get_mat_col
1448 int lpx_get_mat_col(LPX *lp, int j, int ind[], double val[]);
1449 /* retrieve column of the constraint matrix */
1451 #define lpx_create_index _glp_lpx_create_index
1452 void lpx_create_index(LPX *lp);
1453 /* create the name index */
1455 #define lpx_find_row _glp_lpx_find_row
1456 int lpx_find_row(LPX *lp, const char *name);
1457 /* find row by its name */
1459 #define lpx_find_col _glp_lpx_find_col
1460 int lpx_find_col(LPX *lp, const char *name);
1461 /* find column by its name */
1463 #define lpx_delete_index _glp_lpx_delete_index
1464 void lpx_delete_index(LPX *lp);
1465 /* delete the name index */
1467 #define lpx_scale_prob _glp_lpx_scale_prob
1468 void lpx_scale_prob(LPX *lp);
1469 /* scale problem data */
1471 #define lpx_unscale_prob _glp_lpx_unscale_prob
1472 void lpx_unscale_prob(LPX *lp);
1473 /* unscale problem data */
1475 #define lpx_set_row_stat _glp_lpx_set_row_stat
1476 void lpx_set_row_stat(LPX *lp, int i, int stat);
1477 /* set (change) row status */
1479 #define lpx_set_col_stat _glp_lpx_set_col_stat
1480 void lpx_set_col_stat(LPX *lp, int j, int stat);
1481 /* set (change) column status */
1483 #define lpx_std_basis _glp_lpx_std_basis
1484 void lpx_std_basis(LPX *lp);
1485 /* construct standard initial LP basis */
1487 #define lpx_adv_basis _glp_lpx_adv_basis
1488 void lpx_adv_basis(LPX *lp);
1489 /* construct advanced initial LP basis */
1491 #define lpx_cpx_basis _glp_lpx_cpx_basis
1492 void lpx_cpx_basis(LPX *lp);
1493 /* construct Bixby's initial LP basis */
1495 #define lpx_simplex _glp_lpx_simplex
1496 int lpx_simplex(LPX *lp);
1497 /* easy-to-use driver to the simplex method */
1499 #define lpx_exact _glp_lpx_exact
1500 int lpx_exact(LPX *lp);
1501 /* easy-to-use driver to the exact simplex method */
1503 #define lpx_get_status _glp_lpx_get_status
1504 int lpx_get_status(LPX *lp);
1505 /* retrieve generic status of basic solution */
1507 #define lpx_get_prim_stat _glp_lpx_get_prim_stat
1508 int lpx_get_prim_stat(LPX *lp);
1509 /* retrieve primal status of basic solution */
1511 #define lpx_get_dual_stat _glp_lpx_get_dual_stat
1512 int lpx_get_dual_stat(LPX *lp);
1513 /* retrieve dual status of basic solution */
1515 #define lpx_get_obj_val _glp_lpx_get_obj_val
1516 double lpx_get_obj_val(LPX *lp);
1517 /* retrieve objective value (basic solution) */
1519 #define lpx_get_row_stat _glp_lpx_get_row_stat
1520 int lpx_get_row_stat(LPX *lp, int i);
1521 /* retrieve row status (basic solution) */
1523 #define lpx_get_row_prim _glp_lpx_get_row_prim
1524 double lpx_get_row_prim(LPX *lp, int i);
1525 /* retrieve row primal value (basic solution) */
1527 #define lpx_get_row_dual _glp_lpx_get_row_dual
1528 double lpx_get_row_dual(LPX *lp, int i);
1529 /* retrieve row dual value (basic solution) */
1531 #define lpx_get_row_info _glp_lpx_get_row_info
1532 void lpx_get_row_info(LPX *lp, int i, int *tagx, double *vx,
1533 double *dx);
1534 /* obtain row solution information */
1536 #define lpx_get_col_stat _glp_lpx_get_col_stat
1537 int lpx_get_col_stat(LPX *lp, int j);
1538 /* retrieve column status (basic solution) */
1540 #define lpx_get_col_prim _glp_lpx_get_col_prim
1541 double lpx_get_col_prim(LPX *lp, int j);
1542 /* retrieve column primal value (basic solution) */
1544 #define lpx_get_col_dual _glp_lpx_get_col_dual
1545 double lpx_get_col_dual(glp_prob *lp, int j);
1546 /* retrieve column dual value (basic solution) */
1548 #define lpx_get_col_info _glp_lpx_get_col_info
1549 void lpx_get_col_info(LPX *lp, int j, int *tagx, double *vx,
1550 double *dx);
1551 /* obtain column solution information (obsolete) */
1553 #define lpx_get_ray_info _glp_lpx_get_ray_info
1554 int lpx_get_ray_info(LPX *lp);
1555 /* determine what causes primal unboundness */
1557 #define lpx_check_kkt _glp_lpx_check_kkt
1558 void lpx_check_kkt(LPX *lp, int scaled, LPXKKT *kkt);
1559 /* check Karush-Kuhn-Tucker conditions */
1561 #define lpx_warm_up _glp_lpx_warm_up
1562 int lpx_warm_up(LPX *lp);
1563 /* "warm up" LP basis */
1565 #define lpx_eval_tab_row _glp_lpx_eval_tab_row
1566 int lpx_eval_tab_row(LPX *lp, int k, int ind[], double val[]);
1567 /* compute row of the simplex table */
1569 #define lpx_eval_tab_col _glp_lpx_eval_tab_col
1570 int lpx_eval_tab_col(LPX *lp, int k, int ind[], double val[]);
1571 /* compute column of the simplex table */
1573 #define lpx_transform_row _glp_lpx_transform_row
1574 int lpx_transform_row(LPX *lp, int len, int ind[], double val[]);
1575 /* transform explicitly specified row */
1577 #define lpx_transform_col _glp_lpx_transform_col
1578 int lpx_transform_col(LPX *lp, int len, int ind[], double val[]);
1579 /* transform explicitly specified column */
1581 #define lpx_prim_ratio_test _glp_lpx_prim_ratio_test
1582 int lpx_prim_ratio_test(LPX *lp, int len, const int ind[],
1583 const double val[], int how, double tol);
1584 /* perform primal ratio test */
1586 #define lpx_dual_ratio_test _glp_lpx_dual_ratio_test
1587 int lpx_dual_ratio_test(LPX *lp, int len, const int ind[],
1588 const double val[], int how, double tol);
1589 /* perform dual ratio test */
1591 #define lpx_interior _glp_lpx_interior
1592 int lpx_interior(LPX *lp);
1593 /* easy-to-use driver to the interior point method */
1595 #define lpx_ipt_status _glp_lpx_ipt_status
1596 int lpx_ipt_status(LPX *lp);
1597 /* retrieve status of interior-point solution */
1599 #define lpx_ipt_obj_val _glp_lpx_ipt_obj_val
1600 double lpx_ipt_obj_val(LPX *lp);
1601 /* retrieve objective value (interior point) */
1603 #define lpx_ipt_row_prim _glp_lpx_ipt_row_prim
1604 double lpx_ipt_row_prim(LPX *lp, int i);
1605 /* retrieve row primal value (interior point) */
1607 #define lpx_ipt_row_dual _glp_lpx_ipt_row_dual
1608 double lpx_ipt_row_dual(LPX *lp, int i);
1609 /* retrieve row dual value (interior point) */
1611 #define lpx_ipt_col_prim _glp_lpx_ipt_col_prim
1612 double lpx_ipt_col_prim(LPX *lp, int j);
1613 /* retrieve column primal value (interior point) */
1615 #define lpx_ipt_col_dual _glp_lpx_ipt_col_dual
1616 double lpx_ipt_col_dual(LPX *lp, int j);
1617 /* retrieve column dual value (interior point) */
1619 #define lpx_set_class _glp_lpx_set_class
1620 void lpx_set_class(LPX *lp, int klass);
1621 /* set problem class */
1623 #define lpx_get_class _glp_lpx_get_class
1624 int lpx_get_class(LPX *lp);
1625 /* determine problem klass */
1627 #define lpx_set_col_kind _glp_lpx_set_col_kind
1628 void lpx_set_col_kind(LPX *lp, int j, int kind);
1629 /* set (change) column kind */
1631 #define lpx_get_col_kind _glp_lpx_get_col_kind
1632 int lpx_get_col_kind(LPX *lp, int j);
1633 /* retrieve column kind */
1635 #define lpx_get_num_int _glp_lpx_get_num_int
1636 int lpx_get_num_int(LPX *lp);
1637 /* retrieve number of integer columns */
1639 #define lpx_get_num_bin _glp_lpx_get_num_bin
1640 int lpx_get_num_bin(LPX *lp);
1641 /* retrieve number of binary columns */
1643 #define lpx_integer _glp_lpx_integer
1644 int lpx_integer(LPX *lp);
1645 /* easy-to-use driver to the branch-and-bound method */
1647 #define lpx_intopt _glp_lpx_intopt
1648 int lpx_intopt(LPX *lp);
1649 /* easy-to-use driver to the branch-and-bound method */
1651 #define lpx_mip_status _glp_lpx_mip_status
1652 int lpx_mip_status(LPX *lp);
1653 /* retrieve status of MIP solution */
1655 #define lpx_mip_obj_val _glp_lpx_mip_obj_val
1656 double lpx_mip_obj_val(LPX *lp);
1657 /* retrieve objective value (MIP solution) */
1659 #define lpx_mip_row_val _glp_lpx_mip_row_val
1660 double lpx_mip_row_val(LPX *lp, int i);
1661 /* retrieve row value (MIP solution) */
1663 #define lpx_mip_col_val _glp_lpx_mip_col_val
1664 double lpx_mip_col_val(LPX *lp, int j);
1665 /* retrieve column value (MIP solution) */
1667 #define lpx_check_int _glp_lpx_check_int
1668 void lpx_check_int(LPX *lp, LPXKKT *kkt);
1669 /* check integer feasibility conditions */
1671 #define lpx_reset_parms _glp_lpx_reset_parms
1672 void lpx_reset_parms(LPX *lp);
1673 /* reset control parameters to default values */
1675 #define lpx_set_int_parm _glp_lpx_set_int_parm
1676 void lpx_set_int_parm(LPX *lp, int parm, int val);
1677 /* set (change) integer control parameter */
1679 #define lpx_get_int_parm _glp_lpx_get_int_parm
1680 int lpx_get_int_parm(LPX *lp, int parm);
1681 /* query integer control parameter */
1683 #define lpx_set_real_parm _glp_lpx_set_real_parm
1684 void lpx_set_real_parm(LPX *lp, int parm, double val);
1685 /* set (change) real control parameter */
1687 #define lpx_get_real_parm _glp_lpx_get_real_parm
1688 double lpx_get_real_parm(LPX *lp, int parm);
1689 /* query real control parameter */
1691 #define lpx_read_mps _glp_lpx_read_mps
1692 LPX *lpx_read_mps(const char *fname);
1693 /* read problem data in fixed MPS format */
1695 #define lpx_write_mps _glp_lpx_write_mps
1696 int lpx_write_mps(LPX *lp, const char *fname);
1697 /* write problem data in fixed MPS format */
1699 #define lpx_read_bas _glp_lpx_read_bas
1700 int lpx_read_bas(LPX *lp, const char *fname);
1701 /* read LP basis in fixed MPS format */
1703 #define lpx_write_bas _glp_lpx_write_bas
1704 int lpx_write_bas(LPX *lp, const char *fname);
1705 /* write LP basis in fixed MPS format */
1707 #define lpx_read_freemps _glp_lpx_read_freemps
1708 LPX *lpx_read_freemps(const char *fname);
1709 /* read problem data in free MPS format */
1711 #define lpx_write_freemps _glp_lpx_write_freemps
1712 int lpx_write_freemps(LPX *lp, const char *fname);
1713 /* write problem data in free MPS format */
1715 #define lpx_read_cpxlp _glp_lpx_read_cpxlp
1716 LPX *lpx_read_cpxlp(const char *fname);
1717 /* read problem data in CPLEX LP format */
1719 #define lpx_write_cpxlp _glp_lpx_write_cpxlp
1720 int lpx_write_cpxlp(LPX *lp, const char *fname);
1721 /* write problem data in CPLEX LP format */
1723 #define lpx_read_model _glp_lpx_read_model
1724 LPX *lpx_read_model(const char *model, const char *data,
1725 const char *output);
1726 /* read LP/MIP model written in GNU MathProg language */
1728 #define lpx_print_prob _glp_lpx_print_prob
1729 int lpx_print_prob(LPX *lp, const char *fname);
1730 /* write problem data in plain text format */
1732 #define lpx_print_sol _glp_lpx_print_sol
1733 int lpx_print_sol(LPX *lp, const char *fname);
1734 /* write LP problem solution in printable format */
1736 #define lpx_print_sens_bnds _glp_lpx_print_sens_bnds
1737 int lpx_print_sens_bnds(LPX *lp, const char *fname);
1738 /* write bounds sensitivity information */
1740 #define lpx_print_ips _glp_lpx_print_ips
1741 int lpx_print_ips(LPX *lp, const char *fname);
1742 /* write interior point solution in printable format */
1744 #define lpx_print_mip _glp_lpx_print_mip
1745 int lpx_print_mip(LPX *lp, const char *fname);
1746 /* write MIP problem solution in printable format */
1748 #define lpx_is_b_avail _glp_lpx_is_b_avail
1749 int lpx_is_b_avail(LPX *lp);
1750 /* check if LP basis is available */
1752 #define lpx_write_pb _glp_lpx_write_pb
1753 int lpx_write_pb(LPX *lp, const char *fname, int normalized,
1754 int binarize);
1755 /* write problem data in (normalized) OPB format */
1757 #define lpx_main _glp_lpx_main
1758 int lpx_main(int argc, const char *argv[]);
1759 /* stand-alone LP/MIP solver */
1761 #ifdef __cplusplus
1762 }
1763 #endif
1765 #endif
1767 /* eof */