Changeset 1060 for trunk


Ignore:
Timestamp:
Feb 1, 2014 12:26:24 PM (6 years ago)
Author:
pbelotti
Message:

FP: correct handling of tabu list and solution pool

Location:
trunk/Couenne/src/heuristics
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Couenne/src/heuristics/CouenneFPpool.cpp

    r1058 r1060  
    7373        ((*i) -> Image () -> Linearity () > LINEAR)) {
    7474
    75       double 
     75      double
    7676        diff = 0.,
    7777        fval = (*((*i) -> Image ())) ();
     
    133133  switch (comparedTerm) {
    134134
    135     case SUM_NINF:     return (nNLinf_   + nIinf_   < other.nNLinf_   + other.nIinf_);
    136     case SUM_INF:      return (maxNLinf_ + maxIinf_ < other.maxNLinf_ + other.maxIinf_);
    137     case OBJVAL:       return (objVal_              < other.objVal_ - COUENNE_EPS * CoinMax (1., CoinMax (objVal_, other.objVal_)));
     135  case SUM_INF:      if (maxNLinf_ + maxIinf_ < other.maxNLinf_ + other.maxIinf_)                                             return true;
     136  case OBJVAL:       if (objVal_              < other.objVal_ - COUENNE_EPS * CoinMax (1., CoinMax (objVal_, other.objVal_))) return true;
     137  case SUM_NINF:     if (nNLinf_   + nIinf_   < other.nNLinf_   + other.nIinf_)                                               return true;
    138138    // so that if objective is close these two solutions will be deemed equal
    139139
    140     case ALL_VARS: {
    141       // lexicographical comparison: unless the two solutions have the
    142       // same subvector, comparison will tell them apart
    143 
    144       for (std::vector <exprVar *>::iterator i = problem_ -> Variables (). begin ();
    145            i != problem_ -> Variables (). end ();
    146            ++i)
    147 
    148         if ((*i) -> Multiplicity () > 0) {
    149 
    150           int indVar = (*i) -> Index ();
    151 
    152           if (x_ [indVar] < other.x_ [indVar] - COUENNE_EPS)
    153             return true;
    154         }
    155 
    156       return false;
    157     }
    158 
    159     case INTEGER_VARS: {
    160 
    161       // lexicographical comparison: unless the two solutions have the
    162       // same integer subvector, comparison will tell them apart
    163 
    164       for (std::vector <exprVar *>::iterator i = problem_ -> Variables (). begin ();
    165            i != problem_ -> Variables (). end ();
    166            ++i)
    167 
    168         if (((*i) -> Multiplicity () > 0) &&
    169             (*i) -> isInteger ()) {
    170 
    171           int indVar = (*i) -> Index ();
     140  case INTEGER_VARS: {
     141
     142    // lexicographical comparison: unless the two solutions have the
     143    // same integer subvector, comparison will tell them apart
     144
     145    for (std::vector <exprVar *>::iterator i = problem_ -> Variables (). begin ();
     146         i != problem_ -> Variables (). end ();
     147         ++i)
     148
     149      if (((*i) -> Multiplicity () > 0) &&
     150          (*i) -> isInteger ()) {
     151
     152        int indVar = (*i) -> Index ();
    172153       
    173           if (x_ [indVar] < other.x_ [indVar] - COUENNE_EPS)
    174             return true;
    175         }
    176 
    177       return false;
    178     }
     154        if (x_ [indVar] > other.x_ [indVar] + COUENNE_EPS)
     155          return false;
     156      }
     157
     158    return true;
     159  }
     160
     161  case ALL_VARS: {
     162    // lexicographical comparison: unless the two solutions have the
     163    // same subvector, comparison will tell them apart
     164
     165    for (std::vector <exprVar *>::iterator i = problem_ -> Variables (). begin ();
     166         i != problem_ -> Variables (). end ();
     167         ++i)
     168
     169      if ((*i) -> Multiplicity () > 0) {
     170
     171        int indVar = (*i) -> Index ();
     172
     173        if (x_ [indVar] > other.x_ [indVar] + COUENNE_EPS)
     174          return false;
     175      }
     176
     177    return true;
     178  }
    179179  }
    180180
  • trunk/Couenne/src/heuristics/CouenneFPscipSolve.cpp

    r1059 r1060  
    166166        // }
    167167
     168        /* FIXME: restore
     169
    168170        assert (fabs (lbs [j] - problem_ -> Lb (j)) < SCIPfeastol (scip));
    169171        assert (fabs (ubs [j] - problem_ -> Ub (j)) < SCIPfeastol (scip));
     
    171173
    172174        assert (nEntries <= 2*nvars - 2);
     175        */
    173176
    174177        double x_rounded = floor (x [j] + .5);
     
    304307        SCIP_CALL( SCIPsetLongintParam(scip, "limits/stallnodes", 1000) );
    305308        SCIP_CALL( SCIPsetLongintParam(scip, "limits/nodes", 10000) );
     309        SCIP_CALL( SCIPsetRealParam   (scip, "limits/gap", .001) );
    306310
    307311        // disable cutting plane separation
     
    338342        SCIP_CALL( SCIPsetLongintParam(scip, "limits/stallnodes", 500) );
    339343        SCIP_CALL( SCIPsetLongintParam(scip, "limits/nodes", 5000) );
     344        SCIP_CALL( SCIPsetRealParam   (scip, "limits/gap", .005) );
    340345
    341346        // disable expensive dual techniques
  • trunk/Couenne/src/heuristics/CouenneFeasPump.cpp

    r1058 r1060  
    256256        if (tabuPool_ . find (newSol) == tabuPool_ . end ()) {
    257257
     258          //tabuPool_ . insert (newSol);
     259
    258260          try_again = true;
    259261          break;
     
    295297    //    pool and use it instead
    296298
     299    problem_ -> Jnlst () -> Printf (J_WARNING, J_NLPHEURISTIC, "FP: %d solutions in pool, %d in tabu list\n", pool_ -> Set (). size (), tabuPool_ . size ());
     300
    297301    CouenneFPsolution checkedSol (problem_, iSol, false); // false is for not allocating space for this
    298302
     
    313317
    314318        // try to find non-tabu solution in the solution pool
     319
    315320        do {
    316321
    317             // retrieve the top solution from the pool
    318             pool_ -> findClosestAndReplace (iSol, nSol, problem_ -> nVars ());
    319 
    320             CouenneFPsolution newSol (problem_, iSol);
    321 
    322             // we found a solution that is not in the tabu list
    323             if (tabuPool_. find (newSol) == tabuPool_ . end ())
    324               break;
    325 
    326             // the pool is empty -> bail out
    327             if (pool_ -> Set ().empty ())
    328               {
    329                 delete[] iSol;
    330                 iSol = NULL;
    331               }
     322          // retrieve the top solution from the pool
     323          pool_ -> findClosestAndReplace (iSol, nSol, problem_ -> nVars ());
     324
     325          CouenneFPsolution newSol (problem_, iSol);
     326
     327          // we found a solution that is not in the tabu list
     328          if (tabuPool_. find (newSol) == tabuPool_ . end ()) {
     329
     330            tabuPool_ . insert (newSol);
     331            break;
     332          }
     333
     334          // the pool is empty -> just round
     335          if (pool_ -> Set ().empty ())
     336            {
     337              int n = problem_ -> nVars ();
     338
     339              if (!iSol)
     340                iSol = new double [n];
     341
     342              for (int i=0; i<n; i++)
     343                iSol [i] = (problem_ -> Var (i) -> isInteger ()) ?
     344                  COUENNE_round (nSol [i]) :
     345                  nSol [i];
     346
     347              // delete[] iSol;
     348              // iSol = NULL;
     349            }
    332350
    333351        } while( !pool_ -> Set ().empty() );
     
    396414        }
    397415      }
    398     }
     416    }
     417
     418    if (!iSol)
     419      break;
    399420
    400421    problem_ -> Jnlst () -> Printf (J_WARNING, J_NLPHEURISTIC, "FP: checking IP solution for feasibility\n");
     
    486507            // we found a solution that is not in the tabu list
    487508            if (tabuPool_ . find (newSol) == tabuPool_ . end ()) {
     509
     510              tabuPool_ . insert (newSol);
    488511              try_again = true;
    489512              break;
  • trunk/Couenne/src/heuristics/CouenneFeasPumpConstructors.cpp

    r1058 r1060  
    5615612: objective value; \
    5625623: compare value of all variables; \
    563 4: compare value of all integers.");
    564 }
     5634: compare value of all integers (RECOMMENDED).");
     564}
Note: See TracChangeset for help on using the changeset viewer.