Cbc 2.10.12
Loading...
Searching...
No Matches
CbcHeuristic.hpp
Go to the documentation of this file.
1/* $Id$ */
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#include "CbcModel.hpp"
16
17class OsiSolverInterface;
18
19class CbcModel;
20#ifdef COIN_HAS_CLP
21#include "OsiClpSolverInterface.hpp"
22#endif
23//#############################################################################
24
27
30
32private:
36
37private:
44
45public:
47
50 double distance(const CbcHeuristicNode *node) const;
51 double minDistance(const CbcHeuristicNodeList &nodeList) const;
53 const double threshold) const;
54 double avgDistance(const CbcHeuristicNodeList &nodeList) const;
55};
56
58private:
61
62private:
63 std::vector< CbcHeuristicNode * > nodes_;
64
65public:
70
72 void append(const CbcHeuristicNodeList &nodes);
73 inline const CbcHeuristicNode *node(int i) const
74 {
75 return nodes_[i];
76 }
77 inline int size() const
78 {
79 return static_cast< int >(nodes_.size());
80 }
81};
82
83//#############################################################################
85
87private:
88 void gutsOfDelete() {}
89 void gutsOfCopy(const CbcHeuristic &rhs);
90
91public:
92 // Default Constructor
94
95 // Constructor with model - assumed before cuts
97
98 // Copy constructor
100
101 virtual ~CbcHeuristic();
102
104 virtual CbcHeuristic *clone() const = 0;
105
108
110 virtual void setModel(CbcModel *model);
111
113 virtual void resetModel(CbcModel *model) = 0;
114
120 virtual int solution(double &objectiveValue,
121 double *newSolution)
122 = 0;
123
131 virtual int solution2(double & /*objectiveValue*/,
132 double * /*newSolution*/,
133 OsiCuts & /*cs*/)
134 {
135 return 0;
136 }
137
139 virtual void validate() {}
140
145 inline void setWhen(int value)
146 {
147 when_ = value;
148 }
149
150 inline int when() const
151 {
152 return when_;
153 }
154
156 inline void setNumberNodes(int value)
157 {
158 numberNodes_ = value;
159 }
160
161 inline int numberNodes() const
162 {
163 return numberNodes_;
164 }
165
175 inline void setSwitches(int value)
176 {
177 switches_ = value;
178 }
179
190 inline int switches() const
191 {
192 return switches_;
193 }
194
195 bool exitNow(double bestObjective) const;
197 inline void setFeasibilityPumpOptions(int value)
198 {
200 }
201
202 inline int feasibilityPumpOptions() const
203 {
205 }
206
207 inline void setModelOnly(CbcModel *model)
208 {
209 model_ = model;
210 }
211
213 inline void setFractionSmall(double value)
214 {
215 fractionSmall_ = value;
216 }
217
218 inline double fractionSmall() const
219 {
220 return fractionSmall_;
221 }
222
223 inline int numberSolutionsFound() const
224 {
226 }
227
229 {
231 }
232
242 int smallBranchAndBound(OsiSolverInterface *solver, int numberNodes,
243 double *newSolution, double &newSolutionValue,
244 double cutoff, std::string name) const;
246 virtual void generateCpp(FILE *) {}
248 void generateCpp(FILE *fp, const char *heuristic);
250 virtual bool canDealWithOdd() const
251 {
252 return false;
253 }
254
255 inline const char *heuristicName() const
256 {
257 return heuristicName_.c_str();
258 }
259
260 inline void setHeuristicName(const char *name)
261 {
262 heuristicName_ = name;
263 }
264
265 void setSeed(int value);
267 int getSeed() const;
269 inline void setDecayFactor(double value)
270 {
271 decayFactor_ = value;
272 }
273
274 void setInputSolution(const double *solution, double objValue);
275 /* Runs if bit set
276 0 - before cuts at root node (or from doHeuristics)
277 1 - during cuts at root
278 2 - after root node cuts
279 3 - after cuts at other nodes
280 4 - during cuts at other nodes
281 8 added if previous heuristic in loop found solution
282 */
283 inline void setWhereFrom(int value)
284 {
285 whereFrom_ = value;
286 }
287 inline int whereFrom() const
288 {
289 return whereFrom_;
290 }
291
297 inline void setShallowDepth(int value)
298 {
299 shallowDepth_ = value;
300 }
301
302 inline void setHowOftenShallow(int value)
303 {
304 howOftenShallow_ = value;
305 }
306
309 inline void setMinDistanceToRun(int value)
310 {
311 minDistanceToRun_ = value;
312 }
313
322 virtual bool shouldHeurRun(int whereFrom);
328 inline int numRuns() const
329 {
330 return numRuns_;
331 }
332
334 inline int numCouldRun() const
335 {
336 return numCouldRun_;
337 }
338
339 inline double trueObjValue(double value) const
340 {
341 return (model_->moreSpecialOptions2()&67108864)==0 ? value : -value;
342 }
343
344#ifdef COIN_HAS_CLP
345 inline bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn) const
346 {
347 const OsiClpSolverInterface *clpSolver
348 = dynamic_cast< const OsiClpSolverInterface * >(solver);
349 if (clpSolver)
350 return clpSolver->isHeuristicInteger(iColumn);
351 else
352 return solver->isInteger(iColumn);
353 }
354#else
355 inline bool isHeuristicInteger(const OsiSolverInterface *solver, int iColumn)
356 {
357 return solver->isInteger(iColumn);
358 }
359#endif
368 OsiSolverInterface *cloneBut(int type);
369
370protected:
374 int when_;
384 mutable double fractionSmall_;
386 CoinThreadRandom randomNumberGenerator_;
388 std::string heuristicName_;
389
391 mutable int howOften_;
404 mutable int switches_;
405 /* Runs if bit set
406 0 - before cuts at root node (or from doHeuristics)
407 1 - during cuts at root
408 2 - after root node cuts
409 3 - after cuts at other nodes
410 4 - during cuts at other nodes
411 8 added if previous heuristic in loop found solution
412 */
437
440
443
446
448 mutable int numberNodesDone_;
449
450 // Input solution - so can be used as seed
452
453#ifdef JJF_ZERO
455 double *lowerBoundLastNode_;
457 double *upperBoundLastNode_;
458#endif
459};
460
462
463class CbcRounding : public CbcHeuristic {
464public:
465 // Default Constructor
467
468 // Constructor with model - assumed before cuts
470
471 // Copy constructor
473
474 // Destructor
476
479
481 virtual CbcHeuristic *clone() const;
483 virtual void generateCpp(FILE *fp);
484
486 virtual void resetModel(CbcModel *model);
487
489 virtual void setModel(CbcModel *model);
490
497 virtual int solution(double &objectiveValue,
498 double *newSolution);
505 virtual int solution(double &objectiveValue,
506 double *newSolution,
507 double solutionValue);
509 virtual void validate();
510
512 void setSeed(int value)
513 {
514 seed_ = value;
515 }
516
524 virtual bool shouldHeurRun(int whereFrom);
525
526protected:
527 // Data
528
529 // Original matrix by column
530 CoinPackedMatrix matrix_;
531
532 // Original matrix by
533 CoinPackedMatrix matrixByRow_;
534
535 // Down locks
536 unsigned short *down_;
537
538 // Up locks
539 unsigned short *up_;
540
541 // Equality locks
542 unsigned short *equal_;
543
544 // Seed for random stuff
545 int seed_;
546};
547
552
554public:
555 // Default Constructor
557
562 CbcHeuristicPartial(CbcModel &model, int fixPriority = 10000, int numberNodes = 200);
563
564 // Copy constructor
566
567 // Destructor
569
572
574 virtual CbcHeuristic *clone() const;
576 virtual void generateCpp(FILE *fp);
577
579 virtual void resetModel(CbcModel *model);
580
582 virtual void setModel(CbcModel *model);
583
590 virtual int solution(double &objectiveValue,
591 double *newSolution);
593 virtual void validate();
594
596 void setFixPriority(int value)
597 {
598 fixPriority_ = value;
599 }
600
602 virtual bool shouldHeurRun(int whereFrom);
603
604protected:
605 // Data
606
607 // All variables with abs priority <= this will be fixed
609};
610
614
616public:
617 // Default Constructor
619
620 /* Constructor with model
621 */
623
624 // Copy constructor
626
627 // Destructor
629
632
634 virtual CbcHeuristic *clone() const;
636 virtual void generateCpp(FILE *fp);
637
639 virtual void setModel(CbcModel *model);
640
652 virtual int solution(double &objectiveValue,
653 double *newSolution);
655 virtual void resetModel(CbcModel *model);
656
657protected:
658};
659
662
664public:
665 // Default Constructor
667
668 // Constructor with model - assumed before cuts
670
671 // Copy constructor
673
674 // Destructor
676
678 virtual CbcHeuristicJustOne *clone() const;
679
682
684 virtual void generateCpp(FILE *fp);
685
692 virtual int solution(double &objectiveValue,
693 double *newSolution);
695 virtual void resetModel(CbcModel *model);
696
698 virtual void setModel(CbcModel *model);
700
706 virtual bool selectVariableToBranch(OsiSolverInterface * /*solver*/,
707 const double * /*newSolution*/,
708 int & /*bestColumn*/,
709 int & /*bestRound*/)
710 {
711 return true;
712 }
713
714 virtual void validate();
716 void addHeuristic(const CbcHeuristic *heuristic, double probability);
719
720protected:
721 // Data
722
723 // Probability of running a heuristic
725
726 // Heuristics
728
729 // Number of heuristics
731};
732#endif
733
734/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
735*/
Abstract branching object base class Now just difference with OsiBranchingObject.
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
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)
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 trueObjValue(double value) const
Return objective function value with sign corrected.
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
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...
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)