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

Last change on this file since 2280 was 2280, checked in by forrest, 3 years ago

allow heuristics to see if integers are 'optional'

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 23.1 KB
Line 
1/* $Id: CbcHeuristic.hpp 2280 2016-06-14 14:39:54Z 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#ifdef COIN_HAS_CLP
20#include "OsiClpSolverInterface.hpp"
21#endif
22//#############################################################################
23
24class CbcHeuristicNodeList;
25class CbcBranchingObject;
26
27/** A class describing the branching decisions that were made to get
28    to the node where a heuristic was invoked from */
29
30class CbcHeuristicNode {
31private:
32    void gutsOfConstructor(CbcModel& model);
33    CbcHeuristicNode();
34    CbcHeuristicNode& operator=(const CbcHeuristicNode&);
35private:
36    /// The number of branching decisions made
37    int numObjects_;
38    /** The indices of the branching objects. Note: an index may be
39        listed multiple times. E.g., a general integer variable that has
40        been branched on multiple times. */
41    CbcBranchingObject** brObj_;
42public:
43    CbcHeuristicNode(CbcModel& model);
44
45    CbcHeuristicNode(const CbcHeuristicNode& rhs);
46    ~CbcHeuristicNode();
47    double distance(const CbcHeuristicNode* node) const;
48    double minDistance(const CbcHeuristicNodeList& nodeList) const;
49    bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList,
50                            const double threshold) const;
51    double avgDistance(const CbcHeuristicNodeList& nodeList) const;
52};
53
54class CbcHeuristicNodeList {
55private:
56    void gutsOfDelete();
57    void gutsOfCopy(const CbcHeuristicNodeList& rhs);
58private:
59    std::vector<CbcHeuristicNode*> nodes_;
60public:
61    CbcHeuristicNodeList() {}
62    CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
63    CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
64    ~CbcHeuristicNodeList();
65
66    void append(CbcHeuristicNode*& node);
67    void append(const CbcHeuristicNodeList& nodes);
68    inline const CbcHeuristicNode* node(int i) const {
69        return nodes_[i];
70    }
71    inline int size() const {
72        return static_cast<int>(nodes_.size());
73    }
74};
75
76//#############################################################################
77/** Heuristic base class */
78
79class CbcHeuristic {
80private:
81    void gutsOfDelete() {}
82    void gutsOfCopy(const CbcHeuristic & rhs);
83
84public:
85    // Default Constructor
86    CbcHeuristic ();
87
88    // Constructor with model - assumed before cuts
89    CbcHeuristic (CbcModel & model);
90
91    // Copy constructor
92    CbcHeuristic ( const CbcHeuristic &);
93
94    virtual ~CbcHeuristic();
95
96    /// Clone
97    virtual CbcHeuristic * clone() const = 0;
98
99    /// Assignment operator
100    CbcHeuristic & operator=(const CbcHeuristic& rhs);
101
102    /// update model (This is needed if cliques update matrix etc)
103    virtual void setModel(CbcModel * model);
104
105    /// Resets stuff if model changes
106    virtual void resetModel(CbcModel * model) = 0;
107
108    /** returns 0 if no solution, 1 if valid solution
109        with better objective value than one passed in
110        Sets solution values if good, sets objective value
111        This is called after cuts have been added - so can not add cuts
112    */
113    virtual int solution(double & objectiveValue,
114                         double * newSolution) = 0;
115
116    /** returns 0 if no solution, 1 if valid solution, -1 if just
117        returning an estimate of best possible solution
118        with better objective value than one passed in
119        Sets solution values if good, sets objective value (only if nonzero code)
120        This is called at same time as cut generators - so can add cuts
121        Default is do nothing
122    */
123    virtual int solution2(double & /*objectiveValue*/,
124                          double * /*newSolution*/,
125                          OsiCuts & /*cs*/) {
126        return 0;
127    }
128
129    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
130    virtual void validate() {}
131
132    /** Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
133        If 10 added then don't worry if validate says there are funny objects
134        as user knows it will be fine
135    */
136    inline void setWhen(int value) {
137        when_ = value;
138    }
139    /// Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always
140    inline int when() const {
141        return when_;
142    }
143
144    /// Sets number of nodes in subtree (default 200)
145    inline void setNumberNodes(int value) {
146        numberNodes_ = value;
147    }
148    /// Gets number of nodes in a subtree (default 200)
149    inline int numberNodes() const {
150        return numberNodes_;
151    }
152    /** Switches (does not apply equally to all heuristics)
153        1 bit - stop once allowable gap on objective reached
154        2 bit - always do given number of passes
155        4 bit - weaken cutoff by 5% every 50 passes?
156        8 bit - if has cutoff and suminf bobbling for 20 passes then
157                first try halving distance to best possible then
158                try keep halving distance to known cutoff
159        16 bit - needs new solution to run
160        1024 bit - stop all heuristics on max time
161    */
162    inline void setSwitches(int value) {
163        switches_ = value;
164    }
165    /** Switches (does not apply equally to all heuristics)
166        1 bit - stop once allowable gap on objective reached
167        2 bit - always do given number of passes
168        4 bit - weaken cutoff by 5% every 50 passes?
169        8 bit - if has cutoff and suminf bobbling for 20 passes then
170                first try halving distance to best possible then
171                try keep halving distance to known cutoff
172        16 bit - needs new solution to run
173        1024 bit - stop all heuristics on max time
174        65536 bit and above used for temporary communication
175    */
176    inline int switches() const {
177        return switches_;
178    }
179    /// Whether to exit at once on gap
180    bool exitNow(double bestObjective) const;
181    /// Sets feasibility pump options (-1 is off)
182    inline void setFeasibilityPumpOptions(int value) {
183        feasibilityPumpOptions_ = value;
184    }
185    /// Gets feasibility pump options (-1 is off)
186    inline int feasibilityPumpOptions() const {
187        return feasibilityPumpOptions_;
188    }
189    /// Just set model - do not do anything else
190    inline void setModelOnly(CbcModel * model) {
191        model_ = model;
192    }
193
194
195    /// Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
196    inline void setFractionSmall(double value) {
197        fractionSmall_ = value;
198    }
199    /// Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1.0)
200    inline double fractionSmall() const {
201        return fractionSmall_;
202    }
203    /// Get how many solutions the heuristic thought it got
204    inline int numberSolutionsFound() const {
205        return numberSolutionsFound_;
206    }
207    /// Increment how many solutions the heuristic thought it got
208    inline void incrementNumberSolutionsFound() {
209        numberSolutionsFound_++;
210    }
211
212    /** Do mini branch and bound - return
213        0 not finished - no solution
214        1 not finished - solution
215        2 finished - no solution
216        3 finished - solution
217        (could add global cut if finished)
218        -1 returned on size
219        -2 time or user event
220    */
221    int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes,
222                            double * newSolution, double & newSolutionValue,
223                            double cutoff , std::string name) const;
224    /// Create C++ lines to get to current state
225    virtual void generateCpp( FILE * ) {}
226    /// Create C++ lines to get to current state - does work for base class
227    void generateCpp( FILE * fp, const char * heuristic) ;
228    /// Returns true if can deal with "odd" problems e.g. sos type 2
229    virtual bool canDealWithOdd() const {
230        return false;
231    }
232    /// return name of heuristic
233    inline const char *heuristicName() const {
234        return heuristicName_.c_str();
235    }
236    /// set name of heuristic
237    inline void setHeuristicName(const char *name) {
238        heuristicName_ = name;
239    }
240    /// Set random number generator seed
241    void setSeed(int value);
242    /// Get random number generator seed
243    int getSeed() const;
244    /// Sets decay factor (for howOften) on failure
245    inline void setDecayFactor(double value) {
246        decayFactor_ = value;
247    }
248    /// Set input solution
249    void setInputSolution(const double * solution, double objValue);
250    /* Runs if bit set
251        0 - before cuts at root node (or from doHeuristics)
252        1 - during cuts at root
253        2 - after root node cuts
254        3 - after cuts at other nodes
255        4 - during cuts at other nodes
256            8 added if previous heuristic in loop found solution
257     */
258    inline void setWhereFrom(int value) {
259        whereFrom_ = value;
260    }
261    inline int whereFrom() const {
262        return whereFrom_;
263    }
264    /** Upto this depth we call the tree shallow and the heuristic can be called
265        multiple times. That is, the test whether the current node is far from
266        the others where the jeuristic was invoked will not be done, only the
267        frequency will be tested. After that depth the heuristic will can be
268        invoked only once per node, right before branching. That's when it'll be
269        tested whether the heur should run at all. */
270    inline void setShallowDepth(int value) {
271        shallowDepth_ = value;
272    }
273    /** How often to invoke the heuristics in the shallow part of the tree */
274    inline void setHowOftenShallow(int value) {
275        howOftenShallow_ = value;
276    }
277    /** How "far" should this node be from every other where the heuristic was
278        run in order to allow the heuristic to run in this node, too. Currently
279        this is tested, but we may switch to avgDistanceToRun_ in the future. */
280    inline void setMinDistanceToRun(int value) {
281        minDistanceToRun_ = value;
282    }
283
284    /** Check whether the heuristic should run at all
285        0 - before cuts at root node (or from doHeuristics)
286        1 - during cuts at root
287        2 - after root node cuts
288        3 - after cuts at other nodes
289        4 - during cuts at other nodes
290            8 added if previous heuristic in loop found solution
291    */
292    virtual bool shouldHeurRun(int whereFrom);
293    /** Check whether the heuristic should run this time */
294    bool shouldHeurRun_randomChoice();
295    void debugNodes();
296    void printDistanceToNodes();
297    /// how many times the heuristic has actually run
298    inline int numRuns() const {
299        return numRuns_;
300    }
301
302    /// How many times the heuristic could run
303    inline int numCouldRun() const {
304        return numCouldRun_;
305    }
306    /// Is it integer for heuristics?
307#ifdef COIN_HAS_CLP
308  inline bool isHeuristicInteger(const OsiSolverInterface * solver, int iColumn) const
309  {
310    const OsiClpSolverInterface * clpSolver
311    = dynamic_cast<const OsiClpSolverInterface *> (solver);
312    if (clpSolver)
313        return clpSolver->isHeuristicInteger(iColumn);
314      else
315        return solver->isInteger(iColumn);
316  }
317#else
318  inline bool isHeuristicInteger(const OsiSolverInterface * solver, int iColumn)
319  { return solver->isInteger(iColumn);}
320#endif
321    /*! \brief Clone, but ...
322
323      If type is
324        - 0 clone the solver for the model,
325        - 1 clone the continuous solver for the model
326        - Add 2 to say without integer variables which are at low priority
327        - Add 4 to say quite likely infeasible so give up easily (clp only).
328    */
329    OsiSolverInterface * cloneBut(int type);
330protected:
331
332    /// Model
333    CbcModel * model_;
334    /// When flag - 0 off, 1 at root, 2 other than root, 3 always
335    int when_;
336    /// Number of nodes in any sub tree
337    int numberNodes_;
338    /** Feasibility pump options , -1 is off
339        >=0 for feasibility pump itself
340        -2 quick proximity search
341        -3 longer proximity search
342    */
343    int feasibilityPumpOptions_;
344    /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
345    mutable double fractionSmall_;
346    /// Thread specific random number generator
347    CoinThreadRandom randomNumberGenerator_;
348    /// Name for printing
349    std::string heuristicName_;
350
351    /// How often to do (code can change)
352    mutable int howOften_;
353    /// How much to increase how often
354    double decayFactor_;
355    /** Switches (does not apply equally to all heuristics)
356        1 bit - stop once allowable gap on objective reached
357        2 bit - always do given number of passes
358        4 bit - weaken cutoff by 5% every 50 passes?
359        8 bit - if has cutoff and suminf bobbling for 20 passes then
360                first try halving distance to best possible then
361                try keep halving distance to known cutoff
362        16 bit - needs new solution to run
363        1024 bit - stop all heuristics on max time
364    */
365    mutable int switches_;
366    /* Runs if bit set
367        0 - before cuts at root node (or from doHeuristics)
368        1 - during cuts at root
369        2 - after root node cuts
370        3 - after cuts at other nodes
371        4 - during cuts at other nodes
372            8 added if previous heuristic in loop found solution
373     */
374    int whereFrom_;
375    /** Upto this depth we call the tree shallow and the heuristic can be called
376        multiple times. That is, the test whether the current node is far from
377        the others where the jeuristic was invoked will not be done, only the
378        frequency will be tested. After that depth the heuristic will can be
379        invoked only once per node, right before branching. That's when it'll be
380        tested whether the heur should run at all. */
381    int shallowDepth_;
382    /** How often to invoke the heuristics in the shallow part of the tree */
383    int howOftenShallow_;
384    /** How many invocations happened within the same node when in a shallow
385        part of the tree. */
386    int numInvocationsInShallow_;
387    /** How many invocations happened when in the deep part of the tree. For
388        every node we count only one invocation. */
389    int numInvocationsInDeep_;
390    /** After how many deep invocations was the heuristic run last time */
391    int lastRunDeep_;
392    /// how many times the heuristic has actually run
393    int numRuns_;
394    /** How "far" should this node be from every other where the heuristic was
395        run in order to allow the heuristic to run in this node, too. Currently
396        this is tested, but we may switch to avgDistanceToRun_ in the future. */
397    int minDistanceToRun_;
398
399    /// The description of the nodes where this heuristic has been applied
400    CbcHeuristicNodeList runNodes_;
401
402    /// How many times the heuristic could run
403    int numCouldRun_;
404
405    /// How many solutions the heuristic thought it got
406    int numberSolutionsFound_;
407
408    /// How many nodes the heuristic did this go
409    mutable int numberNodesDone_;
410
411    // Input solution - so can be used as seed
412    double * inputSolution_;
413
414
415#ifdef JJF_ZERO
416    /// Lower bounds of last node where the heuristic found a solution
417    double * lowerBoundLastNode_;
418    /// Upper bounds of last node where the heuristic found a solution
419    double * upperBoundLastNode_;
420#endif
421};
422/** Rounding class
423 */
424
425class CbcRounding : public CbcHeuristic {
426public:
427
428    // Default Constructor
429    CbcRounding ();
430
431    // Constructor with model - assumed before cuts
432    CbcRounding (CbcModel & model);
433
434    // Copy constructor
435    CbcRounding ( const CbcRounding &);
436
437    // Destructor
438    ~CbcRounding ();
439
440    /// Assignment operator
441    CbcRounding & operator=(const CbcRounding& rhs);
442
443    /// Clone
444    virtual CbcHeuristic * clone() const;
445    /// Create C++ lines to get to current state
446    virtual void generateCpp( FILE * fp) ;
447
448    /// Resets stuff if model changes
449    virtual void resetModel(CbcModel * model);
450
451    /// update model (This is needed if cliques update matrix etc)
452    virtual void setModel(CbcModel * model);
453
454    using CbcHeuristic::solution ;
455    /** returns 0 if no solution, 1 if valid solution
456        with better objective value than one passed in
457        Sets solution values if good, sets objective value (only if good)
458        This is called after cuts have been added - so can not add cuts
459    */
460    virtual int solution(double & objectiveValue,
461                         double * newSolution);
462    /** returns 0 if no solution, 1 if valid solution
463        with better objective value than one passed in
464        Sets solution values if good, sets objective value (only if good)
465        This is called after cuts have been added - so can not add cuts
466        Use solutionValue rather than solvers one
467    */
468    virtual int solution(double & objectiveValue,
469                         double * newSolution,
470                         double solutionValue);
471    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
472    virtual void validate();
473
474
475    /// Set seed
476    void setSeed(int value) {
477        seed_ = value;
478    }
479    /** Check whether the heuristic should run at all
480        0 - before cuts at root node (or from doHeuristics)
481        1 - during cuts at root
482        2 - after root node cuts
483        3 - after cuts at other nodes
484        4 - during cuts at other nodes
485            8 added if previous heuristic in loop found solution
486    */
487    virtual bool shouldHeurRun(int whereFrom);
488
489protected:
490    // Data
491
492    // Original matrix by column
493    CoinPackedMatrix matrix_;
494
495    // Original matrix by
496    CoinPackedMatrix matrixByRow_;
497
498    // Down locks
499    unsigned short * down_;
500
501    // Up locks
502    unsigned short * up_;
503
504    // Equality locks
505    unsigned short * equal_;
506
507    // Seed for random stuff
508    int seed_;
509};
510
511/** Partial solution class
512    If user knows a partial solution this tries to get an integer solution
513    it uses hotstart information
514 */
515
516class CbcHeuristicPartial : public CbcHeuristic {
517public:
518
519    // Default Constructor
520    CbcHeuristicPartial ();
521
522    /** Constructor with model - assumed before cuts
523        Fixes all variables with priority <= given
524        and does given number of nodes
525    */
526    CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
527
528    // Copy constructor
529    CbcHeuristicPartial ( const CbcHeuristicPartial &);
530
531    // Destructor
532    ~CbcHeuristicPartial ();
533
534    /// Assignment operator
535    CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
536
537    /// Clone
538    virtual CbcHeuristic * clone() const;
539    /// Create C++ lines to get to current state
540    virtual void generateCpp( FILE * fp) ;
541
542    /// Resets stuff if model changes
543    virtual void resetModel(CbcModel * model);
544
545    /// update model (This is needed if cliques update matrix etc)
546    virtual void setModel(CbcModel * model);
547
548    using CbcHeuristic::solution ;
549    /** returns 0 if no solution, 1 if valid solution
550        with better objective value than one passed in
551        Sets solution values if good, sets objective value (only if good)
552        This is called after cuts have been added - so can not add cuts
553    */
554    virtual int solution(double & objectiveValue,
555                         double * newSolution);
556    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
557    virtual void validate();
558
559
560    /// Set priority level
561    void setFixPriority(int value) {
562        fixPriority_ = value;
563    }
564
565    /** Check whether the heuristic should run at all */
566    virtual bool shouldHeurRun(int whereFrom);
567
568protected:
569    // Data
570
571    // All variables with abs priority <= this will be fixed
572    int fixPriority_;
573};
574
575/** heuristic - just picks up any good solution
576    found by solver - see OsiBabSolver
577 */
578
579class CbcSerendipity : public CbcHeuristic {
580public:
581
582    // Default Constructor
583    CbcSerendipity ();
584
585    /* Constructor with model
586    */
587    CbcSerendipity (CbcModel & model);
588
589    // Copy constructor
590    CbcSerendipity ( const CbcSerendipity &);
591
592    // Destructor
593    ~CbcSerendipity ();
594
595    /// Assignment operator
596    CbcSerendipity & operator=(const CbcSerendipity& rhs);
597
598    /// Clone
599    virtual CbcHeuristic * clone() const;
600    /// Create C++ lines to get to current state
601    virtual void generateCpp( FILE * fp) ;
602
603    /// update model
604    virtual void setModel(CbcModel * model);
605
606    using CbcHeuristic::solution ;
607    /** returns 0 if no solution, 1 if valid solution.
608        Sets solution values if good, sets objective value (only if good)
609        We leave all variables which are at one at this node of the
610        tree to that value and will
611        initially set all others to zero.  We then sort all variables in order of their cost
612        divided by the number of entries in rows which are not yet covered.  We randomize that
613        value a bit so that ties will be broken in different ways on different runs of the heuristic.
614        We then choose the best one and set it to one and repeat the exercise.
615
616    */
617    virtual int solution(double & objectiveValue,
618                         double * newSolution);
619    /// Resets stuff if model changes
620    virtual void resetModel(CbcModel * model);
621
622protected:
623};
624
625/** Just One class - this chooses one at random
626 */
627
628class CbcHeuristicJustOne : public CbcHeuristic {
629public:
630
631    // Default Constructor
632    CbcHeuristicJustOne ();
633
634    // Constructor with model - assumed before cuts
635    CbcHeuristicJustOne (CbcModel & model);
636
637    // Copy constructor
638    CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
639
640    // Destructor
641    ~CbcHeuristicJustOne ();
642
643    /// Clone
644    virtual CbcHeuristicJustOne * clone() const;
645
646    /// Assignment operator
647    CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
648
649    /// Create C++ lines to get to current state
650    virtual void generateCpp( FILE * fp) ;
651
652    /** returns 0 if no solution, 1 if valid solution
653        with better objective value than one passed in
654        Sets solution values if good, sets objective value (only if good)
655        This is called after cuts have been added - so can not add cuts
656        This does Fractional Diving
657    */
658    virtual int solution(double & objectiveValue,
659                         double * newSolution);
660    /// Resets stuff if model changes
661    virtual void resetModel(CbcModel * model);
662
663    /// update model (This is needed if cliques update matrix etc)
664    virtual void setModel(CbcModel * model);
665    /// Selects the next variable to branch on
666    /** Returns true if all the fractional variables can be trivially
667        rounded. Returns false, if there is at least one fractional variable
668        that is not trivially roundable. In this case, the bestColumn
669        returned will not be trivially roundable.
670        This is dummy as never called
671    */
672    virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
673                                        const double* /*newSolution*/,
674                                        int& /*bestColumn*/,
675                                        int& /*bestRound*/) {
676        return true;
677    }
678    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
679    virtual void validate();
680    /// Adds an heuristic with probability
681    void addHeuristic(const CbcHeuristic * heuristic, double probability);
682    /// Normalize probabilities
683    void normalizeProbabilities();
684protected:
685    // Data
686
687    // Probability of running a heuristic
688    double * probabilities_;
689
690    // Heuristics
691    CbcHeuristic ** heuristic_;
692
693    // Number of heuristics
694    int numberHeuristics_;
695
696};
697
698#endif
699
Note: See TracBrowser for help on using the repository browser.