source: trunk/Cbc/src/CbcHeuristic.hpp

Last change on this file was 2467, checked in by unxusr, 5 months ago

spaces after angles

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