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

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

Quash a few conversion warnings in 64-bit cl build.

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