glpipp02.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

         /* create constraint coefficients for z[k] */
         for (aij = col->ptr; aij != NULL; aij = aij->c_next)
            ipp_add_aij(ipp, aij->row, bin, aij->val * lfe->val);
         /* create objective coefficient for z[k] */
         bin->c = col->c * lfe->val;
         /* include z[k] in additional constraint (3), if necessary */
         if (u <= two_t - 2)
            ipp_add_aij(ipp, row, bin, lfe->val);
      }
      /* remove the original column x[q] from the problem */
      ipp_remove_col(ipp, col);
      return t;
}

void ipp_nonbin_col_r(IPP *ipp, void *_info)
{     /* recover non-binary column */
      struct nonbin_col *info = _info;
      IPPLFE *lfe;
      double temp;
      xassert(1 <= info->q && info->q <= ipp->ncols);
      xassert(ipp->col_stat[info->q] == 0);
      temp = 0.0;
      for (lfe = info->ptr; lfe != NULL; lfe = lfe->next)
      {  xassert(1 <= lfe->ref && lfe->ref <= ipp->ncols);
         xassert(ipp->col_stat[lfe->ref] == 1);
         temp += lfe->val * ipp->col_mipx[lfe->ref];
      }
      ipp->col_stat[info->q] = 1;
      ipp->col_mipx[info->q] = temp;
      return;
}

/*----------------------------------------------------------------------
-- COEFFICIENT REDUCTION
--
-- Let an inequality constraint is the following:
--
--    sum a[j] * x[j] + a[k] * x[k] <= b,                            (1)
--   j!=k
--
-- where x[k] is a binary variable. Let also be known that:
--
--    sum a[j] * x[j] <= u,                                          (2)
--   j!=k
--
-- where u is an implied upper bound of the row.
--
-- Case 1. If a[k] > 0 and b - a[k] < u < b, a[k] can be replaced by
-- (ak + u - b) and b can be replaced by u.
--
-- Case 2. If a[k] < 0 and b < u < b - a[k], a[k] can be replaced by
-- (b - u) and b remains unchanged.
--
-- In both cases magnitude of a[k] is decreased while the sign of a[k]
-- remains unchanged.
--
-- If a[k] has been changed, the corresponding column x[k] is placed in
-- the active queue for further processing. */

static void reduce_coef(IPP *ipp, IPPROW *row)
{     IPPCOL *col, *c_max;
      IPPAIJ *aij;
      double f_max, ff_max, eps;
      /* the row must be '<=' constraint */
      xassert(row->lb == -DBL_MAX && row->ub != +DBL_MAX);
      /* compute implied upper bound of the row */
      c_max = NULL, f_max = 0.0;
      for (aij = row->ptr; aij != NULL; aij = aij->r_next)
      {  col = aij->col;
         if (aij->val > 0.0 && col->ub == +DBL_MAX ||
             aij->val < 0.0 && col->lb == -DBL_MAX)
         {  if (c_max == NULL)
               c_max = col;
            else
            {  f_max = +DBL_MAX;
               break;
            }
         }
         else
            f_max += aij->val * (aij->val > 0.0 ? col->ub : col->lb);
      }
      /* process all columns in the row */
      for (aij = row->ptr; aij != NULL; aij = aij->r_next)
      {  col = aij->col;
         /* skip non-binary column */
         if (!col->i_flag) continue;
         if (!(col->lb == 0.0 && col->ub == 1.0)) continue;
         /* compute implied upper bound of the row minus a[k] * a[k] */
         if (f_max == +DBL_MAX)
            ff_max = +DBL_MAX;
         else if (c_max == NULL)
            ff_max = f_max -
               aij->val * (aij->val > 0.0 ? col->ub : col->lb);
         else if (c_max == col)
            ff_max = f_max;
         else
            ff_max = +DBL_MAX;
         /* try to reduce constraint coefficient a[k] */
         if (ff_max == +DBL_MAX) continue;
         eps = 1e-5 * (1.0 + fabs(ff_max));
         if (aij->val > 0.0)
         {  /* case 1 */
            if (row->ub - aij->val + eps <= ff_max &&
                ff_max <= row->ub - eps)
            {  aij->val += ff_max - row->ub;
               row->ub = ff_max;
               ipp_enque_col(ipp, col);
            }
         }
         else
         {  /* case 2 */
            if (row->ub + eps <= ff_max &&
               ff_max <= row->ub - aij->val - eps)
            {  aij->val = row->ub - ff_max;
               row->ub = row->ub;
               ipp_enque_col(ipp, col);
            }
         }
      }
      return;
}

/*----------------------------------------------------------------------
-- ipp_reduce_coef - reduce constraint coefficients.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_reduce_coef(IPP *ipp);
--
-- DESCRIPTION
--
-- The routine ipp_reduce_coef tries to reduce constraint coefficients
-- for inequality constraints '<='. */

void ipp_reduce_coef(IPP *ipp)
{     IPPROW *row;
      IPPCOL *col;
      IPPAIJ *aij;
      int pass = 0, total = 0, count;
      /* activate all rows which are '<=' inequalities */
      for (row = ipp->row_ptr; row != NULL; row = row->next)
      {  if (row->lb == -DBL_MAX && row->ub != +DBL_MAX)
            ipp_enque_row(ipp, row);
      }
      /* deactivate all columns */
      for (col = ipp->col_ptr; col != NULL; col = col->next)
         ipp_deque_col(ipp, col);
loop: /* start a next pass for all active rows */
      pass++;
      while (ipp->row_que != NULL)
      {  /* select an active row */
         row = ipp->row_que;
         /* and remove it from the queue */
         ipp_deque_row(ipp, row);
         /* try to reduce constraint coefficients */
         reduce_coef(ipp, row);
      }
      /* now all rows are inactive while all columns whose coefficients
         were reduced are active */
      count = 0;
      while (ipp->col_que != NULL)
      {  count++;
         /* select an active column */
         col = ipp->col_que;
         /* and remove it from the queue */
         ipp_deque_col(ipp, col);
         /* activate corresponding rows for next pass */
         for (aij = col->ptr; aij != NULL; aij = aij->c_next)
         {  row = aij->row;
            if (row->lb == -DBL_MAX && row->ub != +DBL_MAX)
               ipp_enque_row(ipp, row);
         }
      }
      total += count;
      if (count > 0) goto loop;
      xprintf("ipp_reduce_coef: %d pass(es) made, %d coefficient(s) red"
         "uced\n", pass, total);
      return;
}

/*----------------------------------------------------------------------
-- ipp_binarize - replace general integer variables by binary ones.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_binarize(IPP *ipp);
--
-- DESCRIPTION
--
-- The routine ipp_binarize replaces all integer variables by binary
-- variables as explained in comments to the routine ipp_nonbin_col.
--
-- It is highly recommended to previously performs bounds reduction in
-- order to minimize the number of binary variables required. */

void ipp_binarize(IPP *ipp)
{     IPPCOL *col;
      int ncols, nbins;
      /* activate all columns (variables) to be replaced */
      for (col = ipp->col_ptr; col != NULL; col = col->next)
      {  ipp_deque_col(ipp, col);
         if (!col->i_flag) continue;
         if (col->lb == col->ub) continue;
         if (col->lb == 0.0 && col->ub == 1.0) continue;
         xassert(col->lb != -DBL_MAX);
         xassert(col->ub != +DBL_MAX);
         if (col->lb == -DBL_MAX || col->ub == +DBL_MAX ||
             col->ub - col->lb > 32767.0)
         {  xprintf("WARNING: BINARIZATION IMPOSSIBLE\n");
            goto done;
         }
         ipp_enque_col(ipp, col);
      }
      /* perform replacement */
      ncols = nbins = 0;
      while (ipp->col_que != NULL)
      {  /* select an active column to be replaced */
         ncols++;
         col = ipp->col_que;
         /* and remove it from the queue */
         ipp_deque_col(ipp, col);
         /* make the lower bound to be zero, if necessary */
         if (col->lb != 0.0) ipp_shift_col(ipp, col);
         /* if the column became binary, drop it */
         if (col->ub == 1.0) continue;
         /* replace the non-binary column */
         nbins += ipp_nonbin_col(ipp, col);
      }
      if (ncols == 0)
         xprintf(
            "ipp_binarize: no general integer variables detected\n");
      else
         xprintf("ipp_binarize: %d integer variable(s) replaced by %d b"
            "inary ones\n", ncols, nbins);
done: return;
}

/*----------------------------------------------------------------------
-- ipp_reduction - perform coefficient reduction.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_reduction(IPP *ipp);
--
-- DESCRIPTION
--
-- The routine ipp_reduction tries to reduce constraint coefficients
-- for inequality constraints having binary columns (variables).
--
-- It is highly recommended to previously performs bounds reduction in
-- order to made coefficient reduction much more efficient. */

void ipp_reduction(IPP *ipp)
{     IPPROW *row, *dup;
      IPPCOL *col;
      IPPAIJ *aij;
      int nrows;
      /* activate all double-bounded rows to be replaced by ordinary
         inequality rows */
      for (row = ipp->row_ptr; row != NULL; row = row->next)
      {  ipp_deque_row(ipp, row);
         if (row->lb == -DBL_MAX) continue;
         if (row->ub == +DBL_MAX) continue;
         if (row->lb == row->ub) continue;
         /* skip rows having no binary variables */
         for (aij = row->ptr; aij != NULL; aij = aij->r_next)
         {  col = aij->col;
            if (!(col->i_flag && col->lb == 0.0 && col->ub == 1.0))
               break;
         }
         if (aij != NULL) continue;
         ipp_enque_row(ipp, row);
      }
      /* perform replacement */
      nrows = 0;
      while (ipp->row_que != NULL)
      {  /* select an active row to be replaced */
         nrows++;
         row = ipp->row_que;
         /* and remove it from the queue */
         ipp_deque_row(ipp, row);
         /* duplicate the row */
         dup = ipp_add_row(ipp, -DBL_MAX, row->ub);
         row->ub = +DBL_MAX;
         for (aij = row->ptr; aij != NULL; aij = aij->r_next)
            ipp_add_aij(ipp, dup, aij->col, aij->val);
      }
      if (nrows > 0)
         xprintf("ipp_reduction: %d row(s) splitted into single inequal"
            "ities\n", nrows);
      /* replace all '>=' inequalities by '<=' ones */
      for (row = ipp->row_ptr; row != NULL; row = row->next)
      {  if (row->lb != -DBL_MAX && row->ub == +DBL_MAX)
         {  row->ub = - row->lb;
            row->lb = - DBL_MAX;
            for (aij = row->ptr; aij != NULL; aij = aij->r_next)
               aij->val = - aij->val;
         }
      }
      /* call basic reduction routine */
      ipp_reduce_coef(ipp);
      return;
}

/*----------------------------------------------------------------------
-- ipp_postsolve - MIP postsolve processing.
--
-- SYNOPSIS
--
-- #include "glpipp.h"
-- void ipp_postsolve(IPP *ipp);
--
-- DESCRIPTION
--
-- The routine ipp_postsolve performs a postsolve processing to recover
-- a solution of the original problem. It is assumed that a solution of
-- the resultant problem is loaded into the presolver workspace. */

void ipp_postsolve(IPP *ipp)
{     IPPTQE *tqe;
      for (tqe = ipp->tqe_list; tqe != NULL; tqe = tqe->next)
      {  switch (tqe->type)
         {  case IPP_FIXED_COL:
               ipp_fixed_col_r(ipp, tqe->info);
               break;
            case IPP_SHIFT_COL:
               ipp_shift_col_r(ipp, tqe->info);
               break;
            case IPP_NONBIN_COL:
               ipp_nonbin_col_r(ipp, tqe->info);
               break;
            default:
               xassert(tqe != tqe);
         }
      }
      return;
}

/* eof */