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

Last change on this file since 1802 was 1802, checked in by forrest, 7 years ago

add Proximity heuristic (Fischetti and Monaci) - shouldn't break anything

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