source: stable/2.8/Cbc/src/CbcHeuristic.hpp @ 1917

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

sync with trunk rev 1882

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 22.2 KB
RevLine 
[1271]1/* $Id: CbcHeuristic.hpp 1883 2013-04-06 13:33:15Z tkr $ */
[2]2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
[1573]4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
[2]6#ifndef CbcHeuristic_H
7#define CbcHeuristic_H
8
9#include <string>
10#include <vector>
11#include "CoinPackedMatrix.hpp"
12#include "OsiCuts.hpp"
[841]13#include "CoinHelperFunctions.hpp"
[912]14#include "OsiBranchingObject.hpp"
[2]15
16class OsiSolverInterface;
17
18class CbcModel;
19
20//#############################################################################
[912]21
22class CbcHeuristicNodeList;
23class CbcBranchingObject;
24
25/** A class describing the branching decisions that were made to get
[1505]26    to the node where a heuristic was invoked from */
[912]27
28class CbcHeuristicNode {
29private:
[1286]30    void gutsOfConstructor(CbcModel& model);
31    CbcHeuristicNode();
32    CbcHeuristicNode& operator=(const CbcHeuristicNode&);
[912]33private:
[1286]34    /// The number of branching decisions made
35    int numObjects_;
36    /** The indices of the branching objects. Note: an index may be
37        listed multiple times. E.g., a general integer variable that has
38        been branched on multiple times. */
39    CbcBranchingObject** brObj_;
[912]40public:
[1286]41    CbcHeuristicNode(CbcModel& model);
[912]42
[1286]43    CbcHeuristicNode(const CbcHeuristicNode& rhs);
44    ~CbcHeuristicNode();
45    double distance(const CbcHeuristicNode* node) const;
46    double minDistance(const CbcHeuristicNodeList& nodeList) const;
47    bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList,
48                            const double threshold) const;
49    double avgDistance(const CbcHeuristicNodeList& nodeList) const;
[912]50};
51
52class CbcHeuristicNodeList {
53private:
[1286]54    void gutsOfDelete();
55    void gutsOfCopy(const CbcHeuristicNodeList& rhs);
[912]56private:
[1286]57    std::vector<CbcHeuristicNode*> nodes_;
[912]58public:
[1286]59    CbcHeuristicNodeList() {}
60    CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
61    CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
62    ~CbcHeuristicNodeList();
63
64    void append(CbcHeuristicNode*& node);
65    void append(const CbcHeuristicNodeList& nodes);
66    inline const CbcHeuristicNode* node(int i) const {
67        return nodes_[i];
68    }
69    inline int size() const {
[1505]70        return static_cast<int>(nodes_.size());
[1286]71    }
[912]72};
73
74//#############################################################################
[2]75/** Heuristic base class */
76
77class CbcHeuristic {
[912]78private:
[1286]79    void gutsOfDelete() {}
80    void gutsOfCopy(const CbcHeuristic & rhs);
[912]81
[2]82public:
[1286]83    // Default Constructor
84    CbcHeuristic ();
[2]85
[1286]86    // Constructor with model - assumed before cuts
87    CbcHeuristic (CbcModel & model);
[2]88
[1286]89    // Copy constructor
90    CbcHeuristic ( const CbcHeuristic &);
[2]91
[1286]92    virtual ~CbcHeuristic();
[640]93
[1286]94    /// Clone
95    virtual CbcHeuristic * clone() const = 0;
[640]96
[1286]97    /// Assignment operator
98    CbcHeuristic & operator=(const CbcHeuristic& rhs);
[6]99
[1286]100    /// update model (This is needed if cliques update matrix etc)
101    virtual void setModel(CbcModel * model);
[2]102
[1286]103    /// Resets stuff if model changes
104    virtual void resetModel(CbcModel * model) = 0;
[2]105
[1286]106    /** returns 0 if no solution, 1 if valid solution
107        with better objective value than one passed in
108        Sets solution values if good, sets objective value
109        This is called after cuts have been added - so can not add cuts
110    */
111    virtual int solution(double & objectiveValue,
112                         double * newSolution) = 0;
[72]113
[1286]114    /** returns 0 if no solution, 1 if valid solution, -1 if just
115        returning an estimate of best possible solution
116        with better objective value than one passed in
117        Sets solution values if good, sets objective value (only if nonzero code)
118        This is called at same time as cut generators - so can add cuts
119        Default is do nothing
120    */
121    virtual int solution2(double & /*objectiveValue*/,
122                          double * /*newSolution*/,
123                          OsiCuts & /*cs*/) {
124        return 0;
125    }
[2]126
[1286]127    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
128    virtual void validate() {}
[640]129
[1286]130    /** Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
131        If 10 added then don't worry if validate says there are funny objects
132        as user knows it will be fine
133    */
134    inline void setWhen(int value) {
135        when_ = value;
136    }
137    /// Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always
138    inline int when() const {
139        return when_;
140    }
[640]141
[1286]142    /// Sets number of nodes in subtree (default 200)
143    inline void setNumberNodes(int value) {
144        numberNodes_ = value;
145    }
146    /// Gets number of nodes in a subtree (default 200)
147    inline int numberNodes() const {
148        return numberNodes_;
149    }
150    /** Switches (does not apply equally to all heuristics)
151        1 bit - stop once allowable gap on objective reached
152        2 bit - always do given number of passes
153        4 bit - weaken cutoff by 5% every 50 passes?
154        8 bit - if has cutoff and suminf bobbling for 20 passes then
155                first try halving distance to best possible then
156                try keep halving distance to known cutoff
[1802]157        16 bit - needs new solution to run
[1286]158        1024 bit - stop all heuristics on max time
159    */
160    inline void setSwitches(int value) {
161        switches_ = value;
162    }
163    /** Switches (does not apply equally to all heuristics)
164        1 bit - stop once allowable gap on objective reached
165        2 bit - always do given number of passes
166        4 bit - weaken cutoff by 5% every 50 passes?
167        8 bit - if has cutoff and suminf bobbling for 20 passes then
168                first try halving distance to best possible then
169                try keep halving distance to known cutoff
[1802]170        16 bit - needs new solution to run
[1286]171        1024 bit - stop all heuristics on max time
172    */
173    inline int switches() const {
174        return switches_;
175    }
176    /// Whether to exit at once on gap
177    bool exitNow(double bestObjective) const;
178    /// Sets feasibility pump options (-1 is off)
179    inline void setFeasibilityPumpOptions(int value) {
180        feasibilityPumpOptions_ = value;
181    }
182    /// Gets feasibility pump options (-1 is off)
183    inline int feasibilityPumpOptions() const {
184        return feasibilityPumpOptions_;
185    }
186    /// Just set model - do not do anything else
187    inline void setModelOnly(CbcModel * model) {
188        model_ = model;
189    }
[197]190
[912]191
[1286]192    /// Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
193    inline void setFractionSmall(double value) {
194        fractionSmall_ = value;
195    }
196    /// Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
197    inline double fractionSmall() const {
198        return fractionSmall_;
199    }
200    /// Get how many solutions the heuristic thought it got
201    inline int numberSolutionsFound() const {
202        return numberSolutionsFound_;
203    }
204    /// Increment how many solutions the heuristic thought it got
205    inline void incrementNumberSolutionsFound() {
206        numberSolutionsFound_++;
207    }
208
209    /** Do mini branch and bound - return
210        0 not finished - no solution
211        1 not finished - solution
212        2 finished - no solution
213        3 finished - solution
214        (could add global cut if finished)
215        -1 returned on size
216        -2 time or user event
217    */
218    int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes,
219                            double * newSolution, double & newSolutionValue,
220                            double cutoff , std::string name) const;
221    /// Create C++ lines to get to current state
222    virtual void generateCpp( FILE * ) {}
223    /// Create C++ lines to get to current state - does work for base class
224    void generateCpp( FILE * fp, const char * heuristic) ;
225    /// Returns true if can deal with "odd" problems e.g. sos type 2
226    virtual bool canDealWithOdd() const {
227        return false;
228    }
229    /// return name of heuristic
230    inline const char *heuristicName() const {
231        return heuristicName_.c_str();
232    }
233    /// set name of heuristic
234    inline void setHeuristicName(const char *name) {
235        heuristicName_ = name;
236    }
237    /// Set random number generator seed
238    void setSeed(int value);
[1883]239    /// Get random number generator seed
240    int getSeed() const;
[1286]241    /// Sets decay factor (for howOften) on failure
242    inline void setDecayFactor(double value) {
243        decayFactor_ = value;
244    }
245    /// Set input solution
246    void setInputSolution(const double * solution, double objValue);
247    /* Runs if bit set
248        0 - before cuts at root node (or from doHeuristics)
249        1 - during cuts at root
250        2 - after root node cuts
251        3 - after cuts at other nodes
252        4 - during cuts at other nodes
253            8 added if previous heuristic in loop found solution
254     */
255    inline void setWhereFrom(int value) {
256        whereFrom_ = value;
257    }
[1564]258    inline int whereFrom() const {
259        return whereFrom_;
260    }
[1286]261    /** Upto this depth we call the tree shallow and the heuristic can be called
262        multiple times. That is, the test whether the current node is far from
263        the others where the jeuristic was invoked will not be done, only the
264        frequency will be tested. After that depth the heuristic will can be
265        invoked only once per node, right before branching. That's when it'll be
266        tested whether the heur should run at all. */
267    inline void setShallowDepth(int value) {
268        shallowDepth_ = value;
269    }
270    /** How often to invoke the heuristics in the shallow part of the tree */
271    inline void setHowOftenShallow(int value) {
272        howOftenShallow_ = value;
273    }
274    /** How "far" should this node be from every other where the heuristic was
275        run in order to allow the heuristic to run in this node, too. Currently
276        this is tested, but we may switch to avgDistanceToRun_ in the future. */
277    inline void setMinDistanceToRun(int value) {
278        minDistanceToRun_ = value;
279    }
280
281    /** Check whether the heuristic should run at all
282        0 - before cuts at root node (or from doHeuristics)
283        1 - during cuts at root
284        2 - after root node cuts
285        3 - after cuts at other nodes
286        4 - during cuts at other nodes
287            8 added if previous heuristic in loop found solution
288    */
289    virtual bool shouldHeurRun(int whereFrom);
290    /** Check whether the heuristic should run this time */
291    bool shouldHeurRun_randomChoice();
292    void debugNodes();
293    void printDistanceToNodes();
294    /// how many times the heuristic has actually run
295    inline int numRuns() const {
296        return numRuns_;
297    }
298
299    /// How many times the heuristic could run
300    inline int numCouldRun() const {
301        return numCouldRun_;
302    }
[1600]303    /*! \brief Clone, but ...
304
305      If type is
306        - 0 clone the solver for the model,
307        - 1 clone the continuous solver for the model
308        - Add 2 to say without integer variables which are at low priority
309        - Add 4 to say quite likely infeasible so give up easily (clp only).
310    */
[1286]311    OsiSolverInterface * cloneBut(int type);
[2]312protected:
313
[1286]314    /// Model
315    CbcModel * model_;
316    /// When flag - 0 off, 1 at root, 2 other than root, 3 always
317    int when_;
318    /// Number of nodes in any sub tree
319    int numberNodes_;
[1802]320    /** Feasibility pump options , -1 is off
321        >=0 for feasibility pump itself
322        -2 quick proximity search
323        -3 longer proximity search
324    */
[1286]325    int feasibilityPumpOptions_;
326    /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
327    mutable double fractionSmall_;
328    /// Thread specific random number generator
329    CoinThreadRandom randomNumberGenerator_;
330    /// Name for printing
331    std::string heuristicName_;
[912]332
[1286]333    /// How often to do (code can change)
334    int howOften_;
335    /// How much to increase how often
336    double decayFactor_;
337    /** Switches (does not apply equally to all heuristics)
338        1 bit - stop once allowable gap on objective reached
339        2 bit - always do given number of passes
340        4 bit - weaken cutoff by 5% every 50 passes?
341        8 bit - if has cutoff and suminf bobbling for 20 passes then
342                first try halving distance to best possible then
343                try keep halving distance to known cutoff
[1802]344        16 bit - needs new solution to run
[1286]345        1024 bit - stop all heuristics on max time
346    */
347    mutable int switches_;
348    /* Runs if bit set
349        0 - before cuts at root node (or from doHeuristics)
350        1 - during cuts at root
351        2 - after root node cuts
352        3 - after cuts at other nodes
353        4 - during cuts at other nodes
354            8 added if previous heuristic in loop found solution
355     */
356    int whereFrom_;
357    /** Upto this depth we call the tree shallow and the heuristic can be called
358        multiple times. That is, the test whether the current node is far from
359        the others where the jeuristic was invoked will not be done, only the
360        frequency will be tested. After that depth the heuristic will can be
361        invoked only once per node, right before branching. That's when it'll be
362        tested whether the heur should run at all. */
363    int shallowDepth_;
364    /** How often to invoke the heuristics in the shallow part of the tree */
365    int howOftenShallow_;
366    /** How many invocations happened within the same node when in a shallow
367        part of the tree. */
368    int numInvocationsInShallow_;
369    /** How many invocations happened when in the deep part of the tree. For
370        every node we count only one invocation. */
371    int numInvocationsInDeep_;
372    /** After how many deep invocations was the heuristic run last time */
373    int lastRunDeep_;
374    /// how many times the heuristic has actually run
375    int numRuns_;
376    /** How "far" should this node be from every other where the heuristic was
377        run in order to allow the heuristic to run in this node, too. Currently
378        this is tested, but we may switch to avgDistanceToRun_ in the future. */
379    int minDistanceToRun_;
[912]380
[1286]381    /// The description of the nodes where this heuristic has been applied
382    CbcHeuristicNodeList runNodes_;
[912]383
[1286]384    /// How many times the heuristic could run
385    int numCouldRun_;
[912]386
[1286]387    /// How many solutions the heuristic thought it got
388    int numberSolutionsFound_;
[912]389
[1822]390    /// How many nodes the heuristic did this go
391    mutable int numberNodesDone_;
392
[1286]393    // Input solution - so can be used as seed
394    double * inputSolution_;
[931]395
[940]396
[1393]397#ifdef JJF_ZERO
[1286]398    /// Lower bounds of last node where the heuristic found a solution
399    double * lowerBoundLastNode_;
400    /// Upper bounds of last node where the heuristic found a solution
401    double * upperBoundLastNode_;
[912]402#endif
[2]403};
404/** Rounding class
405 */
406
407class CbcRounding : public CbcHeuristic {
408public:
409
[1286]410    // Default Constructor
411    CbcRounding ();
[2]412
[1286]413    // Constructor with model - assumed before cuts
414    CbcRounding (CbcModel & model);
[640]415
[1286]416    // Copy constructor
417    CbcRounding ( const CbcRounding &);
[2]418
[1286]419    // Destructor
420    ~CbcRounding ();
[6]421
[1286]422    /// Assignment operator
423    CbcRounding & operator=(const CbcRounding& rhs);
[2]424
[1286]425    /// Clone
426    virtual CbcHeuristic * clone() const;
427    /// Create C++ lines to get to current state
428    virtual void generateCpp( FILE * fp) ;
[2]429
[1286]430    /// Resets stuff if model changes
431    virtual void resetModel(CbcModel * model);
[2]432
[1286]433    /// update model (This is needed if cliques update matrix etc)
434    virtual void setModel(CbcModel * model);
435
436    using CbcHeuristic::solution ;
437    /** returns 0 if no solution, 1 if valid solution
438        with better objective value than one passed in
439        Sets solution values if good, sets objective value (only if good)
440        This is called after cuts have been added - so can not add cuts
441    */
442    virtual int solution(double & objectiveValue,
443                         double * newSolution);
444    /** returns 0 if no solution, 1 if valid solution
445        with better objective value than one passed in
446        Sets solution values if good, sets objective value (only if good)
447        This is called after cuts have been added - so can not add cuts
448        Use solutionValue rather than solvers one
449    */
450    virtual int solution(double & objectiveValue,
451                         double * newSolution,
452                         double solutionValue);
453    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
454    virtual void validate();
455
456
457    /// Set seed
458    void setSeed(int value) {
459        seed_ = value;
460    }
461
[2]462protected:
[1286]463    // Data
[2]464
[1286]465    // Original matrix by column
466    CoinPackedMatrix matrix_;
[2]467
[1286]468    // Original matrix by
469    CoinPackedMatrix matrixByRow_;
[2]470
[1286]471    // Down locks
472    unsigned short * down_;
[838]473
[1286]474    // Up locks
475    unsigned short * up_;
[838]476
[1286]477    // Equality locks
478    unsigned short * equal_;
[838]479
[1286]480    // Seed for random stuff
481    int seed_;
[2]482};
483
[854]484/** Partial solution class
485    If user knows a partial solution this tries to get an integer solution
486    it uses hotstart information
487 */
488
489class CbcHeuristicPartial : public CbcHeuristic {
490public:
491
[1286]492    // Default Constructor
493    CbcHeuristicPartial ();
[854]494
[1286]495    /** Constructor with model - assumed before cuts
496        Fixes all variables with priority <= given
497        and does given number of nodes
498    */
499    CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
[854]500
[1286]501    // Copy constructor
502    CbcHeuristicPartial ( const CbcHeuristicPartial &);
[854]503
[1286]504    // Destructor
505    ~CbcHeuristicPartial ();
[854]506
[1286]507    /// Assignment operator
508    CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
[854]509
[1286]510    /// Clone
511    virtual CbcHeuristic * clone() const;
512    /// Create C++ lines to get to current state
513    virtual void generateCpp( FILE * fp) ;
[854]514
[1286]515    /// Resets stuff if model changes
516    virtual void resetModel(CbcModel * model);
[854]517
[1286]518    /// update model (This is needed if cliques update matrix etc)
519    virtual void setModel(CbcModel * model);
[1013]520
[1286]521    using CbcHeuristic::solution ;
522    /** returns 0 if no solution, 1 if valid solution
523        with better objective value than one passed in
524        Sets solution values if good, sets objective value (only if good)
525        This is called after cuts have been added - so can not add cuts
526    */
527    virtual int solution(double & objectiveValue,
528                         double * newSolution);
529    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
530    virtual void validate();
531
532
533    /// Set priority level
534    void setFixPriority(int value) {
535        fixPriority_ = value;
536    }
537
538    /** Check whether the heuristic should run at all */
539    virtual bool shouldHeurRun(int whereFrom);
540
[854]541protected:
[1286]542    // Data
[854]543
[1286]544    // All variables with abs priority <= this will be fixed
545    int fixPriority_;
[854]546};
547
[264]548/** heuristic - just picks up any good solution
549    found by solver - see OsiBabSolver
550 */
[2]551
[264]552class CbcSerendipity : public CbcHeuristic {
553public:
554
[1286]555    // Default Constructor
556    CbcSerendipity ();
[264]557
[1286]558    /* Constructor with model
559    */
560    CbcSerendipity (CbcModel & model);
[640]561
[1286]562    // Copy constructor
563    CbcSerendipity ( const CbcSerendipity &);
[264]564
[1286]565    // Destructor
566    ~CbcSerendipity ();
[264]567
[1286]568    /// Assignment operator
569    CbcSerendipity & operator=(const CbcSerendipity& rhs);
[264]570
[1286]571    /// Clone
572    virtual CbcHeuristic * clone() const;
573    /// Create C++ lines to get to current state
574    virtual void generateCpp( FILE * fp) ;
575
576    /// update model
577    virtual void setModel(CbcModel * model);
578
579    using CbcHeuristic::solution ;
580    /** returns 0 if no solution, 1 if valid solution.
581        Sets solution values if good, sets objective value (only if good)
582        We leave all variables which are at one at this node of the
583        tree to that value and will
584        initially set all others to zero.  We then sort all variables in order of their cost
585        divided by the number of entries in rows which are not yet covered.  We randomize that
586        value a bit so that ties will be broken in different ways on different runs of the heuristic.
587        We then choose the best one and set it to one and repeat the exercise.
588
589    */
590    virtual int solution(double & objectiveValue,
591                         double * newSolution);
592    /// Resets stuff if model changes
593    virtual void resetModel(CbcModel * model);
594
[264]595protected:
596};
597
[961]598/** Just One class - this chooses one at random
599 */
600
601class CbcHeuristicJustOne : public CbcHeuristic {
602public:
603
[1286]604    // Default Constructor
605    CbcHeuristicJustOne ();
[961]606
[1286]607    // Constructor with model - assumed before cuts
608    CbcHeuristicJustOne (CbcModel & model);
[961]609
[1286]610    // Copy constructor
611    CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
[961]612
[1286]613    // Destructor
614    ~CbcHeuristicJustOne ();
[961]615
[1286]616    /// Clone
617    virtual CbcHeuristicJustOne * clone() const;
[961]618
[1286]619    /// Assignment operator
620    CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
621
622    /// Create C++ lines to get to current state
623    virtual void generateCpp( FILE * fp) ;
624
625    /** returns 0 if no solution, 1 if valid solution
626        with better objective value than one passed in
627        Sets solution values if good, sets objective value (only if good)
628        This is called after cuts have been added - so can not add cuts
629        This does Fractional Diving
630    */
631    virtual int solution(double & objectiveValue,
632                         double * newSolution);
633    /// Resets stuff if model changes
634    virtual void resetModel(CbcModel * model);
635
636    /// update model (This is needed if cliques update matrix etc)
637    virtual void setModel(CbcModel * model);
638    /// Selects the next variable to branch on
639    /** Returns true if all the fractional variables can be trivially
640        rounded. Returns false, if there is at least one fractional variable
641        that is not trivially roundable. In this case, the bestColumn
642        returned will not be trivially roundable.
643        This is dummy as never called
644    */
645    virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
646                                        const double* /*newSolution*/,
647                                        int& /*bestColumn*/,
648                                        int& /*bestRound*/) {
649        return true;
650    }
651    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
652    virtual void validate();
653    /// Adds an heuristic with probability
654    void addHeuristic(const CbcHeuristic * heuristic, double probability);
655    /// Normalize probabilities
656    void normalizeProbabilities();
[961]657protected:
[1286]658    // Data
[961]659
[1286]660    // Probability of running a heuristic
661    double * probabilities_;
[961]662
[1286]663    // Heuristics
664    CbcHeuristic ** heuristic_;
[961]665
[1286]666    // Number of heuristics
667    int numberHeuristics_;
[961]668
669};
670
[2]671#endif
[1432]672
Note: See TracBrowser for help on using the repository browser.