source: trunk/Cbc/src/CbcHeuristic.hpp @ 1569

Last change on this file since 1569 was 1564, checked in by forrest, 9 years ago

add some heuristic variants

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