Context Navigation

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

Line
1	/* glpnpp05.c */
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 "glpnpp.h"
26
27	/***********************************************************************
28	* NAME
29	*
30	* npp_clean_prob - perform initial LP/MIP processing
31	*
32	* SYNOPSIS
33	*
34	* #include "glpnpp.h"
35	* void npp_clean_prob(NPP *npp);
36	*
37	* DESCRIPTION
38	*
39	* The routine npp_clean_prob performs initial LP/MIP processing that
40	* currently includes:
41	*
42	* 1) removing free rows;
43	*
44	* 2) replacing double-sided constraint rows with almost identical
45	* bounds, by equality constraint rows;
46	*
47	* 3) removing fixed columns;
48	*
49	* 4) replacing double-bounded columns with almost identical bounds by
50	* fixed columns and removing those columns;
51	*
52	* 5) initial processing constraint coefficients (not implemented);
53	*
54	* 6) initial processing objective coefficients (not implemented). */
55
56	void npp_clean_prob(NPP *npp)
57	{ /* perform initial LP/MIP processing */
58	NPPROW row, next_row;
59	NPPCOL col, next_col;
60	int ret;
61	xassert(npp == npp);
62	/* process rows which originally are free */
63	for (row = npp->r_head; row != NULL; row = next_row)
64	{ next_row = row->next;
65	if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
66	{ /* process free row */
67	#ifdef GLP_DEBUG
68	xprintf("1");
69	#endif
70	npp_free_row(npp, row);
71	/* row was deleted */
72	}
73	}
74	/* process rows which originally are double-sided inequalities */
75	for (row = npp->r_head; row != NULL; row = next_row)
76	{ next_row = row->next;
77	if (row->lb != -DBL_MAX && row->ub != +DBL_MAX &&
78	row->lb < row->ub)
79	{ ret = npp_make_equality(npp, row);
80	if (ret == 0)
81	;
82	else if (ret == 1)
83	{ /* row was replaced by equality constraint */
84	#ifdef GLP_DEBUG
85	xprintf("2");
86	#endif
87	}
88	else
89	xassert(ret != ret);
90	}
91	}
92	/* process columns which are originally fixed */
93	for (col = npp->c_head; col != NULL; col = next_col)
94	{ next_col = col->next;
95	if (col->lb == col->ub)
96	{ /* process fixed column */
97	#ifdef GLP_DEBUG
98	xprintf("3");
99	#endif
100	npp_fixed_col(npp, col);
101	/* column was deleted */
102	}
103	}
104	/* process columns which are originally double-bounded */
105	for (col = npp->c_head; col != NULL; col = next_col)
106	{ next_col = col->next;
107	if (col->lb != -DBL_MAX && col->ub != +DBL_MAX &&
108	col->lb < col->ub)
109	{ ret = npp_make_fixed(npp, col);
110	if (ret == 0)
111	;
112	else if (ret == 1)
113	{ /* column was replaced by fixed column; process it */
114	#ifdef GLP_DEBUG
115	xprintf("4");
116	#endif
117	npp_fixed_col(npp, col);
118	/* column was deleted */
119	}
120	}
121	}
122	return;
123	}
124
125	/***********************************************************************
126	* NAME
127	*
128	* npp_process_row - perform basic row processing
129	*
130	* SYNOPSIS
131	*
132	* #include "glpnpp.h"
133	* int npp_process_row(NPP npp, NPPROW row, int hard);
134	*
135	* DESCRIPTION
136	*
137	* The routine npp_process_row performs basic row processing that
138	* currently includes:
139	*
140	* 1) removing empty row;
141	*
142	* 2) removing equality constraint row singleton and corresponding
143	* column;
144	*
145	* 3) removing inequality constraint row singleton and corresponding
146	* column if it was fixed;
147	*
148	* 4) performing general row analysis;
149	*
150	* 5) removing redundant row bounds;
151	*
152	* 6) removing forcing row and corresponding columns;
153	*
154	* 7) removing row which becomes free due to redundant bounds;
155	*
156	* 8) computing implied bounds for all columns in the row and using
157	* them to strengthen current column bounds (MIP only, optional,
158	* performed if the flag hard is on).
159	*
160	* Additionally the routine may activate affected rows and/or columns
161	* for further processing.
162	*
163	* RETURNS
164	*
165	* 0 success;
166	*
167	* GLP_ENOPFS primal/integer infeasibility detected;
168	*
169	* GLP_ENODFS dual infeasibility detected. */
170
171	int npp_process_row(NPP npp, NPPROW row, int hard)
172	{ /* perform basic row processing */
173	NPPCOL *col;
174	NPPAIJ aij, next_aij, *aaa;
175	int ret;
176	/* row must not be free */
177	xassert(!(row->lb == -DBL_MAX && row->ub == +DBL_MAX));
178	/* start processing row */
179	if (row->ptr == NULL)
180	{ /* empty row */
181	ret = npp_empty_row(npp, row);
182	if (ret == 0)
183	{ /* row was deleted */
184	#ifdef GLP_DEBUG
185	xprintf("A");
186	#endif
187	return 0;
188	}
189	else if (ret == 1)
190	{ /* primal infeasibility */
191	return GLP_ENOPFS;
192	}
193	else
194	xassert(ret != ret);
195	}
196	if (row->ptr->r_next == NULL)
197	{ /* row singleton */
198	col = row->ptr->col;
199	if (row->lb == row->ub)
200	{ /* equality constraint */
201	ret = npp_eq_singlet(npp, row);
202	if (ret == 0)
203	{ /* column was fixed, row was deleted */
204	#ifdef GLP_DEBUG
205	xprintf("B");
206	#endif
207	/* activate rows affected by column */
208	for (aij = col->ptr; aij != NULL; aij = aij->c_next)
209	npp_activate_row(npp, aij->row);
210	/* process fixed column */
211	npp_fixed_col(npp, col);
212	/* column was deleted */
213	return 0;
214	}
215	else if (ret == 1 \|\| ret == 2)
216	{ /* primal/integer infeasibility */
217	return GLP_ENOPFS;
218	}
219	else
220	xassert(ret != ret);
221	}
222	else
223	{ /* inequality constraint */
224	ret = npp_ineq_singlet(npp, row);
225	if (0 <= ret && ret <= 3)
226	{ /* row was deleted */
227	#ifdef GLP_DEBUG
228	xprintf("C");
229	#endif
230	/* activate column, since its length was changed due to
231	row deletion */
232	npp_activate_col(npp, col);
233	if (ret >= 2)
234	{ /* column bounds changed significantly or column was
235	fixed */
236	/* activate rows affected by column */
237	for (aij = col->ptr; aij != NULL; aij = aij->c_next)
238	npp_activate_row(npp, aij->row);
239	}
240	if (ret == 3)
241	{ /* column was fixed; process it */
242	#ifdef GLP_DEBUG
243	xprintf("D");
244	#endif
245	npp_fixed_col(npp, col);
246	/* column was deleted */
247	}
248	return 0;
249	}
250	else if (ret == 4)
251	{ /* primal infeasibility */
252	return GLP_ENOPFS;
253	}
254	else
255	xassert(ret != ret);
256	}
257	}
258	#if 0
259	/* sometimes this causes too large round-off errors; probably
260	pivot coefficient should be chosen more carefully */
261	if (row->ptr->r_next->r_next == NULL)
262	{ /* row doubleton */
263	if (row->lb == row->ub)
264	{ /* equality constraint */
265	if (!(row->ptr->col->is_int \|\|
266	row->ptr->r_next->col->is_int))
267	{ /* both columns are continuous */
268	NPPCOL *q;
269	q = npp_eq_doublet(npp, row);
270	if (q != NULL)
271	{ /* column q was eliminated */
272	#ifdef GLP_DEBUG
273	xprintf("E");
274	#endif
275	/* now column q is singleton of type "implied slack
276	variable"; we process it here to make sure that on
277	recovering basic solution the row is always active
278	equality constraint (as required by the routine
279	rcv_eq_doublet) */
280	xassert(npp_process_col(npp, q) == 0);
281	/* column q was deleted; note that row p also may be
282	deleted */
283	return 0;
284	}
285	}
286	}
287	}
288	#endif
289	/* general row analysis */
290	ret = npp_analyze_row(npp, row);
291	xassert(0x00 <= ret && ret <= 0xFF);
292	if (ret == 0x33)
293	{ /* row bounds are inconsistent with column bounds */
294	return GLP_ENOPFS;
295	}
296	if ((ret & 0x0F) == 0x00)
297	{ /* row lower bound does not exist or redundant */
298	if (row->lb != -DBL_MAX)
299	{ /* remove redundant row lower bound */
300	#ifdef GLP_DEBUG
301	xprintf("F");
302	#endif
303	npp_inactive_bound(npp, row, 0);
304	}
305	}
306	else if ((ret & 0x0F) == 0x01)
307	{ /* row lower bound can be active */
308	/* see below */
309	}
310	else if ((ret & 0x0F) == 0x02)
311	{ /* row lower bound is a forcing bound */
312	#ifdef GLP_DEBUG
313	xprintf("G");
314	#endif
315	/* process forcing row */
316	if (npp_forcing_row(npp, row, 0) == 0)
317	fixup: { /* columns were fixed, row was made free */
318	for (aij = row->ptr; aij != NULL; aij = next_aij)
319	{ /* process column fixed by forcing row */
320	#ifdef GLP_DEBUG
321	xprintf("H");
322	#endif
323	col = aij->col;
324	next_aij = aij->r_next;
325	/* activate rows affected by column */
326	for (aaa = col->ptr; aaa != NULL; aaa = aaa->c_next)
327	npp_activate_row(npp, aaa->row);
328	/* process fixed column */
329	npp_fixed_col(npp, col);
330	/* column was deleted */
331	}
332	/* process free row (which now is empty due to deletion of
333	all its columns) */
334	npp_free_row(npp, row);
335	/* row was deleted */
336	return 0;
337	}
338	}
339	else
340	xassert(ret != ret);
341	if ((ret & 0xF0) == 0x00)
342	{ /* row upper bound does not exist or redundant */
343	if (row->ub != +DBL_MAX)
344	{ /* remove redundant row upper bound */
345	#ifdef GLP_DEBUG
346	xprintf("I");
347	#endif
348	npp_inactive_bound(npp, row, 1);
349	}
350	}
351	else if ((ret & 0xF0) == 0x10)
352	{ /* row upper bound can be active */
353	/* see below */
354	}
355	else if ((ret & 0xF0) == 0x20)
356	{ /* row upper bound is a forcing bound */
357	#ifdef GLP_DEBUG
358	xprintf("J");
359	#endif
360	/* process forcing row */
361	if (npp_forcing_row(npp, row, 1) == 0) goto fixup;
362	}
363	else
364	xassert(ret != ret);
365	if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
366	{ /* row became free due to redundant bounds removal */
367	#ifdef GLP_DEBUG
368	xprintf("K");
369	#endif
370	/* activate its columns, since their length will change due
371	to row deletion */
372	for (aij = row->ptr; aij != NULL; aij = aij->r_next)
373	npp_activate_col(npp, aij->col);
374	/* process free row */
375	npp_free_row(npp, row);
376	/* row was deleted */
377	return 0;
378	}
379	#if 1 /* 23/XII-2009 */
380	/* row lower and/or upper bounds can be active */
381	if (npp->sol == GLP_MIP && hard)
382	{ /* improve current column bounds (optional) */
383	if (npp_improve_bounds(npp, row, 1) < 0)
384	return GLP_ENOPFS;
385	}
386	#endif
387	return 0;
388	}
389
390	/***********************************************************************
391	* NAME
392	*
393	* npp_improve_bounds - improve current column bounds
394	*
395	* SYNOPSIS
396	*
397	* #include "glpnpp.h"
398	* int npp_improve_bounds(NPP npp, NPPROW row, int flag);
399	*
400	* DESCRIPTION
401	*
402	* The routine npp_improve_bounds analyzes specified row (inequality
403	* or equality constraint) to determine implied column bounds and then
404	* uses these bounds to improve (strengthen) current column bounds.
405	*
406	* If the flag is on and current column bounds changed significantly
407	* or the column was fixed, the routine activate rows affected by the
408	* column for further processing. (This feature is intended to be used
409	* in the main loop of the routine npp_process_row.)
410	*
411	* NOTE: This operation can be used for MIP problem only.
412	*
413	* RETURNS
414	*
415	* The routine npp_improve_bounds returns the number of significantly
416	* changed bounds plus the number of column having been fixed due to
417	* bound improvements. However, if the routine detects primal/integer
418	* infeasibility, it returns a negative value. */
419
420	int npp_improve_bounds(NPP npp, NPPROW row, int flag)
421	{ /* improve current column bounds */
422	NPPCOL *col;
423	NPPAIJ aij, next_aij, *aaa;
424	int kase, ret, count = 0;
425	double lb, ub;
426	xassert(npp->sol == GLP_MIP);
427	/* row must not be free */
428	xassert(!(row->lb == -DBL_MAX && row->ub == +DBL_MAX));
429	/* determine implied column bounds */
430	npp_implied_bounds(npp, row);
431	/* and use these bounds to strengthen current column bounds */
432	for (aij = row->ptr; aij != NULL; aij = next_aij)
433	{ col = aij->col;
434	next_aij = aij->r_next;
435	for (kase = 0; kase <= 1; kase++)
436	{ /* save current column bounds */
437	lb = col->lb, ub = col->ub;
438	if (kase == 0)
439	{ /* process implied column lower bound */
440	if (col->ll.ll == -DBL_MAX) continue;
441	ret = npp_implied_lower(npp, col, col->ll.ll);
442	}
443	else
444	{ /* process implied column upper bound */
445	if (col->uu.uu == +DBL_MAX) continue;
446	ret = npp_implied_upper(npp, col, col->uu.uu);
447	}
448	if (ret == 0 \|\| ret == 1)
449	{ /* current column bounds did not change or changed, but
450	not significantly; restore current column bounds */
451	col->lb = lb, col->ub = ub;
452	}
453	else if (ret == 2 \|\| ret == 3)
454	{ /* current column bounds changed significantly or column
455	was fixed */
456	#ifdef GLP_DEBUG
457	xprintf("L");
458	#endif
459	count++;
460	/* activate other rows affected by column, if required */
461	if (flag)
462	{ for (aaa = col->ptr; aaa != NULL; aaa = aaa->c_next)
463	{ if (aaa->row != row)
464	npp_activate_row(npp, aaa->row);
465	}
466	}
467	if (ret == 3)
468	{ /* process fixed column */
469	#ifdef GLP_DEBUG
470	xprintf("M");
471	#endif
472	npp_fixed_col(npp, col);
473	/* column was deleted */
474	break; /* for kase */
475	}
476	}
477	else if (ret == 4)
478	{ /* primal/integer infeasibility */
479	return -1;
480	}
481	else
482	xassert(ret != ret);
483	}
484	}
485	return count;
486	}
487
488	/***********************************************************************
489	* NAME
490	*
491	* npp_process_col - perform basic column processing
492	*
493	* SYNOPSIS
494	*
495	* #include "glpnpp.h"
496	* int npp_process_col(NPP npp, NPPCOL col);
497	*
498	* DESCRIPTION
499	*
500	* The routine npp_process_col performs basic column processing that
501	* currently includes:
502	*
503	* 1) fixing and removing empty column;
504	*
505	* 2) removing column singleton, which is implied slack variable, and
506	* corresponding row if it becomes free;
507	*
508	* 3) removing bounds of column, which is implied free variable, and
509	* replacing corresponding row by equality constraint.
510	*
511	* Additionally the routine may activate affected rows and/or columns
512	* for further processing.
513	*
514	* RETURNS
515	*
516	* 0 success;
517	*
518	* GLP_ENOPFS primal/integer infeasibility detected;
519	*
520	* GLP_ENODFS dual infeasibility detected. */
521
522	int npp_process_col(NPP npp, NPPCOL col)
523	{ /* perform basic column processing */
524	NPPROW *row;
525	NPPAIJ *aij;
526	int ret;
527	/* column must not be fixed */
528	xassert(col->lb < col->ub);
529	/* start processing column */
530	if (col->ptr == NULL)
531	{ /* empty column */
532	ret = npp_empty_col(npp, col);
533	if (ret == 0)
534	{ /* column was fixed and deleted */
535	#ifdef GLP_DEBUG
536	xprintf("N");
537	#endif
538	return 0;
539	}
540	else if (ret == 1)
541	{ /* dual infeasibility */
542	return GLP_ENODFS;
543	}
544	else
545	xassert(ret != ret);
546	}
547	if (col->ptr->c_next == NULL)
548	{ /* column singleton */
549	row = col->ptr->row;
550	if (row->lb == row->ub)
551	{ /* equality constraint */
552	if (!col->is_int)
553	slack: { /* implied slack variable */
554	#ifdef GLP_DEBUG
555	xprintf("O");
556	#endif
557	npp_implied_slack(npp, col);
558	/* column was deleted */
559	if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
560	{ /* row became free due to implied slack variable */
561	#ifdef GLP_DEBUG
562	xprintf("P");
563	#endif
564	/* activate columns affected by row */
565	for (aij = row->ptr; aij != NULL; aij = aij->r_next)
566	npp_activate_col(npp, aij->col);
567	/* process free row */
568	npp_free_row(npp, row);
569	/* row was deleted */
570	}
571	else
572	{ /* row became inequality constraint; activate it
573	since its length changed due to column deletion */
574	npp_activate_row(npp, row);
575	}
576	return 0;
577	}
578	}
579	else
580	{ /* inequality constraint */
581	if (!col->is_int)
582	{ ret = npp_implied_free(npp, col);
583	if (ret == 0)
584	{ /* implied free variable */
585	#ifdef GLP_DEBUG
586	xprintf("Q");
587	#endif
588	/* column bounds were removed, row was replaced by
589	equality constraint */
590	goto slack;
591	}
592	else if (ret == 1)
593	{ /* column is not implied free variable, because its
594	lower and/or upper bounds can be active */
595	}
596	else if (ret == 2)
597	{ /* dual infeasibility */
598	return GLP_ENODFS;
599	}
600	}
601	}
602	}
603	/* column still exists */
604	return 0;
605	}
606
607	/***********************************************************************
608	* NAME
609	*
610	* npp_process_prob - perform basic LP/MIP processing
611	*
612	* SYNOPSIS
613	*
614	* #include "glpnpp.h"
615	* int npp_process_prob(NPP *npp, int hard);
616	*
617	* DESCRIPTION
618	*
619	* The routine npp_process_prob performs basic LP/MIP processing that
620	* currently includes:
621	*
622	* 1) initial LP/MIP processing (see the routine npp_clean_prob),
623	*
624	* 2) basic row processing (see the routine npp_process_row), and
625	*
626	* 3) basic column processing (see the routine npp_process_col).
627	*
628	* If the flag hard is on, the routine attempts to improve current
629	* column bounds multiple times within the main processing loop, in
630	* which case this feature may take a time. Otherwise, if the flag hard
631	* is off, improving column bounds is performed only once at the end of
632	* the main loop. (Note that this feature is used for MIP only.)
633	*
634	* The routine uses two sets: the set of active rows and the set of
635	* active columns. Rows/columns are marked by a flag (the field temp in
636	* NPPROW/NPPCOL). If the flag is non-zero, the row/column is active,
637	* in which case it is placed in the beginning of the row/column list;
638	* otherwise, if the flag is zero, the row/column is inactive, in which
639	* case it is placed in the end of the row/column list. If a row/column
640	* being currently processed may affect other rows/columns, the latters
641	* are activated for further processing.
642	*
643	* RETURNS
644	*
645	* 0 success;
646	*
647	* GLP_ENOPFS primal/integer infeasibility detected;
648	*
649	* GLP_ENODFS dual infeasibility detected. */
650
651	int npp_process_prob(NPP *npp, int hard)
652	{ /* perform basic LP/MIP processing */
653	NPPROW *row;
654	NPPCOL *col;
655	int processing, ret;
656	/* perform initial LP/MIP processing */
657	npp_clean_prob(npp);
658	/* activate all remaining rows and columns */
659	for (row = npp->r_head; row != NULL; row = row->next)
660	row->temp = 1;
661	for (col = npp->c_head; col != NULL; col = col->next)
662	col->temp = 1;
663	/* main processing loop */
664	processing = 1;
665	while (processing)
666	{ processing = 0;
667	/* process all active rows */
668	for (;;)
669	{ row = npp->r_head;
670	if (row == NULL \|\| !row->temp) break;
671	npp_deactivate_row(npp, row);
672	ret = npp_process_row(npp, row, hard);
673	if (ret != 0) goto done;
674	processing = 1;
675	}
676	/* process all active columns */
677	for (;;)
678	{ col = npp->c_head;
679	if (col == NULL \|\| !col->temp) break;
680	npp_deactivate_col(npp, col);
681	ret = npp_process_col(npp, col);
682	if (ret != 0) goto done;
683	processing = 1;
684	}
685	}
686	#if 1 /* 23/XII-2009 */
687	if (npp->sol == GLP_MIP && !hard)
688	{ /* improve current column bounds (optional) */
689	for (row = npp->r_head; row != NULL; row = row->next)
690	{ if (npp_improve_bounds(npp, row, 0) < 0)
691	{ ret = GLP_ENOPFS;
692	goto done;
693	}
694	}
695	}
696	#endif
697	/* all seems ok */
698	ret = 0;
699	done: xassert(ret == 0 \|\| ret == GLP_ENOPFS \|\| ret == GLP_ENODFS);
700	#ifdef GLP_DEBUG
701	xprintf("\n");
702	#endif
703	return ret;
704	}
705
706	/**********************************************************************/
707
708	int npp_simplex(NPP npp, const glp_smcp parm)
709	{ /* process LP prior to applying primal/dual simplex method */
710	int ret;
711	xassert(npp->sol == GLP_SOL);
712	xassert(parm == parm);
713	ret = npp_process_prob(npp, 0);
714	return ret;
715	}
716
717	/**********************************************************************/
718
719	int npp_integer(NPP npp, const glp_iocp parm)
720	{ /* process MIP prior to applying branch-and-bound method */
721	NPPROW row, prev_row;
722	NPPCOL *col;
723	NPPAIJ *aij;
724	int count, ret;
725	xassert(npp->sol == GLP_MIP);
726	xassert(parm == parm);
727	/==============================================================/
728	/* perform basic MIP processing */
729	ret = npp_process_prob(npp, 1);
730	if (ret != 0) goto done;
731	/==============================================================/
732	/* binarize problem, if required */
733	if (parm->binarize)
734	npp_binarize_prob(npp);
735	/==============================================================/
736	/* identify hidden packing inequalities */
737	count = 0;
738	/* new rows will be added to the end of the row list, so we go
739	from the end to beginning of the row list */
740	for (row = npp->r_tail; row != NULL; row = prev_row)
741	{ prev_row = row->prev;
742	/* skip free row */
743	if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) continue;
744	/* skip equality constraint */
745	if (row->lb == row->ub) continue;
746	/* skip row having less than two variables */
747	if (row->ptr == NULL \|\| row->ptr->r_next == NULL) continue;
748	/* skip row having non-binary variables */
749	for (aij = row->ptr; aij != NULL; aij = aij->r_next)
750	{ col = aij->col;
751	if (!(col->is_int && col->lb == 0.0 && col->ub == 1.0))
752	break;
753	}
754	if (aij != NULL) continue;
755	count += npp_hidden_packing(npp, row);
756	}
757	if (count > 0)
758	xprintf("%d hidden packing inequaliti(es) were detected\n",
759	count);
760	/==============================================================/
761	/* identify hidden covering inequalities */
762	count = 0;
763	/* new rows will be added to the end of the row list, so we go
764	from the end to beginning of the row list */
765	for (row = npp->r_tail; row != NULL; row = prev_row)
766	{ prev_row = row->prev;
767	/* skip free row */
768	if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) continue;
769	/* skip equality constraint */
770	if (row->lb == row->ub) continue;
771	/* skip row having less than three variables */
772	if (row->ptr == NULL \|\| row->ptr->r_next == NULL \|\|
773	row->ptr->r_next->r_next == NULL) continue;
774	/* skip row having non-binary variables */
775	for (aij = row->ptr; aij != NULL; aij = aij->r_next)
776	{ col = aij->col;
777	if (!(col->is_int && col->lb == 0.0 && col->ub == 1.0))
778	break;
779	}
780	if (aij != NULL) continue;
781	count += npp_hidden_covering(npp, row);
782	}
783	if (count > 0)
784	xprintf("%d hidden covering inequaliti(es) were detected\n",
785	count);
786	/==============================================================/
787	/* reduce inequality constraint coefficients */
788	count = 0;
789	/* new rows will be added to the end of the row list, so we go
790	from the end to beginning of the row list */
791	for (row = npp->r_tail; row != NULL; row = prev_row)
792	{ prev_row = row->prev;
793	/* skip equality constraint */
794	if (row->lb == row->ub) continue;
795	count += npp_reduce_ineq_coef(npp, row);
796	}
797	if (count > 0)
798	xprintf("%d constraint coefficient(s) were reduced\n", count);
799	/==============================================================/
800	#ifdef GLP_DEBUG
801	routine(npp);
802	#endif
803	/==============================================================/
804	/* all seems ok */
805	ret = 0;
806	done: return ret;
807	}
808
809	/* eof */

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

Context Navigation

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

Download in other formats: