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

Last change on this file since 1573 was 1573, checked in by lou, 8 years ago

Change to EPL license notice.

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