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

Last change on this file since 2094 was 2094, checked in by forrest, 4 years ago

for memory leaks and heuristics and some experimental stuff

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