Changeset 221


Ignore:
Timestamp:
Jul 8, 2009 5:34:02 PM (12 years ago)
Author:
pbelotti
Message:

split strong branching code to avoid repeated code

Location:
trunk/Couenne/src/branch
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/Couenne/src/branch/CouenneChooseStrong.hpp

    r215 r221  
    1515#include "CouenneJournalist.hpp"
    1616
     17class Bonmin::HotInfo;
    1718class CouenneProblem;
    1819template <class T> class CouenneSolverInterface;
     
    7778  protected:
    7879
     80  /// does one side of the branching
     81  int simulateBranch (OsiObject *Object,
     82                      OsiBranchingInformation *info,
     83                      OsiBranchingObject *branch,
     84                      OsiSolverInterface *solver,
     85                      Bonmin::HotInfo * result,
     86                      int direction);
     87
     88  /// subroutine of simulateBranch for integer FBBT
     89  bool StrongBranchingFBBT (OsiObject *Object,
     90                            OsiSolverInterface *solver);
     91
    7992    /// Pointer to the associated MINLP problem
    8093    CouenneProblem *problem_;
  • trunk/Couenne/src/branch/CouenneChooseVariable.hpp

    r141 r221  
    1 /* $Id$ */
    2 /*
     1/* $Id$
     2 *
    33 * Name:    CouenneChooseVariable.hpp
    44 * Authors: Pierre Bonami, IBM Corp.
  • trunk/Couenne/src/branch/doStrongBranching.cpp

    r215 r221  
    102102      Bonmin::HotInfo * result = results_ () + iDo; // retrieve i-th object to test
    103103
    104       OsiObject     *Object = solver_ -> objects () [result -> whichObject ()];
    105       CouenneObject *CouObj = dynamic_cast <CouenneObject *> (Object);
     104      OsiObject *Object = solver_ -> objects () [result -> whichObject ()];
    106105
    107106      // For now just 2 way
     
    112111      if (cb) cb -> setSimulate (true);
    113112
     113      int
     114        status0 = -1,
     115        status1 = -1;
     116
     117      ///////////////////////////////////////////////////////////////////////////
     118
    114119      /* Try the first direction.  Each subsequent call to branch()
    115120         performs the specified branch and advances the branch object
    116121         state to the next branch alternative. */
    117122
    118       int
    119         status0 = -1,
    120         status1 = -1;
    121 
    122       OsiSolverInterface * thisSolver = solver;
    123 
    124       // DOWN DIRECTION ///////////////////////////////////////////////////////
    125 
    126       if (branch -> boundBranch ()) { // a (variable) bound branch
    127 
    128         if (branch -> branch (solver) > COUENNE_INFINITY) // branch is infeasible
    129           result -> setDownStatus (status0 = 1);
    130 
    131         else { // branch is feasible, solve and compare
    132 
    133           bool infeasible = false;
    134 
    135           // Bound tightening if not a CouenneObject -- explicit bound tightening
    136           if (!CouObj) {
    137 
    138             int
    139               indVar = Object   -> columnNumber (),
    140               nvars  = problem_ -> nVars ();
    141 
    142             t_chg_bounds *chg_bds = new t_chg_bounds [nvars];
    143 
    144             chg_bds [indVar].setUpper (t_chg_bounds::CHANGED);
    145 
    146             if (problem_ -> doFBBT ()) {         // problem allowed to do FBBT
    147 
    148               problem_ -> installCutOff ();
    149 
    150               if (!problem_ -> btCore (chg_bds)) // done FBBT and this branch is infeasible
    151                 infeasible = true;        // ==> report it
    152 
    153               else {
    154                 const double
    155                   *lb = solver -> getColLower (),
    156                   *ub = solver -> getColUpper ();
    157 
    158                 for (int i=0; i<nvars; i++) {
    159                   if (problem_ -> Lb (i) > lb [i]) solver -> setColLower (i, problem_ -> Lb (i));
    160                   if (problem_ -> Ub (i) < ub [i]) solver -> setColUpper (i, problem_ -> Ub (i));
    161                 }
    162               }
    163             }
    164 
    165             delete [] chg_bds;
    166           }
    167 
    168           if (infeasible) result -> setDownStatus (status0 = 1);
    169           else {
    170 
    171             solver -> solveFromHotStart ();
    172 
    173             if (pseudoUpdateLP_ && CouObj && solver -> isProvenOptimal ()) {
    174               CouNumber dist = distance (lpSol, solver -> getColSolution (), numberColumns);
    175               if (dist > COUENNE_EPS)
    176                 CouObj -> setEstimate (dist, 0);
    177             }
    178           }
    179         }
    180 
    181       } else {                       // some more complex branch, have to clone solver
    182 
    183         // adding cuts or something
    184         thisSolver = solver -> clone ();
    185 
    186         if (branch -> branch (thisSolver) > COUENNE_INFINITY)
    187           result -> setDownStatus (status0 = 1);
    188 
    189         else { // set hot start iterations
    190           int limit;
    191           thisSolver -> getIntParam (OsiMaxNumIterationHotStart, limit);
    192           thisSolver -> setIntParam (OsiMaxNumIteration,         limit);
    193 
    194           thisSolver -> resolve ();
    195           if (pseudoUpdateLP_ && CouObj && thisSolver -> isProvenOptimal ()) {
    196             CouNumber dist = distance (lpSol, thisSolver -> getColSolution (), numberColumns);
    197             if (dist > COUENNE_EPS)
    198               CouObj -> setEstimate (dist, 0);
    199           }
    200         }
    201       }
    202 
    203       // can check if we got solution
    204       // status is 0 finished, 1 infeasible and 2 unfinished and 3 is solution
    205 
    206       /*if (CouObj)
    207         jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, "dnEst %g upEst %g\n",
    208                           CouObj->downEstimate(),
    209                           CouObj->upEstimate());*/
    210 
    211       // only update information if this branch is feasible
    212       if (status0 < 0)
    213         status0 = result -> updateInformation (thisSolver, info, this);
    214 
    215       numberStrongIterations_ += thisSolver -> getIterationCount();
    216 
    217       if ((status0 == 3) && (trustStrongForSolution_)) {
    218         // new solution already saved
    219         info -> cutoff_ = goodObjectiveValue_;
    220         problem_ -> setCutOff (goodObjectiveValue_);
    221         status0 = 0;
    222       }
    223 
    224       if (solver != thisSolver)
    225         delete thisSolver;
     123      status0 = simulateBranch (Object, info, branch, solver, result, -1);
    226124
    227125      // save current bounds as tightened by the down branch; will be
     
    237135      }
    238136
    239       // UP DIRECTION ///////////////////////////////////////////////////////
    240 
    241       thisSolver = solver;
    242 
    243       if (branch -> boundBranch ()) { // (variable) bound branch
    244 
    245         if (branch -> branch (solver) > COUENNE_INFINITY)
    246           result -> setUpStatus (status1 = 1);
    247 
    248         else {
    249 
    250           bool infeasible = false;
    251 
    252           // Bound tightening if not a CouenneObject -- explicit bound tightening
    253           if (!CouObj) {
    254 
    255             int
    256               indVar = Object   -> columnNumber (),
    257               nvars  = problem_ -> nVars ();
    258 
    259             t_chg_bounds *chg_bds = new t_chg_bounds [nvars];
    260 
    261             chg_bds [indVar].setLower (t_chg_bounds::CHANGED);
    262 
    263             if (problem_ -> doFBBT ()) {         // problem allowed to do FBBT
    264 
    265               problem_ -> installCutOff ();
    266 
    267               if (!problem_ -> btCore (chg_bds)) // done FBBT and this branch is infeasible
    268                 infeasible = true;        // ==> report it
    269 
    270               else {
    271                 const double
    272                   *lb = solver -> getColLower (),
    273                   *ub = solver -> getColUpper ();
    274 
    275                 for (int i=0; i<nvars; i++) {
    276                   if (problem_ -> Lb (i) > lb [i]) solver -> setColLower (i, problem_ -> Lb (i));
    277                   if (problem_ -> Ub (i) < ub [i]) solver -> setColUpper (i, problem_ -> Ub (i));
    278                 }
    279               }
    280             }
    281 
    282             delete [] chg_bds;
    283           }
    284 
    285           if (infeasible) result -> setUpStatus (status0 = 1);
    286           else {
    287 
    288             solver -> solveFromHotStart ();
    289 
    290             if (pseudoUpdateLP_ && CouObj && solver -> isProvenOptimal ()) {
    291               CouNumber dist = distance (lpSol, solver -> getColSolution (), numberColumns);
    292               if (dist > COUENNE_EPS)
    293                 CouObj -> setEstimate (dist, 1);
    294             }
    295           }
    296         }
    297       } else {                     // some more complex branch, have to clone solver
    298 
    299         // adding cuts or something
    300         thisSolver = solver -> clone ();
    301 
    302         if (branch -> branch (thisSolver) > COUENNE_INFINITY)
    303           result -> setUpStatus (status1 = 1);
    304 
    305         else {
    306           // set hot start iterations
    307           int limit;
    308           thisSolver -> getIntParam (OsiMaxNumIterationHotStart, limit);
    309           thisSolver -> setIntParam (OsiMaxNumIteration,         limit);
    310 
    311           thisSolver -> resolve();
    312           if (pseudoUpdateLP_ && CouObj && thisSolver -> isProvenOptimal ()) {
    313             CouNumber dist = distance (lpSol, thisSolver -> getColSolution (), numberColumns);
    314             if (dist > COUENNE_EPS)
    315               CouObj -> setEstimate (dist, 1);
    316           }
    317         }
    318       }
    319 
    320       // can check if we got solution
    321       // status is 0 finished, 1 infeasible and 2 unfinished and 3 is solution
    322 
    323       /*if (CouObj)
    324         jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, "dnEst %g upEst %g\n",
    325                           CouObj->downEstimate(),
    326                           CouObj->upEstimate());*/
    327 
    328       // only update information if this branch is feasible
    329       if (status1 < 0)
    330         status1 = result -> updateInformation (thisSolver, info, this);
    331 
    332       numberStrongDone_++;
    333       numberStrongIterations_ += thisSolver->getIterationCount();
    334 
    335       if ((status1 == 3) && (trustStrongForSolution_)) {
    336         // new solution already saved
    337         info -> cutoff_ = goodObjectiveValue_;
    338         problem_ -> setCutOff (goodObjectiveValue_);
    339         status1 = 0;
    340       }
     137      status1 = simulateBranch (Object, info, branch, solver, result, +1);
     138
     139      ///////////////////////////////////////////////////////////////////////////
    341140
    342141      jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, "-------\n");
     
    345144
    346145      /////////////////////////////////////////////////////////////////////////////
    347 
    348       if (solver != thisSolver)
    349         delete thisSolver;
    350146
    351147      bool tightened = false;
     
    465261    return returnCode;
    466262  }
     263
     264
     265// Do one side of strong branching
     266int CouenneChooseStrong::simulateBranch (OsiObject *Object,
     267                                         OsiBranchingInformation *info,
     268                                         OsiBranchingObject *branch,
     269                                         OsiSolverInterface *solver,
     270                                         Bonmin::HotInfo * result,
     271                                         int direction) {
     272
     273  int status = -1;
     274
     275  OsiSolverInterface *thisSolver = solver;
     276
     277  // Bound tightening if not a CouenneObject -- explicit bound tightening
     278  CouenneObject *CouObj = dynamic_cast <CouenneObject *> (Object);
     279
     280  if (branch -> boundBranch ()) { // a (variable) bound branch
     281
     282    if (branch -> branch (solver) > COUENNE_INFINITY) { // branch is infeasible
     283      if (direction < 0) result -> setDownStatus (status = 1);
     284      else               result -> setUpStatus   (status = 1);
     285    }
     286
     287    else // branch seems feasible, solve and compare
     288
     289      if (!CouObj && !StrongBranchingFBBT (Object, solver)) {
     290
     291        status = 1;
     292
     293        if (direction < 0) result -> setDownStatus (1);
     294        else               result -> setUpStatus   (1);
     295
     296      } else {
     297
     298        solver -> solveFromHotStart ();
     299
     300        if (pseudoUpdateLP_ && CouObj && solver -> isProvenOptimal ()) {
     301          CouNumber dist = distance (info -> solution_, solver -> getColSolution (),
     302                                     problem_ -> nVars ());
     303          if (dist > COUENNE_EPS)
     304            CouObj -> setEstimate (dist, 0);
     305        }
     306      }
     307
     308  } else {                       // some more complex branch, have to clone solver
     309
     310    // adding cuts or something
     311    thisSolver = solver -> clone ();
     312
     313    if (branch -> branch (thisSolver) > COUENNE_INFINITY) {
     314
     315      if (direction < 0) result -> setDownStatus (status = 1);
     316      else               result -> setUpStatus   (status = 1);
     317
     318    } else // set hot start iterations
     319
     320      if (!CouObj && !StrongBranchingFBBT (Object, thisSolver)) {
     321
     322        status = 1;
     323
     324        if (direction < 0) result -> setDownStatus (1);
     325        else               result -> setUpStatus   (1);
     326
     327      } else {
     328
     329        int limit;
     330        thisSolver -> getIntParam (OsiMaxNumIterationHotStart, limit);
     331        thisSolver -> setIntParam (OsiMaxNumIteration,         limit);
     332
     333        thisSolver -> resolve ();
     334        if (pseudoUpdateLP_ && CouObj && thisSolver -> isProvenOptimal ()) {
     335          CouNumber dist = distance (info -> solution_, thisSolver -> getColSolution (),
     336                                   problem_ -> nVars ());
     337          if (dist > COUENNE_EPS)
     338            CouObj -> setEstimate (dist, 0);
     339        }
     340      }
     341  }
     342
     343  // can check if we got solution
     344  // status is 0 finished, 1 infeasible and 2 unfinished and 3 is solution
     345
     346  // only update information if this branch is feasible
     347  if (status < 0)
     348    status = result -> updateInformation (thisSolver, info, this);
     349
     350  numberStrongIterations_ += thisSolver -> getIterationCount ();
     351
     352  if ((status == 3) && (trustStrongForSolution_)) {
     353    // new solution already saved
     354    info -> cutoff_ = goodObjectiveValue_;
     355    problem_ -> setCutOff (goodObjectiveValue_);
     356    status = 0;
     357  }
     358
     359  if (solver != thisSolver)
     360    delete thisSolver;
     361
     362  return status;
     363}
     364
     365
     366/// Called from simulateBranch when object is not CouenneObject and
     367/// therefore needs explicit FBBT
     368bool CouenneChooseStrong::StrongBranchingFBBT (OsiObject *Object,
     369                                               OsiSolverInterface *solver) {
     370
     371  bool feasible = true;
     372
     373  if (problem_ -> doFBBT ()) {
     374
     375    int
     376      indVar = Object   -> columnNumber (),
     377      nvars  = problem_ -> nVars ();
     378
     379    t_chg_bounds *chg_bds = new t_chg_bounds [nvars];
     380    chg_bds [indVar].setUpper (t_chg_bounds::CHANGED);
     381    problem_ -> installCutOff ();
     382
     383    if ((feasible = problem_ -> btCore (chg_bds))) {
     384
     385      const double
     386        *lb = solver -> getColLower (),
     387        *ub = solver -> getColUpper ();
     388         
     389      for (int i=0; i<nvars; i++) {
     390        if (problem_ -> Lb (i) > lb [i]) solver -> setColLower (i, problem_ -> Lb (i));
     391        if (problem_ -> Ub (i) < ub [i]) solver -> setColUpper (i, problem_ -> Ub (i));
     392      }
     393    }
     394
     395    delete [] chg_bds;
     396  }
     397
     398  return feasible;
     399}
Note: See TracChangeset for help on using the changeset viewer.