source: branches/devel/Cbc/src/CbcGenBaB.cpp @ 591

Last change on this file since 591 was 591, checked in by lou, 13 years ago

Initial commit of cbc-generic source.

  • Property svn:eol-style set to native
File size: 26.9 KB
Line 
1/*
2  Copyright (C) 2007, Lou Hafer, International Business Machines Corporation
3  and others.  All Rights Reserved.
4
5  This file is part of cbc-generic.
6*/
7
8#include <iostream>
9
10#include "CoinTime.hpp"
11
12#include "OsiSolverInterface.hpp"
13#include "OsiChooseVariable.hpp"
14
15#include "CglPreProcess.hpp"
16
17#include "CbcModel.hpp"
18#include "CbcCutGenerator.hpp"
19#include "CbcBranchActual.hpp"
20#include "CbcStrategy.hpp"
21
22#include "CbcGenCtlBlk.hpp"
23#include "CbcGenParam.hpp"
24#include "CbcGenCbcParam.hpp"
25
26#define CBC_TRACK_SOLVERS 1
27#define COIN_CBC_VERBOSITY 5
28
29/*
30  The support functions for the main branch-and-cut action routine.
31*/
32
33namespace {
34
35/*
36  A hack to fix variables based on reduced cost prior to branch-and-cut. Note
37  that we're *not* looking at the integrality gap here. Given the reduced costs
38  of the root relaxation, we're simply placing a bet that variables with really
39  unfavourable reduced costs that are at their most favourable bound in the
40  root relaxation will never move from that bound.
41
42  For the standard OsiSolverInterface, this requires a bit of effort as the
43  solution and bounds arrays are const and the functions to change them have
44  incompatible interfaces.
45*/
46
47void reducedCostHack (OsiSolverInterface *osi, double threshold)
48
49{ int numCols = osi->getNumCols() ;
50  int i ;
51  const double *lower = osi->getColLower() ;
52  const double *upper = osi->getColUpper() ;
53  const double *solution = osi->getColSolution() ;
54  const double *dj = osi->getReducedCost() ;
55/*
56  First task: scan the columns looking for variables that are at their
57  favourable bound and have reduced cost that exceeds the threshold. Remember
58  the column index and the value.
59*/
60  double *chgBnds = new double [numCols] ;
61  int *chgCols = new int [numCols] ;
62
63  int numFixed = 0 ;
64  for (i = 0 ; i < numCols ; i++)
65  { if (osi->isInteger(i))
66    { double value = solution[i] ;
67      if (value < lower[i]+1.0e-5 && dj[i] > threshold)
68      { chgCols[numFixed] = i ;
69        chgBnds[numFixed] = lower[i] ;
70        numFixed++ ; }
71      else
72      if (value > upper[i]-1.0e-5 && dj[i] < -threshold)
73      { chgCols[numFixed] = i ;
74        chgBnds[numFixed] = upper[i] ;
75        numFixed++ ; } } }
76/*
77  Second task: For variables that we want to fix, we need to:
78    * Prepare an array with the new lower and upper bounds for variables that
79      will be fixed. setColSetBounds requires an array with column indices and
80      an array with new values for both bounds.
81    * Set the correct value in a copy of the current solution. setColSolution
82      requires a complete solution.
83*/
84  if (numFixed > 0)
85  { double *newSoln = CoinCopyOfArray(solution,numCols) ;
86    double *newBnds = new double [2*numFixed] ;
87    double *bndPtr = &newBnds[0] ;
88    for (i = 0 ; i < numFixed ; i++)
89    { int j = chgCols[i] ;
90      double val = chgBnds[i] ;
91      *bndPtr++ = val ;
92      *bndPtr++ = val ;
93      newSoln[j] = val ; }
94    osi->setColSetBounds(&chgCols[0],&chgCols[numFixed],&newBnds[0]) ;
95    osi->setColSolution(&newSoln[0]) ;
96
97    std::cout
98      << "Reduced cost fixing prior to B&C: " << numFixed
99      << " columns fixed." << std::endl ;
100
101    delete[] newSoln ;
102    delete[] newBnds ; }
103 
104  delete[] chgBnds ;
105  delete[] chgCols ;
106
107  return ; }
108
109/*
110  Helper routine to solve a continuous relaxation and print something
111  intelligent when the result is other than optimal. Returns true if the
112  result is optimal, false otherwise.
113*/
114
115bool solveRelaxation (CbcModel *model)
116
117{ OsiSolverInterface *osi = model->solver() ;
118
119  model->initialSolve() ;
120
121  if (!(osi->isProvenOptimal()))
122  { bool reason = false ;
123    if (osi->isProvenPrimalInfeasible())
124    { std::cout
125        << "Continuous relaxation is primal infeasible." << std::endl ;
126      reason = true ; }
127    if (osi->isProvenDualInfeasible())
128    { std::cout
129        << "Continuous relaxation is dual infeasible." << std::endl ;
130      reason = true ; }
131    if (osi->isIterationLimitReached())
132    { std::cout
133        << "Continuous solver reached iteration limit." << std::endl ;
134      reason = true ; }
135    if (osi->isAbandoned())
136    { std::cout
137        << "Continuous solver abandoned the problem." << std::endl ;
138      reason = true ; }
139    if (reason == false)
140    { std::cout
141        << "Continuous solver failed for unknown reason." << std::endl ; }
142    return (false) ; }
143
144  return (true) ; }
145
146
147/*
148  Helper routine to establish a priority vector.
149*/
150
151void setupPriorities (CbcModel *model, CbcGenCtlBlk::BPControl how)
152
153{ int numCols = model->getNumCols() ;
154  int *sort = new int[numCols] ;
155  double *dsort = new double[numCols] ;
156  int *priority = new int[numCols] ;
157  const double *objective = model->getObjCoefficients() ;
158  int iColumn ;
159  int n = 0 ;
160  bool priorityOK = true ;
161
162  for (iColumn = 0 ; iColumn < numCols ; iColumn++)
163  { if (model->isInteger(iColumn))
164    { sort[n] = n ;
165      if (how == CbcGenCtlBlk::BPCost)
166      { dsort[n++] = -objective[iColumn] ; }
167      else
168      if (how == CbcGenCtlBlk::BPOrder)
169      { dsort[n++] = iColumn ; }
170      else
171      { std::cerr
172          << "setupPriorities: Unrecognised priority specification."
173          << std::endl ;
174        priorityOK = false ; } } }
175
176  if (priorityOK)
177  { CoinSort_2(dsort,dsort+n,sort) ;
178
179    int level = 0 ;
180    double last = -1.0e100 ;
181    for (int i = 0 ; i < n ; i++)
182    { int iPut = sort[i] ;
183      if (dsort[i] != last)
184      { level++ ;
185        last = dsort[i] ; }
186      priority[iPut] = level ; }
187
188    model->passInPriorities(priority,false) ; }
189
190  delete [] priority ;
191  delete [] sort ;
192  delete [] dsort ;
193 
194  return ; }
195
196
197/*
198  Helper routine to install a batch of heuristics. Each call to getXXXHeuristic
199  will return a pointer to the heuristic object in gen iff the heuristic is
200  enabled.
201*/
202
203void installHeuristics (CbcGenCtlBlk *ctlBlk, CbcModel *model)
204
205{ CbcGenCtlBlk::CGControl action ;
206  CbcHeuristic *gen ;
207  CbcTreeLocal *localTree ;
208/*
209  FPump goes first because it only works before there's a solution.
210*/
211  action = ctlBlk->getFPump(gen,model) ;
212  if (action != CbcGenCtlBlk::CGOff)
213  { model->addHeuristic(gen) ; }
214  action = ctlBlk->getRounding(gen,model) ;
215  if (action != CbcGenCtlBlk::CGOff)
216  { model->addHeuristic(gen) ; }
217  action = ctlBlk->getCombine(gen,model) ;
218  if (action != CbcGenCtlBlk::CGOff)
219  { model->addHeuristic(gen) ; }
220  action = ctlBlk->getGreedyCover(gen,model) ;
221  if (action != CbcGenCtlBlk::CGOff)
222  { model->addHeuristic(gen) ; }
223  action = ctlBlk->getGreedyEquality(gen,model) ;
224  if (action != CbcGenCtlBlk::CGOff)
225  { model->addHeuristic(gen) ; }
226/*
227  This one's a bit different. We acquire the local tree and install it in the
228  model.
229*/
230  action = ctlBlk->getTreeLocal(localTree,model) ;
231  if (action != CbcGenCtlBlk::CGOff)
232  { model->passInTreeHandler(*localTree) ; }
233
234  return ; }
235
236
237/*
238  Helper routine to install cut generators.
239
240  I need to install the new lift-and-project generator (LandP). Also need to
241  figure out stored cuts.
242*/
243
244void installCutGenerators (CbcGenCtlBlk *ctlBlk, CbcModel *model)
245
246{ int switches[20] ;
247  int genCnt = 0 ;
248  CbcGenCtlBlk::CGControl action ;
249  CglCutGenerator *gen ;
250
251/*
252  The magic numbers for the howOften parameter that determines how often the
253  generator is invoked. -100 is disabled, -99 is root only, -98 will stay
254  active only so long as it generates cuts that improve the objective. A value
255  1 <= k <= 90 means the generator will be called every k nodes. If k is
256  negative, then it can be switched off if unproductive. If k is positive,
257  it'll carry on regardless.
258*/
259  int howOften[CbcGenCtlBlk::CGMarker] ;
260  howOften[CbcGenCtlBlk::CGOff] = -100 ;
261  howOften[CbcGenCtlBlk::CGOn] = -1 ;
262  howOften[CbcGenCtlBlk::CGRoot] = -99 ;
263  howOften[CbcGenCtlBlk::CGIfMove] = -98 ;
264  howOften[CbcGenCtlBlk::CGForceOn] = 1 ;
265  howOften[CbcGenCtlBlk::CGForceBut] = 1 ;
266
267/*
268  A negative value for rowCuts means that the specified actions happen only at
269  the root.
270*/
271  action = ctlBlk->getProbing(gen) ;
272  if (action != CbcGenCtlBlk::CGOff)
273  { if (action == CbcGenCtlBlk::CGForceBut)
274    { CglProbing *probingGen = dynamic_cast<CglProbing *>(gen) ;
275      probingGen->setRowCuts(-3) ; }
276    model->addCutGenerator(gen,howOften[action],"Probing") ;
277    switches[genCnt++] = 0 ; }
278  action = ctlBlk->getGomory(gen) ;
279  if (action != CbcGenCtlBlk::CGOff)
280  { model->addCutGenerator(gen,howOften[action],"Gomory") ;
281    switches[genCnt++] = -1 ; }
282  action = ctlBlk->getKnapsack(gen) ;
283  if (action != CbcGenCtlBlk::CGOff)
284  { model->addCutGenerator(gen,howOften[action],"Knapsack") ;
285    switches[genCnt++] = 0 ; }
286  action = ctlBlk->getRedSplit(gen) ;
287  if (action != CbcGenCtlBlk::CGOff)
288  { model->addCutGenerator(gen,howOften[action],"RedSplit") ;
289    switches[genCnt++] = 1 ; }
290  action = ctlBlk->getClique(gen) ;
291  if (action != CbcGenCtlBlk::CGOff)
292  { model->addCutGenerator(gen,howOften[action],"Clique") ;
293    switches[genCnt++] = 0 ; }
294  action = ctlBlk->getMir(gen) ;
295  if (action != CbcGenCtlBlk::CGOff)
296  { model->addCutGenerator(gen,howOften[action],"MIR2") ;
297    switches[genCnt++] = -1 ; }
298  action = ctlBlk->getFlow(gen) ;
299  if (action != CbcGenCtlBlk::CGOff)
300  { model->addCutGenerator(gen,howOften[action],"Flow") ;
301    switches[genCnt++] = 1 ; }
302  action = ctlBlk->getTwomir(gen) ;
303  if (action != CbcGenCtlBlk::CGOff)
304  { model->addCutGenerator(gen,howOften[action],"2-MIR") ;
305    switches[genCnt++] = 1 ; }
306/*
307  Set control parameters on cut generators. cutDepth says `use this generator
308  when (depth in tree) mod cutDepth == 0'. setSwitchOffIfLessThan says `switch
309  this generator off if the number of cuts at the root is less than the given
310  value'. Sort of. I need to document the magic numbers for howOften , etc.
311*/
312  genCnt = model->numberCutGenerators() ;
313  int iGen ;
314  for (iGen = 0 ; iGen < genCnt ; iGen++)
315  { CbcCutGenerator *generator = model->cutGenerator(iGen) ;
316    int howOften = generator->howOften() ;
317    if (howOften == -98 || howOften == -99) 
318    { generator->setSwitchOffIfLessThan(switches[iGen]) ; }
319    generator->setTiming(true) ;
320    int cutDepth = ctlBlk->getCutDepth() ;
321    if (cutDepth >= 0)
322    { generator->setWhatDepth(cutDepth) ; } }
323/*
324  Now some additional control parameters that affect cut generation activity.
325
326  Minimum drop is the minimum objective degradation required to continue with
327  cut passes.  We want at least .05 unless the objective is tiny, in which
328  case we'll drop down to a floor of .0001.
329*/
330  { double objFrac = fabs(model->getMinimizationObjValue())*.001+.0001 ;
331    double minDrop = min(.05,objFrac) ;
332    model->setMinimumDrop(minDrop) ; }
333/*
334  Set the maximum number of rounds of cut generation at the root and at nodes
335  in the tree. If the value is positive, cut generation will terminate early
336  if the objective degradation doesn't meet the minimum drop requirement. If
337  the value is negatie, minimum drop is not considered.
338
339  At the root, for small problems, push for 100 passes (really we're betting
340  that we'll stop because no cuts were generated). For medium size problems,
341  the same but say we can quit if we're not achieving the minimum drop.  For
342  big problems, cut the number of rounds to 20.  The user may have expressed
343  an opinion; if so, it's already set.
344
345  Once we're in the tree, aim for one pass per activation.
346*/
347  if (ctlBlk->setByUser_[CbcCbcParam::CUTPASS] == false)
348  { int numCols = model->getNumCols() ;
349    if (numCols < 500)
350      model->setMaximumCutPassesAtRoot(-100) ;
351    else
352    if (numCols < 5000)
353      model->setMaximumCutPassesAtRoot(100) ;
354    else
355      model->setMaximumCutPassesAtRoot(20) ; }
356
357  model->setMaximumCutPasses(1) ;
358
359  return ; }
360
361/*
362  Install `objects' (integers, SOS sets, etc.) in the OSI. Cribbed from
363  CoinSolve 061216 and subjected to moderate rewriting. A substantial amount
364  of code that's only relevant for AMPL has been deleted. We're only supporting
365  OsiObjects in cbc-generic.
366*/
367
368void setupObjects (OsiSolverInterface *osi,
369                   bool didIPP, CglPreProcess *ippObj)
370
371{ int numInts = osi->getNumIntegers() ;
372  int numObjs = osi->numberObjects() ;
373/*
374  Does this OSI have defined objects already? If not, we'd best define the
375  basic integer objects.
376*/
377  if (numInts == 0 || numObjs == 0)
378  { osi->findIntegers(false) ;
379    numInts = osi->getNumIntegers() ;
380    numObjs = osi->numberObjects() ; }
381/*
382  If we did preprocessing and discovered SOS sets, create SOS objects and
383  install them in the OSI. The priority of SOS objects is set so that larger
384  sets have higher (lower numeric value) priority. The priority of the
385  original objects is reset to be lower than the priority of any SOS object.
386  Since the SOS objects are copied into the OSI, we need to delete our
387  originals once they've been installed.
388
389  It's not clear to me that this is the right thing to do, particularly if
390  the OSI comes equipped with complex objects.  -- lh, 061216 --
391*/
392  if (didIPP && ippObj->numberSOS())
393  { OsiObject **oldObjs = osi->objects() ;
394    int numCols = osi->getNumCols() ;
395
396    for (int iObj = 0 ; iObj < numObjs ; iObj++)
397    { oldObjs[iObj]->setPriority(numCols+1) ; }
398
399    int numSOS = ippObj->numberSOS() ;
400    OsiObject **sosObjs = new OsiObject *[numSOS] ;
401    const int *starts = ippObj->startSOS() ;
402    const int *which = ippObj->whichSOS() ;
403    const int *type = ippObj->typeSOS() ;
404    const double *weight = ippObj->weightSOS() ;
405    int iSOS ;
406    for (iSOS = 0 ; iSOS < numSOS ; iSOS++)
407    { int iStart = starts[iSOS] ;
408      int sosLen = starts[iSOS+1]-iStart ;
409      sosObjs[iSOS] =
410          new OsiSOS(osi,sosLen,which+iStart,weight+iStart,type[iSOS]) ;
411      sosObjs[iSOS]->setPriority(numCols-sosLen) ; }
412    osi->addObjects(numSOS,sosObjs) ;
413
414    for (iSOS = 0 ; iSOS < numSOS ; iSOS++)
415      delete sosObjs[iSOS] ;
416    delete [] sosObjs ; }
417
418  return ; }
419
420} // end local namespace
421
422
423namespace CbcGenParamUtils
424{
425
426/*
427  Run branch-and-cut.
428*/
429
430int doBaCParam (CoinParam *param)
431
432{ assert (param != 0) ;
433  CbcGenParam *genParam = dynamic_cast<CbcGenParam *>(param) ;
434  assert (genParam != 0) ;
435  CbcGenCtlBlk *ctlBlk = genParam->obj() ;
436  assert (ctlBlk != 0) ;
437  CbcModel *model = ctlBlk->model_ ;
438  assert (model != 0) ;
439/*
440  Setup to return nonfatal/fatal error (1/-1) by default.
441*/
442  int retval ;
443  if (CoinParamUtils::isInteractive())
444  { retval = 1 ; }
445  else
446  { retval = -1 ; }
447  ctlBlk->setBaBStatus(CbcGenCtlBlk::BACAbandon,CbcGenCtlBlk::BACmInvalid,
448                       CbcGenCtlBlk::BACwNotStarted,false,0) ;
449/*
450  We ain't gonna do squat without a good model.
451*/
452  if (!ctlBlk->goodModel_)
453  { std::cout << "** Current model not valid!" << std::endl ;
454    return (retval) ; }
455/*
456  Start the clock ticking.
457*/
458  double time1 = CoinCpuTime() ;
459  double time2 ;
460/*
461  Create a clone of the model which we can modify with impunity. Extract
462  the underlying solver for convenient access.
463*/
464  CbcModel babModel(*model) ;
465  OsiSolverInterface *babSolver = babModel.solver() ;
466  assert (babSolver != 0) ;
467# if CBC_TRACK_SOLVERS > 0
468  std::cout
469    << "doBaCParam: initial babSolver is "
470    << std::hex << babSolver << std::dec
471    << ", log level " << babSolver->messageHandler()->logLevel()
472    << "." << std::endl ;
473# endif
474/*
475  Solve the root relaxation. Bail unless it solves to optimality.
476*/
477  if (!solveRelaxation(&babModel))
478  { ctlBlk->setBaBStatus(&babModel,CbcGenCtlBlk::BACwBareRoot) ;
479    return (0) ; }
480# if COIN_CBC_VERBOSITY > 0
481  std::cout
482    << "doBaCParam: initial relaxation z = "
483    << babSolver->getObjValue() << "." << std::endl ;
484# endif
485/*
486  Are we up for fixing variables based on reduced cost alone?
487*/
488  if (ctlBlk->djFix_.action_ == true)
489  { reducedCostHack(babSolver,ctlBlk->djFix_.threshold_) ; }
490/*
491  Time to consider preprocessing. We'll do a bit of setup before getting to
492  the meat of the issue.
493
494  preIppSolver will hold a clone of the unpreprocessed constraint system.
495  We'll need it when we postprocess. ippSolver holds the preprocessed
496  constraint system.  Again, we clone it and give the clone to babModel for
497  B&C. Presumably we need an unmodified copy of the preprocessed system to
498  do postprocessing, but the copy itself is hidden inside the preprocess
499  object.
500*/
501  OsiSolverInterface *preIppSolver = 0 ;
502  CglPreProcess ippObj ;
503  bool didIPP = false ;
504
505  int numberChanged = 0 ;
506  int numberOriginalColumns = babSolver->getNumCols() ;
507  CbcGenCtlBlk::IPPControl ippAction = ctlBlk->getIPPAction() ;
508
509  if (!(ippAction == CbcGenCtlBlk::IPPOff ||
510        ippAction == CbcGenCtlBlk::IPPStrategy))
511  { double timeLeft = babModel.getMaximumSeconds() ;
512    preIppSolver = babSolver->clone() ;
513    OsiSolverInterface *ippSolver ;
514#   if CBC_TRACK_SOLVERS > 0
515    std::cout
516      << "doBaCParam: clone made prior to IPP is "
517      << std::hex << preIppSolver << std::dec
518      << ", log level " << preIppSolver->messageHandler()->logLevel()
519      << "." << std::endl ;
520#   endif
521
522    preIppSolver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo) ;
523    ippObj.messageHandler()->setLogLevel(babModel.logLevel()) ;
524   
525    CglProbing probingGen ;
526    probingGen.setUsingObjective(true) ;
527    probingGen.setMaxPass(3) ;
528    probingGen.setMaxProbeRoot(preIppSolver->getNumCols()) ;
529    probingGen.setMaxElements(100) ;
530    probingGen.setMaxLookRoot(50) ;
531    probingGen.setRowCuts(3) ;
532    ippObj.addCutGenerator(&probingGen) ;
533/*
534  For preProcessNonDefault, the 2nd parameter controls the conversion of
535  clique and SOS constraints. 0 does nothing, -1 converts <= to ==, and
536  2 and 3 form SOS sets under strict and not-so-strict conditions,
537  respectively.
538*/
539    int convert = 0 ;
540    if (ippAction == CbcGenCtlBlk::IPPEqual)
541    { convert = -1 ; }
542    else
543    if (ippAction == CbcGenCtlBlk::IPPEqualAll)
544    { convert = -2 ; }
545    else
546    if (ippAction == CbcGenCtlBlk::IPPSOS)
547    { convert = 2 ; }
548    else
549    if (ippAction == CbcGenCtlBlk::IPPTrySOS)
550    { convert = 3 ; }
551
552    ippSolver = ippObj.preProcessNonDefault(*preIppSolver,convert,10) ;
553#   if CBC_TRACK_SOLVERS > 0
554    std::cout
555      << "doBaCParam: solver returned from IPP is "
556      << std::hex << ippSolver << std::dec ;
557    if (ippSolver)
558    { std::cout
559        << ", log level " << ippSolver->messageHandler()->logLevel() ; }
560    std::cout << "." << std::endl ;
561#   endif
562/*
563  ippSolver == 0 is success of a sort --- integer preprocess has found the
564  problem to be infeasible or unbounded. Need to think about how to indicate
565  status.
566*/
567    if (!ippSolver)
568    { std::cout
569        << "Integer preprocess says infeasible or unbounded" << std::endl ;
570      delete preIppSolver ;
571      ctlBlk->setBaBStatus(&babModel,CbcGenCtlBlk::BACwIPP) ;
572      return (0) ; }
573#   if COIN_CBC_VERBOSITY > 0
574    else
575    { std::cout
576        << "After integer preprocessing, model has "
577        << ippSolver->getNumRows()
578        << " rows, " << ippSolver->getNumCols() << " columns, and "
579        << ippSolver->getNumElements() << " elements." << std::endl ; }
580#   endif
581
582    preIppSolver->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo) ;
583    ippSolver->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo) ;
584
585    if (ippAction == CbcGenCtlBlk::IPPSave)
586    { ippSolver->writeMps("presolved","mps",1.0) ;
587      std::cout
588        << "Integer preprocessed model written to `presolved.mps' "
589        << "as minimisation problem." << std::endl ; }
590   
591    OsiSolverInterface *osiTmp = ippSolver->clone() ;
592    babModel.assignSolver(osiTmp) ;
593    babSolver = babModel.solver() ;
594#   if CBC_TRACK_SOLVERS > 0
595    std::cout
596      << "doBaCParam: clone of IPP solver passed to babModel is "
597      << std::hex << babSolver << std::dec
598      << ", log level " << babSolver->messageHandler()->logLevel()
599      << "." << std::endl ;
600#   endif
601    if (!solveRelaxation(&babModel))
602    { delete preIppSolver ;
603      ctlBlk->setBaBStatus(&babModel,CbcGenCtlBlk::BACwIPPRelax) ;
604      return (0) ; }
605#   if COIN_CBC_VERBOSITY > 0
606    std::cout
607      << "doBaCParam: presolved relaxation z = "
608      << babSolver->getObjValue() << "." << std::endl ;
609#   endif
610    babModel.setMaximumSeconds(timeLeft-(CoinCpuTime()-time1)) ;
611    didIPP = true ; }
612/*
613  At this point, babModel and babSolver hold the constraint system we'll use
614  for B&C (either the original system or the preprocessed system) and we have
615  a solution to the lp relaxation.
616
617  If we're using the COSTSTRATEGY option, set up priorities here and pass
618  them to the babModel.
619*/
620  if (ctlBlk->priorityAction_ != CbcGenCtlBlk::BPOff)
621  { setupPriorities(&babModel,ctlBlk->priorityAction_) ; }
622/*
623  Install heuristics and cutting planes.
624*/
625  installHeuristics(ctlBlk,&babModel) ;
626  installCutGenerators(ctlBlk,&babModel) ;
627/*
628  Set up status print frequency for babModel.
629*/
630  if (babModel.getNumCols() > 2000 || babModel.getNumRows() > 1500 ||
631      babModel.messageHandler()->logLevel() > 1)
632    babModel.setPrintFrequency(100) ;
633/*
634  If we've read in a known good solution for debugging, activate the row cut
635  debugger.
636*/
637  if (ctlBlk->debugSol_.values_)
638  { if (ctlBlk->debugSol_.numCols_ == babModel.getNumCols())
639    { babSolver->activateRowCutDebugger(ctlBlk->debugSol_.values_) ; }
640    else
641    { std::cout
642        << "doBaCParam: debug file has incorrect number of columns."
643        << std::endl ; } }
644/*
645  Set ratio-based integrality gap, if specified by user.
646*/
647  if (ctlBlk->setByUser_[CbcCbcParam::GAPRATIO] == true)
648  { double obj = babSolver->getObjValue() ;
649    double gapRatio = babModel.getDblParam(CbcModel::CbcAllowableFractionGap) ;
650    double gap = gapRatio*(1.0e-5+fabs(obj)) ;
651    babModel.setAllowableGap(gap) ;
652    std::cout
653      << "doBaCParam: Continuous objective = " << obj
654      << ", so allowable gap set to " << gap << std::endl ; }
655/*
656  A bit of mystery code. As best I can figure, setSpecialOptions(2) suppresses
657  the removal of warm start information when checkSolution runs an lp to check
658  a solution. John's comment, ``probably faster to use a basis to get integer
659  solutions'' makes some sense in this context. Didn't try to track down
660  moreMipOptions just yet.
661*/
662  babModel.setSpecialOptions(babModel.specialOptions()|2) ;
663/*
664  { int ndx = whichParam(MOREMIPOPTIONS,numberParameters,parameters) ;
665    int moreMipOptions = parameters[ndx].intValue() ;
666    if (moreMipOptions >= 0)
667    { printf("more mip options %d\n",moreMipOptions);
668      babModel.setSearchStrategy(moreMipOptions); } }
669*/
670/*
671  Begin the final run-up to branch-and-cut.
672
673  Make sure that objects are set up in the solver. It's possible that whoever
674  loaded the model into the solver also set up objects. But it's also
675  entirely likely that none exist to this point (and interesting to note that
676  IPP doesn't need to know anything about objects).
677*/
678  setupObjects(babSolver,didIPP,&ippObj) ;
679/*
680  Set the branching method. We can't do this until we establish objects,
681  because the constructor will set up arrays based on the number of objects,
682  and there's no provision to set this information after creation. Arguably not
683  good --- it'd be nice to set this in the prototype model that's cloned for
684  this routine. In CoinSolve, shadowPriceMode is handled with the TESTOSI
685  option.
686*/
687  OsiChooseStrong strong(babSolver) ;
688  strong.setNumberBeforeTrusted(babModel.numberBeforeTrust()) ;
689  strong.setNumberStrong(babModel.numberStrong()) ;
690  strong.setShadowPriceMode(ctlBlk->chooseStrong_.shadowPriceMode_) ;
691  CbcBranchDefaultDecision decision ;
692  decision.setChooseMethod(strong) ;
693  babModel.setBranchingMethod(decision) ;
694/*
695  Here I've deleted a huge block of code that deals with external priorities,
696  branch direction, pseudocosts, and solution. (PRIORITYIN) Also a block of
697  code that generates C++ code.
698*/
699/*
700  Set up strategy for branch-and-cut. Note that the integer code supplied to
701  setupPreProcessing is *not* compatible with the IPPAction enum. But at least
702  it's documented. See desiredPreProcess_ in CbcStrategyDefault. `1' is
703  accidentally equivalent to IPPOn.
704*/
705
706  if (ippAction == CbcGenCtlBlk::IPPStrategy)
707  { CbcStrategyDefault strategy(true,5,5) ;
708    strategy.setupPreProcessing(1) ;
709    babModel.setStrategy(strategy) ; }
710/*
711  Yes! At long last, we're ready for the big call. Do branch and cut. In
712  general, the solver used to return the solution will not be the solver we
713  passed in, so reset babSolver here.
714*/
715  int statistics = (ctlBlk->printOpt_ > 0) ? ctlBlk->printOpt_ : 0 ;
716# if CBC_TRACK_SOLVERS > 0
717  std::cout
718    << "doBaCParam: solver at call to branchAndBound is "
719    << std::hex << babModel.solver() << std::dec
720    << ", log level " << babModel.solver()->messageHandler()->logLevel()
721    << "." << std::endl ;
722# endif
723  babModel.branchAndBound(statistics) ;
724  babSolver = babModel.solver() ;
725# if CBC_TRACK_SOLVERS > 0
726  std::cout
727    << "doBaCParam: solver at return from branchAndBound is "
728    << std::hex << babModel.solver() << std::dec
729    << ", log level " << babModel.solver()->messageHandler()->logLevel()
730    << "." << std::endl ;
731# endif
732/*
733  Write out solution to preprocessed model.
734*/
735  if (ctlBlk->debugCreate_ == "createAfterPre" &&
736      babModel.bestSolution())
737  { CbcGenParamUtils::saveSolution(babSolver,"debug.file") ; }
738/*
739  Print some information about branch-and-cut.
740*/
741# if COIN_CBC_VERBOSITY > 0
742  std::cout
743    << "Cuts at root node changed objective from "
744    << babModel.getContinuousObjective()
745    << " to " << babModel.rootObjectiveAfterCuts() << std::endl ;
746 
747  for (int iGen = 0 ; iGen < babModel.numberCutGenerators() ; iGen++)
748  { CbcCutGenerator *generator = babModel.cutGenerator(iGen) ;
749    std::cout
750      << generator->cutGeneratorName() << " was tried "
751      << generator->numberTimesEntered() << " times and created "
752      << generator->numberCutsInTotal() << " cuts of which "
753      << generator->numberCutsActive()
754      << " were active after adding rounds of cuts" ;
755    if (generator->timing())
756    { std::cout << " ( " << generator->timeInCutGenerator() << " seconds)" ; }
757    std::cout << std::endl ; }
758# endif
759
760  time2 = CoinCpuTime();
761  ctlBlk->totalTime_ += time2-time1;
762/*
763  If we performed integer preprocessing, time to back it out.
764*/
765  if (ippAction != CbcGenCtlBlk::IPPOff)
766  { 
767#   if CBC_TRACK_SOLVERS > 0
768    std::cout
769      << "doBaCParam: solver passed to IPP postprocess is "
770      << std::hex << babSolver << std::dec << "." << std::endl ;
771#   endif
772    ippObj.postProcess(*babSolver);
773    babModel.assignSolver(preIppSolver) ;
774    babSolver = babModel.solver() ;
775#   if CBC_TRACK_SOLVERS > 0
776    std::cout
777      << "doBaCParam: solver in babModel after IPP postprocess is "
778      << std::hex << babSolver << std::dec << "." << std::endl ;
779#   endif
780  }
781/*
782  Write out postprocessed solution to debug file, if requested.
783*/
784  if (ctlBlk->debugCreate_ == "create" && babModel.bestSolution())
785  { CbcGenParamUtils::saveSolution(babSolver,"debug.file") ; }
786/*
787  If we have a good solution, detach the solver with the answer. Fill in the
788  rest of the status information for the benefit of the wider world.
789*/
790  bool keepAnswerSolver = false ;
791  OsiSolverInterface *answerSolver = 0 ;
792  if (babModel.bestSolution())
793  { babModel.setModelOwnsSolver(false) ;
794    keepAnswerSolver = true ;
795    answerSolver = babSolver ; }
796  ctlBlk->setBaBStatus(&babModel,CbcGenCtlBlk::BACwBAC,
797                       keepAnswerSolver,answerSolver) ;
798/*
799  And one last bit of information & statistics.
800*/
801  ctlBlk->printBaBStatus() ;
802  std::cout << "    " ;
803  if (keepAnswerSolver)
804  { std::cout
805    << "objective " << babModel.getObjValue() << "; " ; }
806  std::cout
807    << babModel.getNodeCount() << " nodes and "
808    << babModel.getIterationCount() << " iterations - took "
809    << time2-time1 << " seconds" << std::endl ;
810
811  return (0) ; }
812
813} // end namespace CbcGenParamutils
Note: See TracBrowser for help on using the repository browser.