alpar@9: /* glpnpp05.c */
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@9: *
alpar@9: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9: *  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9: *  E-mail: <mao@gnu.org>.
alpar@9: *
alpar@9: *  GLPK is free software: you can redistribute it and/or modify it
alpar@9: *  under the terms of the GNU General Public License as published by
alpar@9: *  the Free Software Foundation, either version 3 of the License, or
alpar@9: *  (at your option) any later version.
alpar@9: *
alpar@9: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9: *  License for more details.
alpar@9: *
alpar@9: *  You should have received a copy of the GNU General Public License
alpar@9: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9: ***********************************************************************/
alpar@9: 
alpar@9: #include "glpnpp.h"
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  npp_clean_prob - perform initial LP/MIP processing
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpnpp.h"
alpar@9: *  void npp_clean_prob(NPP *npp);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine npp_clean_prob performs initial LP/MIP processing that
alpar@9: *  currently includes:
alpar@9: *
alpar@9: *  1) removing free rows;
alpar@9: *
alpar@9: *  2) replacing double-sided constraint rows with almost identical
alpar@9: *     bounds, by equality constraint rows;
alpar@9: *
alpar@9: *  3) removing fixed columns;
alpar@9: *
alpar@9: *  4) replacing double-bounded columns with almost identical bounds by
alpar@9: *     fixed columns and removing those columns;
alpar@9: *
alpar@9: *  5) initial processing constraint coefficients (not implemented);
alpar@9: *
alpar@9: *  6) initial processing objective coefficients (not implemented). */
alpar@9: 
alpar@9: void npp_clean_prob(NPP *npp)
alpar@9: {     /* perform initial LP/MIP processing */
alpar@9:       NPPROW *row, *next_row;
alpar@9:       NPPCOL *col, *next_col;
alpar@9:       int ret;
alpar@9:       xassert(npp == npp);
alpar@9:       /* process rows which originally are free */
alpar@9:       for (row = npp->r_head; row != NULL; row = next_row)
alpar@9:       {  next_row = row->next;
alpar@9:          if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
alpar@9:          {  /* process free row */
alpar@9: #ifdef GLP_DEBUG
alpar@9:             xprintf("1");
alpar@9: #endif
alpar@9:             npp_free_row(npp, row);
alpar@9:             /* row was deleted */
alpar@9:          }
alpar@9:       }
alpar@9:       /* process rows which originally are double-sided inequalities */
alpar@9:       for (row = npp->r_head; row != NULL; row = next_row)
alpar@9:       {  next_row = row->next;
alpar@9:          if (row->lb != -DBL_MAX && row->ub != +DBL_MAX &&
alpar@9:              row->lb < row->ub)
alpar@9:          {  ret = npp_make_equality(npp, row);
alpar@9:             if (ret == 0)
alpar@9:                ;
alpar@9:             else if (ret == 1)
alpar@9:             {  /* row was replaced by equality constraint */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                xprintf("2");
alpar@9: #endif
alpar@9:             }
alpar@9:             else
alpar@9:                xassert(ret != ret);
alpar@9:          }
alpar@9:       }
alpar@9:       /* process columns which are originally fixed */
alpar@9:       for (col = npp->c_head; col != NULL; col = next_col)
alpar@9:       {  next_col = col->next;
alpar@9:          if (col->lb == col->ub)
alpar@9:          {  /* process fixed column */
alpar@9: #ifdef GLP_DEBUG
alpar@9:             xprintf("3");
alpar@9: #endif
alpar@9:             npp_fixed_col(npp, col);
alpar@9:             /* column was deleted */
alpar@9:          }
alpar@9:       }
alpar@9:       /* process columns which are originally double-bounded */
alpar@9:       for (col = npp->c_head; col != NULL; col = next_col)
alpar@9:       {  next_col = col->next;
alpar@9:          if (col->lb != -DBL_MAX && col->ub != +DBL_MAX &&
alpar@9:              col->lb < col->ub)
alpar@9:          {  ret = npp_make_fixed(npp, col);
alpar@9:             if (ret == 0)
alpar@9:                ;
alpar@9:             else if (ret == 1)
alpar@9:             {  /* column was replaced by fixed column; process it */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                xprintf("4");
alpar@9: #endif
alpar@9:                npp_fixed_col(npp, col);
alpar@9:                /* column was deleted */
alpar@9:             }
alpar@9:          }
alpar@9:       }
alpar@9:       return;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  npp_process_row - perform basic row processing
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpnpp.h"
alpar@9: *  int npp_process_row(NPP *npp, NPPROW *row, int hard);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine npp_process_row performs basic row processing that
alpar@9: *  currently includes:
alpar@9: *
alpar@9: *  1) removing empty row;
alpar@9: *
alpar@9: *  2) removing equality constraint row singleton and corresponding
alpar@9: *     column;
alpar@9: *
alpar@9: *  3) removing inequality constraint row singleton and corresponding
alpar@9: *     column if it was fixed;
alpar@9: *
alpar@9: *  4) performing general row analysis;
alpar@9: *
alpar@9: *  5) removing redundant row bounds;
alpar@9: *
alpar@9: *  6) removing forcing row and corresponding columns;
alpar@9: *
alpar@9: *  7) removing row which becomes free due to redundant bounds;
alpar@9: *
alpar@9: *  8) computing implied bounds for all columns in the row and using
alpar@9: *     them to strengthen current column bounds (MIP only, optional,
alpar@9: *     performed if the flag hard is on).
alpar@9: *
alpar@9: *  Additionally the routine may activate affected rows and/or columns
alpar@9: *  for further processing.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  0           success;
alpar@9: *
alpar@9: *  GLP_ENOPFS  primal/integer infeasibility detected;
alpar@9: *
alpar@9: *  GLP_ENODFS  dual infeasibility detected. */
alpar@9: 
alpar@9: int npp_process_row(NPP *npp, NPPROW *row, int hard)
alpar@9: {     /* perform basic row processing */
alpar@9:       NPPCOL *col;
alpar@9:       NPPAIJ *aij, *next_aij, *aaa;
alpar@9:       int ret;
alpar@9:       /* row must not be free */
alpar@9:       xassert(!(row->lb == -DBL_MAX && row->ub == +DBL_MAX));
alpar@9:       /* start processing row */
alpar@9:       if (row->ptr == NULL)
alpar@9:       {  /* empty row */
alpar@9:          ret = npp_empty_row(npp, row);
alpar@9:          if (ret == 0)
alpar@9:          {  /* row was deleted */
alpar@9: #ifdef GLP_DEBUG
alpar@9:             xprintf("A");
alpar@9: #endif
alpar@9:             return 0;
alpar@9:          }
alpar@9:          else if (ret == 1)
alpar@9:          {  /* primal infeasibility */
alpar@9:             return GLP_ENOPFS;
alpar@9:          }
alpar@9:          else
alpar@9:             xassert(ret != ret);
alpar@9:       }
alpar@9:       if (row->ptr->r_next == NULL)
alpar@9:       {  /* row singleton */
alpar@9:          col = row->ptr->col;
alpar@9:          if (row->lb == row->ub)
alpar@9:          {  /* equality constraint */
alpar@9:             ret = npp_eq_singlet(npp, row);
alpar@9:             if (ret == 0)
alpar@9:             {  /* column was fixed, row was deleted */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                xprintf("B");
alpar@9: #endif
alpar@9:                /* activate rows affected by column */
alpar@9:                for (aij = col->ptr; aij != NULL; aij = aij->c_next)
alpar@9:                   npp_activate_row(npp, aij->row);
alpar@9:                /* process fixed column */
alpar@9:                npp_fixed_col(npp, col);
alpar@9:                /* column was deleted */
alpar@9:                return 0;
alpar@9:             }
alpar@9:             else if (ret == 1 || ret == 2)
alpar@9:             {  /* primal/integer infeasibility */
alpar@9:                return GLP_ENOPFS;
alpar@9:             }
alpar@9:             else
alpar@9:                xassert(ret != ret);
alpar@9:          }
alpar@9:          else
alpar@9:          {  /* inequality constraint */
alpar@9:             ret = npp_ineq_singlet(npp, row);
alpar@9:             if (0 <= ret && ret <= 3)
alpar@9:             {  /* row was deleted */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                xprintf("C");
alpar@9: #endif
alpar@9:                /* activate column, since its length was changed due to
alpar@9:                   row deletion */
alpar@9:                npp_activate_col(npp, col);
alpar@9:                if (ret >= 2)
alpar@9:                {  /* column bounds changed significantly or column was
alpar@9:                      fixed */
alpar@9:                   /* activate rows affected by column */
alpar@9:                   for (aij = col->ptr; aij != NULL; aij = aij->c_next)
alpar@9:                      npp_activate_row(npp, aij->row);
alpar@9:                }
alpar@9:                if (ret == 3)
alpar@9:                {  /* column was fixed; process it */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                   xprintf("D");
alpar@9: #endif
alpar@9:                   npp_fixed_col(npp, col);
alpar@9:                   /* column was deleted */
alpar@9:                }
alpar@9:                return 0;
alpar@9:             }
alpar@9:             else if (ret == 4)
alpar@9:             {  /* primal infeasibility */
alpar@9:                return GLP_ENOPFS;
alpar@9:             }
alpar@9:             else
alpar@9:                xassert(ret != ret);
alpar@9:          }
alpar@9:       }
alpar@9: #if 0
alpar@9:       /* sometimes this causes too large round-off errors; probably
alpar@9:          pivot coefficient should be chosen more carefully */
alpar@9:       if (row->ptr->r_next->r_next == NULL)
alpar@9:       {  /* row doubleton */
alpar@9:          if (row->lb == row->ub)
alpar@9:          {  /* equality constraint */
alpar@9:             if (!(row->ptr->col->is_int ||
alpar@9:                   row->ptr->r_next->col->is_int))
alpar@9:             {  /* both columns are continuous */
alpar@9:                NPPCOL *q;
alpar@9:                q = npp_eq_doublet(npp, row);
alpar@9:                if (q != NULL)
alpar@9:                {  /* column q was eliminated */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                   xprintf("E");
alpar@9: #endif
alpar@9:                   /* now column q is singleton of type "implied slack
alpar@9:                      variable"; we process it here to make sure that on
alpar@9:                      recovering basic solution the row is always active
alpar@9:                      equality constraint (as required by the routine
alpar@9:                      rcv_eq_doublet) */
alpar@9:                   xassert(npp_process_col(npp, q) == 0);
alpar@9:                   /* column q was deleted; note that row p also may be
alpar@9:                      deleted */
alpar@9:                   return 0;
alpar@9:                }
alpar@9:             }
alpar@9:          }
alpar@9:       }
alpar@9: #endif
alpar@9:       /* general row analysis */
alpar@9:       ret = npp_analyze_row(npp, row);
alpar@9:       xassert(0x00 <= ret && ret <= 0xFF);
alpar@9:       if (ret == 0x33)
alpar@9:       {  /* row bounds are inconsistent with column bounds */
alpar@9:          return GLP_ENOPFS;
alpar@9:       }
alpar@9:       if ((ret & 0x0F) == 0x00)
alpar@9:       {  /* row lower bound does not exist or redundant */
alpar@9:          if (row->lb != -DBL_MAX)
alpar@9:          {  /* remove redundant row lower bound */
alpar@9: #ifdef GLP_DEBUG
alpar@9:             xprintf("F");
alpar@9: #endif
alpar@9:             npp_inactive_bound(npp, row, 0);
alpar@9:          }
alpar@9:       }
alpar@9:       else if ((ret & 0x0F) == 0x01)
alpar@9:       {  /* row lower bound can be active */
alpar@9:          /* see below */
alpar@9:       }
alpar@9:       else if ((ret & 0x0F) == 0x02)
alpar@9:       {  /* row lower bound is a forcing bound */
alpar@9: #ifdef GLP_DEBUG
alpar@9:          xprintf("G");
alpar@9: #endif
alpar@9:          /* process forcing row */
alpar@9:          if (npp_forcing_row(npp, row, 0) == 0)
alpar@9: fixup:   {  /* columns were fixed, row was made free */
alpar@9:             for (aij = row->ptr; aij != NULL; aij = next_aij)
alpar@9:             {  /* process column fixed by forcing row */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                xprintf("H");
alpar@9: #endif
alpar@9:                col = aij->col;
alpar@9:                next_aij = aij->r_next;
alpar@9:                /* activate rows affected by column */
alpar@9:                for (aaa = col->ptr; aaa != NULL; aaa = aaa->c_next)
alpar@9:                   npp_activate_row(npp, aaa->row);
alpar@9:                /* process fixed column */
alpar@9:                npp_fixed_col(npp, col);
alpar@9:                /* column was deleted */
alpar@9:             }
alpar@9:             /* process free row (which now is empty due to deletion of
alpar@9:                all its columns) */
alpar@9:             npp_free_row(npp, row);
alpar@9:             /* row was deleted */
alpar@9:             return 0;
alpar@9:          }
alpar@9:       }
alpar@9:       else
alpar@9:          xassert(ret != ret);
alpar@9:       if ((ret & 0xF0) == 0x00)
alpar@9:       {  /* row upper bound does not exist or redundant */
alpar@9:          if (row->ub != +DBL_MAX)
alpar@9:          {  /* remove redundant row upper bound */
alpar@9: #ifdef GLP_DEBUG
alpar@9:             xprintf("I");
alpar@9: #endif
alpar@9:             npp_inactive_bound(npp, row, 1);
alpar@9:          }
alpar@9:       }
alpar@9:       else if ((ret & 0xF0) == 0x10)
alpar@9:       {  /* row upper bound can be active */
alpar@9:          /* see below */
alpar@9:       }
alpar@9:       else if ((ret & 0xF0) == 0x20)
alpar@9:       {  /* row upper bound is a forcing bound */
alpar@9: #ifdef GLP_DEBUG
alpar@9:          xprintf("J");
alpar@9: #endif
alpar@9:          /* process forcing row */
alpar@9:          if (npp_forcing_row(npp, row, 1) == 0) goto fixup;
alpar@9:       }
alpar@9:       else
alpar@9:          xassert(ret != ret);
alpar@9:       if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
alpar@9:       {  /* row became free due to redundant bounds removal */
alpar@9: #ifdef GLP_DEBUG
alpar@9:          xprintf("K");
alpar@9: #endif
alpar@9:          /* activate its columns, since their length will change due
alpar@9:             to row deletion */
alpar@9:          for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9:             npp_activate_col(npp, aij->col);
alpar@9:          /* process free row */
alpar@9:          npp_free_row(npp, row);
alpar@9:          /* row was deleted */
alpar@9:          return 0;
alpar@9:       }
alpar@9: #if 1 /* 23/XII-2009 */
alpar@9:       /* row lower and/or upper bounds can be active */
alpar@9:       if (npp->sol == GLP_MIP && hard)
alpar@9:       {  /* improve current column bounds (optional) */
alpar@9:          if (npp_improve_bounds(npp, row, 1) < 0)
alpar@9:             return GLP_ENOPFS;
alpar@9:       }
alpar@9: #endif
alpar@9:       return 0;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  npp_improve_bounds - improve current column bounds
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpnpp.h"
alpar@9: *  int npp_improve_bounds(NPP *npp, NPPROW *row, int flag);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine npp_improve_bounds analyzes specified row (inequality
alpar@9: *  or equality constraint) to determine implied column bounds and then
alpar@9: *  uses these bounds to improve (strengthen) current column bounds.
alpar@9: *
alpar@9: *  If the flag is on and current column bounds changed significantly
alpar@9: *  or the column was fixed, the routine activate rows affected by the
alpar@9: *  column for further processing. (This feature is intended to be used
alpar@9: *  in the main loop of the routine npp_process_row.)
alpar@9: *
alpar@9: *  NOTE: This operation can be used for MIP problem only.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  The routine npp_improve_bounds returns the number of significantly
alpar@9: *  changed bounds plus the number of column having been fixed due to
alpar@9: *  bound improvements. However, if the routine detects primal/integer
alpar@9: *  infeasibility, it returns a negative value. */
alpar@9: 
alpar@9: int npp_improve_bounds(NPP *npp, NPPROW *row, int flag)
alpar@9: {     /* improve current column bounds */
alpar@9:       NPPCOL *col;
alpar@9:       NPPAIJ *aij, *next_aij, *aaa;
alpar@9:       int kase, ret, count = 0;
alpar@9:       double lb, ub;
alpar@9:       xassert(npp->sol == GLP_MIP);
alpar@9:       /* row must not be free */
alpar@9:       xassert(!(row->lb == -DBL_MAX && row->ub == +DBL_MAX));
alpar@9:       /* determine implied column bounds */
alpar@9:       npp_implied_bounds(npp, row);
alpar@9:       /* and use these bounds to strengthen current column bounds */
alpar@9:       for (aij = row->ptr; aij != NULL; aij = next_aij)
alpar@9:       {  col = aij->col;
alpar@9:          next_aij = aij->r_next;
alpar@9:          for (kase = 0; kase <= 1; kase++)
alpar@9:          {  /* save current column bounds */
alpar@9:             lb = col->lb, ub = col->ub;
alpar@9:             if (kase == 0)
alpar@9:             {  /* process implied column lower bound */
alpar@9:                if (col->ll.ll == -DBL_MAX) continue;
alpar@9:                ret = npp_implied_lower(npp, col, col->ll.ll);
alpar@9:             }
alpar@9:             else
alpar@9:             {  /* process implied column upper bound */
alpar@9:                if (col->uu.uu == +DBL_MAX) continue;
alpar@9:                ret = npp_implied_upper(npp, col, col->uu.uu);
alpar@9:             }
alpar@9:             if (ret == 0 || ret == 1)
alpar@9:             {  /* current column bounds did not change or changed, but
alpar@9:                   not significantly; restore current column bounds */
alpar@9:                col->lb = lb, col->ub = ub;
alpar@9:             }
alpar@9:             else if (ret == 2 || ret == 3)
alpar@9:             {  /* current column bounds changed significantly or column
alpar@9:                   was fixed */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                xprintf("L");
alpar@9: #endif
alpar@9:                count++;
alpar@9:                /* activate other rows affected by column, if required */
alpar@9:                if (flag)
alpar@9:                {  for (aaa = col->ptr; aaa != NULL; aaa = aaa->c_next)
alpar@9:                   {  if (aaa->row != row)
alpar@9:                         npp_activate_row(npp, aaa->row);
alpar@9:                   }
alpar@9:                }
alpar@9:                if (ret == 3)
alpar@9:                {  /* process fixed column */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                   xprintf("M");
alpar@9: #endif
alpar@9:                   npp_fixed_col(npp, col);
alpar@9:                   /* column was deleted */
alpar@9:                   break; /* for kase */
alpar@9:                }
alpar@9:             }
alpar@9:             else if (ret == 4)
alpar@9:             {  /* primal/integer infeasibility */
alpar@9:                return -1;
alpar@9:             }
alpar@9:             else
alpar@9:                xassert(ret != ret);
alpar@9:          }
alpar@9:       }
alpar@9:       return count;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  npp_process_col - perform basic column processing
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpnpp.h"
alpar@9: *  int npp_process_col(NPP *npp, NPPCOL *col);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine npp_process_col performs basic column processing that
alpar@9: *  currently includes:
alpar@9: *
alpar@9: *  1) fixing and removing empty column;
alpar@9: *
alpar@9: *  2) removing column singleton, which is implied slack variable, and
alpar@9: *     corresponding row if it becomes free;
alpar@9: *
alpar@9: *  3) removing bounds of column, which is implied free variable, and
alpar@9: *     replacing corresponding row by equality constraint.
alpar@9: *
alpar@9: *  Additionally the routine may activate affected rows and/or columns
alpar@9: *  for further processing.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  0           success;
alpar@9: *
alpar@9: *  GLP_ENOPFS  primal/integer infeasibility detected;
alpar@9: *
alpar@9: *  GLP_ENODFS  dual infeasibility detected. */
alpar@9: 
alpar@9: int npp_process_col(NPP *npp, NPPCOL *col)
alpar@9: {     /* perform basic column processing */
alpar@9:       NPPROW *row;
alpar@9:       NPPAIJ *aij;
alpar@9:       int ret;
alpar@9:       /* column must not be fixed */
alpar@9:       xassert(col->lb < col->ub);
alpar@9:       /* start processing column */
alpar@9:       if (col->ptr == NULL)
alpar@9:       {  /* empty column */
alpar@9:          ret = npp_empty_col(npp, col);
alpar@9:          if (ret == 0)
alpar@9:          {  /* column was fixed and deleted */
alpar@9: #ifdef GLP_DEBUG
alpar@9:             xprintf("N");
alpar@9: #endif
alpar@9:             return 0;
alpar@9:          }
alpar@9:          else if (ret == 1)
alpar@9:          {  /* dual infeasibility */
alpar@9:             return GLP_ENODFS;
alpar@9:          }
alpar@9:          else
alpar@9:             xassert(ret != ret);
alpar@9:       }
alpar@9:       if (col->ptr->c_next == NULL)
alpar@9:       {  /* column singleton */
alpar@9:          row = col->ptr->row;
alpar@9:          if (row->lb == row->ub)
alpar@9:          {  /* equality constraint */
alpar@9:             if (!col->is_int)
alpar@9: slack:      {  /* implied slack variable */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                xprintf("O");
alpar@9: #endif
alpar@9:                npp_implied_slack(npp, col);
alpar@9:                /* column was deleted */
alpar@9:                if (row->lb == -DBL_MAX && row->ub == +DBL_MAX)
alpar@9:                {  /* row became free due to implied slack variable */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                   xprintf("P");
alpar@9: #endif
alpar@9:                   /* activate columns affected by row */
alpar@9:                   for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9:                      npp_activate_col(npp, aij->col);
alpar@9:                   /* process free row */
alpar@9:                   npp_free_row(npp, row);
alpar@9:                   /* row was deleted */
alpar@9:                }
alpar@9:                else
alpar@9:                {  /* row became inequality constraint; activate it
alpar@9:                      since its length changed due to column deletion */
alpar@9:                   npp_activate_row(npp, row);
alpar@9:                }
alpar@9:                return 0;
alpar@9:             }
alpar@9:          }
alpar@9:          else
alpar@9:          {  /* inequality constraint */
alpar@9:             if (!col->is_int)
alpar@9:             {  ret = npp_implied_free(npp, col);
alpar@9:                if (ret == 0)
alpar@9:                {  /* implied free variable */
alpar@9: #ifdef GLP_DEBUG
alpar@9:                   xprintf("Q");
alpar@9: #endif
alpar@9:                   /* column bounds were removed, row was replaced by
alpar@9:                      equality constraint */
alpar@9:                   goto slack;
alpar@9:                }
alpar@9:                else if (ret == 1)
alpar@9:                {  /* column is not implied free variable, because its
alpar@9:                      lower and/or upper bounds can be active */
alpar@9:                }
alpar@9:                else if (ret == 2)
alpar@9:                {  /* dual infeasibility */
alpar@9:                   return GLP_ENODFS;
alpar@9:                }
alpar@9:             }
alpar@9:          }
alpar@9:       }
alpar@9:       /* column still exists */
alpar@9:       return 0;
alpar@9: }
alpar@9: 
alpar@9: /***********************************************************************
alpar@9: *  NAME
alpar@9: *
alpar@9: *  npp_process_prob - perform basic LP/MIP processing
alpar@9: *
alpar@9: *  SYNOPSIS
alpar@9: *
alpar@9: *  #include "glpnpp.h"
alpar@9: *  int npp_process_prob(NPP *npp, int hard);
alpar@9: *
alpar@9: *  DESCRIPTION
alpar@9: *
alpar@9: *  The routine npp_process_prob performs basic LP/MIP processing that
alpar@9: *  currently includes:
alpar@9: *
alpar@9: *  1) initial LP/MIP processing (see the routine npp_clean_prob),
alpar@9: *
alpar@9: *  2) basic row processing (see the routine npp_process_row), and
alpar@9: *
alpar@9: *  3) basic column processing (see the routine npp_process_col).
alpar@9: *
alpar@9: *  If the flag hard is on, the routine attempts to improve current
alpar@9: *  column bounds multiple times within the main processing loop, in
alpar@9: *  which case this feature may take a time. Otherwise, if the flag hard
alpar@9: *  is off, improving column bounds is performed only once at the end of
alpar@9: *  the main loop. (Note that this feature is used for MIP only.)
alpar@9: *
alpar@9: *  The routine uses two sets: the set of active rows and the set of
alpar@9: *  active columns. Rows/columns are marked by a flag (the field temp in
alpar@9: *  NPPROW/NPPCOL). If the flag is non-zero, the row/column is active,
alpar@9: *  in which case it is placed in the beginning of the row/column list;
alpar@9: *  otherwise, if the flag is zero, the row/column is inactive, in which
alpar@9: *  case it is placed in the end of the row/column list. If a row/column
alpar@9: *  being currently processed may affect other rows/columns, the latters
alpar@9: *  are activated for further processing.
alpar@9: *
alpar@9: *  RETURNS
alpar@9: *
alpar@9: *  0           success;
alpar@9: *
alpar@9: *  GLP_ENOPFS  primal/integer infeasibility detected;
alpar@9: *
alpar@9: *  GLP_ENODFS  dual infeasibility detected. */
alpar@9: 
alpar@9: int npp_process_prob(NPP *npp, int hard)
alpar@9: {     /* perform basic LP/MIP processing */
alpar@9:       NPPROW *row;
alpar@9:       NPPCOL *col;
alpar@9:       int processing, ret;
alpar@9:       /* perform initial LP/MIP processing */
alpar@9:       npp_clean_prob(npp);
alpar@9:       /* activate all remaining rows and columns */
alpar@9:       for (row = npp->r_head; row != NULL; row = row->next)
alpar@9:          row->temp = 1;
alpar@9:       for (col = npp->c_head; col != NULL; col = col->next)
alpar@9:          col->temp = 1;
alpar@9:       /* main processing loop */
alpar@9:       processing = 1;
alpar@9:       while (processing)
alpar@9:       {  processing = 0;
alpar@9:          /* process all active rows */
alpar@9:          for (;;)
alpar@9:          {  row = npp->r_head;
alpar@9:             if (row == NULL || !row->temp) break;
alpar@9:             npp_deactivate_row(npp, row);
alpar@9:             ret = npp_process_row(npp, row, hard);
alpar@9:             if (ret != 0) goto done;
alpar@9:             processing = 1;
alpar@9:          }
alpar@9:          /* process all active columns */
alpar@9:          for (;;)
alpar@9:          {  col = npp->c_head;
alpar@9:             if (col == NULL || !col->temp) break;
alpar@9:             npp_deactivate_col(npp, col);
alpar@9:             ret = npp_process_col(npp, col);
alpar@9:             if (ret != 0) goto done;
alpar@9:             processing = 1;
alpar@9:          }
alpar@9:       }
alpar@9: #if 1 /* 23/XII-2009 */
alpar@9:       if (npp->sol == GLP_MIP && !hard)
alpar@9:       {  /* improve current column bounds (optional) */
alpar@9:          for (row = npp->r_head; row != NULL; row = row->next)
alpar@9:          {  if (npp_improve_bounds(npp, row, 0) < 0)
alpar@9:             {  ret = GLP_ENOPFS;
alpar@9:                goto done;
alpar@9:             }
alpar@9:          }
alpar@9:       }
alpar@9: #endif
alpar@9:       /* all seems ok */
alpar@9:       ret = 0;
alpar@9: done: xassert(ret == 0 || ret == GLP_ENOPFS || ret == GLP_ENODFS);
alpar@9: #ifdef GLP_DEBUG
alpar@9:       xprintf("\n");
alpar@9: #endif
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /**********************************************************************/
alpar@9: 
alpar@9: int npp_simplex(NPP *npp, const glp_smcp *parm)
alpar@9: {     /* process LP prior to applying primal/dual simplex method */
alpar@9:       int ret;
alpar@9:       xassert(npp->sol == GLP_SOL);
alpar@9:       xassert(parm == parm);
alpar@9:       ret = npp_process_prob(npp, 0);
alpar@9:       return ret;
alpar@9: }
alpar@9: 
alpar@9: /**********************************************************************/
alpar@9: 
alpar@9: int npp_integer(NPP *npp, const glp_iocp *parm)
alpar@9: {     /* process MIP prior to applying branch-and-bound method */
alpar@9:       NPPROW *row, *prev_row;
alpar@9:       NPPCOL *col;
alpar@9:       NPPAIJ *aij;
alpar@9:       int count, ret;
alpar@9:       xassert(npp->sol == GLP_MIP);
alpar@9:       xassert(parm == parm);
alpar@9:       /*==============================================================*/
alpar@9:       /* perform basic MIP processing */
alpar@9:       ret = npp_process_prob(npp, 1);
alpar@9:       if (ret != 0) goto done;
alpar@9:       /*==============================================================*/
alpar@9:       /* binarize problem, if required */
alpar@9:       if (parm->binarize)
alpar@9:          npp_binarize_prob(npp);
alpar@9:       /*==============================================================*/
alpar@9:       /* identify hidden packing inequalities */
alpar@9:       count = 0;
alpar@9:       /* new rows will be added to the end of the row list, so we go
alpar@9:          from the end to beginning of the row list */
alpar@9:       for (row = npp->r_tail; row != NULL; row = prev_row)
alpar@9:       {  prev_row = row->prev;
alpar@9:          /* skip free row */
alpar@9:          if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) continue;
alpar@9:          /* skip equality constraint */
alpar@9:          if (row->lb == row->ub) continue;
alpar@9:          /* skip row having less than two variables */
alpar@9:          if (row->ptr == NULL || row->ptr->r_next == NULL) continue;
alpar@9:          /* skip row having non-binary variables */
alpar@9:          for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9:          {  col = aij->col;
alpar@9:             if (!(col->is_int && col->lb == 0.0 && col->ub == 1.0))
alpar@9:                break;
alpar@9:          }
alpar@9:          if (aij != NULL) continue;
alpar@9:          count += npp_hidden_packing(npp, row);
alpar@9:       }
alpar@9:       if (count > 0)
alpar@9:          xprintf("%d hidden packing inequaliti(es) were detected\n",
alpar@9:             count);
alpar@9:       /*==============================================================*/
alpar@9:       /* identify hidden covering inequalities */
alpar@9:       count = 0;
alpar@9:       /* new rows will be added to the end of the row list, so we go
alpar@9:          from the end to beginning of the row list */
alpar@9:       for (row = npp->r_tail; row != NULL; row = prev_row)
alpar@9:       {  prev_row = row->prev;
alpar@9:          /* skip free row */
alpar@9:          if (row->lb == -DBL_MAX && row->ub == +DBL_MAX) continue;
alpar@9:          /* skip equality constraint */
alpar@9:          if (row->lb == row->ub) continue;
alpar@9:          /* skip row having less than three variables */
alpar@9:          if (row->ptr == NULL || row->ptr->r_next == NULL ||
alpar@9:              row->ptr->r_next->r_next == NULL) continue;
alpar@9:          /* skip row having non-binary variables */
alpar@9:          for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9:          {  col = aij->col;
alpar@9:             if (!(col->is_int && col->lb == 0.0 && col->ub == 1.0))
alpar@9:                break;
alpar@9:          }
alpar@9:          if (aij != NULL) continue;
alpar@9:          count += npp_hidden_covering(npp, row);
alpar@9:       }
alpar@9:       if (count > 0)
alpar@9:          xprintf("%d hidden covering inequaliti(es) were detected\n",
alpar@9:             count);
alpar@9:       /*==============================================================*/
alpar@9:       /* reduce inequality constraint coefficients */
alpar@9:       count = 0;
alpar@9:       /* new rows will be added to the end of the row list, so we go
alpar@9:          from the end to beginning of the row list */
alpar@9:       for (row = npp->r_tail; row != NULL; row = prev_row)
alpar@9:       {  prev_row = row->prev;
alpar@9:          /* skip equality constraint */
alpar@9:          if (row->lb == row->ub) continue;
alpar@9:          count += npp_reduce_ineq_coef(npp, row);
alpar@9:       }
alpar@9:       if (count > 0)
alpar@9:          xprintf("%d constraint coefficient(s) were reduced\n", count);
alpar@9:       /*==============================================================*/
alpar@9: #ifdef GLP_DEBUG
alpar@9:       routine(npp);
alpar@9: #endif
alpar@9:       /*==============================================================*/
alpar@9:       /* all seems ok */
alpar@9:       ret = 0;
alpar@9: done: return ret;
alpar@9: }
alpar@9: 
alpar@9: /* eof */