source: trunk/Cbc/src/CbcStrategy.cpp @ 1521

Last change on this file since 1521 was 1521, checked in by lou, 8 years ago

Changes to externals to make it easier to generate a new stable. Catches a few
changes in comments down in src.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 36.2 KB
Line 
1/* $Id: CbcStrategy.cpp 1521 2010-11-04 16:16:21Z lou $ */
2// Copyright (C) 2005, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#if defined(_MSC_VER)
5// Turn off compiler warning about long names
6#  pragma warning(disable:4786)
7#endif
8
9#include "CbcConfig.h"
10
11#include <cassert>
12#include <cstdlib>
13#include <cmath>
14#include <cfloat>
15
16#include "OsiSolverInterface.hpp"
17#ifdef COIN_HAS_CLP
18#include "OsiClpSolverInterface.hpp"
19#endif
20#include "CbcModel.hpp"
21#include "CbcMessage.hpp"
22#include "CbcStrategy.hpp"
23#include "CbcCutGenerator.hpp"
24#include "CbcBranchActual.hpp"
25#include "CbcNode.hpp"
26#include "CoinWarmStart.hpp"
27#include "CglPreProcess.hpp"
28// Cuts
29
30#include "CglGomory.hpp"
31#include "CglProbing.hpp"
32#include "CglKnapsackCover.hpp"
33#include "CglOddHole.hpp"
34#include "CglClique.hpp"
35#include "CglFlowCover.hpp"
36#include "CglMixedIntegerRounding2.hpp"
37
38// Heuristics
39
40#include "CbcHeuristic.hpp"
41#include "CbcHeuristicLocal.hpp"
42
43// Default Constructor
44CbcStrategy::CbcStrategy()
45        : depth_(0),
46        preProcessState_(0),
47        process_(NULL)
48{
49}
50
51// Destructor
52CbcStrategy::~CbcStrategy ()
53{
54    delete process_;
55}
56// Delete pre-processing object to save memory
57void
58CbcStrategy::deletePreProcess()
59{
60    delete process_;
61    process_ = NULL;
62}
63// Return a new Full node information pointer (descendant of CbcFullNodeInfo)
64CbcNodeInfo *
65CbcStrategy::fullNodeInfo(CbcModel * model, int numberRowsAtContinuous) const
66{
67    return new CbcFullNodeInfo(model, numberRowsAtContinuous);
68}
69// Return a new Partial node information pointer (descendant of CbcPartialNodeInfo)
70CbcNodeInfo *
71CbcStrategy::partialNodeInfo(CbcModel * /*model*/,
72                             CbcNodeInfo * parent, CbcNode * owner,
73                             int numberChangedBounds, const int * variables,
74                             const double * boundChanges,
75                             const CoinWarmStartDiff *basisDiff) const
76{
77    return new CbcPartialNodeInfo(parent, owner, numberChangedBounds, variables,
78                                  boundChanges, basisDiff);
79}
80/* After a CbcModel::resolve this can return a status
81   -1 no effect
82   0 treat as optimal
83   1 as 0 but do not do any more resolves (i.e. no more cuts)
84   2 treat as infeasible
85*/
86int
87CbcStrategy::status(CbcModel * /*model*/, CbcNodeInfo * /*parent*/,
88                    int /*whereFrom*/)
89{
90    return -1;
91}
92
93// Default Constructor
94CbcStrategyDefault::CbcStrategyDefault(int cutsOnlyAtRoot,
95                                       int numberStrong,
96                                       int numberBeforeTrust,
97                                       int printLevel)
98        : CbcStrategy(),
99        cutsOnlyAtRoot_(cutsOnlyAtRoot),
100        numberStrong_(numberStrong),
101        numberBeforeTrust_(numberBeforeTrust),
102        printLevel_(printLevel),
103        desiredPreProcess_(0),
104        preProcessPasses_(0)
105{
106}
107
108
109// Destructor
110CbcStrategyDefault::~CbcStrategyDefault ()
111{
112}
113
114// Clone
115CbcStrategy *
116CbcStrategyDefault::clone() const
117{
118    return new CbcStrategyDefault(*this);
119}
120
121// Copy constructor
122CbcStrategyDefault::CbcStrategyDefault(const CbcStrategyDefault & rhs)
123        :
124        CbcStrategy(rhs),
125        cutsOnlyAtRoot_(rhs.cutsOnlyAtRoot_),
126        numberStrong_(rhs.numberStrong_),
127        numberBeforeTrust_(rhs.numberBeforeTrust_),
128        printLevel_(rhs.printLevel_),
129        desiredPreProcess_(rhs.desiredPreProcess_),
130        preProcessPasses_(rhs.preProcessPasses_)
131{
132    setNested(rhs.getNested());
133}
134
135/*
136  Set up cut generators. Will instantiate Probing, Gomory, Knapsack, Clique,
137  FlowCover, and MIR2 generators. Probing should be the first in the vector
138  of generators as it tightens bounds on continuous variables.
139
140  Cut generators already installed will dominate cut generators instantiated
141  here.
142
143  There's a classic magic number overloaded parameter example here. The
144  variable genFlags below is interpreted as single-bit flags to control
145  whether a cut generator will be instantiated: Probing:1, Gomory:2,
146  Knapsack:4, Clique:8, FlowCover:16, MIR2:32. Normally it's hardcoded to 63.
147  If CBC_GENERATE_TEST is defined, and the model's node limit is set between
148  190000 and 190064, genFlags is loaded with the low-order bits.
149*/
150void
151CbcStrategyDefault::setupCutGenerators(CbcModel & model)
152{
153    if (cutsOnlyAtRoot_ < 0)
154        return; // no cuts wanted
155
156    // Magic number overloaded parameter -- see comment at head.
157    int genFlags = 63;
158#   ifdef CBC_GENERATE_TEST
159    int nNodes = model.getMaximumNodes();
160    if (nNodes >= 190000 && nNodes < 190064)
161        genFlags = nNodes - 190000;
162#   endif
163
164    CglProbing generator1;
165    generator1.setUsingObjective(true);
166    generator1.setMaxPass(1);
167    generator1.setMaxPassRoot(1);
168    // Number of unsatisfied variables to look at
169    generator1.setMaxProbe(10);
170    // How far to follow the consequences
171    generator1.setMaxLook(10);
172    // Only look at rows with fewer than this number of elements
173    generator1.setMaxElements(200);
174    generator1.setMaxElementsRoot(300);
175    //generator1.setRowCuts(3);
176
177    CglGomory generator2;
178    // try larger limit
179    generator2.setLimit(300);
180
181    CglKnapsackCover generator3;
182
183    //CglOddHole generator4;
184    //generator4.setMinimumViolation(0.005);
185    //generator4.setMinimumViolationPer(0.00002);
186    // try larger limit
187    //generator4.setMaximumEntries(200);
188
189    CglClique generator5;
190    generator5.setStarCliqueReport(false);
191    generator5.setRowCliqueReport(false);
192
193    CglMixedIntegerRounding2 mixedGen;
194    CglFlowCover flowGen;
195
196    /*
197      Add in generators. Do not override generators already installed.
198    */
199    int setting = cutsOnlyAtRoot_ ? -99 : -1;
200    int numberGenerators = model.numberCutGenerators();
201    int iGenerator;
202    bool found;
203    found = false;
204    for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
205        CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
206        CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
207        if (cgl) {
208            found = true;
209            break;
210        }
211    }
212    if (!found && (genFlags&1) != 0)
213        model.addCutGenerator(&generator1, setting, "Probing");
214    found = false;
215
216    for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
217        CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
218        CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
219        if (cgl) {
220            found = true;
221            break;
222        }
223    }
224    if (!found && (genFlags&2) != 0)
225        model.addCutGenerator(&generator2, setting, "Gomory");
226
227    found = false;
228    for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
229        CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
230        CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
231        if (cgl) {
232            found = true;
233            break;
234        }
235    }
236    if (!found && (genFlags&4) != 0)
237        model.addCutGenerator(&generator3, setting, "Knapsack");
238    //model.addCutGenerator(&generator4,setting,"OddHole");
239
240    found = false;
241    for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
242        CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
243        CglClique * cgl = dynamic_cast<CglClique *>(generator);
244        if (cgl) {
245            found = true;
246            break;
247        }
248    }
249    if (!found && (genFlags&8) != 0)
250        model.addCutGenerator(&generator5, setting, "Clique");
251
252    found = false;
253    for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
254        CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
255        CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
256        if (cgl) {
257            found = true;
258            break;
259        }
260    }
261    if (!found && (genFlags&16) != 0)
262        model.addCutGenerator(&flowGen, setting, "FlowCover");
263
264    found = false;
265    for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
266        CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
267        CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
268        if (cgl) {
269            found = true;
270            break;
271        }
272    }
273    if (!found && (genFlags&32) != 0)
274        model.addCutGenerator(&mixedGen, setting, "MixedIntegerRounding2");
275
276    // Say we want timings
277    int newNumberGenerators = model.numberCutGenerators();
278    for (iGenerator = numberGenerators; iGenerator < newNumberGenerators; iGenerator++) {
279        CbcCutGenerator * generator = model.cutGenerator(iGenerator);
280        generator->setTiming(true);
281    }
282
283    // Caution! Undocumented magic numbers.
284    int currentPasses = model.getMaximumCutPassesAtRoot();
285    if (currentPasses >= 0) {
286        if (model.getNumCols() < 5000)
287            model.setMaximumCutPassesAtRoot(CoinMax(50, currentPasses)); // use minimum drop
288        else
289            model.setMaximumCutPassesAtRoot(CoinMax(20, currentPasses));
290    } else {
291        currentPasses = -currentPasses;
292        if (model.getNumCols() < 500)
293            model.setMaximumCutPassesAtRoot(-CoinMax(100, currentPasses)); // always do 100 if possible
294        else
295            model.setMaximumCutPassesAtRoot(-CoinMax(20, currentPasses));
296    }
297}
298// Setup heuristics
299void
300CbcStrategyDefault::setupHeuristics(CbcModel & model)
301{
302    // Allow rounding heuristic
303
304    CbcRounding heuristic1(model);
305    heuristic1.setHeuristicName("rounding");
306    int numberHeuristics = model.numberHeuristics();
307    int iHeuristic;
308    bool found;
309    found = false;
310    for (iHeuristic = 0; iHeuristic < numberHeuristics; iHeuristic++) {
311        CbcHeuristic * heuristic = model.heuristic(iHeuristic);
312        CbcRounding * cgl = dynamic_cast<CbcRounding *>(heuristic);
313        if (cgl) {
314            found = true;
315            break;
316        }
317    }
318    if (!found)
319        model.addHeuristic(&heuristic1);
320#ifdef JJF_ZERO
321    // Allow join solutions
322    CbcHeuristicLocal heuristic2(model);
323    heuristic2.setHeuristicName("join solutions");
324    heuristic2.setSearchType(1);
325    found = false;
326    for (iHeuristic = 0; iHeuristic < numberHeuristics; iHeuristic++) {
327        CbcHeuristic * heuristic = model.heuristic(iHeuristic);
328        CbcHeuristicLocal * cgl = dynamic_cast<CbcHeuristicLocal *>(heuristic);
329        if (cgl) {
330            found = true;
331            break;
332        }
333    }
334    if (!found)
335        model.addHeuristic(&heuristic2);
336#endif
337}
338// Do printing stuff
339void
340CbcStrategyDefault::setupPrinting(CbcModel & model, int modelLogLevel)
341{
342    if (!modelLogLevel) {
343        model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
344        model.messageHandler()->setLogLevel(0);
345        model.solver()->messageHandler()->setLogLevel(0);
346    } else if (modelLogLevel == 1) {
347        model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
348        model.messageHandler()->setLogLevel(1);
349        model.solver()->messageHandler()->setLogLevel(0);
350    } else {
351        model.messageHandler()->setLogLevel(CoinMax(2, model.messageHandler()->logLevel()));
352        model.solver()->messageHandler()->setLogLevel(CoinMax(1, model.solver()->messageHandler()->logLevel()));
353        model.setPrintFrequency(CoinMin(50, model.printFrequency()));
354    }
355}
356
357/*
358 Aside from setting CbcModel::numberStrong_ and numberBeforeTrust, the big
359 activity is integer preprocessing. Surely this code to do preprocessing
360 duplicates code to do preprocessing up in the solver main routine. Most of the
361 effort goes into manipulating SOS sets.
362*/
363// Other stuff e.g. strong branching
364void
365CbcStrategyDefault::setupOther(CbcModel & model)
366{
367    // See if preprocessing wanted
368    if (desiredPreProcess_) {
369        delete process_;
370        /*
371          Inaccurate as of 080122 --- assignSolver (below) can now be instructed not to
372          delete the existing solver when the preprocessed solver is assigned to the
373          model. 'Course, we do need to hold on to a pointer somewhere, and that must
374          be captured before this call.
375        */
376        // solver_ should have been cloned outside
377        CglPreProcess * process = new CglPreProcess();
378        // Pass in models message handler
379        process->passInMessageHandler(model.messageHandler());
380        OsiSolverInterface * solver = model.solver();
381#ifdef COIN_HAS_CLP
382        OsiClpSolverInterface * clpSolver = dynamic_cast< OsiClpSolverInterface*> (solver);
383        if (clpSolver && false) {
384            // see if all coefficients multiple of 0.01 (close enough)
385            CoinPackedMatrix * matrix = clpSolver->getModelPtr()->matrix();
386            double * element = matrix->getMutableElements();
387            //const int * row = matrix->getIndices();
388            const CoinBigIndex * columnStart = matrix->getVectorStarts();
389            const int * columnLength = matrix->getVectorLengths();
390            int numberInt = 0;
391            int numberNon = 0;
392            int numberClose = 0;
393            int numberColumns = clpSolver->getNumCols();
394            int iColumn;
395            for (iColumn = 0; iColumn < numberColumns; iColumn++) {
396                for (int j = columnStart[iColumn];
397                        j < columnStart[iColumn] + columnLength[iColumn]; j++) {
398                    //int iRow = row[j];
399                    double value1 = element[j];
400                    double value = fabs(value1);
401                    if (value > 1.0e7) {
402                        if (value != floor(value))
403                            numberNon++;
404                        else
405                            numberInt++;
406                    } else {
407                        int iValue = static_cast<int>( 100 * (value + 0.005));
408                        double value2 = iValue;
409                        if (value2 == 100.0*value) {
410                            numberInt++;
411                        } else if (fabs(value2 - 100.0*value) < 1.0e-5) {
412                            numberClose++;
413                        } else {
414                            numberNon++;
415                        }
416                    }
417                }
418            }
419            if (!numberNon && numberClose) {
420                printf("Tidying %d multiples of 0.01, %d close\n",
421                       numberInt, numberClose);
422                for (iColumn = 0; iColumn < numberColumns; iColumn++) {
423                    for (int j = columnStart[iColumn];
424                            j < columnStart[iColumn] + columnLength[iColumn]; j++) {
425                        //int iRow = row[j];
426                        double value1 = element[j];
427                        double value = fabs(value1);
428                        if (value < 1.0e7) {
429                            int iValue = static_cast<int>( 100 * (value + 0.005));
430                            double value2 = iValue;
431                            if (value2 != 100.0*value) {
432                                value2 *= 0.01;
433                                if (fabs(value - floor(value + 0.5)) <= 1.0e-7)
434                                    value2 = floor(value + 0.5);
435                                if (value1 < 0.0)
436                                    value2 = -value2;
437                                element[j] = value2;
438                            }
439                        }
440                    }
441                }
442            }
443        }
444#endif
445        {
446            // mark some columns as ineligible for presolve
447            int numberColumns = solver->getNumCols();
448            char * prohibited = new char[numberColumns];
449            memset(prohibited, 0, numberColumns);
450            int numberProhibited = 0;
451            /*
452              Create CbcSimpleInteger objects would be more accurate in the general
453              case.  The `false' parameter says we won't delete existing objects.
454
455              Only Clp will produce SOS objects in findIntegers (080122), and that's
456              where a possible conversion can occur. If clp is holding OsiSOS objects,
457              they'll be converted to CbcSOS objects.
458            */
459            // convert to Cbc integers
460            model.findIntegers(false);
461            int numberObjects = model.numberObjects();
462            if (numberObjects) {
463                OsiObject ** objects = model.objects();
464                for (int iObject = 0; iObject < numberObjects; iObject++) {
465                    CbcSOS * obj =
466                        dynamic_cast <CbcSOS *>(objects[iObject]) ;
467                    if (obj) {
468                        // SOS
469                        int n = obj->numberMembers();
470                        const int * which = obj->members();
471                        for (int i = 0; i < n; i++) {
472                            int iColumn = which[i];
473                            prohibited[iColumn] = 1;
474                            numberProhibited++;
475                        }
476                    }
477                }
478            }
479            if (numberProhibited)
480                process->passInProhibited(prohibited, numberColumns);
481            delete [] prohibited;
482        }
483        int logLevel = model.messageHandler()->logLevel();
484#ifdef COIN_HAS_CLP
485        //OsiClpSolverInterface * clpSolver = dynamic_cast< OsiClpSolverInterface*> (solver);
486        ClpSimplex * lpSolver = NULL;
487        if (clpSolver) {
488            if (clpSolver->messageHandler()->logLevel())
489                clpSolver->messageHandler()->setLogLevel(1);
490            if (logLevel > -1)
491                clpSolver->messageHandler()->setLogLevel(CoinMin(logLevel, clpSolver->messageHandler()->logLevel()));
492            lpSolver = clpSolver->getModelPtr();
493            /// If user left factorization frequency then compute
494            lpSolver->defaultFactorizationFrequency();
495        }
496#endif
497        // Tell solver we are in Branch and Cut
498        solver->setHintParam(OsiDoInBranchAndCut, true, OsiHintDo) ;
499        // Default set of cut generators
500        // Limited set that could reduce problem size (drop rows / fix values)
501        CglProbing generator1;
502        generator1.setUsingObjective(true);
503        generator1.setMaxPass(1);
504        generator1.setMaxPassRoot(1);
505        generator1.setMaxProbeRoot(CoinMin(3000, solver->getNumCols()));
506        generator1.setMaxProbeRoot(123);
507        generator1.setMaxElements(100);
508        generator1.setMaxElementsRoot(200);
509        generator1.setMaxLookRoot(50);
510        generator1.setRowCuts(3);
511        //generator1.messageHandler()->setLogLevel(logLevel);
512        // Not needed with pass in process->messageHandler()->setLogLevel(logLevel);
513        // Add in generators
514        process->addCutGenerator(&generator1);
515        int translate[] = {9999, 0, 2, -2, 3, 4, 4, 4};
516        OsiSolverInterface * solver2 =
517            process->preProcessNonDefault(*solver,
518                                          translate[desiredPreProcess_], preProcessPasses_, 6);
519        // Tell solver we are not in Branch and Cut
520        solver->setHintParam(OsiDoInBranchAndCut, false, OsiHintDo) ;
521        if (solver2)
522            solver2->setHintParam(OsiDoInBranchAndCut, false, OsiHintDo) ;
523        bool feasible = true;
524        if (!solver2) {
525            feasible = false;
526            //printf("Pre-processing says infeasible\n");
527            delete process;
528            preProcessState_ = -1;
529            process_ = NULL;
530        } else {
531            // now tighten bounds
532#ifdef COIN_HAS_CLP
533            if (clpSolver) {
534                // model has changed
535                solver = model.solver();
536                OsiClpSolverInterface * clpSolver = dynamic_cast< OsiClpSolverInterface*> (solver);
537                ClpSimplex * lpSolver = clpSolver->getModelPtr();
538                lpSolver->passInMessageHandler(solver->messageHandler());
539                if (lpSolver->tightenPrimalBounds() == 0) {
540                    lpSolver->dual();
541                } else {
542                    feasible = false;
543                }
544            }
545#endif
546            if (feasible) {
547                preProcessState_ = 1;
548                process_ = process;
549                /* Note that original solver will be kept (with false)
550                   and that final solver will also be kept.
551                   This is for post-processing
552
553                   Keep in mind when examining this that linear presolve does not
554                   understand SOS.
555                */
556                OsiSolverInterface * solver3 = solver2->clone();
557                model.assignSolver(solver3, false);
558                if (process_->numberSOS()) {
559                    int numberSOS = process_->numberSOS();
560                    int numberIntegers = model.numberIntegers();
561                    /* model may not have created objects
562                       If none then create
563                       NOTE - put back to original column numbers as
564                       CbcModel will pack down ALL as it doesn't know where from
565                    */
566                    bool someObjects = model.numberObjects() > 0;
567                    if (!numberIntegers || !model.numberObjects()) {
568                        model.findIntegers(true);
569                        numberIntegers = model.numberIntegers();
570                    }
571                    OsiObject ** oldObjects = model.objects();
572                    // Do sets and priorities
573                    OsiObject ** objects = new OsiObject * [numberSOS];
574                    // set old objects to have low priority
575                    int numberOldObjects = model.numberObjects();
576                    int numberColumns = model.getNumCols();
577                    for (int iObj = 0; iObj < numberOldObjects; iObj++) {
578                        int oldPriority = oldObjects[iObj]->priority();
579                        oldObjects[iObj]->setPriority(numberColumns + oldPriority);
580                    }
581                    const int * starts = process_->startSOS();
582                    const int * which = process_->whichSOS();
583                    const int * type = process_->typeSOS();
584                    const double * weight = process_->weightSOS();
585                    int iSOS;
586                    for (iSOS = 0; iSOS < numberSOS; iSOS++) {
587                        int iStart = starts[iSOS];
588                        int n = starts[iSOS+1] - iStart;
589                        objects[iSOS] = new CbcSOS(&model, n, which + iStart, weight + iStart,
590                                                   iSOS, type[iSOS]);
591                        // branch on long sets first
592                        objects[iSOS]->setPriority(numberColumns - n);
593                    }
594                    model.addObjects(numberSOS, objects);
595                    for (iSOS = 0; iSOS < numberSOS; iSOS++)
596                        delete objects[iSOS];
597                    delete [] objects;
598                    if (!someObjects) {
599                        // put back old column numbers
600                        const int * originalColumns = process_->originalColumns();
601                        // use reverse lookup to fake it
602                        int n = originalColumns[numberColumns-1] + 1;
603                        int * fake = new int[n];
604                        int i;
605                        // This was wrong (now is correct) - so could never have been called
606                        abort();
607                        for ( i = 0; i < n; i++)
608                            fake[i] = -1;
609                        for (i = 0; i < numberColumns; i++)
610                            fake[originalColumns[i]] = i;
611                        for (int iObject = 0; iObject < model.numberObjects(); iObject++) {
612                            // redo ids etc
613                            CbcSimpleInteger * obj =
614                                dynamic_cast <CbcSimpleInteger *>(model.modifiableObject(iObject)) ;
615                            if (obj) {
616                                obj->resetSequenceEtc(n, fake);
617                            } else {
618                                // redo ids etc
619                                CbcObject * obj =
620                                    dynamic_cast <CbcObject *>(model.modifiableObject(iObject)) ;
621                                assert (obj);
622                                obj->redoSequenceEtc(&model, n, fake);
623                            }
624                        }
625                        delete [] fake;
626                    }
627                }
628            } else {
629                //printf("Pre-processing says infeasible\n");
630                delete process;
631                preProcessState_ = -1;
632                process_ = NULL;
633            }
634        }
635    }
636    model.setNumberStrong(numberStrong_);
637    model.setNumberBeforeTrust(numberBeforeTrust_);
638}
639
640// Create C++ lines to get to current state
641void
642CbcStrategyDefault::generateCpp( FILE * fp)
643{
644    fprintf(fp, "0#include \"CbcStrategy.hpp\"\n");
645    fprintf(fp, "3  CbcStrategyDefault strategy(%s,%d,%d,%d);\n",
646            cutsOnlyAtRoot_ ? "1" : "0",
647            numberStrong_,
648            numberBeforeTrust_,
649            printLevel_);
650    fprintf(fp, "3  strategy.setupPreProcessing(%d,%d);\n",
651            desiredPreProcess_, preProcessPasses_);
652}
653// Default Constructor
654CbcStrategyDefaultSubTree::CbcStrategyDefaultSubTree(CbcModel * parent ,
655        int cutsOnlyAtRoot,
656        int numberStrong,
657        int numberBeforeTrust,
658        int printLevel)
659        : CbcStrategy(),
660        parentModel_(parent),
661        cutsOnlyAtRoot_(cutsOnlyAtRoot),
662        numberStrong_(numberStrong),
663        numberBeforeTrust_(numberBeforeTrust),
664        printLevel_(printLevel)
665{
666}
667
668
669// Destructor
670CbcStrategyDefaultSubTree::~CbcStrategyDefaultSubTree ()
671{
672}
673
674// Clone
675CbcStrategy *
676CbcStrategyDefaultSubTree::clone() const
677{
678    return new CbcStrategyDefaultSubTree(*this);
679}
680
681// Copy constructor
682CbcStrategyDefaultSubTree::CbcStrategyDefaultSubTree(const CbcStrategyDefaultSubTree & rhs)
683        :
684        CbcStrategy(rhs),
685        parentModel_(rhs.parentModel_),
686        cutsOnlyAtRoot_(rhs.cutsOnlyAtRoot_),
687        numberStrong_(rhs.numberStrong_),
688        numberBeforeTrust_(rhs.numberBeforeTrust_),
689        printLevel_(rhs.printLevel_)
690{
691    setNested(rhs.getNested());
692}
693
694// Setup cut generators
695void
696CbcStrategyDefaultSubTree::setupCutGenerators(CbcModel & model)
697{
698    // Set up some cut generators and defaults
699    if (cutsOnlyAtRoot_ < 0)
700        return; // no cuts wanted
701    // Probing first as gets tight bounds on continuous
702
703    CglProbing generator1;
704    generator1.setUsingObjective(true);
705    generator1.setMaxPass(1);
706    // Number of unsatisfied variables to look at
707    generator1.setMaxProbe(10);
708    // How far to follow the consequences
709    generator1.setMaxLook(10);
710    // Only look at rows with fewer than this number of elements
711    generator1.setMaxElements(200);
712    //generator1.setRowCuts(3);
713
714    CglGomory generator2;
715    // try larger limit
716    generator2.setLimit(300);
717
718    CglKnapsackCover generator3;
719
720    //CglOddHole generator4;
721    //generator4.setMinimumViolation(0.005);
722    //generator4.setMinimumViolationPer(0.00002);
723    // try larger limit
724    //generator4.setMaximumEntries(200);
725
726    CglClique generator5;
727    generator5.setStarCliqueReport(false);
728    generator5.setRowCliqueReport(false);
729
730    CglMixedIntegerRounding2 mixedGen;
731    CglFlowCover flowGen;
732
733    // Add in generators
734    int setting = cutsOnlyAtRoot_ ? -99 : -1;
735    int numberGenerators = model.numberCutGenerators();
736    int numberParentGenerators = parentModel_->numberCutGenerators();
737    int iGenerator;
738    bool found;
739    found = false;
740    int howOften = 0;
741    for (iGenerator = 0; iGenerator < numberParentGenerators; iGenerator++) {
742        CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
743        CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
744        if (cgl) {
745            found = true;
746            howOften = parentModel_->cutGenerator(iGenerator)->howOften();
747            break;
748        }
749    }
750
751    if (found && (howOften >= -1 || howOften == -98)) {
752        found = false;
753        for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
754            CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
755            CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
756            if (cgl) {
757                found = true;
758                break;
759            }
760        }
761        if (!found) {
762            if (howOften == -1)
763                howOften = -98;
764            else if (howOften == -98)
765                howOften = -99;
766            model.addCutGenerator(&generator1, setting, "Probing");
767            CbcCutGenerator * generator =
768                model.cutGenerator(numberGenerators);
769            generator->setHowOften(howOften);
770            numberGenerators++;
771        }
772    }
773    found = false;
774    for (iGenerator = 0; iGenerator < numberParentGenerators; iGenerator++) {
775        CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
776        CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
777        if (cgl) {
778            found = true;
779            howOften = parentModel_->cutGenerator(iGenerator)->howOften();
780            break;
781        }
782    }
783    if (found && howOften >= 0) {
784        found = false;
785        for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
786            CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
787            CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
788            if (cgl) {
789                found = true;
790                break;
791            }
792        }
793        if (!found)
794            model.addCutGenerator(&generator2, setting, "Gomory");
795    }
796    found = false;
797    for (iGenerator = 0; iGenerator < numberParentGenerators; iGenerator++) {
798        CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
799        CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
800        if (cgl) {
801            found = true;
802            howOften = parentModel_->cutGenerator(iGenerator)->howOften();
803            break;
804        }
805    }
806    if (found && howOften >= 0) {
807        found = false;
808        for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
809            CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
810            CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
811            if (cgl) {
812                found = true;
813                break;
814            }
815        }
816        if (!found)
817            model.addCutGenerator(&generator3, setting, "Knapsack");
818    }
819    found = false;
820    for (iGenerator = 0; iGenerator < numberParentGenerators; iGenerator++) {
821        CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
822        CglClique * cgl = dynamic_cast<CglClique *>(generator);
823        if (cgl) {
824            found = true;
825            howOften = parentModel_->cutGenerator(iGenerator)->howOften();
826            break;
827        }
828    }
829    if (found && howOften >= 0) {
830        found = false;
831        for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
832            CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
833            CglClique * cgl = dynamic_cast<CglClique *>(generator);
834            if (cgl) {
835                found = true;
836                break;
837            }
838        }
839        if (!found)
840            model.addCutGenerator(&generator5, setting, "Clique");
841    }
842    found = false;
843    for (iGenerator = 0; iGenerator < numberParentGenerators; iGenerator++) {
844        CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
845        CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
846        if (cgl) {
847            found = true;
848            howOften = parentModel_->cutGenerator(iGenerator)->howOften();
849            break;
850        }
851    }
852    if (found && howOften >= 0) {
853        found = false;
854        for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
855            CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
856            CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
857            if (cgl) {
858                found = true;
859                break;
860            }
861        }
862        if (!found)
863            model.addCutGenerator(&flowGen, setting, "FlowCover");
864        found = false;
865    }
866    for (iGenerator = 0; iGenerator < numberParentGenerators; iGenerator++) {
867        CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
868        CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
869        if (cgl) {
870            found = true;
871            howOften = parentModel_->cutGenerator(iGenerator)->howOften();
872            break;
873        }
874    }
875    if (found && howOften >= 0) {
876        found = false;
877        for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
878            CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
879            CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
880            if (cgl) {
881                found = true;
882                break;
883            }
884        }
885        if (!found)
886            model.addCutGenerator(&mixedGen, setting, "MixedIntegerRounding2");
887    }
888#ifdef JJF_ZERO
889    // Say we want timings
890    int newNumberGenerators = model.numberCutGenerators();
891    for (iGenerator = numberGenerators; iGenerator < newNumberGenerators; iGenerator++) {
892        CbcCutGenerator * generator = model.cutGenerator(iGenerator);
893        generator->setTiming(true);
894    }
895#endif
896    if (model.getNumCols() < -500)
897        model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
898    else if (model.getNumCols() < 5000)
899        model.setMaximumCutPassesAtRoot(100); // use minimum drop
900    else
901        model.setMaximumCutPassesAtRoot(20);
902}
903// Setup heuristics
904void
905CbcStrategyDefaultSubTree::setupHeuristics(CbcModel & model)
906{
907    // Allow rounding heuristic
908
909    CbcRounding heuristic1(model);
910    heuristic1.setHeuristicName("rounding");
911    int numberHeuristics = model.numberHeuristics();
912    int iHeuristic;
913    bool found;
914    found = false;
915    for (iHeuristic = 0; iHeuristic < numberHeuristics; iHeuristic++) {
916        CbcHeuristic * heuristic = model.heuristic(iHeuristic);
917        CbcRounding * cgl = dynamic_cast<CbcRounding *>(heuristic);
918        if (cgl) {
919            found = true;
920            break;
921        }
922    }
923    if (!found)
924        model.addHeuristic(&heuristic1);
925}
926// Do printing stuff
927void
928CbcStrategyDefaultSubTree::setupPrinting(CbcModel & model, int modelLogLevel)
929{
930    if (!modelLogLevel) {
931        model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
932        model.messageHandler()->setLogLevel(0);
933        model.solver()->messageHandler()->setLogLevel(0);
934    } else if (modelLogLevel == 1) {
935        model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
936        model.messageHandler()->setLogLevel(1);
937        model.solver()->messageHandler()->setLogLevel(0);
938    } else {
939        model.messageHandler()->setLogLevel(2);
940        model.solver()->messageHandler()->setLogLevel(1);
941        model.setPrintFrequency(50);
942    }
943}
944// Other stuff e.g. strong branching
945void
946CbcStrategyDefaultSubTree::setupOther(CbcModel & model)
947{
948    model.setNumberStrong(numberStrong_);
949    model.setNumberBeforeTrust(numberBeforeTrust_);
950}
951// For uniform setting of cut and heuristic options
952void
953setCutAndHeuristicOptions(CbcModel & model)
954{
955    int numberGenerators = model.numberCutGenerators();
956    int iGenerator;
957    for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
958        CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
959        CglProbing * cglProbing = dynamic_cast<CglProbing *>(generator);
960        if (cglProbing) {
961            cglProbing->setUsingObjective(1);
962            cglProbing->setMaxPass(1);
963            cglProbing->setMaxPassRoot(1);
964            // Number of unsatisfied variables to look at
965            cglProbing->setMaxProbe(10);
966            cglProbing->setMaxProbeRoot(50);
967            //cglProbing->setMaxProbeRoot(123);
968            // How far to follow the consequences
969            cglProbing->setMaxLook(5);
970            cglProbing->setMaxLookRoot(50);
971            cglProbing->setMaxLookRoot(10);
972            // Only look at rows with fewer than this number of elements
973            cglProbing->setMaxElements(200);
974            cglProbing->setMaxElementsRoot(300);
975            cglProbing->setRowCuts(3);
976        }
977#ifdef JJF_ZERO
978        CglGomory * cglGomory = dynamic_cast<CglGomory *>(generator);
979        if (cglGomory) {
980            // try larger limit
981            cglGomory->setLimitAtRoot(1000);
982            cglGomory->setLimit(50);
983        }
984        CglKnapsackCover * cglKnapsackCover = dynamic_cast<CglKnapsackCover *>(generator);
985        if (cglKnapsackCover) {
986        }
987#endif
988    }
989}
990
991
992
Note: See TracBrowser for help on using the repository browser.