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

Last change on this file since 2093 was 2093, checked in by forrest, 5 years ago

changes for diving heuristic

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 22.2 KB
Line 
1/* $Id: CbcHeuristic.hpp 2093 2014-11-06 16:17:38Z 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
463protected:
464    // Data
465
466    // Original matrix by column
467    CoinPackedMatrix matrix_;
468
469    // Original matrix by
470    CoinPackedMatrix matrixByRow_;
471
472    // Down locks
473    unsigned short * down_;
474
475    // Up locks
476    unsigned short * up_;
477
478    // Equality locks
479    unsigned short * equal_;
480
481    // Seed for random stuff
482    int seed_;
483};
484
485/** Partial solution class
486    If user knows a partial solution this tries to get an integer solution
487    it uses hotstart information
488 */
489
490class CbcHeuristicPartial : public CbcHeuristic {
491public:
492
493    // Default Constructor
494    CbcHeuristicPartial ();
495
496    /** Constructor with model - assumed before cuts
497        Fixes all variables with priority <= given
498        and does given number of nodes
499    */
500    CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
501
502    // Copy constructor
503    CbcHeuristicPartial ( const CbcHeuristicPartial &);
504
505    // Destructor
506    ~CbcHeuristicPartial ();
507
508    /// Assignment operator
509    CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
510
511    /// Clone
512    virtual CbcHeuristic * clone() const;
513    /// Create C++ lines to get to current state
514    virtual void generateCpp( FILE * fp) ;
515
516    /// Resets stuff if model changes
517    virtual void resetModel(CbcModel * model);
518
519    /// update model (This is needed if cliques update matrix etc)
520    virtual void setModel(CbcModel * model);
521
522    using CbcHeuristic::solution ;
523    /** returns 0 if no solution, 1 if valid solution
524        with better objective value than one passed in
525        Sets solution values if good, sets objective value (only if good)
526        This is called after cuts have been added - so can not add cuts
527    */
528    virtual int solution(double & objectiveValue,
529                         double * newSolution);
530    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
531    virtual void validate();
532
533
534    /// Set priority level
535    void setFixPriority(int value) {
536        fixPriority_ = value;
537    }
538
539    /** Check whether the heuristic should run at all */
540    virtual bool shouldHeurRun(int whereFrom);
541
542protected:
543    // Data
544
545    // All variables with abs priority <= this will be fixed
546    int fixPriority_;
547};
548
549/** heuristic - just picks up any good solution
550    found by solver - see OsiBabSolver
551 */
552
553class CbcSerendipity : public CbcHeuristic {
554public:
555
556    // Default Constructor
557    CbcSerendipity ();
558
559    /* Constructor with model
560    */
561    CbcSerendipity (CbcModel & model);
562
563    // Copy constructor
564    CbcSerendipity ( const CbcSerendipity &);
565
566    // Destructor
567    ~CbcSerendipity ();
568
569    /// Assignment operator
570    CbcSerendipity & operator=(const CbcSerendipity& rhs);
571
572    /// Clone
573    virtual CbcHeuristic * clone() const;
574    /// Create C++ lines to get to current state
575    virtual void generateCpp( FILE * fp) ;
576
577    /// update model
578    virtual void setModel(CbcModel * model);
579
580    using CbcHeuristic::solution ;
581    /** returns 0 if no solution, 1 if valid solution.
582        Sets solution values if good, sets objective value (only if good)
583        We leave all variables which are at one at this node of the
584        tree to that value and will
585        initially set all others to zero.  We then sort all variables in order of their cost
586        divided by the number of entries in rows which are not yet covered.  We randomize that
587        value a bit so that ties will be broken in different ways on different runs of the heuristic.
588        We then choose the best one and set it to one and repeat the exercise.
589
590    */
591    virtual int solution(double & objectiveValue,
592                         double * newSolution);
593    /// Resets stuff if model changes
594    virtual void resetModel(CbcModel * model);
595
596protected:
597};
598
599/** Just One class - this chooses one at random
600 */
601
602class CbcHeuristicJustOne : public CbcHeuristic {
603public:
604
605    // Default Constructor
606    CbcHeuristicJustOne ();
607
608    // Constructor with model - assumed before cuts
609    CbcHeuristicJustOne (CbcModel & model);
610
611    // Copy constructor
612    CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
613
614    // Destructor
615    ~CbcHeuristicJustOne ();
616
617    /// Clone
618    virtual CbcHeuristicJustOne * clone() const;
619
620    /// Assignment operator
621    CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
622
623    /// Create C++ lines to get to current state
624    virtual void generateCpp( FILE * fp) ;
625
626    /** returns 0 if no solution, 1 if valid solution
627        with better objective value than one passed in
628        Sets solution values if good, sets objective value (only if good)
629        This is called after cuts have been added - so can not add cuts
630        This does Fractional Diving
631    */
632    virtual int solution(double & objectiveValue,
633                         double * newSolution);
634    /// Resets stuff if model changes
635    virtual void resetModel(CbcModel * model);
636
637    /// update model (This is needed if cliques update matrix etc)
638    virtual void setModel(CbcModel * model);
639    /// Selects the next variable to branch on
640    /** Returns true if all the fractional variables can be trivially
641        rounded. Returns false, if there is at least one fractional variable
642        that is not trivially roundable. In this case, the bestColumn
643        returned will not be trivially roundable.
644        This is dummy as never called
645    */
646    virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
647                                        const double* /*newSolution*/,
648                                        int& /*bestColumn*/,
649                                        int& /*bestRound*/) {
650        return true;
651    }
652    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
653    virtual void validate();
654    /// Adds an heuristic with probability
655    void addHeuristic(const CbcHeuristic * heuristic, double probability);
656    /// Normalize probabilities
657    void normalizeProbabilities();
658protected:
659    // Data
660
661    // Probability of running a heuristic
662    double * probabilities_;
663
664    // Heuristics
665    CbcHeuristic ** heuristic_;
666
667    // Number of heuristics
668    int numberHeuristics_;
669
670};
671
672#endif
673
Note: See TracBrowser for help on using the repository browser.