Cbc 2.10.5
Loading...
Searching...
No Matches
CbcHeuristic.hpp
Go to the documentation of this file.
1/* $Id: CbcHeuristic.hpp 2467 2019-01-03 21:26:29Z unxusr $ */
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
26
31private:
35
36private:
43
44public:
46
49 double distance(const CbcHeuristicNode *node) const;
50 double minDistance(const CbcHeuristicNodeList &nodeList) const;
52 const double threshold) const;
53 double avgDistance(const CbcHeuristicNodeList &nodeList) const;
54};
55
57private:
60
61private:
62 std::vector< CbcHeuristicNode * > nodes_;
63
64public:
69
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//#############################################################################
86private:
87 void gutsOfDelete() {}
88 void gutsOfCopy(const CbcHeuristic &rhs);
89
90public:
91 // Default Constructor
93
94 // Constructor with model - assumed before cuts
96
97 // Copy constructor
99
100 virtual ~CbcHeuristic();
101
103 virtual CbcHeuristic *clone() const = 0;
104
107
109 virtual void setModel(CbcModel *model);
110
112 virtual void resetModel(CbcModel *model) = 0;
113
119 virtual int solution(double &objectiveValue,
120 double *newSolution)
121 = 0;
122
130 virtual int solution2(double & /*objectiveValue*/,
131 double * /*newSolution*/,
132 OsiCuts & /*cs*/)
133 {
134 return 0;
135 }
136
138 virtual void validate() {}
139
144 inline void setWhen(int value)
145 {
146 when_ = value;
147 }
149 inline int when() const
150 {
151 return when_;
152 }
153
155 inline void setNumberNodes(int value)
156 {
157 numberNodes_ = value;
158 }
160 inline int numberNodes() const
161 {
162 return numberNodes_;
163 }
174 inline void setSwitches(int value)
175 {
176 switches_ = value;
177 }
189 inline int switches() const
190 {
191 return switches_;
192 }
194 bool exitNow(double bestObjective) const;
196 inline void setFeasibilityPumpOptions(int value)
197 {
199 }
201 inline int feasibilityPumpOptions() const
202 {
204 }
206 inline void setModelOnly(CbcModel *model)
207 {
208 model_ = model;
209 }
210
212 inline void setFractionSmall(double value)
213 {
214 fractionSmall_ = value;
215 }
217 inline double fractionSmall() const
218 {
219 return fractionSmall_;
220 }
222 inline int numberSolutionsFound() const
223 {
225 }
228 {
230 }
231
241 int smallBranchAndBound(OsiSolverInterface *solver, int numberNodes,
242 double *newSolution, double &newSolutionValue,
243 double cutoff, std::string name) const;
245 virtual void generateCpp(FILE *) {}
247 void generateCpp(FILE *fp, const char *heuristic);
249 virtual bool canDealWithOdd() const
250 {
251 return false;
252 }
254 inline const char *heuristicName() const
255 {
256 return heuristicName_.c_str();
257 }
259 inline void setHeuristicName(const char *name)
260 {
261 heuristicName_ = name;
262 }
264 void setSeed(int value);
266 int getSeed() const;
268 inline void setDecayFactor(double value)
269 {
270 decayFactor_ = value;
271 }
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 }
296 inline void setShallowDepth(int value)
297 {
298 shallowDepth_ = value;
299 }
301 inline void setHowOftenShallow(int value)
302 {
303 howOftenShallow_ = value;
304 }
308 inline void setMinDistanceToRun(int value)
309 {
310 minDistanceToRun_ = value;
311 }
312
321 virtual bool shouldHeurRun(int whereFrom);
327 inline int numRuns() const
328 {
329 return numRuns_;
330 }
331
333 inline int numCouldRun() const
334 {
335 return numCouldRun_;
336 }
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
362 OsiSolverInterface *cloneBut(int type);
363
364protected:
368 int when_;
378 mutable double fractionSmall_;
380 CoinThreadRandom randomNumberGenerator_;
382 std::string heuristicName_;
383
385 mutable int howOften_;
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 */
431
434
437
440
442 mutable int numberNodesDone_;
443
444 // Input solution - so can be used as seed
446
447#ifdef JJF_ZERO
449 double *lowerBoundLastNode_;
451 double *upperBoundLastNode_;
452#endif
453};
457class CbcRounding : public CbcHeuristic {
458public:
459 // Default Constructor
461
462 // Constructor with model - assumed before cuts
464
465 // Copy constructor
467
468 // Destructor
470
473
475 virtual CbcHeuristic *clone() const;
477 virtual void generateCpp(FILE *fp);
478
480 virtual void resetModel(CbcModel *model);
481
483 virtual void setModel(CbcModel *model);
484
491 virtual int solution(double &objectiveValue,
492 double *newSolution);
499 virtual int solution(double &objectiveValue,
500 double *newSolution,
501 double solutionValue);
503 virtual void validate();
504
506 void setSeed(int value)
507 {
508 seed_ = value;
509 }
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
548public:
549 // Default Constructor
551
556 CbcHeuristicPartial(CbcModel &model, int fixPriority = 10000, int numberNodes = 200);
557
558 // Copy constructor
560
561 // Destructor
563
566
568 virtual CbcHeuristic *clone() const;
570 virtual void generateCpp(FILE *fp);
571
573 virtual void resetModel(CbcModel *model);
574
576 virtual void setModel(CbcModel *model);
577
584 virtual int solution(double &objectiveValue,
585 double *newSolution);
587 virtual void validate();
588
590 void setFixPriority(int value)
591 {
592 fixPriority_ = value;
593 }
594
596 virtual bool shouldHeurRun(int whereFrom);
597
598protected:
599 // Data
600
601 // All variables with abs priority <= this will be fixed
603};
604
610public:
611 // Default Constructor
613
614 /* Constructor with model
615 */
617
618 // Copy constructor
620
621 // Destructor
623
626
628 virtual CbcHeuristic *clone() const;
630 virtual void generateCpp(FILE *fp);
631
633 virtual void setModel(CbcModel *model);
634
646 virtual int solution(double &objectiveValue,
647 double *newSolution);
649 virtual void resetModel(CbcModel *model);
650
651protected:
652};
653
658public:
659 // Default Constructor
661
662 // Constructor with model - assumed before cuts
664
665 // Copy constructor
667
668 // Destructor
670
672 virtual CbcHeuristicJustOne *clone() const;
673
676
678 virtual void generateCpp(FILE *fp);
679
686 virtual int solution(double &objectiveValue,
687 double *newSolution);
689 virtual void resetModel(CbcModel *model);
690
692 virtual void setModel(CbcModel *model);
694
700 virtual bool selectVariableToBranch(OsiSolverInterface * /*solver*/,
701 const double * /*newSolution*/,
702 int & /*bestColumn*/,
703 int & /*bestRound*/)
704 {
705 return true;
706 }
708 virtual void validate();
710 void addHeuristic(const CbcHeuristic *heuristic, double probability);
713
714protected:
715 // Data
716
717 // Probability of running a heuristic
719
720 // Heuristics
722
723 // Number of heuristics
725};
726#endif
727
728/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
729*/
Abstract branching object base class Now just difference with OsiBranchingObject.
Just One class - this chooses one at random.
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
virtual CbcHeuristicJustOne * clone() const
Clone.
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne &rhs)
Assignment operator.
CbcHeuristic ** heuristic_
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
void normalizeProbabilities()
Normalize probabilities.
virtual bool selectVariableToBranch(OsiSolverInterface *, const double *, int &, int &)
Selects the next variable to branch on.
CbcHeuristicJustOne(const CbcHeuristicJustOne &)
CbcHeuristicJustOne(CbcModel &model)
void addHeuristic(const CbcHeuristic *heuristic, double probability)
Adds an heuristic with probability.
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
CbcHeuristicNodeList(const CbcHeuristicNodeList &rhs)
const CbcHeuristicNode * node(int i) const
void append(CbcHeuristicNode *&node)
void gutsOfCopy(const CbcHeuristicNodeList &rhs)
void append(const CbcHeuristicNodeList &nodes)
std::vector< CbcHeuristicNode * > nodes_
CbcHeuristicNodeList & operator=(const CbcHeuristicNodeList &rhs)
A class describing the branching decisions that were made to get to the node where a heuristic was in...
CbcHeuristicNode & operator=(const CbcHeuristicNode &)
double distance(const CbcHeuristicNode *node) const
CbcBranchingObject ** brObj_
The indices of the branching objects.
CbcHeuristicNode(CbcModel &model)
double minDistance(const CbcHeuristicNodeList &nodeList) const
double avgDistance(const CbcHeuristicNodeList &nodeList) const
CbcHeuristicNode(const CbcHeuristicNode &rhs)
void gutsOfConstructor(CbcModel &model)
int numObjects_
The number of branching decisions made.
bool minDistanceIsSmall(const CbcHeuristicNodeList &nodeList, const double threshold) const
Partial solution class If user knows a partial solution this tries to get an integer solution it uses...
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
void setFixPriority(int value)
Set priority level.
CbcHeuristicPartial(const CbcHeuristicPartial &)
virtual CbcHeuristic * clone() const
Clone.
CbcHeuristicPartial & operator=(const CbcHeuristicPartial &rhs)
Assignment operator.
virtual bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all.
CbcHeuristicPartial(CbcModel &model, int fixPriority=10000, int numberNodes=200)
Constructor with model - assumed before cuts Fixes all variables with priority <= given and does give...
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
Heuristic base class.
virtual CbcHeuristic * clone() const =0
Clone.
std::string heuristicName_
Name for printing.
int howOftenShallow_
How often to invoke the heuristics in the shallow part of the tree.
virtual bool canDealWithOdd() const
Returns true if can deal with "odd" problems e.g. sos type 2.
void gutsOfCopy(const CbcHeuristic &rhs)
bool shouldHeurRun_randomChoice()
Check whether the heuristic should run this time.
void setDecayFactor(double value)
Sets decay factor (for howOften) on failure.
double fractionSmall() const
Gets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1....
void printDistanceToNodes()
CbcHeuristic(CbcModel &model)
virtual bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all 0 - before cuts at root node (or from doHeuristics) 1 -...
int lastRunDeep_
After how many deep invocations was the heuristic run last time.
void setHeuristicName(const char *name)
set name of heuristic
void setFractionSmall(double value)
Sets fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound (default 1....
void incrementNumberSolutionsFound()
Increment how many solutions the heuristic thought it got.
int when_
When flag - 0 off, 1 at root, 2 other than root, 3 always.
int switches_
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
int numCouldRun_
How many times the heuristic could run.
int shallowDepth_
Upto this depth we call the tree shallow and the heuristic can be called multiple times.
int numRuns() const
how many times the heuristic has actually run
const char * heuristicName() const
return name of heuristic
virtual void resetModel(CbcModel *model)=0
Resets stuff if model changes.
int numCouldRun() const
How many times the heuristic could run.
int whereFrom() const
void setWhen(int value)
Sets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
void setMinDistanceToRun(int value)
How "far" should this node be from every other where the heuristic was run in order to allow the heur...
int numberSolutionsFound_
How many solutions the heuristic thought it got.
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
double fractionSmall_
Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound.
void setFeasibilityPumpOptions(int value)
Sets feasibility pump options (-1 is off)
virtual int solution(double &objectiveValue, double *newSolution)=0
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
int numberNodes() const
Gets number of nodes in a subtree (default 200)
void setModelOnly(CbcModel *model)
Just set model - do not do anything else.
void generateCpp(FILE *fp, const char *heuristic)
Create C++ lines to get to current state - does work for base class.
void setInputSolution(const double *solution, double objValue)
Set input solution.
int numRuns_
how many times the heuristic has actually run
void setShallowDepth(int value)
Upto this depth we call the tree shallow and the heuristic can be called multiple times.
void setWhereFrom(int value)
CbcModel * model_
Model.
int numberNodesDone_
How many nodes the heuristic did this go.
int numberNodes_
Number of nodes in any sub tree.
virtual void generateCpp(FILE *)
Create C++ lines to get to current state.
double * inputSolution_
int when() const
Gets "when" flag - 0 off, 1 at root, 2 other than root, 3 always.
virtual int solution2(double &, double *, OsiCuts &)
returns 0 if no solution, 1 if valid solution, -1 if just returning an estimate of best possible solu...
double decayFactor_
How much to increase how often.
int feasibilityPumpOptions_
Feasibility pump options , -1 is off >=0 for feasibility pump itself -2 quick proximity search -3 lon...
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
CbcHeuristic(const CbcHeuristic &)
int minDistanceToRun_
How "far" should this node be from every other where the heuristic was run in order to allow the heur...
OsiSolverInterface * cloneBut(int type)
Clone, but ...
int numInvocationsInDeep_
How many invocations happened when in the deep part of the tree.
void debugNodes()
CoinThreadRandom randomNumberGenerator_
Thread specific random number generator.
int smallBranchAndBound(OsiSolverInterface *solver, int numberNodes, double *newSolution, double &newSolutionValue, double cutoff, std::string name) const
Do mini branch and bound - return 0 not finished - no solution 1 not finished - solution 2 finished -...
void setSeed(int value)
Set random number generator seed.
int numberSolutionsFound() const
Get how many solutions the heuristic thought it got.
void gutsOfDelete()
int getSeed() const
Get random number generator seed.
int feasibilityPumpOptions() const
Gets feasibility pump options (-1 is off)
virtual ~CbcHeuristic()
int switches() const
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
int howOften_
How often to do (code can change)
CbcHeuristicNodeList runNodes_
The description of the nodes where this heuristic has been applied.
void setHowOftenShallow(int value)
How often to invoke the heuristics in the shallow part of the tree.
int numInvocationsInShallow_
How many invocations happened within the same node when in a shallow part of the tree.
bool exitNow(double bestObjective) const
Whether to exit at once on gap.
CbcHeuristic & operator=(const CbcHeuristic &rhs)
Assignment operator.
void setSwitches(int value)
Switches (does not apply equally to all heuristics) 1 bit - stop once allowable gap on objective reac...
bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn)
Is it integer for heuristics?
void setNumberNodes(int value)
Sets number of nodes in subtree (default 200)
Simple Branch and bound class.
Definition CbcModel.hpp:100
Rounding class.
CoinPackedMatrix matrix_
CbcRounding(const CbcRounding &)
CbcRounding & operator=(const CbcRounding &rhs)
Assignment operator.
unsigned short * up_
unsigned short * down_
virtual void setModel(CbcModel *model)
update model (This is needed if cliques update matrix etc)
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
CoinPackedMatrix matrixByRow_
unsigned short * equal_
void setSeed(int value)
Set seed.
virtual CbcHeuristic * clone() const
Clone.
virtual bool shouldHeurRun(int whereFrom)
Check whether the heuristic should run at all 0 - before cuts at root node (or from doHeuristics) 1 -...
CbcRounding(CbcModel &model)
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
virtual int solution(double &objectiveValue, double *newSolution, double solutionValue)
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
virtual void validate()
Validate model i.e. sets when_ to 0 if necessary (may be NULL)
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution with better objective value than one passed in Sets sol...
heuristic - just picks up any good solution found by solver - see OsiBabSolver
virtual void resetModel(CbcModel *model)
Resets stuff if model changes.
virtual CbcHeuristic * clone() const
Clone.
virtual int solution(double &objectiveValue, double *newSolution)
returns 0 if no solution, 1 if valid solution.
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
CbcSerendipity & operator=(const CbcSerendipity &rhs)
Assignment operator.
CbcSerendipity(const CbcSerendipity &)
virtual void setModel(CbcModel *model)
update model
CbcSerendipity(CbcModel &model)