CouenneFPpool.cpp

Go to the documentation of this file.

/* $Id: CouenneFPpool.cpp 1061 2014-02-01 19:22:28Z pbelotti $
 *
 * Name:    CouenneFPpool.cpp
 * Authors: Pietro Belotti
 *          Timo Berthold, ZIB Berlin
 * Purpose: Pool of MILP- (and why not? NLP-) feasible solutions for
 *          restart use in the Feasibility Pump
 * 
 * This file is licensed under the Eclipse Public License (EPL)
 */

#include "CoinHelperFunctions.hpp"

#include "CouenneProblem.hpp"
#include "CouenneFPpool.hpp"
#include "CouenneFeasPump.hpp"
#include "CouenneExprVar.hpp"
#include "CouenneExprAux.hpp"

static const double COMP_TOLERANCE = COUENNE_EPS; // not global

using namespace Couenne;

CouenneFPsolution::CouenneFPsolution (CouenneProblem *p, CouNumber *x, bool copied):

  x_        (NULL),
  n_        (p -> nVars ()),
  nNLinf_   (0),
  nIinf_    (0),
  objVal_   (0.),
  maxNLinf_ (0.),
  maxIinf_  (0.),
  copied_   (copied),
  problem_  (p) {


  if (copied_) {
    x_ = x;
    return;
  }

  x_ = CoinCopyOfArray (x, p -> nVars ());

  for (std::vector <exprVar *>::iterator i = p -> Variables (). begin (); 
       i != p -> Variables (). end ();
       ++i) {

    if ((*i) -> Multiplicity () <= 0)
      continue;

    CouNumber 
      vval = (**i) ();

    if ((*i) -> isInteger ()) {

      double inf = CoinMax (vval - floor (vval + COUENNE_EPS),
                            ceil (vval - COUENNE_EPS) - vval);

      if (inf > COUENNE_EPS) {

        ++nIinf_;
 
        if (inf > maxIinf_) 
          maxIinf_ = inf;
      }
    }

    if (((*i) -> Type () == AUX) &&
        ((*i) -> Image () -> Linearity () > LINEAR)) {

      double
        diff = 0.,
        fval = (*((*i) -> Image ())) ();

      if      ((*i) -> sign () != expression::AUX_GEQ) diff = CoinMax (diff, vval - fval);
      else if ((*i) -> sign () != expression::AUX_LEQ) diff = CoinMax (diff, fval - vval);

      if (diff > COUENNE_EPS) {

        ++nNLinf_;

        if (diff > maxNLinf_)
          maxNLinf_ = diff;
      }
    }
  }
}


CouenneFPsolution::CouenneFPsolution (const CouenneFPsolution &src):
  x_          (src.x_ ? CoinCopyOfArray (src.x_, src.n_) : NULL),
  n_          (src.n_),
  nNLinf_     (src.nNLinf_),
  nIinf_      (src.nIinf_),
  objVal_     (src.objVal_),
  maxNLinf_   (src.maxNLinf_),
  maxIinf_    (src.maxIinf_),
  copied_     (false),
  problem_    (src.problem_) {}


CouenneFPsolution &CouenneFPsolution::operator= (const CouenneFPsolution &src) {

  x_         = src.x_ ? CoinCopyOfArray (src.x_, src.n_) : NULL;
  n_         = src.n_;
  nNLinf_    = src.nNLinf_;
  nIinf_     = src.nIinf_;
  objVal_    = src.objVal_;
  maxNLinf_  = src.maxNLinf_;
  maxIinf_   = src.maxIinf_;
  copied_    = false;
  problem_   = src.problem_;

  return *this;
}

CouenneFPsolution::~CouenneFPsolution () {

  if (x_ && !copied_)
    delete [] x_;
}

bool CouenneFPsolution::compare (const CouenneFPsolution &other, enum what_to_compare comparedTerm) const {

  switch (comparedTerm) {

  case SUM_INF:      if (maxNLinf_ + maxIinf_ < other.maxNLinf_ + other.maxIinf_)                                             return true;
  case OBJVAL:       if (objVal_              < other.objVal_ - COUENNE_EPS * CoinMax (1., CoinMax (objVal_, other.objVal_))) return true;
  case SUM_NINF:     if (nNLinf_   + nIinf_   < other.nNLinf_   + other.nIinf_)                                               return true;
    // so that if objective is close these two solutions will be deemed equal

  case INTEGER_VARS: {

    // lexicographical comparison: unless the two solutions have the
    // same integer subvector, comparison will tell them apart

    for (std::vector <exprVar *>::iterator i = problem_ -> Variables (). begin (); 
         i != problem_ -> Variables (). end ();
         ++i)

      if (((*i) -> Multiplicity () > 0) && 
          (*i) -> isInteger ()) {

        int indVar = (*i) -> Index ();

        // LEXICOGRAPHICAL ORDERING: return true upon finding the
        // first element with lower element

#if 0
        if (0) {
          printf (" (%d,%g,%g,%g)", indVar, x_ [indVar], other.x_ [indVar], x_ [indVar] - other.x_ [indVar]);

          if (x_ [indVar] < other.x_ [indVar] - COUENNE_EPS)
            printf ("\n-----\n");
        }
#endif
        if (x_ [indVar] < other.x_ [indVar] - COUENNE_EPS)
          return true;
      }

    //printf ("\n####\n");
    return false;
  }

  case ALL_VARS: {
    // lexicographical comparison: unless the two solutions have the
    // same subvector, comparison will tell them apart

    for (std::vector <exprVar *>::iterator i = problem_ -> Variables (). begin (); 
         i != problem_ -> Variables (). end ();
         ++i) 

      if ((*i) -> Multiplicity () > 0) {

        int indVar = (*i) -> Index ();

        if (x_ [indVar] < other.x_ [indVar] + COUENNE_EPS)
          return true;
      }

    return false;
  }
  }

  printf ("CouenneFPsolution::compare: bad compared term\n");
  abort ();
}


CouenneFPpool::CouenneFPpool (const CouenneFPpool &src):
  set_     (src.set_),
  problem_ (src.problem_) {}


CouenneFPpool &CouenneFPpool::operator= (const CouenneFPpool &src) {

  set_     = src.set_;
  problem_ = src.problem_;

  return *this;
}

bool compareSol::operator() (const CouenneFPsolution &one, 
                             const CouenneFPsolution &two) const {

  return one. compare (two, comparedTerm_);

  // register const double
  //   *x1 = one.x (),
  //   *x2 = two.x ();

  // register int n = one.n ();

  // while (n--)
  //   if ((*x1++ - *x2++) <= COMP_TOLERANCE)
  //     return true;

  // return false;
}

void CouenneFPpool::findClosestAndReplace (double *&sol, const double *nSol, int nvars)  {

   double bestdist = COIN_DBL_MAX;
   std::set <CouenneFPsolution, compareSol>::iterator bestsol = set_. end ();

   if( nSol )
   {
     for (std::set <CouenneFPsolution, compareSol>::iterator i = set_. begin (); 
           i != set_. end (); ++i)
      {
        //compute distance of pool solution and NLP solution

        register double 
           dist = 0.0,
           delta;

        const register double 
          *x = i -> x (),
          *s = nSol;

        register bool move_on = false;

        for (int j = nvars, k=0; j--; ++k) {

          delta = *x++ - *s++;

          if (problem_ -> Var (k) -> Multiplicity () <= 0)
            continue;

          dist += delta * delta;

          if (dist >= bestdist) { // interrupt check of this solution
                                  // if already above current best
            move_on = true;
            break;
          }
        }

        if (move_on) 
          continue;

        //update best solution
        if( dist < bestdist )
         {
            bestdist = dist;
            bestsol = i;
         }
      }
   }
   else 
      bestsol = set_. begin ();

   if( bestsol != set_. end () )
   {
     delete [] sol;
     sol = CoinCopyOfArray ((*bestsol).x(), nvars); 
     set_. erase(bestsol);
   }   
}