COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpapi19.c @ 2:4c8956a7bdf4

Last change on this file since 2:4c8956a7bdf4 was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 14 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 45.2 KB
Line 
1/* glpapi19.c (stand-alone LP/MIP solver) */
2
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 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***********************************************************************/
24
25#include "glpapi.h"
26#include "glpgmp.h"
27
28struct csa
29{     /* common storage area */
30      glp_prob *prob;
31      /* LP/MIP problem object */
32      glp_bfcp bfcp;
33      /* basis factorization control parameters */
34      glp_smcp smcp;
35      /* simplex method control parameters */
36      glp_iptcp iptcp;
37      /* interior-point method control parameters */
38      glp_iocp iocp;
39      /* integer optimizer control parameters */
40      glp_tran *tran;
41      /* model translator workspace */
42      glp_graph *graph;
43      /* network problem object */
44      int format;
45      /* problem file format: */
46#define FMT_MPS_DECK    1  /* fixed MPS */
47#define FMT_MPS_FILE    2  /* free MPS */
48#define FMT_LP          3  /* CPLEX LP */
49#define FMT_GLP         4  /* GLPK LP/MIP */
50#define FMT_MATHPROG    5  /* MathProg */
51#define FMT_MIN_COST    6  /* DIMACS min-cost flow */
52#define FMT_MAX_FLOW    7  /* DIMACS maximum flow */
53      const char *in_file;
54      /* name of input problem file */
55#define DATA_MAX 10
56      /* maximal number of input data files */
57      int ndf;
58      /* number of input data files specified */
59      const char *in_data[1+DATA_MAX];
60      /* name(s) of input data file(s) */
61      const char *out_dpy;
62      /* name of output file to send display output; NULL means the
63         display output is sent to the terminal */
64      int seed;
65      /* seed value to be passed to the MathProg translator; initially
66         set to 1; 0x80000000 means the value is omitted */
67      int solution;
68      /* solution type flag: */
69#define SOL_BASIC       1  /* basic */
70#define SOL_INTERIOR    2  /* interior-point */
71#define SOL_INTEGER     3  /* mixed integer */
72      const char *in_res;
73      /* name of input solution file in raw format */
74      int dir;
75      /* optimization direction flag:
76         0       - not specified
77         GLP_MIN - minimization
78         GLP_MAX - maximization */
79      int scale;
80      /* automatic problem scaling flag */
81      const char *out_sol;
82      /* name of output solution file in printable format */
83      const char *out_res;
84      /* name of output solution file in raw format */
85      const char *out_ranges;
86      /* name of output file to write sensitivity analysis report */
87      int check;
88      /* input data checking flag; no solution is performed */
89      const char *new_name;
90      /* new name to be assigned to the problem */
91      const char *out_mps;
92      /* name of output problem file in fixed MPS format */
93      const char *out_freemps;
94      /* name of output problem file in free MPS format */
95      const char *out_cpxlp;
96      /* name of output problem file in CPLEX LP format */
97      const char *out_glp;
98      /* name of output problem file in GLPK format */
99      const char *out_pb;
100      /* name of output problem file in OPB format */
101      const char *out_npb;
102      /* name of output problem file in normalized OPB format */
103      const char *log_file;
104      /* name of output file to hardcopy terminal output */
105      int crash;
106      /* initial basis option: */
107#define USE_STD_BASIS   1  /* use standard basis */
108#define USE_ADV_BASIS   2  /* use advanced basis */
109#define USE_CPX_BASIS   3  /* use Bixby's basis */
110#define USE_INI_BASIS   4  /* use initial basis from ini_file */
111      const char *ini_file;
112      /* name of input file containing initial basis */
113      int exact;
114      /* flag to use glp_exact rather than glp_simplex */
115      int xcheck;
116      /* flag to check final basis with glp_exact */
117      int nomip;
118      /* flag to consider MIP as pure LP */
119};
120
121static void print_help(const char *my_name)
122{     /* print help information */
123      xprintf("Usage: %s [options...] filename\n", my_name);
124      xprintf("\n");
125      xprintf("General options:\n");
126      xprintf("   --mps             read LP/MIP problem in fixed MPS fo"
127         "rmat\n");
128      xprintf("   --freemps         read LP/MIP problem in free MPS for"
129         "mat (default)\n");
130      xprintf("   --lp              read LP/MIP problem in CPLEX LP for"
131         "mat\n");
132      xprintf("   --glp             read LP/MIP problem in GLPK format "
133         "\n");
134      xprintf("   --math            read LP/MIP model written in GNU Ma"
135         "thProg modeling\n");
136      xprintf("                     language\n");
137      xprintf("   -m filename, --model filename\n");
138      xprintf("                     read model section and optional dat"
139         "a section from\n");
140      xprintf("                     filename (same as --math)\n");
141      xprintf("   -d filename, --data filename\n");
142      xprintf("                     read data section from filename (fo"
143         "r --math only);\n");
144      xprintf("                     if model file also has data section"
145         ", it is ignored\n");
146      xprintf("   -y filename, --display filename\n");
147      xprintf("                     send display output to filename (fo"
148         "r --math only);\n");
149      xprintf("                     by default the output is sent to te"
150         "rminal\n");
151      xprintf("   --seed value      initialize pseudo-random number gen"
152         "erator used in\n");
153      xprintf("                     MathProg model with specified seed "
154         "(any integer);\n");
155      xprintf("                     if seed value is ?, some random see"
156         "d will be used\n");
157      xprintf("   --mincost         read min-cost flow problem in DIMAC"
158         "S format\n");
159      xprintf("   --maxflow         read maximum flow problem in DIMACS"
160         " format\n");
161      xprintf("   --simplex         use simplex method (default)\n");
162      xprintf("   --interior        use interior point method (LP only)"
163         "\n");
164      xprintf("   -r filename, --read filename\n");
165      xprintf("                     read solution from filename rather "
166         "to find it with\n");
167      xprintf("                     the solver\n");
168      xprintf("   --min             minimization\n");
169      xprintf("   --max             maximization\n");
170      xprintf("   --scale           scale problem (default)\n");
171      xprintf("   --noscale         do not scale problem\n");
172      xprintf("   -o filename, --output filename\n");
173      xprintf("                     write solution to filename in print"
174         "able format\n");
175      xprintf("   -w filename, --write filename\n");
176      xprintf("                     write solution to filename in plain"
177         " text format\n");
178      xprintf("   --ranges filename\n");
179      xprintf("                     write sensitivity analysis report t"
180         "o filename in\n");
181      xprintf("                     printable format (simplex only)\n");
182      xprintf("   --tmlim nnn       limit solution time to nnn seconds "
183         "\n");
184      xprintf("   --memlim nnn      limit available memory to nnn megab"
185         "ytes\n");
186      xprintf("   --check           do not solve problem, check input d"
187         "ata only\n");
188      xprintf("   --name probname   change problem name to probname\n");
189      xprintf("   --wmps filename   write problem to filename in fixed "
190         "MPS format\n");
191      xprintf("   --wfreemps filename\n");
192      xprintf("                     write problem to filename in free M"
193         "PS format\n");
194      xprintf("   --wlp filename    write problem to filename in CPLEX "
195         "LP format\n");
196      xprintf("   --wglp filename   write problem to filename in GLPK f"
197         "ormat\n");
198#if 0
199      xprintf("   --wpb filename    write problem to filename in OPB fo"
200         "rmat\n");
201      xprintf("   --wnpb filename   write problem to filename in normal"
202         "ized OPB format\n");
203#endif
204      xprintf("   --log filename    write copy of terminal output to fi"
205         "lename\n");
206      xprintf("   -h, --help        display this help information and e"
207         "xit\n");
208      xprintf("   -v, --version     display program version and exit\n")
209         ;
210      xprintf("\n");
211      xprintf("LP basis factorization options:\n");
212      xprintf("   --luf             LU + Forrest-Tomlin update\n");
213      xprintf("                     (faster, less stable; default)\n");
214      xprintf("   --cbg             LU + Schur complement + Bartels-Gol"
215         "ub update\n");
216      xprintf("                     (slower, more stable)\n");
217      xprintf("   --cgr             LU + Schur complement + Givens rota"
218         "tion update\n");
219      xprintf("                     (slower, more stable)\n");
220      xprintf("\n");
221      xprintf("Options specific to simplex solver:\n");
222      xprintf("   --primal          use primal simplex (default)\n");
223      xprintf("   --dual            use dual simplex\n");
224      xprintf("   --std             use standard initial basis of all s"
225         "lacks\n");
226      xprintf("   --adv             use advanced initial basis (default"
227         ")\n");
228      xprintf("   --bib             use Bixby's initial basis\n");
229      xprintf("   --ini filename    use as initial basis previously sav"
230         "ed with -w\n");
231      xprintf("                     (disables LP presolver)\n");
232      xprintf("   --steep           use steepest edge technique (defaul"
233         "t)\n");
234      xprintf("   --nosteep         use standard \"textbook\" pricing\n"
235         );
236      xprintf("   --relax           use Harris' two-pass ratio test (de"
237         "fault)\n");
238      xprintf("   --norelax         use standard \"textbook\" ratio tes"
239         "t\n");
240      xprintf("   --presol          use presolver (default; assumes --s"
241         "cale and --adv)\n");
242      xprintf("   --nopresol        do not use presolver\n");
243      xprintf("   --exact           use simplex method based on exact a"
244         "rithmetic\n");
245      xprintf("   --xcheck          check final basis using exact arith"
246         "metic\n");
247      xprintf("\n");
248      xprintf("Options specific to interior-point solver:\n");
249      xprintf("   --nord            use natural (original) ordering\n");
250      xprintf("   --qmd             use quotient minimum degree orderin"
251         "g\n");
252      xprintf("   --amd             use approximate minimum degree orde"
253         "ring (default)\n");
254      xprintf("   --symamd          use approximate minimum degree orde"
255         "ring\n");
256      xprintf("\n");
257      xprintf("Options specific to MIP solver:\n");
258      xprintf("   --nomip           consider all integer variables as c"
259         "ontinuous\n");
260      xprintf("                     (allows solving MIP as pure LP)\n");
261      xprintf("   --first           branch on first integer variable\n")
262         ;
263      xprintf("   --last            branch on last integer variable\n");
264      xprintf("   --mostf           branch on most fractional variable "
265         "\n");
266      xprintf("   --drtom           branch using heuristic by Driebeck "
267         "and Tomlin\n");
268      xprintf("                     (default)\n");
269      xprintf("   --pcost           branch using hybrid pseudocost heur"
270         "istic (may be\n");
271      xprintf("                     useful for hard instances)\n");
272      xprintf("   --dfs             backtrack using depth first search "
273         "\n");
274      xprintf("   --bfs             backtrack using breadth first searc"
275         "h\n");
276      xprintf("   --bestp           backtrack using the best projection"
277         " heuristic\n");
278      xprintf("   --bestb           backtrack using node with best loca"
279         "l bound\n");
280      xprintf("                     (default)\n");
281      xprintf("   --intopt          use MIP presolver (default)\n");
282      xprintf("   --nointopt        do not use MIP presolver\n");
283      xprintf("   --binarize        replace general integer variables b"
284         "y binary ones\n");
285      xprintf("                     (assumes --intopt)\n");
286      xprintf("   --fpump           apply feasibility pump heuristic\n")
287         ;
288      xprintf("   --gomory          generate Gomory's mixed integer cut"
289         "s\n");
290      xprintf("   --mir             generate MIR (mixed integer roundin"
291         "g) cuts\n");
292      xprintf("   --cover           generate mixed cover cuts\n");
293      xprintf("   --clique          generate clique cuts\n");
294      xprintf("   --cuts            generate all cuts above\n");
295      xprintf("   --mipgap tol      set relative mip gap tolerance to t"
296         "ol\n");
297      xprintf("\n");
298      xprintf("For description of the MPS and CPLEX LP formats see Refe"
299         "rence Manual.\n");
300      xprintf("For description of the modeling language see \"GLPK: Mod"
301         "eling Language\n");
302      xprintf("GNU MathProg\". Both documents are included in the GLPK "
303         "distribution.\n");
304      xprintf("\n");
305      xprintf("See GLPK web page at <http://www.gnu.org/software/glpk/g"
306         "lpk.html>.\n");
307      xprintf("\n");
308      xprintf("Please report bugs to <bug-glpk@gnu.org>.\n");
309      return;
310}
311
312static void print_version(int briefly)
313{     /* print version information */
314      xprintf("GLPSOL: GLPK LP/MIP Solver, v%s\n", glp_version());
315      if (briefly) goto done;
316      xprintf("\n");
317      xprintf("Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, "
318         "2007, 2008,\n");
319      xprintf("2009, 2010 Andrew Makhorin, Department for Applied Infor"
320         "matics, Moscow\n");
321      xprintf("Aviation Institute, Moscow, Russia. All rights reserved."
322         "\n");
323      xprintf("\n");
324      xprintf("This program has ABSOLUTELY NO WARRANTY.\n");
325      xprintf("\n");
326      xprintf("This program is free software; you may re-distribute it "
327         "under the terms\n");
328      xprintf("of the GNU General Public License version 3 or later.\n")
329         ;
330done: return;
331}
332
333static int parse_cmdline(struct csa *csa, int argc, const char *argv[])
334{     /* parse command-line parameters */
335      int k;
336#define p(str) (strcmp(argv[k], str) == 0)
337      for (k = 1; k < argc; k++)
338      {  if (p("--mps"))
339            csa->format = FMT_MPS_DECK;
340         else if (p("--freemps"))
341            csa->format = FMT_MPS_FILE;
342         else if (p("--lp") || p("--cpxlp"))
343            csa->format = FMT_LP;
344         else if (p("--glp"))
345            csa->format = FMT_GLP;
346         else if (p("--math") || p("-m") || p("--model"))
347            csa->format = FMT_MATHPROG;
348         else if (p("-d") || p("--data"))
349         {  k++;
350            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
351            {  xprintf("No input data file specified\n");
352               return 1;
353            }
354            if (csa->ndf == DATA_MAX)
355            {  xprintf("Too many input data files\n");
356               return 1;
357            }
358            csa->in_data[++(csa->ndf)] = argv[k];
359         }
360         else if (p("-y") || p("--display"))
361         {  k++;
362            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
363            {  xprintf("No display output file specified\n");
364               return 1;
365            }
366            if (csa->out_dpy != NULL)
367            {  xprintf("Only one display output file allowed\n");
368               return 1;
369            }
370            csa->out_dpy = argv[k];
371         }
372         else if (p("--seed"))
373         {  k++;
374            if (k == argc || argv[k][0] == '\0' ||
375               argv[k][0] == '-' && !isdigit((unsigned char)argv[k][1]))
376            {  xprintf("No seed value specified\n");
377               return 1;
378            }
379            if (strcmp(argv[k], "?") == 0)
380               csa->seed = 0x80000000;
381            else if (str2int(argv[k], &csa->seed))
382            {  xprintf("Invalid seed value `%s'\n", argv[k]);
383               return 1;
384            }
385         }
386         else if (p("--mincost"))
387            csa->format = FMT_MIN_COST;
388         else if (p("--maxflow"))
389            csa->format = FMT_MAX_FLOW;
390         else if (p("--simplex"))
391            csa->solution = SOL_BASIC;
392         else if (p("--interior"))
393            csa->solution = SOL_INTERIOR;
394#if 1 /* 28/V-2010 */
395         else if (p("--alien"))
396            csa->iocp.alien = GLP_ON;
397#endif
398         else if (p("-r") || p("--read"))
399         {  k++;
400            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
401            {  xprintf("No input solution file specified\n");
402               return 1;
403            }
404            if (csa->in_res != NULL)
405            {  xprintf("Only one input solution file allowed\n");
406               return 1;
407            }
408            csa->in_res = argv[k];
409         }
410         else if (p("--min"))
411            csa->dir = GLP_MIN;
412         else if (p("--max"))
413            csa->dir = GLP_MAX;
414         else if (p("--scale"))
415            csa->scale = 1;
416         else if (p("--noscale"))
417            csa->scale = 0;
418         else if (p("-o") || p("--output"))
419         {  k++;
420            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
421            {  xprintf("No output solution file specified\n");
422               return 1;
423            }
424            if (csa->out_sol != NULL)
425            {  xprintf("Only one output solution file allowed\n");
426               return 1;
427            }
428            csa->out_sol = argv[k];
429         }
430         else if (p("-w") || p("--write"))
431         {  k++;
432            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
433            {  xprintf("No output solution file specified\n");
434               return 1;
435            }
436            if (csa->out_res != NULL)
437            {  xprintf("Only one output solution file allowed\n");
438               return 1;
439            }
440            csa->out_res = argv[k];
441         }
442         else if (p("--ranges") || p("--bounds"))
443         {  k++;
444            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
445            {  xprintf("No output file specified to write sensitivity a"
446                  "nalysis report\n");
447               return 1;
448            }
449            if (csa->out_ranges != NULL)
450            {  xprintf("Only one output file allowed to write sensitivi"
451                  "ty analysis report\n");
452               return 1;
453            }
454            csa->out_ranges = argv[k];
455         }
456         else if (p("--tmlim"))
457         {  int tm_lim;
458            k++;
459            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
460            {  xprintf("No time limit specified\n");
461               return 1;
462            }
463            if (str2int(argv[k], &tm_lim) || tm_lim < 0)
464            {  xprintf("Invalid time limit `%s'\n", argv[k]);
465               return 1;
466            }
467            if (tm_lim <= INT_MAX / 1000)
468               csa->smcp.tm_lim = csa->iocp.tm_lim = 1000 * tm_lim;
469            else
470               csa->smcp.tm_lim = csa->iocp.tm_lim = INT_MAX;
471         }
472         else if (p("--memlim"))
473         {  int mem_lim;
474            k++;
475            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
476            {  xprintf("No memory limit specified\n");
477               return 1;
478            }
479            if (str2int(argv[k], &mem_lim) || mem_lim < 1)
480            {  xprintf("Invalid memory limit `%s'\n", argv[k]);
481               return 1;
482            }
483            glp_mem_limit(mem_lim);
484         }
485         else if (p("--check"))
486            csa->check = 1;
487         else if (p("--name"))
488         {  k++;
489            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
490            {  xprintf("No problem name specified\n");
491               return 1;
492            }
493            if (csa->new_name != NULL)
494            {  xprintf("Only one problem name allowed\n");
495               return 1;
496            }
497            csa->new_name = argv[k];
498         }
499         else if (p("--wmps"))
500         {  k++;
501            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
502            {  xprintf("No fixed MPS output file specified\n");
503               return 1;
504            }
505            if (csa->out_mps != NULL)
506            {  xprintf("Only one fixed MPS output file allowed\n");
507               return 1;
508            }
509            csa->out_mps = argv[k];
510         }
511         else if (p("--wfreemps"))
512         {  k++;
513            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
514            {  xprintf("No free MPS output file specified\n");
515               return 1;
516            }
517            if (csa->out_freemps != NULL)
518            {  xprintf("Only one free MPS output file allowed\n");
519               return 1;
520            }
521            csa->out_freemps = argv[k];
522         }
523         else if (p("--wlp") || p("--wcpxlp") || p("--wlpt"))
524         {  k++;
525            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
526            {  xprintf("No CPLEX LP output file specified\n");
527               return 1;
528            }
529            if (csa->out_cpxlp != NULL)
530            {  xprintf("Only one CPLEX LP output file allowed\n");
531               return 1;
532            }
533            csa->out_cpxlp = argv[k];
534         }
535         else if (p("--wglp"))
536         {  k++;
537            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
538            {  xprintf("No GLPK LP/MIP output file specified\n");
539               return 1;
540            }
541            if (csa->out_glp != NULL)
542            {  xprintf("Only one GLPK LP/MIP output file allowed\n");
543               return 1;
544            }
545            csa->out_glp = argv[k];
546         }
547         else if (p("--wpb"))
548         {  k++;
549            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
550            {  xprintf("No problem output file specified\n");
551               return 1;
552            }
553            if (csa->out_pb != NULL)
554            {  xprintf("Only one OPB output file allowed\n");
555               return 1;
556            }
557            csa->out_pb = argv[k];
558         }
559         else if (p("--wnpb"))
560         {  k++;
561            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
562            {  xprintf("No problem output file specified\n");
563               return 1;
564            }
565            if (csa->out_npb != NULL)
566            {  xprintf("Only one normalized OPB output file allowed\n");
567               return 1;
568            }
569            csa->out_npb = argv[k];
570         }
571         else if (p("--log"))
572         {  k++;
573            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
574            {  xprintf("No log file specified\n");
575               return 1;
576            }
577            if (csa->log_file != NULL)
578            {  xprintf("Only one log file allowed\n");
579               return 1;
580            }
581            csa->log_file = argv[k];
582         }
583         else if (p("-h") || p("--help"))
584         {  print_help(argv[0]);
585            return -1;
586         }
587         else if (p("-v") || p("--version"))
588         {  print_version(0);
589            return -1;
590         }
591         else if (p("--luf"))
592            csa->bfcp.type = GLP_BF_FT;
593         else if (p("--cbg"))
594            csa->bfcp.type = GLP_BF_BG;
595         else if (p("--cgr"))
596            csa->bfcp.type = GLP_BF_GR;
597         else if (p("--primal"))
598            csa->smcp.meth = GLP_PRIMAL;
599         else if (p("--dual"))
600            csa->smcp.meth = GLP_DUAL;
601         else if (p("--std"))
602            csa->crash = USE_STD_BASIS;
603         else if (p("--adv"))
604            csa->crash = USE_ADV_BASIS;
605         else if (p("--bib"))
606            csa->crash = USE_CPX_BASIS;
607         else if (p("--ini"))
608         {  csa->crash = USE_INI_BASIS;
609            csa->smcp.presolve = GLP_OFF;
610            k++;
611            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
612            {  xprintf("No initial basis file specified\n");
613               return 1;
614            }
615            if (csa->ini_file != NULL)
616            {  xprintf("Only one initial basis file allowed\n");
617               return 1;
618            }
619            csa->ini_file = argv[k];
620         }
621         else if (p("--steep"))
622            csa->smcp.pricing = GLP_PT_PSE;
623         else if (p("--nosteep"))
624            csa->smcp.pricing = GLP_PT_STD;
625         else if (p("--relax"))
626            csa->smcp.r_test = GLP_RT_HAR;
627         else if (p("--norelax"))
628            csa->smcp.r_test = GLP_RT_STD;
629         else if (p("--presol"))
630            csa->smcp.presolve = GLP_ON;
631         else if (p("--nopresol"))
632            csa->smcp.presolve = GLP_OFF;
633         else if (p("--exact"))
634            csa->exact = 1;
635         else if (p("--xcheck"))
636            csa->xcheck = 1;
637         else if (p("--nord"))
638            csa->iptcp.ord_alg = GLP_ORD_NONE;
639         else if (p("--qmd"))
640            csa->iptcp.ord_alg = GLP_ORD_QMD;
641         else if (p("--amd"))
642            csa->iptcp.ord_alg = GLP_ORD_AMD;
643         else if (p("--symamd"))
644            csa->iptcp.ord_alg = GLP_ORD_SYMAMD;
645         else if (p("--nomip"))
646            csa->nomip = 1;
647         else if (p("--first"))
648            csa->iocp.br_tech = GLP_BR_FFV;
649         else if (p("--last"))
650            csa->iocp.br_tech = GLP_BR_LFV;
651         else if (p("--drtom"))
652            csa->iocp.br_tech = GLP_BR_DTH;
653         else if (p("--mostf"))
654            csa->iocp.br_tech = GLP_BR_MFV;
655         else if (p("--pcost"))
656            csa->iocp.br_tech = GLP_BR_PCH;
657         else if (p("--dfs"))
658            csa->iocp.bt_tech = GLP_BT_DFS;
659         else if (p("--bfs"))
660            csa->iocp.bt_tech = GLP_BT_BFS;
661         else if (p("--bestp"))
662            csa->iocp.bt_tech = GLP_BT_BPH;
663         else if (p("--bestb"))
664            csa->iocp.bt_tech = GLP_BT_BLB;
665         else if (p("--intopt"))
666            csa->iocp.presolve = GLP_ON;
667         else if (p("--nointopt"))
668            csa->iocp.presolve = GLP_OFF;
669         else if (p("--binarize"))
670            csa->iocp.presolve = csa->iocp.binarize = GLP_ON;
671         else if (p("--fpump"))
672            csa->iocp.fp_heur = GLP_ON;
673         else if (p("--gomory"))
674            csa->iocp.gmi_cuts = GLP_ON;
675         else if (p("--mir"))
676            csa->iocp.mir_cuts = GLP_ON;
677         else if (p("--cover"))
678            csa->iocp.cov_cuts = GLP_ON;
679         else if (p("--clique"))
680            csa->iocp.clq_cuts = GLP_ON;
681         else if (p("--cuts"))
682            csa->iocp.gmi_cuts = csa->iocp.mir_cuts =
683            csa->iocp.cov_cuts = csa->iocp.clq_cuts = GLP_ON;
684         else if (p("--mipgap"))
685         {  double mip_gap;
686            k++;
687            if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
688            {  xprintf("No relative gap tolerance specified\n");
689               return 1;
690            }
691            if (str2num(argv[k], &mip_gap) || mip_gap < 0.0)
692            {  xprintf("Invalid relative mip gap tolerance `%s'\n",
693                  argv[k]);
694               return 1;
695            }
696            csa->iocp.mip_gap = mip_gap;
697         }
698         else if (argv[k][0] == '-' ||
699                 (argv[k][0] == '-' && argv[k][1] == '-'))
700         {  xprintf("Invalid option `%s'; try %s --help\n",
701               argv[k], argv[0]);
702            return 1;
703         }
704         else
705         {  if (csa->in_file != NULL)
706            {  xprintf("Only one input problem file allowed\n");
707               return 1;
708            }
709            csa->in_file = argv[k];
710         }
711      }
712#undef p
713      return 0;
714}
715
716typedef struct { double rhs, pi; } v_data;
717typedef struct { double low, cap, cost, x; } a_data;
718
719int glp_main(int argc, const char *argv[])
720{     /* stand-alone LP/MIP solver */
721      struct csa _csa, *csa = &_csa;
722      int ret;
723      glp_long start;
724      /* perform initialization */
725      csa->prob = glp_create_prob();
726      glp_get_bfcp(csa->prob, &csa->bfcp);
727      glp_init_smcp(&csa->smcp);
728      csa->smcp.presolve = GLP_ON;
729      glp_init_iptcp(&csa->iptcp);
730      glp_init_iocp(&csa->iocp);
731      csa->iocp.presolve = GLP_ON;
732      csa->tran = NULL;
733      csa->graph = NULL;
734      csa->format = FMT_MPS_FILE;
735      csa->in_file = NULL;
736      csa->ndf = 0;
737      csa->out_dpy = NULL;
738      csa->seed = 1;
739      csa->solution = SOL_BASIC;
740      csa->in_res = NULL;
741      csa->dir = 0;
742      csa->scale = 1;
743      csa->out_sol = NULL;
744      csa->out_res = NULL;
745      csa->out_ranges = NULL;
746      csa->check = 0;
747      csa->new_name = NULL;
748      csa->out_mps = NULL;
749      csa->out_freemps = NULL;
750      csa->out_cpxlp = NULL;
751      csa->out_glp = NULL;
752      csa->out_pb = NULL;
753      csa->out_npb = NULL;
754      csa->log_file = NULL;
755      csa->crash = USE_ADV_BASIS;
756      csa->ini_file = NULL;
757      csa->exact = 0;
758      csa->xcheck = 0;
759      csa->nomip = 0;
760      /* parse command-line parameters */
761      ret = parse_cmdline(csa, argc, argv);
762      if (ret < 0)
763      {  ret = EXIT_SUCCESS;
764         goto done;
765      }
766      if (ret > 0)
767      {  ret = EXIT_FAILURE;
768         goto done;
769      }
770      /*--------------------------------------------------------------*/
771      /* remove all output files specified in the command line */
772      if (csa->out_dpy != NULL) remove(csa->out_dpy);
773      if (csa->out_sol != NULL) remove(csa->out_sol);
774      if (csa->out_res != NULL) remove(csa->out_res);
775      if (csa->out_ranges != NULL) remove(csa->out_ranges);
776      if (csa->out_mps != NULL) remove(csa->out_mps);
777      if (csa->out_freemps != NULL) remove(csa->out_freemps);
778      if (csa->out_cpxlp != NULL) remove(csa->out_cpxlp);
779      if (csa->out_glp != NULL) remove(csa->out_glp);
780      if (csa->out_pb != NULL) remove(csa->out_pb);
781      if (csa->out_npb != NULL) remove(csa->out_npb);
782      if (csa->log_file != NULL) remove(csa->log_file);
783      /*--------------------------------------------------------------*/
784      /* open log file, if required */
785      if (csa->log_file != NULL)
786      {  if (glp_open_tee(csa->log_file))
787         {  xprintf("Unable to create log file\n");
788            ret = EXIT_FAILURE;
789            goto done;
790         }
791      }
792      /*--------------------------------------------------------------*/
793      /* print version information */
794      print_version(1);
795      /*--------------------------------------------------------------*/
796      /* print parameters specified in the command line */
797      if (argc > 1)
798      {  int k, len = INT_MAX;
799         xprintf("Parameter(s) specified in the command line:");
800         for (k = 1; k < argc; k++)
801         {  if (len > 72)
802               xprintf("\n"), len = 0;
803            xprintf(" %s", argv[k]);
804            len += 1 + strlen(argv[k]);
805         }
806         xprintf("\n");
807      }
808      /*--------------------------------------------------------------*/
809      /* read problem data from the input file */
810      if (csa->in_file == NULL)
811      {  xprintf("No input problem file specified; try %s --help\n",
812            argv[0]);
813         ret = EXIT_FAILURE;
814         goto done;
815      }
816      if (csa->format == FMT_MPS_DECK)
817      {  ret = glp_read_mps(csa->prob, GLP_MPS_DECK, NULL,
818            csa->in_file);
819         if (ret != 0)
820err1:    {  xprintf("MPS file processing error\n");
821            ret = EXIT_FAILURE;
822            goto done;
823         }
824      }
825      else if (csa->format == FMT_MPS_FILE)
826      {  ret = glp_read_mps(csa->prob, GLP_MPS_FILE, NULL,
827            csa->in_file);
828         if (ret != 0) goto err1;
829      }
830      else if (csa->format == FMT_LP)
831      {  ret = glp_read_lp(csa->prob, NULL, csa->in_file);
832         if (ret != 0)
833         {  xprintf("CPLEX LP file processing error\n");
834            ret = EXIT_FAILURE;
835            goto done;
836         }
837      }
838      else if (csa->format == FMT_GLP)
839      {  ret = glp_read_prob(csa->prob, 0, csa->in_file);
840         if (ret != 0)
841         {  xprintf("GLPK LP/MIP file processing error\n");
842            ret = EXIT_FAILURE;
843            goto done;
844         }
845      }
846      else if (csa->format == FMT_MATHPROG)
847      {  int k;
848         /* allocate the translator workspace */
849         csa->tran = glp_mpl_alloc_wksp();
850         /* set seed value */
851         if (csa->seed == 0x80000000)
852         {  csa->seed = glp_time().lo;
853            xprintf("Seed value %d will be used\n", csa->seed);
854         }
855         _glp_mpl_init_rand(csa->tran, csa->seed);
856         /* read model section and optional data section */
857         if (glp_mpl_read_model(csa->tran, csa->in_file, csa->ndf > 0))
858err2:    {  xprintf("MathProg model processing error\n");
859            ret = EXIT_FAILURE;
860            goto done;
861         }
862         /* read optional data section(s), if necessary */
863         for (k = 1; k <= csa->ndf; k++)
864         {  if (glp_mpl_read_data(csa->tran, csa->in_data[k]))
865               goto err2;
866         }
867         /* generate the model */
868         if (glp_mpl_generate(csa->tran, csa->out_dpy)) goto err2;
869         /* build the problem instance from the model */
870         glp_mpl_build_prob(csa->tran, csa->prob);
871      }
872      else if (csa->format == FMT_MIN_COST)
873      {  csa->graph = glp_create_graph(sizeof(v_data), sizeof(a_data));
874         ret = glp_read_mincost(csa->graph, offsetof(v_data, rhs),
875            offsetof(a_data, low), offsetof(a_data, cap),
876            offsetof(a_data, cost), csa->in_file);
877         if (ret != 0)
878         {  xprintf("DIMACS file processing error\n");
879            ret = EXIT_FAILURE;
880            goto done;
881         }
882         glp_mincost_lp(csa->prob, csa->graph, GLP_ON,
883            offsetof(v_data, rhs), offsetof(a_data, low),
884            offsetof(a_data, cap), offsetof(a_data, cost));
885         glp_set_prob_name(csa->prob, csa->in_file);
886      }
887      else if (csa->format == FMT_MAX_FLOW)
888      {  int s, t;
889         csa->graph = glp_create_graph(sizeof(v_data), sizeof(a_data));
890         ret = glp_read_maxflow(csa->graph, &s, &t,
891            offsetof(a_data, cap), csa->in_file);
892         if (ret != 0)
893         {  xprintf("DIMACS file processing error\n");
894            ret = EXIT_FAILURE;
895            goto done;
896         }
897         glp_maxflow_lp(csa->prob, csa->graph, GLP_ON, s, t,
898            offsetof(a_data, cap));
899         glp_set_prob_name(csa->prob, csa->in_file);
900      }
901      else
902         xassert(csa != csa);
903      /*--------------------------------------------------------------*/
904      /* change problem name, if required */
905      if (csa->new_name != NULL)
906         glp_set_prob_name(csa->prob, csa->new_name);
907      /* change optimization direction, if required */
908      if (csa->dir != 0)
909         glp_set_obj_dir(csa->prob, csa->dir);
910      /* sort elements of the constraint matrix */
911      glp_sort_matrix(csa->prob);
912      /*--------------------------------------------------------------*/
913      /* write problem data in fixed MPS format, if required */
914      if (csa->out_mps != NULL)
915      {  ret = glp_write_mps(csa->prob, GLP_MPS_DECK, NULL,
916            csa->out_mps);
917         if (ret != 0)
918         {  xprintf("Unable to write problem in fixed MPS format\n");
919            ret = EXIT_FAILURE;
920            goto done;
921         }
922      }
923      /* write problem data in free MPS format, if required */
924      if (csa->out_freemps != NULL)
925      {  ret = glp_write_mps(csa->prob, GLP_MPS_FILE, NULL,
926            csa->out_freemps);
927         if (ret != 0)
928         {  xprintf("Unable to write problem in free MPS format\n");
929            ret = EXIT_FAILURE;
930            goto done;
931         }
932      }
933      /* write problem data in CPLEX LP format, if required */
934      if (csa->out_cpxlp != NULL)
935      {  ret = glp_write_lp(csa->prob, NULL, csa->out_cpxlp);
936         if (ret != 0)
937         {  xprintf("Unable to write problem in CPLEX LP format\n");
938            ret = EXIT_FAILURE;
939            goto done;
940         }
941      }
942      /* write problem data in GLPK format, if required */
943      if (csa->out_glp != NULL)
944      {  ret = glp_write_prob(csa->prob, 0, csa->out_glp);
945         if (ret != 0)
946         {  xprintf("Unable to write problem in GLPK format\n");
947            ret = EXIT_FAILURE;
948            goto done;
949         }
950      }
951      /* write problem data in OPB format, if required */
952      if (csa->out_pb != NULL)
953      {  ret = lpx_write_pb(csa->prob, csa->out_pb, 0, 0);
954         if (ret != 0)
955         {  xprintf("Unable to write problem in OPB format\n");
956            ret = EXIT_FAILURE;
957            goto done;
958         }
959      }
960      /* write problem data in normalized OPB format, if required */
961      if (csa->out_npb != NULL)
962      {  ret = lpx_write_pb(csa->prob, csa->out_npb, 1, 1);
963         if (ret != 0)
964         {  xprintf(
965               "Unable to write problem in normalized OPB format\n");
966            ret = EXIT_FAILURE;
967            goto done;
968         }
969      }
970      /*--------------------------------------------------------------*/
971      /* if only problem data check is required, skip computations */
972      if (csa->check)
973      {  ret = EXIT_SUCCESS;
974         goto done;
975      }
976      /*--------------------------------------------------------------*/
977      /* determine the solution type */
978      if (!csa->nomip &&
979          glp_get_num_int(csa->prob) + glp_get_num_bin(csa->prob) > 0)
980      {  if (csa->solution == SOL_INTERIOR)
981         {  xprintf("Interior-point method is not able to solve MIP pro"
982               "blem; use --simplex\n");
983            ret = EXIT_FAILURE;
984            goto done;
985         }
986         csa->solution = SOL_INTEGER;
987      }
988      /*--------------------------------------------------------------*/
989      /* if solution is provided, read it and skip computations */
990      if (csa->in_res != NULL)
991      {  if (csa->solution == SOL_BASIC)
992            ret = glp_read_sol(csa->prob, csa->in_res);
993         else if (csa->solution == SOL_INTERIOR)
994            ret = glp_read_ipt(csa->prob, csa->in_res);
995         else if (csa->solution == SOL_INTEGER)
996            ret = glp_read_mip(csa->prob, csa->in_res);
997         else
998            xassert(csa != csa);
999         if (ret != 0)
1000         {  xprintf("Unable to read problem solution\n");
1001            ret = EXIT_FAILURE;
1002            goto done;
1003         }
1004         goto skip;
1005      }
1006      /*--------------------------------------------------------------*/
1007      /* scale the problem data, if required */
1008      if (csa->scale)
1009      {  if (csa->solution == SOL_BASIC && !csa->smcp.presolve ||
1010             csa->solution == SOL_INTERIOR ||
1011             csa->solution == SOL_INTEGER && !csa->iocp.presolve)
1012            glp_scale_prob(csa->prob, GLP_SF_AUTO);
1013      }
1014      /*--------------------------------------------------------------*/
1015      /* construct starting LP basis */
1016      if (csa->solution == SOL_BASIC && !csa->smcp.presolve ||
1017          csa->solution == SOL_INTEGER && !csa->iocp.presolve)
1018      {  if (csa->crash == USE_STD_BASIS)
1019            glp_std_basis(csa->prob);
1020         else if (csa->crash == USE_ADV_BASIS)
1021            glp_adv_basis(csa->prob, 0);
1022         else if (csa->crash == USE_CPX_BASIS)
1023            glp_cpx_basis(csa->prob);
1024         else if (csa->crash == USE_INI_BASIS)
1025         {  ret = glp_read_sol(csa->prob, csa->ini_file);
1026            if (ret != 0)
1027            {  xprintf("Unable to read initial basis\n");
1028               ret = EXIT_FAILURE;
1029               goto done;
1030            }
1031         }
1032         else
1033            xassert(csa != csa);
1034      }
1035      /*--------------------------------------------------------------*/
1036      /* solve the problem */
1037      start = xtime();
1038      if (csa->solution == SOL_BASIC)
1039      {  if (!csa->exact)
1040         {  glp_set_bfcp(csa->prob, &csa->bfcp);
1041            glp_simplex(csa->prob, &csa->smcp);
1042            if (csa->xcheck)
1043            {  if (csa->smcp.presolve &&
1044                   glp_get_status(csa->prob) != GLP_OPT)
1045                  xprintf("If you need to check final basis for non-opt"
1046                     "imal solution, use --nopresol\n");
1047               else
1048                  glp_exact(csa->prob, &csa->smcp);
1049            }
1050            if (csa->out_sol != NULL || csa->out_res != NULL)
1051            {  if (csa->smcp.presolve &&
1052                   glp_get_status(csa->prob) != GLP_OPT)
1053               xprintf("If you need actual output for non-optimal solut"
1054                  "ion, use --nopresol\n");
1055            }
1056         }
1057         else
1058            glp_exact(csa->prob, &csa->smcp);
1059      }
1060      else if (csa->solution == SOL_INTERIOR)
1061         glp_interior(csa->prob, &csa->iptcp);
1062      else if (csa->solution == SOL_INTEGER)
1063      {  if (!csa->iocp.presolve)
1064         {  glp_set_bfcp(csa->prob, &csa->bfcp);
1065            glp_simplex(csa->prob, &csa->smcp);
1066         }
1067#if 0
1068         csa->iocp.msg_lev = GLP_MSG_DBG;
1069         csa->iocp.pp_tech = GLP_PP_NONE;
1070#endif
1071         glp_intopt(csa->prob, &csa->iocp);
1072      }
1073      else
1074         xassert(csa != csa);
1075      /*--------------------------------------------------------------*/
1076      /* display statistics */
1077      xprintf("Time used:   %.1f secs\n", xdifftime(xtime(), start));
1078      {  glp_long tpeak;
1079         char buf[50];
1080         glp_mem_usage(NULL, NULL, NULL, &tpeak);
1081         xprintf("Memory used: %.1f Mb (%s bytes)\n",
1082            xltod(tpeak) / 1048576.0, xltoa(tpeak, buf));
1083      }
1084      /*--------------------------------------------------------------*/
1085skip: /* postsolve the model, if necessary */
1086      if (csa->tran != NULL)
1087      {  if (csa->solution == SOL_BASIC)
1088            ret = glp_mpl_postsolve(csa->tran, csa->prob, GLP_SOL);
1089         else if (csa->solution == SOL_INTERIOR)
1090            ret = glp_mpl_postsolve(csa->tran, csa->prob, GLP_IPT);
1091         else if (csa->solution == SOL_INTEGER)
1092            ret = glp_mpl_postsolve(csa->tran, csa->prob, GLP_MIP);
1093         else
1094            xassert(csa != csa);
1095         if (ret != 0)
1096         {  xprintf("Model postsolving error\n");
1097            ret = EXIT_FAILURE;
1098            goto done;
1099         }
1100      }
1101      /*--------------------------------------------------------------*/
1102      /* write problem solution in printable format, if required */
1103      if (csa->out_sol != NULL)
1104      {  if (csa->solution == SOL_BASIC)
1105            ret = lpx_print_sol(csa->prob, csa->out_sol);
1106         else if (csa->solution == SOL_INTERIOR)
1107            ret = lpx_print_ips(csa->prob, csa->out_sol);
1108         else if (csa->solution == SOL_INTEGER)
1109            ret = lpx_print_mip(csa->prob, csa->out_sol);
1110         else
1111            xassert(csa != csa);
1112         if (ret != 0)
1113         {  xprintf("Unable to write problem solution\n");
1114            ret = EXIT_FAILURE;
1115            goto done;
1116         }
1117      }
1118      /* write problem solution in printable format, if required */
1119      if (csa->out_res != NULL)
1120      {  if (csa->solution == SOL_BASIC)
1121            ret = glp_write_sol(csa->prob, csa->out_res);
1122         else if (csa->solution == SOL_INTERIOR)
1123            ret = glp_write_ipt(csa->prob, csa->out_res);
1124         else if (csa->solution == SOL_INTEGER)
1125            ret = glp_write_mip(csa->prob, csa->out_res);
1126         else
1127            xassert(csa != csa);
1128         if (ret != 0)
1129         {  xprintf("Unable to write problem solution\n");
1130            ret = EXIT_FAILURE;
1131            goto done;
1132         }
1133      }
1134      /* write sensitivity analysis report, if required */
1135      if (csa->out_ranges != NULL)
1136      {  if (csa->solution == SOL_BASIC)
1137         {  if (glp_get_status(csa->prob) == GLP_OPT)
1138            {  if (glp_bf_exists(csa->prob))
1139ranges:        {  ret = glp_print_ranges(csa->prob, 0, NULL, 0,
1140                     csa->out_ranges);
1141                  if (ret != 0)
1142                  {  xprintf("Unable to write sensitivity analysis repo"
1143                        "rt\n");
1144                     ret = EXIT_FAILURE;
1145                     goto done;
1146                  }
1147               }
1148               else
1149               {  ret = glp_factorize(csa->prob);
1150                  if (ret == 0) goto ranges;
1151                  xprintf("Cannot produce sensitivity analysis report d"
1152                     "ue to error in basis factorization (glp_factorize"
1153                     " returned %d); try --nopresol\n", ret);
1154               }
1155            }
1156            else
1157               xprintf("Cannot produce sensitivity analysis report for "
1158                  "non-optimal basic solution\n");
1159         }
1160         else
1161            xprintf("Cannot produce sensitivity analysis report for int"
1162               "erior-point or MIP solution\n");
1163      }
1164      /*--------------------------------------------------------------*/
1165      /* all seems to be ok */
1166      ret = EXIT_SUCCESS;
1167      /*--------------------------------------------------------------*/
1168done: /* delete the LP/MIP problem object */
1169      if (csa->prob != NULL)
1170         glp_delete_prob(csa->prob);
1171      /* free the translator workspace, if necessary */
1172      if (csa->tran != NULL)
1173         glp_mpl_free_wksp(csa->tran);
1174      /* delete the network problem object, if necessary */
1175      if (csa->graph != NULL)
1176         glp_delete_graph(csa->graph);
1177      xassert(gmp_pool_count() == 0);
1178      gmp_free_mem();
1179      /* close log file, if necessary */
1180      if (csa->log_file != NULL) glp_close_tee();
1181      /* check that no memory blocks are still allocated */
1182      {  int count;
1183         glp_long total;
1184         glp_mem_usage(&count, NULL, &total, NULL);
1185         if (count != 0)
1186            xerror("Error: %d memory block(s) were lost\n", count);
1187         xassert(count == 0);
1188         xassert(total.lo == 0 && total.hi == 0);
1189      }
1190      /* free the GLPK environment */
1191      glp_free_env();
1192      /* return to the control program */
1193      return ret;
1194}
1195
1196/* eof */
Note: See TracBrowser for help on using the repository browser.