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

Last change on this file since 1600 was 1600, checked in by lou, 9 years ago

Kill off doxydoc complaints.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 21.8 KB
Line 
1/* $Id: CbcHeuristic.hpp 1600 2011-02-19 19:24:26Z 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    /*! \brief Clone, but ...
300
301      If type is
302        - 0 clone the solver for the model,
303        - 1 clone the continuous solver for the model
304        - Add 2 to say without integer variables which are at low priority
305        - Add 4 to say quite likely infeasible so give up easily (clp only).
306    */
307    OsiSolverInterface * cloneBut(int type);
308protected:
309
310    /// Model
311    CbcModel * model_;
312    /// When flag - 0 off, 1 at root, 2 other than root, 3 always
313    int when_;
314    /// Number of nodes in any sub tree
315    int numberNodes_;
316    /// Feasibility pump options (-1 is off)
317    int feasibilityPumpOptions_;
318    /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
319    mutable double fractionSmall_;
320    /// Thread specific random number generator
321    CoinThreadRandom randomNumberGenerator_;
322    /// Name for printing
323    std::string heuristicName_;
324
325    /// How often to do (code can change)
326    int howOften_;
327    /// How much to increase how often
328    double decayFactor_;
329    /** Switches (does not apply equally to all heuristics)
330        1 bit - stop once allowable gap on objective reached
331        2 bit - always do given number of passes
332        4 bit - weaken cutoff by 5% every 50 passes?
333        8 bit - if has cutoff and suminf bobbling for 20 passes then
334                first try halving distance to best possible then
335                try keep halving distance to known cutoff
336        1024 bit - stop all heuristics on max time
337    */
338    mutable int switches_;
339    /* Runs if bit set
340        0 - before cuts at root node (or from doHeuristics)
341        1 - during cuts at root
342        2 - after root node cuts
343        3 - after cuts at other nodes
344        4 - during cuts at other nodes
345            8 added if previous heuristic in loop found solution
346     */
347    int whereFrom_;
348    /** Upto this depth we call the tree shallow and the heuristic can be called
349        multiple times. That is, the test whether the current node is far from
350        the others where the jeuristic was invoked will not be done, only the
351        frequency will be tested. After that depth the heuristic will can be
352        invoked only once per node, right before branching. That's when it'll be
353        tested whether the heur should run at all. */
354    int shallowDepth_;
355    /** How often to invoke the heuristics in the shallow part of the tree */
356    int howOftenShallow_;
357    /** How many invocations happened within the same node when in a shallow
358        part of the tree. */
359    int numInvocationsInShallow_;
360    /** How many invocations happened when in the deep part of the tree. For
361        every node we count only one invocation. */
362    int numInvocationsInDeep_;
363    /** After how many deep invocations was the heuristic run last time */
364    int lastRunDeep_;
365    /// how many times the heuristic has actually run
366    int numRuns_;
367    /** How "far" should this node be from every other where the heuristic was
368        run in order to allow the heuristic to run in this node, too. Currently
369        this is tested, but we may switch to avgDistanceToRun_ in the future. */
370    int minDistanceToRun_;
371
372    /// The description of the nodes where this heuristic has been applied
373    CbcHeuristicNodeList runNodes_;
374
375    /// How many times the heuristic could run
376    int numCouldRun_;
377
378    /// How many solutions the heuristic thought it got
379    int numberSolutionsFound_;
380
381    // Input solution - so can be used as seed
382    double * inputSolution_;
383
384
385#ifdef JJF_ZERO
386    /// Lower bounds of last node where the heuristic found a solution
387    double * lowerBoundLastNode_;
388    /// Upper bounds of last node where the heuristic found a solution
389    double * upperBoundLastNode_;
390#endif
391};
392/** Rounding class
393 */
394
395class CbcRounding : public CbcHeuristic {
396public:
397
398    // Default Constructor
399    CbcRounding ();
400
401    // Constructor with model - assumed before cuts
402    CbcRounding (CbcModel & model);
403
404    // Copy constructor
405    CbcRounding ( const CbcRounding &);
406
407    // Destructor
408    ~CbcRounding ();
409
410    /// Assignment operator
411    CbcRounding & operator=(const CbcRounding& rhs);
412
413    /// Clone
414    virtual CbcHeuristic * clone() const;
415    /// Create C++ lines to get to current state
416    virtual void generateCpp( FILE * fp) ;
417
418    /// Resets stuff if model changes
419    virtual void resetModel(CbcModel * model);
420
421    /// update model (This is needed if cliques update matrix etc)
422    virtual void setModel(CbcModel * model);
423
424    using CbcHeuristic::solution ;
425    /** returns 0 if no solution, 1 if valid solution
426        with better objective value than one passed in
427        Sets solution values if good, sets objective value (only if good)
428        This is called after cuts have been added - so can not add cuts
429    */
430    virtual int solution(double & objectiveValue,
431                         double * newSolution);
432    /** returns 0 if no solution, 1 if valid solution
433        with better objective value than one passed in
434        Sets solution values if good, sets objective value (only if good)
435        This is called after cuts have been added - so can not add cuts
436        Use solutionValue rather than solvers one
437    */
438    virtual int solution(double & objectiveValue,
439                         double * newSolution,
440                         double solutionValue);
441    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
442    virtual void validate();
443
444
445    /// Set seed
446    void setSeed(int value) {
447        seed_ = value;
448    }
449
450protected:
451    // Data
452
453    // Original matrix by column
454    CoinPackedMatrix matrix_;
455
456    // Original matrix by
457    CoinPackedMatrix matrixByRow_;
458
459    // Down locks
460    unsigned short * down_;
461
462    // Up locks
463    unsigned short * up_;
464
465    // Equality locks
466    unsigned short * equal_;
467
468    // Seed for random stuff
469    int seed_;
470};
471
472/** Partial solution class
473    If user knows a partial solution this tries to get an integer solution
474    it uses hotstart information
475 */
476
477class CbcHeuristicPartial : public CbcHeuristic {
478public:
479
480    // Default Constructor
481    CbcHeuristicPartial ();
482
483    /** Constructor with model - assumed before cuts
484        Fixes all variables with priority <= given
485        and does given number of nodes
486    */
487    CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
488
489    // Copy constructor
490    CbcHeuristicPartial ( const CbcHeuristicPartial &);
491
492    // Destructor
493    ~CbcHeuristicPartial ();
494
495    /// Assignment operator
496    CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
497
498    /// Clone
499    virtual CbcHeuristic * clone() const;
500    /// Create C++ lines to get to current state
501    virtual void generateCpp( FILE * fp) ;
502
503    /// Resets stuff if model changes
504    virtual void resetModel(CbcModel * model);
505
506    /// update model (This is needed if cliques update matrix etc)
507    virtual void setModel(CbcModel * model);
508
509    using CbcHeuristic::solution ;
510    /** returns 0 if no solution, 1 if valid solution
511        with better objective value than one passed in
512        Sets solution values if good, sets objective value (only if good)
513        This is called after cuts have been added - so can not add cuts
514    */
515    virtual int solution(double & objectiveValue,
516                         double * newSolution);
517    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
518    virtual void validate();
519
520
521    /// Set priority level
522    void setFixPriority(int value) {
523        fixPriority_ = value;
524    }
525
526    /** Check whether the heuristic should run at all */
527    virtual bool shouldHeurRun(int whereFrom);
528
529protected:
530    // Data
531
532    // All variables with abs priority <= this will be fixed
533    int fixPriority_;
534};
535
536/** heuristic - just picks up any good solution
537    found by solver - see OsiBabSolver
538 */
539
540class CbcSerendipity : public CbcHeuristic {
541public:
542
543    // Default Constructor
544    CbcSerendipity ();
545
546    /* Constructor with model
547    */
548    CbcSerendipity (CbcModel & model);
549
550    // Copy constructor
551    CbcSerendipity ( const CbcSerendipity &);
552
553    // Destructor
554    ~CbcSerendipity ();
555
556    /// Assignment operator
557    CbcSerendipity & operator=(const CbcSerendipity& rhs);
558
559    /// Clone
560    virtual CbcHeuristic * clone() const;
561    /// Create C++ lines to get to current state
562    virtual void generateCpp( FILE * fp) ;
563
564    /// update model
565    virtual void setModel(CbcModel * model);
566
567    using CbcHeuristic::solution ;
568    /** returns 0 if no solution, 1 if valid solution.
569        Sets solution values if good, sets objective value (only if good)
570        We leave all variables which are at one at this node of the
571        tree to that value and will
572        initially set all others to zero.  We then sort all variables in order of their cost
573        divided by the number of entries in rows which are not yet covered.  We randomize that
574        value a bit so that ties will be broken in different ways on different runs of the heuristic.
575        We then choose the best one and set it to one and repeat the exercise.
576
577    */
578    virtual int solution(double & objectiveValue,
579                         double * newSolution);
580    /// Resets stuff if model changes
581    virtual void resetModel(CbcModel * model);
582
583protected:
584};
585
586/** Just One class - this chooses one at random
587 */
588
589class CbcHeuristicJustOne : public CbcHeuristic {
590public:
591
592    // Default Constructor
593    CbcHeuristicJustOne ();
594
595    // Constructor with model - assumed before cuts
596    CbcHeuristicJustOne (CbcModel & model);
597
598    // Copy constructor
599    CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
600
601    // Destructor
602    ~CbcHeuristicJustOne ();
603
604    /// Clone
605    virtual CbcHeuristicJustOne * clone() const;
606
607    /// Assignment operator
608    CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
609
610    /// Create C++ lines to get to current state
611    virtual void generateCpp( FILE * fp) ;
612
613    /** returns 0 if no solution, 1 if valid solution
614        with better objective value than one passed in
615        Sets solution values if good, sets objective value (only if good)
616        This is called after cuts have been added - so can not add cuts
617        This does Fractional Diving
618    */
619    virtual int solution(double & objectiveValue,
620                         double * newSolution);
621    /// Resets stuff if model changes
622    virtual void resetModel(CbcModel * model);
623
624    /// update model (This is needed if cliques update matrix etc)
625    virtual void setModel(CbcModel * model);
626    /// Selects the next variable to branch on
627    /** Returns true if all the fractional variables can be trivially
628        rounded. Returns false, if there is at least one fractional variable
629        that is not trivially roundable. In this case, the bestColumn
630        returned will not be trivially roundable.
631        This is dummy as never called
632    */
633    virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
634                                        const double* /*newSolution*/,
635                                        int& /*bestColumn*/,
636                                        int& /*bestRound*/) {
637        return true;
638    }
639    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
640    virtual void validate();
641    /// Adds an heuristic with probability
642    void addHeuristic(const CbcHeuristic * heuristic, double probability);
643    /// Normalize probabilities
644    void normalizeProbabilities();
645protected:
646    // Data
647
648    // Probability of running a heuristic
649    double * probabilities_;
650
651    // Heuristics
652    CbcHeuristic ** heuristic_;
653
654    // Number of heuristics
655    int numberHeuristics_;
656
657};
658
659#endif
660
Note: See TracBrowser for help on using the repository browser.