COIN-OR::LEMON - Graph Library

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

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 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
56void 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
171int 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)
317fixup:   {  /* 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
420int 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
522int 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)
553slack:      {  /* 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
651int 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;
699done: 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
708int 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
719int 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;
806done: return ret;
807}
808
809/* eof */
Note: See TracBrowser for help on using the repository browser.