source: lemon-project-template-glpk/deps/glpk/src/glpios02.c

/* glpios02.c (preprocess current subproblem) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
*  2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
*  E-mail: <mao@gnu.org>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#include "glpios.h"

/***********************************************************************
*  prepare_row_info - prepare row info to determine implied bounds
*
*  Given a row (linear form)
*
*      n
*     sum a[j] * x[j]                                                (1)
*     j=1
*
*  and bounds of columns (variables)
*
*     l[j] <= x[j] <= u[j]                                           (2)
*
*  this routine computes f_min, j_min, f_max, j_max needed to determine
*  implied bounds.
*
*  ALGORITHM
*
*  Let J+ = {j : a[j] > 0} and J- = {j : a[j] < 0}.
*
*  Parameters f_min and j_min are computed as follows:
*
*  1) if there is no x[k] such that k in J+ and l[k] = -inf or k in J-
*     and u[k] = +inf, then
*
*     f_min :=   sum   a[j] * l[j] +   sum   a[j] * u[j]
*              j in J+               j in J-
*                                                                    (3)
*     j_min := 0
*
*  2) if there is exactly one x[k] such that k in J+ and l[k] = -inf
*     or k in J- and u[k] = +inf, then
*
*     f_min :=   sum       a[j] * l[j] +   sum       a[j] * u[j]
*              j in J+\{k}               j in J-\{k}
*                                                                    (4)
*     j_min := k
*
*  3) if there are two or more x[k] such that k in J+ and l[k] = -inf
*     or k in J- and u[k] = +inf, then
*
*     f_min := -inf
*                                                                    (5)
*     j_min := 0
*
*  Parameters f_max and j_max are computed in a similar way as follows:
*
*  1) if there is no x[k] such that k in J+ and u[k] = +inf or k in J-
*     and l[k] = -inf, then
*
*     f_max :=   sum   a[j] * u[j] +   sum   a[j] * l[j]
*              j in J+               j in J-
*                                                                    (6)
*     j_max := 0
*
*  2) if there is exactly one x[k] such that k in J+ and u[k] = +inf
*     or k in J- and l[k] = -inf, then
*
*     f_max :=   sum       a[j] * u[j] +   sum       a[j] * l[j]
*              j in J+\{k}               j in J-\{k}
*                                                                    (7)
*     j_max := k
*
*  3) if there are two or more x[k] such that k in J+ and u[k] = +inf
*     or k in J- and l[k] = -inf, then
*
*     f_max := +inf
*                                                                    (8)
*     j_max := 0                                                      */

struct f_info
{     int j_min, j_max;
      double f_min, f_max;
};

static void prepare_row_info(int n, const double a[], const double l[],
      const double u[], struct f_info *f)
{     int j, j_min, j_max;
      double f_min, f_max;
      xassert(n >= 0);
      /* determine f_min and j_min */
      f_min = 0.0, j_min = 0;
      for (j = 1; j <= n; j++)
      {  if (a[j] > 0.0)
         {  if (l[j] == -DBL_MAX)
            {  if (j_min == 0)
                  j_min = j;
               else
               {  f_min = -DBL_MAX, j_min = 0;
                  break;
               }
            }
            else
               f_min += a[j] * l[j];
         }
         else if (a[j] < 0.0)
         {  if (u[j] == +DBL_MAX)
            {  if (j_min == 0)
                  j_min = j;
               else
               {  f_min = -DBL_MAX, j_min = 0;
                  break;
               }
            }
            else
               f_min += a[j] * u[j];
         }
         else
            xassert(a != a);
      }
      f->f_min = f_min, f->j_min = j_min;
      /* determine f_max and j_max */
      f_max = 0.0, j_max = 0;
      for (j = 1; j <= n; j++)
      {  if (a[j] > 0.0)
         {  if (u[j] == +DBL_MAX)
            {  if (j_max == 0)
                  j_max = j;
               else
               {  f_max = +DBL_MAX, j_max = 0;
                  break;
               }
            }
            else
               f_max += a[j] * u[j];
         }
         else if (a[j] < 0.0)
         {  if (l[j] == -DBL_MAX)
            {  if (j_max == 0)
                  j_max = j;
               else
               {  f_max = +DBL_MAX, j_max = 0;
                  break;
               }
            }
            else
               f_max += a[j] * l[j];
         }
         else
            xassert(a != a);
      }
      f->f_max = f_max, f->j_max = j_max;
      return;
}

/***********************************************************************
*  row_implied_bounds - determine row implied bounds
*
*  Given a row (linear form)
*
*      n
*     sum a[j] * x[j]
*     j=1
*
*  and bounds of columns (variables)
*
*     l[j] <= x[j] <= u[j]
*
*  this routine determines implied bounds of the row.
*
*  ALGORITHM
*
*  Let J+ = {j : a[j] > 0} and J- = {j : a[j] < 0}.
*
*  The implied lower bound of the row is computed as follows:
*
*     L' :=   sum   a[j] * l[j] +   sum   a[j] * u[j]                (9)
*           j in J+               j in J-
*
*  and as it follows from (3), (4), and (5):
*
*     L' := if j_min = 0 then f_min else -inf                       (10)
*
*  The implied upper bound of the row is computed as follows:
*
*     U' :=   sum   a[j] * u[j] +   sum   a[j] * l[j]               (11)
*           j in J+               j in J-
*
*  and as it follows from (6), (7), and (8):
*
*     U' := if j_max = 0 then f_max else +inf                       (12)
*
*  The implied bounds are stored in locations LL and UU. */

static void row_implied_bounds(const struct f_info *f, double *LL,
      double *UU)
{     *LL = (f->j_min == 0 ? f->f_min : -DBL_MAX);
      *UU = (f->j_max == 0 ? f->f_max : +DBL_MAX);
      return;
}

/***********************************************************************
*  col_implied_bounds - determine column implied bounds
*
*  Given a row (constraint)
*
*           n
*     L <= sum a[j] * x[j] <= U                                     (13)
*          j=1
*
*  and bounds of columns (variables)
*
*     l[j] <= x[j] <= u[j]
*
*  this routine determines implied bounds of variable x[k].
*
*  It is assumed that if L != -inf, the lower bound of the row can be
*  active, and if U != +inf, the upper bound of the row can be active.
*
*  ALGORITHM
*
*  From (13) it follows that
*
*     L <= sum a[j] * x[j] + a[k] * x[k] <= U
*          j!=k
*  or
*
*     L - sum a[j] * x[j] <= a[k] * x[k] <= U - sum a[j] * x[j]
*         j!=k                                  j!=k
*
*  Thus, if the row lower bound L can be active, implied lower bound of
*  term a[k] * x[k] can be determined as follows:
*
*     ilb(a[k] * x[k]) = min(L - sum a[j] * x[j]) =
*                                j!=k
*                                                                   (14)
*                      = L - max sum a[j] * x[j]
*                            j!=k
*
*  where, as it follows from (6), (7), and (8)
*
*                           / f_max - a[k] * u[k], j_max = 0, a[k] > 0
*                           |
*                           | f_max - a[k] * l[k], j_max = 0, a[k] < 0
*     max sum a[j] * x[j] = {
*         j!=k              | f_max,               j_max = k
*                           |
*                           \ +inf,                j_max != 0
*
*  and if the upper bound U can be active, implied upper bound of term
*  a[k] * x[k] can be determined as follows:
*
*     iub(a[k] * x[k]) = max(U - sum a[j] * x[j]) =
*                                j!=k
*                                                                   (15)
*                      = U - min sum a[j] * x[j]
*                            j!=k
*
*  where, as it follows from (3), (4), and (5)
*
*                           / f_min - a[k] * l[k], j_min = 0, a[k] > 0
*                           |
*                           | f_min - a[k] * u[k], j_min = 0, a[k] < 0
*     min sum a[j] * x[j] = {
*         j!=k              | f_min,               j_min = k
*                           |
*                           \ -inf,                j_min != 0
*
*  Since
*
*     ilb(a[k] * x[k]) <= a[k] * x[k] <= iub(a[k] * x[k])
*
*  implied lower and upper bounds of x[k] are determined as follows:
*
*     l'[k] := if a[k] > 0 then ilb / a[k] else ulb / a[k]          (16)
*
*     u'[k] := if a[k] > 0 then ulb / a[k] else ilb / a[k]          (17)
*
*  The implied bounds are stored in locations ll and uu. */

static void col_implied_bounds(const struct f_info *f, int n,
      const double a[], double L, double U, const double l[],
      const double u[], int k, double *ll, double *uu)
{     double ilb, iub;
      xassert(n >= 0);
      xassert(1 <= k && k <= n);
      /* determine implied lower bound of term a[k] * x[k] (14) */
      if (L == -DBL_MAX || f->f_max == +DBL_MAX)
         ilb = -DBL_MAX;
      else if (f->j_max == 0)
      {  if (a[k] > 0.0)
         {  xassert(u[k] != +DBL_MAX);
            ilb = L - (f->f_max - a[k] * u[k]);
         }
         else if (a[k] < 0.0)
         {  xassert(l[k] != -DBL_MAX);
            ilb = L - (f->f_max - a[k] * l[k]);
         }
         else
            xassert(a != a);
      }
      else if (f->j_max == k)
         ilb = L - f->f_max;
      else
         ilb = -DBL_MAX;
      /* determine implied upper bound of term a[k] * x[k] (15) */
      if (U == +DBL_MAX || f->f_min == -DBL_MAX)
         iub = +DBL_MAX;
      else if (f->j_min == 0)
      {  if (a[k] > 0.0)
         {  xassert(l[k] != -DBL_MAX);
            iub = U - (f->f_min - a[k] * l[k]);
         }
         else if (a[k] < 0.0)
         {  xassert(u[k] != +DBL_MAX);
            iub = U - (f->f_min - a[k] * u[k]);
         }
         else
            xassert(a != a);
      }
      else if (f->j_min == k)
         iub = U - f->f_min;
      else
         iub = +DBL_MAX;
      /* determine implied bounds of x[k] (16) and (17) */
#if 1
      /* do not use a[k] if it has small magnitude to prevent wrong
         implied bounds; for example, 1e-15 * x1 >= x2 + x3, where
         x1 >= -10, x2, x3 >= 0, would lead to wrong conclusion that
         x1 >= 0 */
      if (fabs(a[k]) < 1e-6)
         *ll = -DBL_MAX, *uu = +DBL_MAX; else
#endif
      if (a[k] > 0.0)
      {  *ll = (ilb == -DBL_MAX ? -DBL_MAX : ilb / a[k]);
         *uu = (iub == +DBL_MAX ? +DBL_MAX : iub / a[k]);
      }
      else if (a[k] < 0.0)
      {  *ll = (iub == +DBL_MAX ? -DBL_MAX : iub / a[k]);
         *uu = (ilb == -DBL_MAX ? +DBL_MAX : ilb / a[k]);
      }
      else
         xassert(a != a);
      return;
}

/***********************************************************************
*  check_row_bounds - check and relax original row bounds
*
*  Given a row (constraint)
*
*           n
*     L <= sum a[j] * x[j] <= U
*          j=1
*
*  and bounds of columns (variables)
*
*     l[j] <= x[j] <= u[j]
*
*  this routine checks the original row bounds L and U for feasibility
*  and redundancy. If the original lower bound L or/and upper bound U
*  cannot be active due to bounds of variables, the routine remove them
*  replacing by -inf or/and +inf, respectively.
*
*  If no primal infeasibility is detected, the routine returns zero,
*  otherwise non-zero. */

static int check_row_bounds(const struct f_info *f, double *L_,
      double *U_)
{     int ret = 0;
      double L = *L_, U = *U_, LL, UU;
      /* determine implied bounds of the row */
      row_implied_bounds(f, &LL, &UU);
      /* check if the original lower bound is infeasible */
      if (L != -DBL_MAX)
      {  double eps = 1e-3 * (1.0 + fabs(L));
         if (UU < L - eps)
         {  ret = 1;
            goto done;
         }
      }
      /* check if the original upper bound is infeasible */
      if (U != +DBL_MAX)
      {  double eps = 1e-3 * (1.0 + fabs(U));
         if (LL > U + eps)
         {  ret = 1;
            goto done;
         }
      }
      /* check if the original lower bound is redundant */
      if (L != -DBL_MAX)
      {  double eps = 1e-12 * (1.0 + fabs(L));
         if (LL > L - eps)
         {  /* it cannot be active, so remove it */
            *L_ = -DBL_MAX;
         }
      }
      /* check if the original upper bound is redundant */
      if (U != +DBL_MAX)
      {  double eps = 1e-12 * (1.0 + fabs(U));
         if (UU < U + eps)
         {  /* it cannot be active, so remove it */
            *U_ = +DBL_MAX;
         }
      }
done: return ret;
}

/***********************************************************************
*  check_col_bounds - check and tighten original column bounds
*
*  Given a row (constraint)
*
*           n
*     L <= sum a[j] * x[j] <= U
*          j=1
*
*  and bounds of columns (variables)
*
*     l[j] <= x[j] <= u[j]
*
*  for column (variable) x[j] this routine checks the original column
*  bounds l[j] and u[j] for feasibility and redundancy. If the original
*  lower bound l[j] or/and upper bound u[j] cannot be active due to
*  bounds of the constraint and other variables, the routine tighten
*  them replacing by corresponding implied bounds, if possible.
*
*  NOTE: It is assumed that if L != -inf, the row lower bound can be
*        active, and if U != +inf, the row upper bound can be active.
*
*  The flag means that variable x[j] is required to be integer.
*
*  New actual bounds for x[j] are stored in locations lj and uj.
*
*  If no primal infeasibility is detected, the routine returns zero,
*  otherwise non-zero. */

static int check_col_bounds(const struct f_info *f, int n,
      const double a[], double L, double U, const double l[],
      const double u[], int flag, int j, double *_lj, double *_uj)
{     int ret = 0;
      double lj, uj, ll, uu;
      xassert(n >= 0);
      xassert(1 <= j && j <= n);
      lj = l[j], uj = u[j];
      /* determine implied bounds of the column */
      col_implied_bounds(f, n, a, L, U, l, u, j, &ll, &uu);
      /* if x[j] is integral, round its implied bounds */
      if (flag)
      {  if (ll != -DBL_MAX)
            ll = (ll - floor(ll) < 1e-3 ? floor(ll) : ceil(ll));
         if (uu != +DBL_MAX)
            uu = (ceil(uu) - uu < 1e-3 ? ceil(uu) : floor(uu));
      }
      /* check if the original lower bound is infeasible */
      if (lj != -DBL_MAX)
      {  double eps = 1e-3 * (1.0 + fabs(lj));
         if (uu < lj - eps)
         {  ret = 1;
            goto done;
         }
      }
      /* check if the original upper bound is infeasible */
      if (uj != +DBL_MAX)
      {  double eps = 1e-3 * (1.0 + fabs(uj));
         if (ll > uj + eps)
         {  ret = 1;
            goto done;
         }
      }
      /* check if the original lower bound is redundant */
      if (ll != -DBL_MAX)
      {  double eps = 1e-3 * (1.0 + fabs(ll));
         if (lj < ll - eps)
         {  /* it cannot be active, so tighten it */
            lj = ll;
         }
      }
      /* check if the original upper bound is redundant */
      if (uu != +DBL_MAX)
      {  double eps = 1e-3 * (1.0 + fabs(uu));
         if (uj > uu + eps)
         {  /* it cannot be active, so tighten it */
            uj = uu;
         }
      }
      /* due to round-off errors it may happen that lj > uj (although
         lj < uj + eps, since no primal infeasibility is detected), so
         adjuct the new actual bounds to provide lj <= uj */
      if (!(lj == -DBL_MAX || uj == +DBL_MAX))
      {  double t1 = fabs(lj), t2 = fabs(uj);
         double eps = 1e-10 * (1.0 + (t1 <= t2 ? t1 : t2));
         if (lj > uj - eps)
         {  if (lj == l[j])
               uj = lj;
            else if (uj == u[j])
               lj = uj;
            else if (t1 <= t2)
               uj = lj;
            else
               lj = uj;
         }
      }
      *_lj = lj, *_uj = uj;
done: return ret;
}

/***********************************************************************
*  check_efficiency - check if change in column bounds is efficient
*
*  Given the original bounds of a column l and u and its new actual
*  bounds l' and u' (possibly tighten by the routine check_col_bounds)
*  this routine checks if the change in the column bounds is efficient
*  enough. If so, the routine returns non-zero, otherwise zero.
*
*  The flag means that the variable is required to be integer. */

static int check_efficiency(int flag, double l, double u, double ll,
      double uu)
{     int eff = 0;
      /* check efficiency for lower bound */
      if (l < ll)
      {  if (flag || l == -DBL_MAX)
            eff++;
         else
         {  double r;
            if (u == +DBL_MAX)
               r = 1.0 + fabs(l);
            else
               r = 1.0 + (u - l);
            if (ll - l >= 0.25 * r)
               eff++;
         }
      }
      /* check efficiency for upper bound */
      if (u > uu)
      {  if (flag || u == +DBL_MAX)
            eff++;
         else
         {  double r;
            if (l == -DBL_MAX)
               r = 1.0 + fabs(u);
            else
               r = 1.0 + (u - l);
            if (u - uu >= 0.25 * r)
               eff++;
         }
      }
      return eff;
}

/***********************************************************************
*  basic_preprocessing - perform basic preprocessing
*
*  This routine performs basic preprocessing of the specified MIP that
*  includes relaxing some row bounds and tightening some column bounds.
*
*  On entry the arrays L and U contains original row bounds, and the
*  arrays l and u contains original column bounds:
*
*  L[0] is the lower bound of the objective row;
*  L[i], i = 1,...,m, is the lower bound of i-th row;
*  U[0] is the upper bound of the objective row;
*  U[i], i = 1,...,m, is the upper bound of i-th row;
*  l[0] is not used;
*  l[j], j = 1,...,n, is the lower bound of j-th column;
*  u[0] is not used;
*  u[j], j = 1,...,n, is the upper bound of j-th column.
*
*  On exit the arrays L, U, l, and u contain new actual bounds of rows
*  and column in the same locations.
*
*  The parameters nrs and num specify an initial list of rows to be
*  processed:
*
*  nrs is the number of rows in the initial list, 0 <= nrs <= m+1;
*  num[0] is not used;
*  num[1,...,nrs] are row numbers (0 means the objective row).
*
*  The parameter max_pass specifies the maximal number of times that
*  each row can be processed, max_pass > 0.
*
*  If no primal infeasibility is detected, the routine returns zero,
*  otherwise non-zero. */

static int basic_preprocessing(glp_prob *mip, double L[], double U[],
      double l[], double u[], int nrs, const int num[], int max_pass)
{     int m = mip->m;
      int n = mip->n;
      struct f_info f;
      int i, j, k, len, size, ret = 0;
      int *ind, *list, *mark, *pass;
      double *val, *lb, *ub;
      xassert(0 <= nrs && nrs <= m+1);
      xassert(max_pass > 0);
      /* allocate working arrays */
      ind = xcalloc(1+n, sizeof(int));
      list = xcalloc(1+m+1, sizeof(int));
      mark = xcalloc(1+m+1, sizeof(int));
      memset(&mark[0], 0, (m+1) * sizeof(int));
      pass = xcalloc(1+m+1, sizeof(int));
      memset(&pass[0], 0, (m+1) * sizeof(int));
      val = xcalloc(1+n, sizeof(double));
      lb = xcalloc(1+n, sizeof(double));
      ub = xcalloc(1+n, sizeof(double));
      /* initialize the list of rows to be processed */
      size = 0;
      for (k = 1; k <= nrs; k++)
      {  i = num[k];
         xassert(0 <= i && i <= m);
         /* duplicate row numbers are not allowed */
         xassert(!mark[i]);
         list[++size] = i, mark[i] = 1;
      }
      xassert(size == nrs);
      /* process rows in the list until it becomes empty */
      while (size > 0)
      {  /* get a next row from the list */
         i = list[size--], mark[i] = 0;
         /* increase the row processing count */
         pass[i]++;
         /* if the row is free, skip it */
         if (L[i] == -DBL_MAX && U[i] == +DBL_MAX) continue;
         /* obtain coefficients of the row */
         len = 0;
         if (i == 0)
         {  for (j = 1; j <= n; j++)
            {  GLPCOL *col = mip->col[j];
               if (col->coef != 0.0)
                  len++, ind[len] = j, val[len] = col->coef;
            }
         }
         else
         {  GLPROW *row = mip->row[i];
            GLPAIJ *aij;
            for (aij = row->ptr; aij != NULL; aij = aij->r_next)
               len++, ind[len] = aij->col->j, val[len] = aij->val;
         }
         /* determine lower and upper bounds of columns corresponding
            to non-zero row coefficients */
         for (k = 1; k <= len; k++)
            j = ind[k], lb[k] = l[j], ub[k] = u[j];
         /* prepare the row info to determine implied bounds */
         prepare_row_info(len, val, lb, ub, &f);
         /* check and relax bounds of the row */
         if (check_row_bounds(&f, &L[i], &U[i]))
         {  /* the feasible region is empty */
            ret = 1;
            goto done;
         }
         /* if the row became free, drop it */
         if (L[i] == -DBL_MAX && U[i] == +DBL_MAX) continue;
         /* process columns having non-zero coefficients in the row */
         for (k = 1; k <= len; k++)
         {  GLPCOL *col;
            int flag, eff;
            double ll, uu;
            /* take a next column in the row */
            j = ind[k], col = mip->col[j];
            flag = col->kind != GLP_CV;
            /* check and tighten bounds of the column */
            if (check_col_bounds(&f, len, val, L[i], U[i], lb, ub,
                flag, k, &ll, &uu))
            {  /* the feasible region is empty */
               ret = 1;
               goto done;
            }
            /* check if change in the column bounds is efficient */
            eff = check_efficiency(flag, l[j], u[j], ll, uu);
            /* set new actual bounds of the column */
            l[j] = ll, u[j] = uu;
            /* if the change is efficient, add all rows affected by the
               corresponding column, to the list */
            if (eff > 0)
            {  GLPAIJ *aij;
               for (aij = col->ptr; aij != NULL; aij = aij->c_next)
               {  int ii = aij->row->i;
                  /* if the row was processed maximal number of times,
                     skip it */
                  if (pass[ii] >= max_pass) continue;
                  /* if the row is free, skip it */
                  if (L[ii] == -DBL_MAX && U[ii] == +DBL_MAX) continue;
                  /* put the row into the list */
                  if (mark[ii] == 0)
                  {  xassert(size <= m);
                     list[++size] = ii, mark[ii] = 1;
                  }
               }
            }
         }
      }
done: /* free working arrays */
      xfree(ind);
      xfree(list);
      xfree(mark);
      xfree(pass);
      xfree(val);
      xfree(lb);
      xfree(ub);
      return ret;
}

/***********************************************************************
*  NAME
*
*  ios_preprocess_node - preprocess current subproblem
*
*  SYNOPSIS
*
*  #include "glpios.h"
*  int ios_preprocess_node(glp_tree *tree, int max_pass);
*
*  DESCRIPTION
*
*  The routine ios_preprocess_node performs basic preprocessing of the
*  current subproblem.
*
*  RETURNS
*
*  If no primal infeasibility is detected, the routine returns zero,
*  otherwise non-zero. */

int ios_preprocess_node(glp_tree *tree, int max_pass)
{     glp_prob *mip = tree->mip;
      int m = mip->m;
      int n = mip->n;
      int i, j, nrs, *num, ret = 0;
      double *L, *U, *l, *u;
      /* the current subproblem must exist */
      xassert(tree->curr != NULL);
      /* determine original row bounds */
      L = xcalloc(1+m, sizeof(double));
      U = xcalloc(1+m, sizeof(double));
      switch (mip->mip_stat)
      {  case GLP_UNDEF:
            L[0] = -DBL_MAX, U[0] = +DBL_MAX;
            break;
         case GLP_FEAS:
            switch (mip->dir)
            {  case GLP_MIN:
                  L[0] = -DBL_MAX, U[0] = mip->mip_obj - mip->c0;
                  break;
               case GLP_MAX:
                  L[0] = mip->mip_obj - mip->c0, U[0] = +DBL_MAX;
                  break;
               default:
                  xassert(mip != mip);
            }
            break;
         default:
            xassert(mip != mip);
      }
      for (i = 1; i <= m; i++)
      {  L[i] = glp_get_row_lb(mip, i);
         U[i] = glp_get_row_ub(mip, i);
      }
      /* determine original column bounds */
      l = xcalloc(1+n, sizeof(double));
      u = xcalloc(1+n, sizeof(double));
      for (j = 1; j <= n; j++)
      {  l[j] = glp_get_col_lb(mip, j);
         u[j] = glp_get_col_ub(mip, j);
      }
      /* build the initial list of rows to be analyzed */
      nrs = m + 1;
      num = xcalloc(1+nrs, sizeof(int));
      for (i = 1; i <= nrs; i++) num[i] = i - 1;
      /* perform basic preprocessing */
      if (basic_preprocessing(mip , L, U, l, u, nrs, num, max_pass))
      {  ret = 1;
         goto done;
      }
      /* set new actual (relaxed) row bounds */
      for (i = 1; i <= m; i++)
      {  /* consider only non-active rows to keep dual feasibility */
         if (glp_get_row_stat(mip, i) == GLP_BS)
         {  if (L[i] == -DBL_MAX && U[i] == +DBL_MAX)
               glp_set_row_bnds(mip, i, GLP_FR, 0.0, 0.0);
            else if (U[i] == +DBL_MAX)
               glp_set_row_bnds(mip, i, GLP_LO, L[i], 0.0);
            else if (L[i] == -DBL_MAX)
               glp_set_row_bnds(mip, i, GLP_UP, 0.0, U[i]);
         }
      }
      /* set new actual (tightened) column bounds */
      for (j = 1; j <= n; j++)
      {  int type;
         if (l[j] == -DBL_MAX && u[j] == +DBL_MAX)
            type = GLP_FR;
         else if (u[j] == +DBL_MAX)
            type = GLP_LO;
         else if (l[j] == -DBL_MAX)
            type = GLP_UP;
         else if (l[j] != u[j])
            type = GLP_DB;
         else
            type = GLP_FX;
         glp_set_col_bnds(mip, j, type, l[j], u[j]);
      }
done: /* free working arrays and return */
      xfree(L);
      xfree(U);
      xfree(l);
      xfree(u);
      xfree(num);
      return ret;
}

/* eof */