source: trunk/Cbc/src/CbcGenBaB.cpp @ 1899

Last change on this file since 1899 was 1899, checked in by stefan, 6 years ago

fixup svn properties

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