FixPointGenCuts.cpp

Go to the documentation of this file.

/* $Id: FixPointGenCuts.cpp 1272 2019-02-23 17:27:43Z stefan $
 *
 * Name:    FixPointGenCuts.cpp
 * Author:  Pietro Belotti
 * Purpose: Fix point bound tightener -- separator
 *
 * (C) Pietro Belotti, 2010.
 * This file is licensed under the Eclipse Public License (EPL)
 */

#include "CoinHelperFunctions.hpp"
#include "OsiClpSolverInterface.hpp"
#include "OsiCuts.hpp"
#include "CoinTime.hpp"

#include "CouenneFixPoint.hpp"

#include "CouenneProblem.hpp"
#include "CouennePrecisions.hpp"
#include "CouenneExprVar.hpp"
#include "CouenneInfeasCut.hpp"

using namespace Ipopt;
using namespace Couenne;


void CouenneFixPoint::generateCuts (const OsiSolverInterface &si,
                                    OsiCuts &cs,
                                    const CglTreeInfo treeInfo)
#if CGL_VERSION_MAJOR == 0 && CGL_VERSION_MINOR <= 57
  const
#endif
  {


  if (firstCall_) 
    firstCall_ = false;
  //else
    //if (!(problem_ -> fbbtReachedIterLimit ()))
      //return;

  if (levelStop_ == 0) // turned off; should never happen, can actually assert != 0
    return;

  if (isWiped (cs))
    return;

  // do it at most once per node

  if (treeInfo.inTree && 
      treeInfo.level > 0 &&
      treeInfo.pass > 1)
    return;

  // Avoid if excessive BB tree depth. Run run it at every node until
  // depth -levelStop_, then every other level until -2 levelStop_,
  // then stop.
  if ((levelStop_ < 0) &&                  // If this cut generator has negative frequency option
      ((treeInfo.level > -2*levelStop_) || // AND either we are at a low depth
       ((treeInfo.level > -levelStop_) &&  //     OR the depth is low enough
        (treeInfo.level & 1))))            //        AND it's even,
    return;                                // skip

  double startTime = CoinCpuTime ();

  int nInitTightened = nTightened_;

  if (treeInfo.inTree && 
      treeInfo.level <= 0) {

    problem_ -> Jnlst () -> Printf (J_ERROR, J_COUENNE, "Fixed Point FBBT: "); 
    fflush (stdout);
  }

  //++nRuns_;

  double now = CoinCpuTime ();

  problem_ -> domain () -> push (&si, &cs);

  double 
    *oldLB = CoinCopyOfArray (problem_ -> Lb (), problem_ -> nVars ()),
    *oldUB = CoinCopyOfArray (problem_ -> Ub (), problem_ -> nVars ());

  perfIndicator_. setOldBounds (problem_ -> Lb (), problem_ -> Ub ());


  OsiSolverInterface *fplp = NULL;

  if (true) { // placeholder for later selection of LP solver among
              // those available

    fplp = new OsiClpSolverInterface;
  }



  const CoinPackedMatrix *A = si. getMatrixByRow ();

  const int
    n     = si.  getNumCols (),
    m     = si.  getNumRows (),
    nCuts = cs.sizeRowCuts  (),
    *ind  = A -> getIndices ();

  const double
    *lb  = problem_ -> Lb (), //si.  getColLower (),
    *ub  = problem_ -> Ub (), //si.  getColUpper (),
    *rlb = si.  getRowLower (),
    *rub = si.  getRowUpper (),
    *coe = A -> getElements ();

  if (problem_ -> Jnlst () -> ProduceOutput (J_ERROR, J_BOUNDTIGHTENING))
    for (int i=0; i<n; i++) 
      printf ("----------- x_%d in [%g,%g]\n", i, lb [i], ub [i]);

  // turn off logging
  fplp -> messageHandler () -> setLogLevel (0);

  // add lvars and uvars to the new problem
  for (int i=0; i<n; i++) {
    bool isActive = problem_ -> Var (i) -> Multiplicity () > 0;
    fplp -> addCol (0, NULL, NULL, lb [i], ub [i], isActive ? -1. : 0.); // xL_i
  }

  for (int i=0; i<n; i++) {
    bool isActive = problem_ -> Var (i) -> Multiplicity () > 0;
    fplp -> addCol (0, NULL, NULL, lb [i], ub [i], isActive ? +1. : 0.); // xU_i
  }

  if (extendedModel_) {

    for (int j=0; j<m; j++) fplp -> addCol (0, NULL, NULL, rlb [j],       COIN_DBL_MAX, 0.); // bL_j
    for (int j=0; j<m; j++) fplp -> addCol (0, NULL, NULL, -COIN_DBL_MAX, rub [j],      0.); // bU_j
  }

  // Scan each row of the matrix 
  
  for (int j=0; j<m; j++) { // for each row

    const int nEl = A->getVectorLast(j) - A->getVectorFirst(j), // A -> getVectorSize (j); // # elements in each row
      *rind = &ind [A->getVectorFirst (j)];
    const double *rcoe = &coe [A->getVectorFirst (j)];

    if (!nEl)
      continue;

    if (problem_ -> Jnlst () -> ProduceOutput (J_ERROR, J_BOUNDTIGHTENING)) {

      printf ("row %4d, %4d elements: ", j, nEl);

      for (int i=0; i<nEl; i++) {
        printf ("%+g x%d ", rcoe [i], rind [i]);
        fflush (stdout);
      }

      printf ("\n");
    }

    // create cuts for the xL and xU elements //////////////////////

    if (extendedModel_ || rlb [j] > -COUENNE_INFINITY) 
      for (int i = A->getVectorFirst(j); i < A->getVectorLast(j); i++) 
        createRow (-1, ind [i], n, fplp, rind, rcoe, rlb [j], nEl, extendedModel_, j, m + nCuts); // downward constraints -- on x_i

    if (extendedModel_ || rub [j] <  COUENNE_INFINITY) 
      for (int i = A->getVectorFirst(j); i < A->getVectorLast(j); i++) 
        createRow (+1, ind [i], n, fplp, rind, rcoe, rub [j], nEl, extendedModel_, j, m + nCuts); // downward constraints -- on x_i

    // create (at most 2) cuts for the bL and bU elements //////////////////////

    if (extendedModel_) {
      createRow (-1, 2*n     + j, n, fplp, rind, rcoe, rlb [j], nEl, extendedModel_, j, m + nCuts); // upward constraints -- on bL_i
      createRow (+1, 2*n + m + j, n, fplp, rind, rcoe, rub [j], nEl, extendedModel_, j, m + nCuts); // upward constraints -- on bU_i
    }
  }

  // similarly, scan previous cuts in cs //////////////////////////////////////

  for (int j = 0, jj = nCuts; jj--; j++) {

    // create cuts for the xL and xU elements //////////////////////

    OsiRowCut *cut = cs.rowCutPtr (j);

    const CoinPackedVector &row = cut -> row ();

    const int 
      nEl = row.getNumElements (),
      *ind = row.getIndices ();

    const double *coe = row.getElements ();

    if (extendedModel_) {
      fplp -> addCol (0, NULL, NULL, cut -> lb (),       COIN_DBL_MAX, 0.); // bL_j
      fplp -> addCol (0, NULL, NULL, -COIN_DBL_MAX, cut -> ub (),      0.); // bU_j
    }

    if (extendedModel_ || cut -> lb () > -COUENNE_INFINITY) 
      for (int i=0; i<nEl; i++) 
        createRow (-1, ind [i], n, fplp, ind, coe, cut -> lb (), nEl, extendedModel_, m + j, m + nCuts); // downward constraints -- on x_i

    if (extendedModel_ || cut -> ub () <  COUENNE_INFINITY) 
      for (int i=0; i<nEl; i++)
        createRow (+1, ind [i], n, fplp, ind, coe, cut -> ub (), nEl, extendedModel_, m + j, m + nCuts); // downward constraints -- on x_i

    // create (at most 2) cuts for the bL and bU elements

    if (extendedModel_) {
      createRow (-1, 2*n             + j, n, fplp, ind, coe, cut -> lb (), nEl, extendedModel_, m + j, m + nCuts); // upward constraints -- on bL_i
      createRow (+1, 2*n + m + nCuts + j, n, fplp, ind, coe, cut -> ub (), nEl, extendedModel_, m + j, m + nCuts); // upward constraints -- on bU_i
    }
  }

  // Add zL <= zU constraints

  for (int j=0; j<n; j++) { // for each row

    int    ind [2] = {j,   n + j};
    double coe [2] = {1., -1.};

    CoinPackedVector row (2, ind, coe);
    fplp -> addRow (row, -COIN_DBL_MAX, 0.);
  }

  // Finally, add consistency cuts, bL <= bU

  if (extendedModel_)

    for (int j=0; j<m; j++) { // for each row

      int    ind [2] = {2*n + j, 2*n + m + j};
      double coe [2] = {1.,      -1.};

      CoinPackedVector row (2, ind, coe);
      fplp -> addRow (row, -COIN_DBL_MAX, 0.);
    }


  fplp -> setObjSense (-1.); // we want to maximize

  fplp -> initialSolve ();

  // Extra pre-solve: if the initial LP is unbounded (that is,
  // dual-infeasible but not primal-infeasible), then repeat after a
  // call to BT. This is a cheap way not to throw

  if (fplp -> isProvenDualInfeasible ()) {

    problem_ -> Jnlst () -> Printf (J_WARNING, J_BOUNDTIGHTENING, "FPLP unbounded: extra BT\n");

    if (!(problem_ -> doFBBT ()) &&   // if FBBT was not applied before (because it was excluded,
        !(problem_ -> btCore (NULL))) // do a round of FBBT. If infeasible,
      WipeMakeInfeas (cs);            // well, this is infeasible though FPLP will take the merit

    // Otherwise, reset bounds on auxiliaries based on new bounds in problem_ -> domain ();

    for (int i=0; i<n; i++) {
      fplp -> setColLower (  i, problem_ -> Lb (i)); // set lower bound for xL [i]
      fplp -> setColLower (n+i, problem_ -> Lb (i)); //                     xU
      fplp -> setColUpper (  i, problem_ -> Ub (i)); //     upper           xL
      fplp -> setColUpper (n+i, problem_ -> Ub (i)); //                     xU
    }

    fplp -> resolve ();
  }

  const double 
    *newLB = fplp -> getColSolution (),
    *newUB = newLB + n;

  double infeasBounds [] = {1,-1};

  if (fplp -> isProvenOptimal ()) {

    // if problem not solved to optimality, bounds are useless

    // check old and new bounds

    int 
      *indLB = new int [n],
      *indUB = new int [n],
      ntightenedL = 0,
      ntightenedU = 0;

    double 
      *valLB = new double [n],
      *valUB = new double [n];

    for (int i=0; i<n; i++) {

      if (problem_ -> Jnlst () -> ProduceOutput (J_ERROR, J_BOUNDTIGHTENING))
        printf ("x%d: [%g,%g] --> [%g,%g]\n", i, 
                oldLB [i], oldUB [i], 
                newLB [i], newUB [i]);

      if (newLB [i] > oldLB [i] + COUENNE_EPS) {

        indLB [ntightenedL]   = i;
        valLB [ntightenedL++] = newLB [i];

        ++nTightened_;
      }

      if (newUB [i] < oldUB [i] - COUENNE_EPS) {

        indUB [ntightenedU]   = i;
        valUB [ntightenedU++] = newUB [i];

        ++nTightened_;
      }
    }

    if (ntightenedL || ntightenedU) {

      OsiColCut newBound;

      newBound.setLbs (ntightenedL, indLB, valLB);
      newBound.setUbs (ntightenedU, indUB, valUB);

      cs.insert (newBound);
    }

    delete [] indLB;
    delete [] indUB;
    delete [] valLB;
    delete [] valUB;

    CPUtime_ += CoinCpuTime () - now;

    if (treeInfo.inTree && 
        treeInfo.level <= 0)
      problem_ -> Jnlst () -> Printf (J_ERROR, J_COUENNE, "%d bounds tightened (%g seconds)\n", 
                                      nTightened_ - nInitTightened, CoinCpuTime () - now); 

  } else if (fplp -> isProvenPrimalInfeasible ()) {

    if (treeInfo.inTree &&
        treeInfo.level <= 0)
      problem_ -> Jnlst () -> Printf (J_ERROR, J_COUENNE, " FPLP infeasible.\n");

    WipeMakeInfeas (cs);

    newLB = infeasBounds;
    newUB = infeasBounds + 1;

  } else {

    // we won't use the solution from FPLP, and should tell the BT
    // performance indicator that nothing should change.

    if (treeInfo.inTree && 
        treeInfo.level <= 0)
      problem_ -> Jnlst () -> Printf (J_ERROR, J_COUENNE, " FPLP inconclusive, won't be used.\n");

    newLB = oldLB;
    newUB = oldUB;
  }

  //  problem_ -> Jnlst () -> Printf (J_ERROR, J_BOUNDTIGHTENING, "END\n");

  perfIndicator_. update (newLB, newUB, treeInfo.level);
  perfIndicator_. addToTimer (CoinCpuTime () - startTime);

  delete fplp;

  problem_ -> domain () -> pop ();

  delete [] oldLB;
  delete [] oldUB;
}


// single cut creation. Parameters:
//
//  1) sign:     tells us whether this is a <= or a >= (part of a) constraint.
//  2) indexVar: index of variable we want to do upward or downward bt
//  3) nVars:    number of variables in the original problems (original +
//               auxiliaries). Used to understand if we are adding an
//               up or a down constraint
//  4) p:        solver interface to which we are adding constraints
//  5) indices:  vector containing indices of the linearization constraint (the    i's)
//  6) coe:                        coeffs                                       a_ji's
//  7) rhs:      right-hand side of constraint
//  8) nEl:      number of elements of this linearization cut
//  9) extMod:   extendedModel_
// 10) indCon:   index of constraint being treated (and corresponding bL, bU)
// 11) nCon:     number of constraints

void CouenneFixPoint::createRow (int sign,
                                 int indexVar,
                                 int nVars,
                                 OsiSolverInterface *p,
                                 const int *indices,
                                 const double *coe,
                                 const double rhs,
                                 const int nEl,
                                 bool extMod,
                                 int indCon,
                                 int nCon) const {



  if (problem_ -> Jnlst () -> ProduceOutput (J_ERROR, J_BOUNDTIGHTENING)) {

    printf ("creating constraint from: ");

    for (int i=0; i<nEl; i++)
      printf ("%+g x%d ", coe [i], indices [i]);

    printf ("%c= %g for variable index %d: ", sign > 0 ? '<' : '>', rhs, indexVar);
  }

  int nTerms = nEl;

  if (extMod) 
    nTerms++; // always add one element when using extended model

  int    *iInd = new int    [nTerms];
  double *elem = new double [nTerms];

  // coefficients are really easy

  CoinCopyN (coe, nEl, elem);

  if (extMod) {
    elem [nEl] = -1.; // extended model, coefficient for bL or bU
    iInd [nEl] = 2*nVars + indCon + ((sign > 0) ? nCon : 0);
  }

  // indices are not so easy...

  for (int k=0; k<nEl; k++) {

    int curInd = indices [k];

    iInd [k] = curInd; // Begin with xL_i, same index as x_i in the
                       // original model. Should add n depending on a
                       // few things... 

    if (curInd == indexVar) { // x_k is x_i itself
      if (((sign > 0) && (coe [k] > 0.)) || 
          ((sign < 0) && (coe [k] < 0.)))

      iInd [k] += nVars;

    } else if (((coe [k] > 0.) && (sign < 0)) ||
               ((coe [k] < 0.) && (sign > 0)))

      iInd [k] += nVars;
  }

  CoinPackedVector vec (nTerms, iInd, elem);

  double 
    lb = sign > 0 ? -COIN_DBL_MAX : extMod ? 0. : rhs,
    ub = sign < 0 ? +COIN_DBL_MAX : extMod ? 0. : rhs;

  p -> addRow (vec, lb, ub);

  // Update time spent doing this

  if (problem_ -> Jnlst () -> ProduceOutput (J_ERROR, J_BOUNDTIGHTENING)) {

    for (int i=0; i<nEl; i++)
      printf ("%+g x%d ", elem [i], iInd [i]);

    printf ("in [%g,%g]\n", lb, ub);
  }

  // OsiRowCut *cut = new OsiRowCut (lb, ub, nTerms, nTerms, iInd, elem);
  // cut -> print ();
  // delete cut;

  delete [] iInd;
  delete [] elem;
}