lemon-project-template-glpk
view deps/glpk/src/glpnpp05.c @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 /* glpnpp05.c */
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 *
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
9 * E-mail: <mao@gnu.org>.
10 *
11 * GLPK is free software: you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation, either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
19 * License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
23 ***********************************************************************/
25 #include "glpnpp.h"
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). */
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 }
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. */
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 }
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. */
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 }
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. */
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 }
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. */
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 }
706 /**********************************************************************/
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 }
717 /**********************************************************************/
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 }
809 /* eof */