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

Last change on this file since 1902 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
Line 
1/* $Id: CbcHeuristic.hpp 1883 2013-04-06 13:33:15Z stefan $ */
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    */
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    }
190
191
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);
239    /// Get random number generator seed
240    int getSeed() const;
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    }
258    inline int whereFrom() const {
259        return whereFrom_;
260    }
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    }
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    */
311    OsiSolverInterface * cloneBut(int type);
312protected:
313
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_;
320    /** Feasibility pump options , -1 is off
321        >=0 for feasibility pump itself
322        -2 quick proximity search
323        -3 longer proximity search
324    */
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_;
332
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
344        16 bit - needs new solution to run
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_;
380
381    /// The description of the nodes where this heuristic has been applied
382    CbcHeuristicNodeList runNodes_;
383
384    /// How many times the heuristic could run
385    int numCouldRun_;
386
387    /// How many solutions the heuristic thought it got
388    int numberSolutionsFound_;
389
390    /// How many nodes the heuristic did this go
391    mutable int numberNodesDone_;
392
393    // Input solution - so can be used as seed
394    double * inputSolution_;
395
396
397#ifdef JJF_ZERO
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_;
402#endif
403};
404/** Rounding class
405 */
406
407class CbcRounding : public CbcHeuristic {
408public:
409
410    // Default Constructor
411    CbcRounding ();
412
413    // Constructor with model - assumed before cuts
414    CbcRounding (CbcModel & model);
415
416    // Copy constructor
417    CbcRounding ( const CbcRounding &);
418
419    // Destructor
420    ~CbcRounding ();
421
422    /// Assignment operator
423    CbcRounding & operator=(const CbcRounding& rhs);
424
425    /// Clone
426    virtual CbcHeuristic * clone() const;
427    /// Create C++ lines to get to current state
428    virtual void generateCpp( FILE * fp) ;
429
430    /// Resets stuff if model changes
431    virtual void resetModel(CbcModel * model);
432
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
462protected:
463    // Data
464
465    // Original matrix by column
466    CoinPackedMatrix matrix_;
467
468    // Original matrix by
469    CoinPackedMatrix matrixByRow_;
470
471    // Down locks
472    unsigned short * down_;
473
474    // Up locks
475    unsigned short * up_;
476
477    // Equality locks
478    unsigned short * equal_;
479
480    // Seed for random stuff
481    int seed_;
482};
483
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
492    // Default Constructor
493    CbcHeuristicPartial ();
494
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);
500
501    // Copy constructor
502    CbcHeuristicPartial ( const CbcHeuristicPartial &);
503
504    // Destructor
505    ~CbcHeuristicPartial ();
506
507    /// Assignment operator
508    CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
509
510    /// Clone
511    virtual CbcHeuristic * clone() const;
512    /// Create C++ lines to get to current state
513    virtual void generateCpp( FILE * fp) ;
514
515    /// Resets stuff if model changes
516    virtual void resetModel(CbcModel * model);
517
518    /// update model (This is needed if cliques update matrix etc)
519    virtual void setModel(CbcModel * model);
520
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
541protected:
542    // Data
543
544    // All variables with abs priority <= this will be fixed
545    int fixPriority_;
546};
547
548/** heuristic - just picks up any good solution
549    found by solver - see OsiBabSolver
550 */
551
552class CbcSerendipity : public CbcHeuristic {
553public:
554
555    // Default Constructor
556    CbcSerendipity ();
557
558    /* Constructor with model
559    */
560    CbcSerendipity (CbcModel & model);
561
562    // Copy constructor
563    CbcSerendipity ( const CbcSerendipity &);
564
565    // Destructor
566    ~CbcSerendipity ();
567
568    /// Assignment operator
569    CbcSerendipity & operator=(const CbcSerendipity& rhs);
570
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
595protected:
596};
597
598/** Just One class - this chooses one at random
599 */
600
601class CbcHeuristicJustOne : public CbcHeuristic {
602public:
603
604    // Default Constructor
605    CbcHeuristicJustOne ();
606
607    // Constructor with model - assumed before cuts
608    CbcHeuristicJustOne (CbcModel & model);
609
610    // Copy constructor
611    CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
612
613    // Destructor
614    ~CbcHeuristicJustOne ();
615
616    /// Clone
617    virtual CbcHeuristicJustOne * clone() const;
618
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();
657protected:
658    // Data
659
660    // Probability of running a heuristic
661    double * probabilities_;
662
663    // Heuristics
664    CbcHeuristic ** heuristic_;
665
666    // Number of heuristics
667    int numberHeuristics_;
668
669};
670
671#endif
672
Note: See TracBrowser for help on using the repository browser.