CoinUtils/src/CoinPresolveFixed.cpp

/* $Id: CoinPresolveFixed.cpp 2083 2019-01-06 19:38:09Z unxusr $ */
// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).

#include <stdio.h>
#include <math.h>

#include "CoinPresolveMatrix.hpp"
#include "CoinPresolveFixed.hpp"
#include "CoinHelperFunctions.hpp"
#include "CoinFinite.hpp"

#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
#include "CoinPresolvePsdebug.hpp"
#endif

/* Begin routines associated with remove_fixed_action */

const char *remove_fixed_action::name() const
{
  return ("remove_fixed_action");
}

/*
 * Original comment:
 *
 * invariant:  both reps are loosely packed.
 * coefficients of both reps remain consistent.
 *
 * Note that this concerns variables whose column bounds determine that
 * they are slack; this does NOT concern singleton row constraints that
 * determine that the relevant variable is slack.
 *
 * Invariant:  col and row rep are consistent
 */

/*
  This routine empties the columns for the list of fixed variables passed in
  (fcols, nfcols). As each coefficient a<ij> is set to 0, rlo<i> and rup<i>
  are adjusted accordingly. Note, however, that c<j> is not considered to be
  removed from the objective until column j is physically removed from the
  matrix (drop_empty_cols_action), so the correction to the objective is
  adjusted there.

  If a column solution is available, row activity (acts_) is adjusted.
  remove_fixed_action implicitly assumes that the value of the variable has
  already been forced within bounds. If this isn't true, the correction to
  acts_ will be wrong. See make_fixed_action if you need to force the value
  within bounds first.
*/
const remove_fixed_action *
remove_fixed_action::presolve(CoinPresolveMatrix *prob,
  int *fcols, int nfcols,
  const CoinPresolveAction *next)
{
  double *colels = prob->colels_;
  int *hrow = prob->hrow_;
  CoinBigIndex *mcstrt = prob->mcstrt_;
  int *hincol = prob->hincol_;

  double *rowels = prob->rowels_;
  int *hcol = prob->hcol_;
  CoinBigIndex *mrstrt = prob->mrstrt_;
  int *hinrow = prob->hinrow_;

  double *clo = prob->clo_;
  double *rlo = prob->rlo_;
  double *rup = prob->rup_;
  double *sol = prob->sol_;
  double *acts = prob->acts_;

  presolvehlink *clink = prob->clink_;
  presolvehlink *rlink = prob->rlink_;

  action *actions = new action[nfcols + 1];

#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
#if PRESOLVE_DEBUG > 0
  std::cout
    << "Entering remove_fixed_action::presolve; processing " << nfcols
    << " fixed columns." << std::endl;
#endif
  presolve_check_sol(prob);
  presolve_check_nbasic(prob);
#endif

  /*
  Scan columns to be removed and total up the number of coefficients.
*/
  int estsize = 0;
  int ckc;
  int n = 0;
  for (ckc = 0; ckc < nfcols; ckc++) {
    int j = fcols[ckc];
    if (!prob->colProhibited2(j)) {
      estsize += hincol[j];
      fcols[n++] = j;
    }
  }
  nfcols = n;
  // Allocate arrays to hold coefficients and associated row indices
  double *els_action = new double[estsize];
  int *rows_action = new int[estsize];
  int actsize = 0;
  // faster to do all deletes in row copy at once
  int nrows = prob->nrows_;
  CoinBigIndex *rstrt = new CoinBigIndex[nrows + 1];
  CoinZeroN(rstrt, nrows);

  /*
  Open a loop to excise each column a<j>. The first thing to do is load the
  action entry with the index j, the value of x<j>, and the number of
  entries in a<j>. After we walk the column and tweak the row-major
  representation, we'll simply claim this column is empty by setting
  hincol[j] = 0.
*/
  for (ckc = 0; ckc < nfcols; ckc++) {
    int j = fcols[ckc];
    double solj = clo[j];
    CoinBigIndex kcs = mcstrt[j];
    CoinBigIndex kce = kcs + hincol[j];
    CoinBigIndex k;

    {
      action &f = actions[ckc];
      f.col = j;
      f.sol = solj;
      f.start = actsize;
    }
    /*
  Now walk a<j>. For each row i with a coefficient a<ij> != 0:
    * save the coefficient and row index,
    * substitute the value of x<j>, adjusting the row bounds and lhs value
      accordingly, then
    * delete a<ij> from the row-major representation.
    * Finally: mark the row as changed and add it to the list of rows to be
	processed next. Then, for each remaining column in the row, put it on
	the list of columns to be processed.
*/
    for (k = kcs; k < kce; k++) {
      int row = hrow[k];
      double coeff = colels[k];

      els_action[actsize] = coeff;
      rstrt[row]++; // increase counts
      rows_action[actsize++] = row;

      // Avoid reducing finite infinity.
      if (-PRESOLVE_INF < rlo[row])
        rlo[row] -= solj * coeff;
      if (rup[row] < PRESOLVE_INF)
        rup[row] -= solj * coeff;
      if (sol) {
        acts[row] -= solj * coeff;
      }
#define TRY2
#ifndef TRY2
      presolve_delete_from_row(row, j, mrstrt, hinrow, hcol, rowels);
      if (hinrow[row] == 0) {
        PRESOLVE_REMOVE_LINK(rlink, row);
      }

      // mark unless already marked
      if (!prob->rowChanged(row)) {
        prob->addRow(row);
        CoinBigIndex krs = mrstrt[row];
        CoinBigIndex kre = krs + hinrow[row];
        for (CoinBigIndex k = krs; k < kre; k++) {
          int jcol = hcol[k];
          prob->addCol(jcol);
        }
      }
#endif
    }
    /*
  Remove the column's link from the linked list of columns, and declare
  it empty in the column-major representation. Link removal must execute
  even if the column is already of length 0 when it arrives.
*/
    PRESOLVE_REMOVE_LINK(clink, j);
    hincol[j] = 0;
  }
  /*
  Set the actual end of the coefficient and row index arrays.
*/
  actions[nfcols].start = actsize;
#if PRESOLVE_SUMMARY
  printf("NFIXED:  %d", nfcols);
  if (estsize - actsize > 0) {
    printf(", overalloc %d", estsize - actsize);
  }
  printf("\n");
#endif
  // Now get columns by row
  int *column = new int[actsize];
  CoinBigIndex nel = 0;
  int iRow;
  for (iRow = 0; iRow < nrows; iRow++) {
    CoinBigIndex n = rstrt[iRow];
    rstrt[iRow] = nel;
    nel += n;
  }
  rstrt[nrows] = nel;
  for (ckc = 0; ckc < nfcols; ckc++) {
    int kcs = actions[ckc].start;
    int j = actions[ckc].col;
    int kce;
    if (ckc < nfcols - 1)
      kce = actions[ckc + 1].start;
    else
      kce = actsize;
    for (int k = kcs; k < kce; k++) {
      int iRow = rows_action[k];
      CoinBigIndex put = rstrt[iRow];
      rstrt[iRow]++;
      column[put] = j;
    }
  }
  // Now do rows
  int ncols = prob->ncols_;
  char *mark = new char[ncols];
  memset(mark, 0, ncols);
  // rstrts are now one out i.e. rstrt[0] is end of row 0
  nel = 0;
#ifdef TRY2
  for (iRow = 0; iRow < nrows; iRow++) {
    CoinBigIndex k;
    for (k = nel; k < rstrt[iRow]; k++) {
      mark[column[k]] = 1;
    }
    presolve_delete_many_from_major(iRow, mark, mrstrt, hinrow, hcol, rowels);
#if PRESOLVE_DEBUG > 0
    for (k = nel; k < rstrt[iRow]; k++) {
      assert(mark[column[k]] == 0);
    }
#endif
    if (hinrow[iRow] == 0) {
      PRESOLVE_REMOVE_LINK(rlink, iRow);
    }
    // mark unless already marked
    if (!prob->rowChanged(iRow)) {
      prob->addRow(iRow);
      CoinBigIndex krs = mrstrt[iRow];
      CoinBigIndex kre = krs + hinrow[iRow];
      for (CoinBigIndex k = krs; k < kre; k++) {
        int jcol = hcol[k];
        prob->addCol(jcol);
      }
    }
    nel = rstrt[iRow];
  }
#endif
  delete[] mark;
  delete[] column;
  delete[] rstrt;

  /*
  Create the postsolve object, link it at the head of the list of postsolve
  objects, and return a pointer.
*/
  const remove_fixed_action *fixedActions = new remove_fixed_action(nfcols, actions, els_action, rows_action, next);

#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
  presolve_check_sol(prob);
#if PRESOLVE_DEBUG > 0
  std::cout << "Leaving remove_fixed_action::presolve." << std::endl;
#endif
#endif

  return (fixedActions);
}

remove_fixed_action::remove_fixed_action(int nactions,
  action *actions,
  double *els_action,
  int *rows_action,
  const CoinPresolveAction *next)
  : CoinPresolveAction(next)
  , colrows_(rows_action)
  , colels_(els_action)
  , nactions_(nactions)
  , actions_(actions)
{
}

remove_fixed_action::~remove_fixed_action()
{
  deleteAction(actions_, action *);
  delete[] colels_;
  delete[] colrows_;
}

/*
 * Say we determined that cup - clo <= ztolzb, so we fixed sol at clo.
 * This involved subtracting clo*coeff from ub/lb for each row the
 * variable occurred in.
 * Now when we put the variable back in, by construction the variable
 * is within tolerance, the non-slacks are unchanged, and the
 * distances of the affected slacks from their bounds should remain
 * unchanged (ignoring roundoff errors).
 * It may be that by adding the term back in, the affected constraints
 * now aren't as accurate due to round-off errors; this could happen
 * if only one summand and the slack in the original formulation were large
 * (and naturally had opposite signs), and the new term in the constraint
 * is about the size of the old slack, so the new slack becomes about 0.
 * It may be that there is catastrophic cancellation in the summation,
 * so it might not compute to 0.
 */
void remove_fixed_action::postsolve(CoinPostsolveMatrix *prob) const
{
  action *actions = actions_;
  const int nactions = nactions_;

  double *colels = prob->colels_;
  int *hrow = prob->hrow_;
  CoinBigIndex *mcstrt = prob->mcstrt_;
  int *hincol = prob->hincol_;
  CoinBigIndex *link = prob->link_;
  CoinBigIndex &free_list = prob->free_list_;

  double *clo = prob->clo_;
  double *cup = prob->cup_;
  double *rlo = prob->rlo_;
  double *rup = prob->rup_;

  double *sol = prob->sol_;
  double *dcost = prob->cost_;
  double *rcosts = prob->rcosts_;

  double *acts = prob->acts_;
  double *rowduals = prob->rowduals_;

  unsigned char *colstat = prob->colstat_;

  const double maxmin = prob->maxmin_;

#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
  char *cdone = prob->cdone_;
#if PRESOLVE_DEBUG > 0
  std::cout
    << "Entering remove_fixed_action::postsolve, repopulating " << nactions
    << " columns." << std::endl;
#endif
  presolve_check_threads(prob);
  presolve_check_free_list(prob);
  presolve_check_sol(prob, 2, 2, 2);
  presolve_check_nbasic(prob);
#endif

  double *els_action = colels_;
  int *rows_action = colrows_;
  int end = actions[nactions].start;

  /*
  At one point, it turned out that forcing_constraint_action was putting
  duplicates in the column list it passed to remove_fixed_action. This is now
  fixed, but ... it looks to me like we could be in trouble here if we
  reinstate a column multiple times. Hence the assert.
*/
  for (const action *f = &actions[nactions - 1]; actions <= f; f--) {
    int icol = f->col;
    const double thesol = f->sol;

#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
    if (cdone[icol] == FIXED_VARIABLE) {
      std::cout
        << "RFA::postsolve: column " << icol << " already unfixed!"
        << std::endl;
      assert(cdone[icol] != FIXED_VARIABLE);
    }
    cdone[icol] = FIXED_VARIABLE;
#endif

    sol[icol] = thesol;
    clo[icol] = thesol;
    cup[icol] = thesol;

    CoinBigIndex cs = NO_LINK;
    int start = f->start;
    double dj = maxmin * dcost[icol];

    for (int i = start; i < end; ++i) {
      int row = rows_action[i];
      double coeff = els_action[i];

      // pop free_list
      CoinBigIndex k = free_list;
      assert(k >= 0 && k < prob->bulk0_);
      free_list = link[free_list];
      // restore
      hrow[k] = row;
      colels[k] = coeff;
      link[k] = cs;
      cs = k;

      if (-PRESOLVE_INF < rlo[row])
        rlo[row] += coeff * thesol;
      if (rup[row] < PRESOLVE_INF)
        rup[row] += coeff * thesol;
      acts[row] += coeff * thesol;

      dj -= rowduals[row] * coeff;
    }

#if PRESOLVE_CONSISTENCY > 0
    presolve_check_free_list(prob);
#endif

    mcstrt[icol] = cs;

    rcosts[icol] = dj;
    hincol[icol] = end - start;
    end = start;

    /* Original comment:
     * the bounds in the reduced problem were tightened.
     * that means that this variable may not have been basic
     * because it didn't have to be,
     * but now it may have to.
     * no - the bounds aren't changed by this operation
     */
    /*
  We've reintroduced the variable, but it's still fixed (equal bounds).
  Pick the nonbasic status that agrees with the reduced cost. Later, if
  postsolve unfixes the variable, we'll need to confirm that this status is
  still viable. We live in a minimisation world here.
*/
    if (colstat) {
      if (dj < 0)
        prob->setColumnStatus(icol, CoinPrePostsolveMatrix::atUpperBound);
      else
        prob->setColumnStatus(icol, CoinPrePostsolveMatrix::atLowerBound);
    }
  }

#if PRESOLVE_CONSISTENCY > 0 || PRESOLVE_DEBUG > 0
  presolve_check_threads(prob);
  presolve_check_sol(prob, 2, 2, 2);
  presolve_check_nbasic(prob);
#if PRESOLVE_DEBUG > 0
  std::cout << "Leaving remove_fixed_action::postsolve." << std::endl;
#endif
#endif

  return;
}

/*
  Scan the problem for variables that are already fixed, and remove them.
  There's an implicit assumption that the value of the variable is already
  within bounds. If you want to protect against this possibility, you want to
  use make_fixed.
*/
const CoinPresolveAction *remove_fixed(CoinPresolveMatrix *prob,
  const CoinPresolveAction *next)
{
  int ncols = prob->ncols_;
  int *fcols = new int[ncols];
  int nfcols = 0;

  int *hincol = prob->hincol_;

  double *clo = prob->clo_;
  double *cup = prob->cup_;

  for (int i = 0; i < ncols; i++)
    if (hincol[i] > 0 && clo[i] == cup[i] && !prob->colProhibited2(i))
      fcols[nfcols++] = i;

  if (nfcols > 0) {
    next = remove_fixed_action::presolve(prob, fcols, nfcols, next);
  }
  delete[] fcols;
  return (next);
}

/* End routines associated with remove_fixed_action */

/* Begin routines associated with make_fixed_action */

const char *make_fixed_action::name() const
{
  return ("make_fixed_action");
}

/*
  This routine does the actual job of fixing one or more variables. The set
  of indices to be fixed is specified by nfcols and fcols. fix_to_lower
  specifies the bound where the variable(s) should be fixed. The other bound
  is preserved as part of the action and the bounds are set equal. Note that
  you don't get to specify the bound on a per-variable basis.

  If a primal solution is available, make_fixed_action will adjust the the
  row activity to compensate for forcing the variable within bounds. If the
  bounds are already equal, and the variable is within bounds, you should
  consider remove_fixed_action.
*/
const CoinPresolveAction *
make_fixed_action::presolve(CoinPresolveMatrix *prob,
  int *fcols, int nfcols,
  bool fix_to_lower,
  const CoinPresolveAction *next)

{
  double *clo = prob->clo_;
  double *cup = prob->cup_;
  double *csol = prob->sol_;

  double *colels = prob->colels_;
  int *hrow = prob->hrow_;
  CoinBigIndex *mcstrt = prob->mcstrt_;
  int *hincol = prob->hincol_;

  double *acts = prob->acts_;

#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
#if PRESOLVE_DEBUG > 0
  std::cout
    << "Entering make_fixed_action::presolve, fixed = " << nfcols << "."
    << std::endl;
#endif
  presolve_check_sol(prob);
  presolve_check_nbasic(prob);
#endif

  /*
  Shouldn't happen, but ...
*/
  if (nfcols <= 0) {
#if PRESOLVE_DEBUG > 0
    std::cout
      << "make_fixed_action::presolve: useless call, " << nfcols
      << " to fix." << std::endl;
#endif
    return (next);
  }

  action *actions = new action[nfcols];

  /*
  Scan the set of indices specifying variables to be fixed. For each variable,
  stash the unused bound in the action and set the bounds equal. If the client
  has passed in a primal solution, update it if the value of the variable
  changes.
*/
  for (int ckc = 0; ckc < nfcols; ckc++) {
    int j = fcols[ckc];
    if (prob->colProhibited2(j))
      abort();
    double movement = 0;

    action &f = actions[ckc];

    f.col = j;
    if (fix_to_lower) {
      f.bound = cup[j];
      cup[j] = clo[j];
      if (csol) {
        movement = clo[j] - csol[j];
        csol[j] = clo[j];
      }
    } else {
      f.bound = clo[j];
      clo[j] = cup[j];
      if (csol) {
        movement = cup[j] - csol[j];
        csol[j] = cup[j];
      }
    }
    if (movement) {
      CoinBigIndex k;
      for (k = mcstrt[j]; k < mcstrt[j] + hincol[j]; k++) {
        int row = hrow[k];
        acts[row] += movement * colels[k];
      }
    }
  }
  /*
  Original comment:
  This is unusual in that the make_fixed_action transform contains within it
  a remove_fixed_action transform. Bad idea?

  Explanatory comment:
  Now that we've adjusted the bounds, time to create the postsolve action
  that will restore the original bounds. But wait! We're not done. By calling
  remove_fixed_action::presolve, we will (virtually) remove these variables
  from the model by substituting for the variable where it occurs and emptying
  the column. Cache the postsolve transform that will repopulate the column
  inside the postsolve transform for fixing the bounds.
*/
  if (nfcols > 0) {
    next = new make_fixed_action(nfcols, actions, fix_to_lower,
      remove_fixed_action::presolve(prob, fcols, nfcols, 0),
      next);
  }

#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
  presolve_check_sol(prob);
  presolve_check_nbasic(prob);
#if PRESOLVE_DEBUG > 0
  std::cout << "Leaving make_fixed_action::presolve." << std::endl;
#endif
#endif

  return (next);
}

/*
  Recall that in presolve, make_fixed_action forced a bound to fix a variable,
  then called remove_fixed_action to empty the column. removed_fixed_action
  left a postsolve object hanging off faction_, and our first act here is to
  call r_f_a::postsolve to repopulate the columns. The m_f_a postsolve activity
  consists of relaxing one of the bounds and making sure that the status is
  still viable (we can potentially eliminate the bound here).
*/
void make_fixed_action::postsolve(CoinPostsolveMatrix *prob) const
{
  const action *const actions = actions_;
  const int nactions = nactions_;
  const bool fix_to_lower = fix_to_lower_;

  double *clo = prob->clo_;
  double *cup = prob->cup_;
  double *sol = prob->sol_;
  unsigned char *colstat = prob->colstat_;

#if PRESOLVE_CONSISTENCY > 0 || PRESOLVE_DEBUG > 0
#if PRESOLVE_DEBUG > 0
  std::cout << "Entering make_fixed_action::postsolve." << std::endl;
#endif
  presolve_check_threads(prob);
  presolve_check_sol(prob, 2, 2, 2);
  presolve_check_nbasic(prob);
#endif

  /*
  Repopulate the columns.
*/
  assert(nactions == faction_->nactions_);
  faction_->postsolve(prob);
  /*
  Walk the actions: restore each bound and check that the status is still
  appropriate. Given that we're unfixing a fixed variable, it's safe to assume
  that the unaffected bound is finite.
*/
  for (int cnt = nactions - 1; cnt >= 0; cnt--) {
    const action *f = &actions[cnt];
    int icol = f->col;
    double xj = sol[icol];

    assert(faction_->actions_[cnt].col == icol);

    if (fix_to_lower) {
      double ub = f->bound;
      cup[icol] = ub;
      if (colstat) {
        if (ub >= PRESOLVE_INF || xj != ub) {
          prob->setColumnStatus(icol,
            CoinPrePostsolveMatrix::atLowerBound);
        }
      }
    } else {
      double lb = f->bound;
      clo[icol] = lb;
      if (colstat) {
        if (lb <= -PRESOLVE_INF || xj != lb) {
          prob->setColumnStatus(icol,
            CoinPrePostsolveMatrix::atUpperBound);
        }
      }
    }
  }

#if PRESOLVE_CONSISTENCY > 0 || PRESOLVE_DEBUG > 0
  presolve_check_threads(prob);
  presolve_check_sol(prob, 2, 2, 2);
  presolve_check_nbasic(prob);
  std::cout << "Leaving make_fixed_action::postsolve." << std::endl;
#endif
  return;
}

/*
  Scan the columns and collect indices of columns that have upper and lower
  bounds within the zero tolerance of one another. Hand this list to
  make_fixed_action::presolve() to do the heavy lifting.

  make_fixed_action will compensate for variables which are infeasible, forcing
  them to feasibility and correcting the row activity, before invoking
  remove_fixed_action to remove the variable from the problem. If you're
  confident of feasibility, consider remove_fixed.
*/
const CoinPresolveAction *make_fixed(CoinPresolveMatrix *prob,
  const CoinPresolveAction *next)
{
#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
#if PRESOLVE_DEBUG > 0
  std::cout
    << "Entering make_fixed, checking " << prob->ncols_ << " columns."
    << std::endl;
#endif
  presolve_check_sol(prob);
  presolve_check_nbasic(prob);
#endif

  int ncols = prob->ncols_;
  int *fcols = prob->usefulColumnInt_;
  int nfcols = 0;

  int *hincol = prob->hincol_;

  double *clo = prob->clo_;
  double *cup = prob->cup_;

  for (int i = 0; i < ncols; i++) {
    if (hincol[i] > 0 && fabs(cup[i] - clo[i]) < ZTOLDP && !prob->colProhibited2(i)) {
      fcols[nfcols++] = i;
    }
  }

  /*
  Call m_f_a::presolve to do the heavy lifting. This will create a new
  CoinPresolveAction, which will become the head of the list of
  CoinPresolveAction's currently pointed to by next.

  No point in going through the effort of a call if there are no fixed
  variables.
*/
  if (nfcols > 0)
    next = make_fixed_action::presolve(prob, fcols, nfcols, true, next);

#if PRESOLVE_DEBUG > 0 || PRESOLVE_CONSISTENCY > 0
  presolve_check_sol(prob);
  presolve_check_nbasic(prob);
#if PRESOLVE_DEBUG > 0
  std::cout
    << "Leaving make_fixed, fixed " << nfcols << " columns." << std::endl;
#endif
#endif

  return (next);
}

/*
  Transfer the cost coefficient of a column singleton in an equality to the
  cost coefficients of the remaining variables. Suppose x<s> is the singleton
  and x<t> is some other variable. For movement delta<t>, there must be
  compensating change delta<s> = -(a<it>/a<is>)delta<t>. Substituting in the
  objective, c<s>delta<s> + c<t>delta<t> becomes
    c<s>(-a<it>/a<is>)delta<t> + c<t>delta<t>
    (c<t> - c<s>(a<it>/a<is>))delta<t>
  This is transform (A) below.
*/
void transferCosts(CoinPresolveMatrix *prob)
{
  double *colels = prob->colels_;
  int *hrow = prob->hrow_;
  CoinBigIndex *mcstrt = prob->mcstrt_;
  int *hincol = prob->hincol_;

  double *rowels = prob->rowels_;
  int *hcol = prob->hcol_;
  CoinBigIndex *mrstrt = prob->mrstrt_;
  int *hinrow = prob->hinrow_;

  double *rlo = prob->rlo_;
  double *rup = prob->rup_;
  double *clo = prob->clo_;
  double *cup = prob->cup_;
  int ncols = prob->ncols_;
  double *cost = prob->cost_;
  unsigned char *integerType = prob->integerType_;
  double bias = prob->dobias_;

#if PRESOLVE_DEBUG > 0
  std::cout << "Entering transferCosts." << std::endl;
  presolve_check_sol(prob);
  presolve_check_nbasic(prob);
#endif

  int numberIntegers = 0;
  for (int icol = 0; icol < ncols; icol++) {
    if (integerType[icol])
      numberIntegers++;
  }
  /*
  For unfixed column singletons in equalities, calculate and install transform
  (A) described in the comments at the head of the method.
*/
  int nchanged = 0;
  for (int js = 0; js < ncols; js++) {
    if (cost[js] && hincol[js] == 1 && cup[js] > clo[js]) {
      const CoinBigIndex &jsstrt = mcstrt[js];
      const int &i = hrow[jsstrt];
      if (rlo[i] == rup[i]) {
        const double ratio = cost[js] / colels[jsstrt];
        bias += rlo[i] * ratio;
        const CoinBigIndex &istrt = mrstrt[i];
        const CoinBigIndex iend = istrt + hinrow[i];
        for (CoinBigIndex jj = istrt; jj < iend; jj++) {
          int j = hcol[jj];
          double aij = rowels[jj];
          cost[j] -= ratio * aij;
        }
        cost[js] = 0.0;
        nchanged++;
      }
    }
  }
#if PRESOLVE_DEBUG > 0
  if (nchanged)
    std::cout
      << "  transferred costs for " << nchanged << " singleton columns."
      << std::endl;

  int nPasses = 0;
#endif
  /*
  We don't really need a singleton column to do this trick, just an equality.
  But if the column's not a singleton, it's only worth doing if we can move
  costs onto integer variables that start with costs of zero. Try and find some
  unfixed variable with a nonzero cost, that's involved in an equality where
  there are integer variables with costs of zero. If there's a net gain in the
  number of integer variables with costs (nThen > nNow), do the transform.
  One per column, please.
*/
  if (numberIntegers) {
    int changed = -1;
    while (changed) {
      changed = 0;
      for (int js = 0; js < ncols; js++) {
        if (cost[js] && cup[js] > clo[js]) {
          const CoinBigIndex &jsstrt = mcstrt[js];
          const CoinBigIndex jsend = jsstrt + hincol[js];
          for (CoinBigIndex ii = jsstrt; ii < jsend; ii++) {
            const int &i = hrow[ii];
            if (rlo[i] == rup[i]) {
              int nNow = ((integerType[js]) ? 1 : 0);
              int nThen = 0;
              const CoinBigIndex &istrt = mrstrt[i];
              const CoinBigIndex iend = istrt + hinrow[i];
              for (CoinBigIndex jj = istrt; jj < iend; jj++) {
                int j = hcol[jj];
                if (!cost[j] && integerType[j])
                  nThen++;
              }
              if (nThen > nNow) {
                const double ratio = cost[js] / colels[jsstrt];
                bias += rlo[i] * ratio;
                for (CoinBigIndex jj = istrt; jj < iend; jj++) {
                  int j = hcol[jj];
                  double aij = rowels[jj];
                  cost[j] -= ratio * aij;
                }
                cost[js] = 0.0;
                changed++;
                break;
              }
            }
          }
        }
      }
      if (changed) {
        nchanged += changed;
#if PRESOLVE_DEBUG > 0
        std::cout
          << "    pass " << nPasses++ << " transferred costs to "
          << changed << " integer variables." << std::endl;
#endif
      }
    }
  }
#if PRESOLVE_DEBUG > 0
  if (bias != prob->dobias_)
    std::cout << "  new bias " << bias << "." << std::endl;
#endif
  prob->dobias_ = bias;

#if PRESOLVE_DEBUG > 0
  std::cout << "Leaving transferCosts." << std::endl;
  presolve_check_sol(prob);
  presolve_check_nbasic(prob);
#endif
}

/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
*/