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

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

more output for proximity search

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 22.1 KB
Line 
1/* $Id: CbcHeuristic.hpp 1822 2012-11-29 18:42:40Z 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    /// How many nodes the heuristic did this go
389    mutable int numberNodesDone_;
390
391    // Input solution - so can be used as seed
392    double * inputSolution_;
393
394
395#ifdef JJF_ZERO
396    /// Lower bounds of last node where the heuristic found a solution
397    double * lowerBoundLastNode_;
398    /// Upper bounds of last node where the heuristic found a solution
399    double * upperBoundLastNode_;
400#endif
401};
402/** Rounding class
403 */
404
405class CbcRounding : public CbcHeuristic {
406public:
407
408    // Default Constructor
409    CbcRounding ();
410
411    // Constructor with model - assumed before cuts
412    CbcRounding (CbcModel & model);
413
414    // Copy constructor
415    CbcRounding ( const CbcRounding &);
416
417    // Destructor
418    ~CbcRounding ();
419
420    /// Assignment operator
421    CbcRounding & operator=(const CbcRounding& rhs);
422
423    /// Clone
424    virtual CbcHeuristic * clone() const;
425    /// Create C++ lines to get to current state
426    virtual void generateCpp( FILE * fp) ;
427
428    /// Resets stuff if model changes
429    virtual void resetModel(CbcModel * model);
430
431    /// update model (This is needed if cliques update matrix etc)
432    virtual void setModel(CbcModel * model);
433
434    using CbcHeuristic::solution ;
435    /** returns 0 if no solution, 1 if valid solution
436        with better objective value than one passed in
437        Sets solution values if good, sets objective value (only if good)
438        This is called after cuts have been added - so can not add cuts
439    */
440    virtual int solution(double & objectiveValue,
441                         double * newSolution);
442    /** returns 0 if no solution, 1 if valid solution
443        with better objective value than one passed in
444        Sets solution values if good, sets objective value (only if good)
445        This is called after cuts have been added - so can not add cuts
446        Use solutionValue rather than solvers one
447    */
448    virtual int solution(double & objectiveValue,
449                         double * newSolution,
450                         double solutionValue);
451    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
452    virtual void validate();
453
454
455    /// Set seed
456    void setSeed(int value) {
457        seed_ = value;
458    }
459
460protected:
461    // Data
462
463    // Original matrix by column
464    CoinPackedMatrix matrix_;
465
466    // Original matrix by
467    CoinPackedMatrix matrixByRow_;
468
469    // Down locks
470    unsigned short * down_;
471
472    // Up locks
473    unsigned short * up_;
474
475    // Equality locks
476    unsigned short * equal_;
477
478    // Seed for random stuff
479    int seed_;
480};
481
482/** Partial solution class
483    If user knows a partial solution this tries to get an integer solution
484    it uses hotstart information
485 */
486
487class CbcHeuristicPartial : public CbcHeuristic {
488public:
489
490    // Default Constructor
491    CbcHeuristicPartial ();
492
493    /** Constructor with model - assumed before cuts
494        Fixes all variables with priority <= given
495        and does given number of nodes
496    */
497    CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
498
499    // Copy constructor
500    CbcHeuristicPartial ( const CbcHeuristicPartial &);
501
502    // Destructor
503    ~CbcHeuristicPartial ();
504
505    /// Assignment operator
506    CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
507
508    /// Clone
509    virtual CbcHeuristic * clone() const;
510    /// Create C++ lines to get to current state
511    virtual void generateCpp( FILE * fp) ;
512
513    /// Resets stuff if model changes
514    virtual void resetModel(CbcModel * model);
515
516    /// update model (This is needed if cliques update matrix etc)
517    virtual void setModel(CbcModel * model);
518
519    using CbcHeuristic::solution ;
520    /** returns 0 if no solution, 1 if valid solution
521        with better objective value than one passed in
522        Sets solution values if good, sets objective value (only if good)
523        This is called after cuts have been added - so can not add cuts
524    */
525    virtual int solution(double & objectiveValue,
526                         double * newSolution);
527    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
528    virtual void validate();
529
530
531    /// Set priority level
532    void setFixPriority(int value) {
533        fixPriority_ = value;
534    }
535
536    /** Check whether the heuristic should run at all */
537    virtual bool shouldHeurRun(int whereFrom);
538
539protected:
540    // Data
541
542    // All variables with abs priority <= this will be fixed
543    int fixPriority_;
544};
545
546/** heuristic - just picks up any good solution
547    found by solver - see OsiBabSolver
548 */
549
550class CbcSerendipity : public CbcHeuristic {
551public:
552
553    // Default Constructor
554    CbcSerendipity ();
555
556    /* Constructor with model
557    */
558    CbcSerendipity (CbcModel & model);
559
560    // Copy constructor
561    CbcSerendipity ( const CbcSerendipity &);
562
563    // Destructor
564    ~CbcSerendipity ();
565
566    /// Assignment operator
567    CbcSerendipity & operator=(const CbcSerendipity& rhs);
568
569    /// Clone
570    virtual CbcHeuristic * clone() const;
571    /// Create C++ lines to get to current state
572    virtual void generateCpp( FILE * fp) ;
573
574    /// update model
575    virtual void setModel(CbcModel * model);
576
577    using CbcHeuristic::solution ;
578    /** returns 0 if no solution, 1 if valid solution.
579        Sets solution values if good, sets objective value (only if good)
580        We leave all variables which are at one at this node of the
581        tree to that value and will
582        initially set all others to zero.  We then sort all variables in order of their cost
583        divided by the number of entries in rows which are not yet covered.  We randomize that
584        value a bit so that ties will be broken in different ways on different runs of the heuristic.
585        We then choose the best one and set it to one and repeat the exercise.
586
587    */
588    virtual int solution(double & objectiveValue,
589                         double * newSolution);
590    /// Resets stuff if model changes
591    virtual void resetModel(CbcModel * model);
592
593protected:
594};
595
596/** Just One class - this chooses one at random
597 */
598
599class CbcHeuristicJustOne : public CbcHeuristic {
600public:
601
602    // Default Constructor
603    CbcHeuristicJustOne ();
604
605    // Constructor with model - assumed before cuts
606    CbcHeuristicJustOne (CbcModel & model);
607
608    // Copy constructor
609    CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
610
611    // Destructor
612    ~CbcHeuristicJustOne ();
613
614    /// Clone
615    virtual CbcHeuristicJustOne * clone() const;
616
617    /// Assignment operator
618    CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
619
620    /// Create C++ lines to get to current state
621    virtual void generateCpp( FILE * fp) ;
622
623    /** returns 0 if no solution, 1 if valid solution
624        with better objective value than one passed in
625        Sets solution values if good, sets objective value (only if good)
626        This is called after cuts have been added - so can not add cuts
627        This does Fractional Diving
628    */
629    virtual int solution(double & objectiveValue,
630                         double * newSolution);
631    /// Resets stuff if model changes
632    virtual void resetModel(CbcModel * model);
633
634    /// update model (This is needed if cliques update matrix etc)
635    virtual void setModel(CbcModel * model);
636    /// Selects the next variable to branch on
637    /** Returns true if all the fractional variables can be trivially
638        rounded. Returns false, if there is at least one fractional variable
639        that is not trivially roundable. In this case, the bestColumn
640        returned will not be trivially roundable.
641        This is dummy as never called
642    */
643    virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
644                                        const double* /*newSolution*/,
645                                        int& /*bestColumn*/,
646                                        int& /*bestRound*/) {
647        return true;
648    }
649    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
650    virtual void validate();
651    /// Adds an heuristic with probability
652    void addHeuristic(const CbcHeuristic * heuristic, double probability);
653    /// Normalize probabilities
654    void normalizeProbabilities();
655protected:
656    // Data
657
658    // Probability of running a heuristic
659    double * probabilities_;
660
661    // Heuristics
662    CbcHeuristic ** heuristic_;
663
664    // Number of heuristics
665    int numberHeuristics_;
666
667};
668
669#endif
670
Note: See TracBrowser for help on using the repository browser.