Context Navigation

glpapi06.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: 26.0 KB

Line
1	/* glpapi06.c (simplex method routines) */
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 "glpios.h"
26	#include "glpnpp.h"
27	#include "glpspx.h"
28
29	/***********************************************************************
30	* NAME
31	*
32	* glp_simplex - solve LP problem with the simplex method
33	*
34	* SYNOPSIS
35	*
36	* int glp_simplex(glp_prob P, const glp_smcp parm);
37	*
38	* DESCRIPTION
39	*
40	* The routine glp_simplex is a driver to the LP solver based on the
41	* simplex method. This routine retrieves problem data from the
42	* specified problem object, calls the solver to solve the problem
43	* instance, and stores results of computations back into the problem
44	* object.
45	*
46	* The simplex solver has a set of control parameters. Values of the
47	* control parameters can be passed in a structure glp_smcp, which the
48	* parameter parm points to.
49	*
50	* The parameter parm can be specified as NULL, in which case the LP
51	* solver uses default settings.
52	*
53	* RETURNS
54	*
55	* 0 The LP problem instance has been successfully solved. This code
56	* does not necessarily mean that the solver has found optimal
57	* solution. It only means that the solution process was successful.
58	*
59	* GLP_EBADB
60	* Unable to start the search, because the initial basis specified
61	* in the problem object is invalid--the number of basic (auxiliary
62	* and structural) variables is not the same as the number of rows in
63	* the problem object.
64	*
65	* GLP_ESING
66	* Unable to start the search, because the basis matrix correspodning
67	* to the initial basis is singular within the working precision.
68	*
69	* GLP_ECOND
70	* Unable to start the search, because the basis matrix correspodning
71	* to the initial basis is ill-conditioned, i.e. its condition number
72	* is too large.
73	*
74	* GLP_EBOUND
75	* Unable to start the search, because some double-bounded variables
76	* have incorrect bounds.
77	*
78	* GLP_EFAIL
79	* The search was prematurely terminated due to the solver failure.
80	*
81	* GLP_EOBJLL
82	* The search was prematurely terminated, because the objective
83	* function being maximized has reached its lower limit and continues
84	* decreasing (dual simplex only).
85	*
86	* GLP_EOBJUL
87	* The search was prematurely terminated, because the objective
88	* function being minimized has reached its upper limit and continues
89	* increasing (dual simplex only).
90	*
91	* GLP_EITLIM
92	* The search was prematurely terminated, because the simplex
93	* iteration limit has been exceeded.
94	*
95	* GLP_ETMLIM
96	* The search was prematurely terminated, because the time limit has
97	* been exceeded.
98	*
99	* GLP_ENOPFS
100	* The LP problem instance has no primal feasible solution (only if
101	* the LP presolver is used).
102	*
103	* GLP_ENODFS
104	* The LP problem instance has no dual feasible solution (only if the
105	* LP presolver is used). */
106
107	static void trivial_lp(glp_prob P, const glp_smcp parm)
108	{ /* solve trivial LP which has empty constraint matrix */
109	GLPROW *row;
110	GLPCOL *col;
111	int i, j;
112	double p_infeas, d_infeas, zeta;
113	P->valid = 0;
114	P->pbs_stat = P->dbs_stat = GLP_FEAS;
115	P->obj_val = P->c0;
116	P->some = 0;
117	p_infeas = d_infeas = 0.0;
118	/* make all auxiliary variables basic */
119	for (i = 1; i <= P->m; i++)
120	{ row = P->row[i];
121	row->stat = GLP_BS;
122	row->prim = row->dual = 0.0;
123	/* check primal feasibility */
124	if (row->type == GLP_LO \|\| row->type == GLP_DB \|\|
125	row->type == GLP_FX)
126	{ /* row has lower bound */
127	if (row->lb > + parm->tol_bnd)
128	{ P->pbs_stat = GLP_NOFEAS;
129	if (P->some == 0 && parm->meth != GLP_PRIMAL)
130	P->some = i;
131	}
132	if (p_infeas < + row->lb)
133	p_infeas = + row->lb;
134	}
135	if (row->type == GLP_UP \|\| row->type == GLP_DB \|\|
136	row->type == GLP_FX)
137	{ /* row has upper bound */
138	if (row->ub < - parm->tol_bnd)
139	{ P->pbs_stat = GLP_NOFEAS;
140	if (P->some == 0 && parm->meth != GLP_PRIMAL)
141	P->some = i;
142	}
143	if (p_infeas < - row->ub)
144	p_infeas = - row->ub;
145	}
146	}
147	/* determine scale factor for the objective row */
148	zeta = 1.0;
149	for (j = 1; j <= P->n; j++)
150	{ col = P->col[j];
151	if (zeta < fabs(col->coef)) zeta = fabs(col->coef);
152	}
153	zeta = (P->dir == GLP_MIN ? +1.0 : -1.0) / zeta;
154	/* make all structural variables non-basic */
155	for (j = 1; j <= P->n; j++)
156	{ col = P->col[j];
157	if (col->type == GLP_FR)
158	col->stat = GLP_NF, col->prim = 0.0;
159	else if (col->type == GLP_LO)
160	lo: col->stat = GLP_NL, col->prim = col->lb;
161	else if (col->type == GLP_UP)
162	up: col->stat = GLP_NU, col->prim = col->ub;
163	else if (col->type == GLP_DB)
164	{ if (zeta * col->coef > 0.0)
165	goto lo;
166	else if (zeta * col->coef < 0.0)
167	goto up;
168	else if (fabs(col->lb) <= fabs(col->ub))
169	goto lo;
170	else
171	goto up;
172	}
173	else if (col->type == GLP_FX)
174	col->stat = GLP_NS, col->prim = col->lb;
175	col->dual = col->coef;
176	P->obj_val += col->coef * col->prim;
177	/* check dual feasibility */
178	if (col->type == GLP_FR \|\| col->type == GLP_LO)
179	{ /* column has no upper bound */
180	if (zeta * col->dual < - parm->tol_dj)
181	{ P->dbs_stat = GLP_NOFEAS;
182	if (P->some == 0 && parm->meth == GLP_PRIMAL)
183	P->some = P->m + j;
184	}
185	if (d_infeas < - zeta * col->dual)
186	d_infeas = - zeta * col->dual;
187	}
188	if (col->type == GLP_FR \|\| col->type == GLP_UP)
189	{ /* column has no lower bound */
190	if (zeta * col->dual > + parm->tol_dj)
191	{ P->dbs_stat = GLP_NOFEAS;
192	if (P->some == 0 && parm->meth == GLP_PRIMAL)
193	P->some = P->m + j;
194	}
195	if (d_infeas < + zeta * col->dual)
196	d_infeas = + zeta * col->dual;
197	}
198	}
199	/* simulate the simplex solver output */
200	if (parm->msg_lev >= GLP_MSG_ON && parm->out_dly == 0)
201	{ xprintf("~%6d: obj = %17.9e infeas = %10.3e\n", P->it_cnt,
202	P->obj_val, parm->meth == GLP_PRIMAL ? p_infeas : d_infeas);
203	}
204	if (parm->msg_lev >= GLP_MSG_ALL && parm->out_dly == 0)
205	{ if (P->pbs_stat == GLP_FEAS && P->dbs_stat == GLP_FEAS)
206	xprintf("OPTIMAL SOLUTION FOUND\n");
207	else if (P->pbs_stat == GLP_NOFEAS)
208	xprintf("PROBLEM HAS NO FEASIBLE SOLUTION\n");
209	else if (parm->meth == GLP_PRIMAL)
210	xprintf("PROBLEM HAS UNBOUNDED SOLUTION\n");
211	else
212	xprintf("PROBLEM HAS NO DUAL FEASIBLE SOLUTION\n");
213	}
214	return;
215	}
216
217	static int solve_lp(glp_prob P, const glp_smcp parm)
218	{ /* solve LP directly without using the preprocessor */
219	int ret;
220	if (!glp_bf_exists(P))
221	{ ret = glp_factorize(P);
222	if (ret == 0)
223	;
224	else if (ret == GLP_EBADB)
225	{ if (parm->msg_lev >= GLP_MSG_ERR)
226	xprintf("glp_simplex: initial basis is invalid\n");
227	}
228	else if (ret == GLP_ESING)
229	{ if (parm->msg_lev >= GLP_MSG_ERR)
230	xprintf("glp_simplex: initial basis is singular\n");
231	}
232	else if (ret == GLP_ECOND)
233	{ if (parm->msg_lev >= GLP_MSG_ERR)
234	xprintf(
235	"glp_simplex: initial basis is ill-conditioned\n");
236	}
237	else
238	xassert(ret != ret);
239	if (ret != 0) goto done;
240	}
241	if (parm->meth == GLP_PRIMAL)
242	ret = spx_primal(P, parm);
243	else if (parm->meth == GLP_DUALP)
244	{ ret = spx_dual(P, parm);
245	if (ret == GLP_EFAIL && P->valid)
246	ret = spx_primal(P, parm);
247	}
248	else if (parm->meth == GLP_DUAL)
249	ret = spx_dual(P, parm);
250	else
251	xassert(parm != parm);
252	done: return ret;
253	}
254
255	static int preprocess_and_solve_lp(glp_prob P, const glp_smcp parm)
256	{ /* solve LP using the preprocessor */
257	NPP *npp;
258	glp_prob *lp = NULL;
259	glp_bfcp bfcp;
260	int ret;
261	if (parm->msg_lev >= GLP_MSG_ALL)
262	xprintf("Preprocessing...\n");
263	/* create preprocessor workspace */
264	npp = npp_create_wksp();
265	/* load original problem into the preprocessor workspace */
266	npp_load_prob(npp, P, GLP_OFF, GLP_SOL, GLP_OFF);
267	/* process LP prior to applying primal/dual simplex method */
268	ret = npp_simplex(npp, parm);
269	if (ret == 0)
270	;
271	else if (ret == GLP_ENOPFS)
272	{ if (parm->msg_lev >= GLP_MSG_ALL)
273	xprintf("PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION\n");
274	}
275	else if (ret == GLP_ENODFS)
276	{ if (parm->msg_lev >= GLP_MSG_ALL)
277	xprintf("PROBLEM HAS NO DUAL FEASIBLE SOLUTION\n");
278	}
279	else
280	xassert(ret != ret);
281	if (ret != 0) goto done;
282	/* build transformed LP */
283	lp = glp_create_prob();
284	npp_build_prob(npp, lp);
285	/* if the transformed LP is empty, it has empty solution, which
286	is optimal */
287	if (lp->m == 0 && lp->n == 0)
288	{ lp->pbs_stat = lp->dbs_stat = GLP_FEAS;
289	lp->obj_val = lp->c0;
290	if (parm->msg_lev >= GLP_MSG_ON && parm->out_dly == 0)
291	{ xprintf("~%6d: obj = %17.9e infeas = %10.3e\n", P->it_cnt,
292	lp->obj_val, 0.0);
293	}
294	if (parm->msg_lev >= GLP_MSG_ALL)
295	xprintf("OPTIMAL SOLUTION FOUND BY LP PREPROCESSOR\n");
296	goto post;
297	}
298	if (parm->msg_lev >= GLP_MSG_ALL)
299	{ xprintf("%d row%s, %d column%s, %d non-zero%s\n",
300	lp->m, lp->m == 1 ? "" : "s", lp->n, lp->n == 1 ? "" : "s",
301	lp->nnz, lp->nnz == 1 ? "" : "s");
302	}
303	/* inherit basis factorization control parameters */
304	glp_get_bfcp(P, &bfcp);
305	glp_set_bfcp(lp, &bfcp);
306	/* scale the transformed problem */
307	{ ENV *env = get_env_ptr();
308	int term_out = env->term_out;
309	if (!term_out \|\| parm->msg_lev < GLP_MSG_ALL)
310	env->term_out = GLP_OFF;
311	else
312	env->term_out = GLP_ON;
313	glp_scale_prob(lp, GLP_SF_AUTO);
314	env->term_out = term_out;
315	}
316	/* build advanced initial basis */
317	{ ENV *env = get_env_ptr();
318	int term_out = env->term_out;
319	if (!term_out \|\| parm->msg_lev < GLP_MSG_ALL)
320	env->term_out = GLP_OFF;
321	else
322	env->term_out = GLP_ON;
323	glp_adv_basis(lp, 0);
324	env->term_out = term_out;
325	}
326	/* solve the transformed LP */
327	lp->it_cnt = P->it_cnt;
328	ret = solve_lp(lp, parm);
329	P->it_cnt = lp->it_cnt;
330	/* only optimal solution can be postprocessed */
331	if (!(ret == 0 && lp->pbs_stat == GLP_FEAS && lp->dbs_stat ==
332	GLP_FEAS))
333	{ if (parm->msg_lev >= GLP_MSG_ERR)
334	xprintf("glp_simplex: unable to recover undefined or non-op"
335	"timal solution\n");
336	if (ret == 0)
337	{ if (lp->pbs_stat == GLP_NOFEAS)
338	ret = GLP_ENOPFS;
339	else if (lp->dbs_stat == GLP_NOFEAS)
340	ret = GLP_ENODFS;
341	else
342	xassert(lp != lp);
343	}
344	goto done;
345	}
346	post: /* postprocess solution from the transformed LP */
347	npp_postprocess(npp, lp);
348	/* the transformed LP is no longer needed */
349	glp_delete_prob(lp), lp = NULL;
350	/* store solution to the original problem */
351	npp_unload_sol(npp, P);
352	/* the original LP has been successfully solved */
353	ret = 0;
354	done: /* delete the transformed LP, if it exists */
355	if (lp != NULL) glp_delete_prob(lp);
356	/* delete preprocessor workspace */
357	npp_delete_wksp(npp);
358	return ret;
359	}
360
361	int glp_simplex(glp_prob P, const glp_smcp parm)
362	{ /* solve LP problem with the simplex method */
363	glp_smcp _parm;
364	int i, j, ret;
365	/* check problem object */
366	if (P == NULL \|\| P->magic != GLP_PROB_MAGIC)
367	xerror("glp_simplex: P = %p; invalid problem object\n", P);
368	if (P->tree != NULL && P->tree->reason != 0)
369	xerror("glp_simplex: operation not allowed\n");
370	/* check control parameters */
371	if (parm == NULL)
372	parm = &_parm, glp_init_smcp((glp_smcp *)parm);
373	if (!(parm->msg_lev == GLP_MSG_OFF \|\|
374	parm->msg_lev == GLP_MSG_ERR \|\|
375	parm->msg_lev == GLP_MSG_ON \|\|
376	parm->msg_lev == GLP_MSG_ALL \|\|
377	parm->msg_lev == GLP_MSG_DBG))
378	xerror("glp_simplex: msg_lev = %d; invalid parameter\n",
379	parm->msg_lev);
380	if (!(parm->meth == GLP_PRIMAL \|\|
381	parm->meth == GLP_DUALP \|\|
382	parm->meth == GLP_DUAL))
383	xerror("glp_simplex: meth = %d; invalid parameter\n",
384	parm->meth);
385	if (!(parm->pricing == GLP_PT_STD \|\|
386	parm->pricing == GLP_PT_PSE))
387	xerror("glp_simplex: pricing = %d; invalid parameter\n",
388	parm->pricing);
389	if (!(parm->r_test == GLP_RT_STD \|\|
390	parm->r_test == GLP_RT_HAR))
391	xerror("glp_simplex: r_test = %d; invalid parameter\n",
392	parm->r_test);
393	if (!(0.0 < parm->tol_bnd && parm->tol_bnd < 1.0))
394	xerror("glp_simplex: tol_bnd = %g; invalid parameter\n",
395	parm->tol_bnd);
396	if (!(0.0 < parm->tol_dj && parm->tol_dj < 1.0))
397	xerror("glp_simplex: tol_dj = %g; invalid parameter\n",
398	parm->tol_dj);
399	if (!(0.0 < parm->tol_piv && parm->tol_piv < 1.0))
400	xerror("glp_simplex: tol_piv = %g; invalid parameter\n",
401	parm->tol_piv);
402	if (parm->it_lim < 0)
403	xerror("glp_simplex: it_lim = %d; invalid parameter\n",
404	parm->it_lim);
405	if (parm->tm_lim < 0)
406	xerror("glp_simplex: tm_lim = %d; invalid parameter\n",
407	parm->tm_lim);
408	if (parm->out_frq < 1)
409	xerror("glp_simplex: out_frq = %d; invalid parameter\n",
410	parm->out_frq);
411	if (parm->out_dly < 0)
412	xerror("glp_simplex: out_dly = %d; invalid parameter\n",
413	parm->out_dly);
414	if (!(parm->presolve == GLP_ON \|\| parm->presolve == GLP_OFF))
415	xerror("glp_simplex: presolve = %d; invalid parameter\n",
416	parm->presolve);
417	/* basic solution is currently undefined */
418	P->pbs_stat = P->dbs_stat = GLP_UNDEF;
419	P->obj_val = 0.0;
420	P->some = 0;
421	/* check bounds of double-bounded variables */
422	for (i = 1; i <= P->m; i++)
423	{ GLPROW *row = P->row[i];
424	if (row->type == GLP_DB && row->lb >= row->ub)
425	{ if (parm->msg_lev >= GLP_MSG_ERR)
426	xprintf("glp_simplex: row %d: lb = %g, ub = %g; incorrec"
427	"t bounds\n", i, row->lb, row->ub);
428	ret = GLP_EBOUND;
429	goto done;
430	}
431	}
432	for (j = 1; j <= P->n; j++)
433	{ GLPCOL *col = P->col[j];
434	if (col->type == GLP_DB && col->lb >= col->ub)
435	{ if (parm->msg_lev >= GLP_MSG_ERR)
436	xprintf("glp_simplex: column %d: lb = %g, ub = %g; incor"
437	"rect bounds\n", j, col->lb, col->ub);
438	ret = GLP_EBOUND;
439	goto done;
440	}
441	}
442	/* solve LP problem */
443	if (parm->msg_lev >= GLP_MSG_ALL)
444	{ xprintf("GLPK Simplex Optimizer, v%s\n", glp_version());
445	xprintf("%d row%s, %d column%s, %d non-zero%s\n",
446	P->m, P->m == 1 ? "" : "s", P->n, P->n == 1 ? "" : "s",
447	P->nnz, P->nnz == 1 ? "" : "s");
448	}
449	if (P->nnz == 0)
450	trivial_lp(P, parm), ret = 0;
451	else if (!parm->presolve)
452	ret = solve_lp(P, parm);
453	else
454	ret = preprocess_and_solve_lp(P, parm);
455	done: /* return to the application program */
456	return ret;
457	}
458
459	/***********************************************************************
460	* NAME
461	*
462	* glp_init_smcp - initialize simplex method control parameters
463	*
464	* SYNOPSIS
465	*
466	* void glp_init_smcp(glp_smcp *parm);
467	*
468	* DESCRIPTION
469	*
470	* The routine glp_init_smcp initializes control parameters, which are
471	* used by the simplex solver, with default values.
472	*
473	* Default values of the control parameters are stored in a glp_smcp
474	* structure, which the parameter parm points to. */
475
476	void glp_init_smcp(glp_smcp *parm)
477	{ parm->msg_lev = GLP_MSG_ALL;
478	parm->meth = GLP_PRIMAL;
479	parm->pricing = GLP_PT_PSE;
480	parm->r_test = GLP_RT_HAR;
481	parm->tol_bnd = 1e-7;
482	parm->tol_dj = 1e-7;
483	parm->tol_piv = 1e-10;
484	parm->obj_ll = -DBL_MAX;
485	parm->obj_ul = +DBL_MAX;
486	parm->it_lim = INT_MAX;
487	parm->tm_lim = INT_MAX;
488	parm->out_frq = 500;
489	parm->out_dly = 0;
490	parm->presolve = GLP_OFF;
491	return;
492	}
493
494	/***********************************************************************
495	* NAME
496	*
497	* glp_get_status - retrieve generic status of basic solution
498	*
499	* SYNOPSIS
500	*
501	* int glp_get_status(glp_prob *lp);
502	*
503	* RETURNS
504	*
505	* The routine glp_get_status reports the generic status of the basic
506	* solution for the specified problem object as follows:
507	*
508	* GLP_OPT - solution is optimal;
509	* GLP_FEAS - solution is feasible;
510	* GLP_INFEAS - solution is infeasible;
511	* GLP_NOFEAS - problem has no feasible solution;
512	* GLP_UNBND - problem has unbounded solution;
513	* GLP_UNDEF - solution is undefined. */
514
515	int glp_get_status(glp_prob *lp)
516	{ int status;
517	status = glp_get_prim_stat(lp);
518	switch (status)
519	{ case GLP_FEAS:
520	switch (glp_get_dual_stat(lp))
521	{ case GLP_FEAS:
522	status = GLP_OPT;
523	break;
524	case GLP_NOFEAS:
525	status = GLP_UNBND;
526	break;
527	case GLP_UNDEF:
528	case GLP_INFEAS:
529	status = status;
530	break;
531	default:
532	xassert(lp != lp);
533	}
534	break;
535	case GLP_UNDEF:
536	case GLP_INFEAS:
537	case GLP_NOFEAS:
538	status = status;
539	break;
540	default:
541	xassert(lp != lp);
542	}
543	return status;
544	}
545
546	/***********************************************************************
547	* NAME
548	*
549	* glp_get_prim_stat - retrieve status of primal basic solution
550	*
551	* SYNOPSIS
552	*
553	* int glp_get_prim_stat(glp_prob *lp);
554	*
555	* RETURNS
556	*
557	* The routine glp_get_prim_stat reports the status of the primal basic
558	* solution for the specified problem object as follows:
559	*
560	* GLP_UNDEF - primal solution is undefined;
561	* GLP_FEAS - primal solution is feasible;
562	* GLP_INFEAS - primal solution is infeasible;
563	* GLP_NOFEAS - no primal feasible solution exists. */
564
565	int glp_get_prim_stat(glp_prob *lp)
566	{ int pbs_stat = lp->pbs_stat;
567	return pbs_stat;
568	}
569
570	/***********************************************************************
571	* NAME
572	*
573	* glp_get_dual_stat - retrieve status of dual basic solution
574	*
575	* SYNOPSIS
576	*
577	* int glp_get_dual_stat(glp_prob *lp);
578	*
579	* RETURNS
580	*
581	* The routine glp_get_dual_stat reports the status of the dual basic
582	* solution for the specified problem object as follows:
583	*
584	* GLP_UNDEF - dual solution is undefined;
585	* GLP_FEAS - dual solution is feasible;
586	* GLP_INFEAS - dual solution is infeasible;
587	* GLP_NOFEAS - no dual feasible solution exists. */
588
589	int glp_get_dual_stat(glp_prob *lp)
590	{ int dbs_stat = lp->dbs_stat;
591	return dbs_stat;
592	}
593
594	/***********************************************************************
595	* NAME
596	*
597	* glp_get_obj_val - retrieve objective value (basic solution)
598	*
599	* SYNOPSIS
600	*
601	* double glp_get_obj_val(glp_prob *lp);
602	*
603	* RETURNS
604	*
605	* The routine glp_get_obj_val returns value of the objective function
606	* for basic solution. */
607
608	double glp_get_obj_val(glp_prob *lp)
609	{ /struct LPXCPS cps = lp->cps;*/
610	double z;
611	z = lp->obj_val;
612	/if (cps->round && fabs(z) < 1e-9) z = 0.0;/
613	return z;
614	}
615
616	/***********************************************************************
617	* NAME
618	*
619	* glp_get_row_stat - retrieve row status
620	*
621	* SYNOPSIS
622	*
623	* int glp_get_row_stat(glp_prob *lp, int i);
624	*
625	* RETURNS
626	*
627	* The routine glp_get_row_stat returns current status assigned to the
628	* auxiliary variable associated with i-th row as follows:
629	*
630	* GLP_BS - basic variable;
631	* GLP_NL - non-basic variable on its lower bound;
632	* GLP_NU - non-basic variable on its upper bound;
633	* GLP_NF - non-basic free (unbounded) variable;
634	* GLP_NS - non-basic fixed variable. */
635
636	int glp_get_row_stat(glp_prob *lp, int i)
637	{ if (!(1 <= i && i <= lp->m))
638	xerror("glp_get_row_stat: i = %d; row number out of range\n",
639	i);
640	return lp->row[i]->stat;
641	}
642
643	/***********************************************************************
644	* NAME
645	*
646	* glp_get_row_prim - retrieve row primal value (basic solution)
647	*
648	* SYNOPSIS
649	*
650	* double glp_get_row_prim(glp_prob *lp, int i);
651	*
652	* RETURNS
653	*
654	* The routine glp_get_row_prim returns primal value of the auxiliary
655	* variable associated with i-th row. */
656
657	double glp_get_row_prim(glp_prob *lp, int i)
658	{ /struct LPXCPS cps = lp->cps;*/
659	double prim;
660	if (!(1 <= i && i <= lp->m))
661	xerror("glp_get_row_prim: i = %d; row number out of range\n",
662	i);
663	prim = lp->row[i]->prim;
664	/if (cps->round && fabs(prim) < 1e-9) prim = 0.0;/
665	return prim;
666	}
667
668	/***********************************************************************
669	* NAME
670	*
671	* glp_get_row_dual - retrieve row dual value (basic solution)
672	*
673	* SYNOPSIS
674	*
675	* double glp_get_row_dual(glp_prob *lp, int i);
676	*
677	* RETURNS
678	*
679	* The routine glp_get_row_dual returns dual value (i.e. reduced cost)
680	* of the auxiliary variable associated with i-th row. */
681
682	double glp_get_row_dual(glp_prob *lp, int i)
683	{ /struct LPXCPS cps = lp->cps;*/
684	double dual;
685	if (!(1 <= i && i <= lp->m))
686	xerror("glp_get_row_dual: i = %d; row number out of range\n",
687	i);
688	dual = lp->row[i]->dual;
689	/if (cps->round && fabs(dual) < 1e-9) dual = 0.0;/
690	return dual;
691	}
692
693	/***********************************************************************
694	* NAME
695	*
696	* glp_get_col_stat - retrieve column status
697	*
698	* SYNOPSIS
699	*
700	* int glp_get_col_stat(glp_prob *lp, int j);
701	*
702	* RETURNS
703	*
704	* The routine glp_get_col_stat returns current status assigned to the
705	* structural variable associated with j-th column as follows:
706	*
707	* GLP_BS - basic variable;
708	* GLP_NL - non-basic variable on its lower bound;
709	* GLP_NU - non-basic variable on its upper bound;
710	* GLP_NF - non-basic free (unbounded) variable;
711	* GLP_NS - non-basic fixed variable. */
712
713	int glp_get_col_stat(glp_prob *lp, int j)
714	{ if (!(1 <= j && j <= lp->n))
715	xerror("glp_get_col_stat: j = %d; column number out of range\n"
716	, j);
717	return lp->col[j]->stat;
718	}
719
720	/***********************************************************************
721	* NAME
722	*
723	* glp_get_col_prim - retrieve column primal value (basic solution)
724	*
725	* SYNOPSIS
726	*
727	* double glp_get_col_prim(glp_prob *lp, int j);
728	*
729	* RETURNS
730	*
731	* The routine glp_get_col_prim returns primal value of the structural
732	* variable associated with j-th column. */
733
734	double glp_get_col_prim(glp_prob *lp, int j)
735	{ /struct LPXCPS cps = lp->cps;*/
736	double prim;
737	if (!(1 <= j && j <= lp->n))
738	xerror("glp_get_col_prim: j = %d; column number out of range\n"
739	, j);
740	prim = lp->col[j]->prim;
741	/if (cps->round && fabs(prim) < 1e-9) prim = 0.0;/
742	return prim;
743	}
744
745	/***********************************************************************
746	* NAME
747	*
748	* glp_get_col_dual - retrieve column dual value (basic solution)
749	*
750	* SYNOPSIS
751	*
752	* double glp_get_col_dual(glp_prob *lp, int j);
753	*
754	* RETURNS
755	*
756	* The routine glp_get_col_dual returns dual value (i.e. reduced cost)
757	* of the structural variable associated with j-th column. */
758
759	double glp_get_col_dual(glp_prob *lp, int j)
760	{ /struct LPXCPS cps = lp->cps;*/
761	double dual;
762	if (!(1 <= j && j <= lp->n))
763	xerror("glp_get_col_dual: j = %d; column number out of range\n"
764	, j);
765	dual = lp->col[j]->dual;
766	/if (cps->round && fabs(dual) < 1e-9) dual = 0.0;/
767	return dual;
768	}
769
770	/***********************************************************************
771	* NAME
772	*
773	* glp_get_unbnd_ray - determine variable causing unboundedness
774	*
775	* SYNOPSIS
776	*
777	* int glp_get_unbnd_ray(glp_prob *lp);
778	*
779	* RETURNS
780	*
781	* The routine glp_get_unbnd_ray returns the number k of a variable,
782	* which causes primal or dual unboundedness. If 1 <= k <= m, it is
783	* k-th auxiliary variable, and if m+1 <= k <= m+n, it is (k-m)-th
784	* structural variable, where m is the number of rows, n is the number
785	* of columns in the problem object. If such variable is not defined,
786	* the routine returns 0.
787	*
788	* COMMENTS
789	*
790	* If it is not exactly known which version of the simplex solver
791	* detected unboundedness, i.e. whether the unboundedness is primal or
792	* dual, it is sufficient to check the status of the variable reported
793	* with the routine glp_get_row_stat or glp_get_col_stat. If the
794	* variable is non-basic, the unboundedness is primal, otherwise, if
795	* the variable is basic, the unboundedness is dual (the latter case
796	* means that the problem has no primal feasible dolution). */
797
798	int glp_get_unbnd_ray(glp_prob *lp)
799	{ int k;
800	k = lp->some;
801	xassert(k >= 0);
802	if (k > lp->m + lp->n) k = 0;
803	return k;
804	}
805
806	/* eof */

Note: See TracBrowser for help on using the repository browser.

Context Navigation

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

Download in other formats: