Context Navigation

glpapi19.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f 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
28	struct 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
121	static 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
312	static 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	;
330	done: return;
331	}
332
333	static 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
716	typedef struct { double rhs, pi; } v_data;
717	typedef struct { double low, cap, cost, x; } a_data;
718
719	int 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)
820	err1: { 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))
858	err2: { 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	/--------------------------------------------------------------/
1085	skip: /* 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))
1139	ranges: { 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	/--------------------------------------------------------------/
1168	done: /* 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.

Context Navigation

source: glpk-cmake/src/glpapi19.c @ 1:c445c931472f

Download in other formats: