source: trunk/Cbc/src/CbcGenBaB.cpp

Last change on this file was 2467, checked in by unxusr, 5 months ago

spaces after angles

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