Main Page
Related Pages
Namespaces
Classes
Files
File List
File Members
opt
build
coinor-cbc
coinor-cbc-2.5.0
Cbc
src
CbcHeuristic.hpp
Go to the documentation of this file.
1
/* $Id: CbcHeuristic.hpp 1432 2010-02-07 19:33:53Z bjarni $ */
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
14
class
OsiSolverInterface;
15
16
class
CbcModel
;
17
18
//#############################################################################
19
20
class
CbcHeuristicNodeList
;
21
class
CbcBranchingObject
;
22
26
class
CbcHeuristicNode
{
27
private
:
28
void
gutsOfConstructor
(
CbcModel
& model);
29
CbcHeuristicNode
();
30
CbcHeuristicNode
&
operator=
(
const
CbcHeuristicNode
&);
31
private
:
33
int
numObjects_
;
37
CbcBranchingObject
**
brObj_
;
38
public
:
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
50
class
CbcHeuristicNodeList
{
51
private
:
52
void
gutsOfDelete
();
53
void
gutsOfCopy
(
const
CbcHeuristicNodeList
& rhs);
54
private
:
55
std::vector<CbcHeuristicNode*>
nodes_
;
56
public
:
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
nodes_
.size();
69
}
70
};
71
72
//#############################################################################
75
class
CbcHeuristic
{
76
private
:
77
void
gutsOfDelete
() {}
78
void
gutsOfCopy
(
const
CbcHeuristic
& rhs);
79
80
public
:
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
93
virtual
CbcHeuristic
*
clone
()
const
= 0;
94
96
CbcHeuristic
&
operator=
(
const
CbcHeuristic
& rhs);
97
99
virtual
void
setModel
(
CbcModel
* model);
100
102
virtual
void
resetModel
(
CbcModel
* model) = 0;
103
109
virtual
int
solution
(
double
& objectiveValue,
110
double
* newSolution) = 0;
111
119
virtual
int
solution2
(
double
&
/*objectiveValue*/
,
120
double
*
/*newSolution*/
,
121
OsiCuts &
/*cs*/
) {
122
return
0;
123
}
124
126
virtual
void
validate
() {}
127
132
inline
void
setWhen
(
int
value) {
133
when_
= value;
134
}
136
inline
int
when
()
const
{
137
return
when_
;
138
}
139
141
inline
void
setNumberNodes
(
int
value) {
142
numberNodes_
= value;
143
}
145
inline
int
numberNodes
()
const
{
146
return
numberNodes_
;
147
}
157
inline
void
setSwitches
(
int
value) {
158
switches_
= value;
159
}
169
inline
int
switches
()
const
{
170
return
switches_
;
171
}
173
bool
exitNow
(
double
bestObjective)
const
;
175
inline
void
setFeasibilityPumpOptions
(
int
value) {
176
feasibilityPumpOptions_
= value;
177
}
179
inline
int
feasibilityPumpOptions
()
const
{
180
return
feasibilityPumpOptions_
;
181
}
183
inline
void
setModelOnly
(
CbcModel
* model) {
184
model_
= model;
185
}
186
187
189
inline
void
setFractionSmall
(
double
value) {
190
fractionSmall_
= value;
191
}
193
inline
double
fractionSmall
()
const
{
194
return
fractionSmall_
;
195
}
197
inline
int
numberSolutionsFound
()
const
{
198
return
numberSolutionsFound_
;
199
}
201
inline
void
incrementNumberSolutionsFound
() {
202
numberSolutionsFound_
++;
203
}
204
214
int
smallBranchAndBound
(OsiSolverInterface * solver,
int
numberNodes
,
215
double
* newSolution,
double
& newSolutionValue,
216
double
cutoff , std::string name)
const
;
218
virtual
void
generateCpp
( FILE * ) {}
220
void
generateCpp
( FILE * fp,
const
char
* heuristic) ;
222
virtual
bool
canDealWithOdd
()
const
{
223
return
false
;
224
}
226
inline
const
char
*
heuristicName
()
const
{
227
return
heuristicName_
.c_str();
228
}
230
inline
void
setHeuristicName
(
const
char
*name) {
231
heuristicName_
= name;
232
}
234
void
setSeed
(
int
value);
236
inline
void
setDecayFactor
(
double
value) {
237
decayFactor_
= value;
238
}
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
}
258
inline
void
setShallowDepth
(
int
value) {
259
shallowDepth_
= value;
260
}
262
inline
void
setHowOftenShallow
(
int
value) {
263
howOftenShallow_
= value;
264
}
268
inline
void
setMinDistanceToRun
(
int
value) {
269
minDistanceToRun_
= value;
270
}
271
280
virtual
bool
shouldHeurRun
(
int
whereFrom);
282
bool
shouldHeurRun_randomChoice
();
283
void
debugNodes
();
284
void
printDistanceToNodes
();
286
inline
int
numRuns
()
const
{
287
return
numRuns_
;
288
}
289
291
inline
int
numCouldRun
()
const
{
292
return
numCouldRun_
;
293
}
298
OsiSolverInterface *
cloneBut
(
int
type);
299
protected
:
300
302
CbcModel
*
model_
;
304
int
when_
;
306
int
numberNodes_
;
308
int
feasibilityPumpOptions_
;
310
mutable
double
fractionSmall_
;
312
CoinThreadRandom
randomNumberGenerator_
;
314
std::string
heuristicName_
;
315
317
int
howOften_
;
319
double
decayFactor_
;
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_
;
345
int
shallowDepth_
;
347
int
howOftenShallow_
;
350
int
numInvocationsInShallow_
;
353
int
numInvocationsInDeep_
;
355
int
lastRunDeep_
;
357
int
numRuns_
;
361
int
minDistanceToRun_
;
362
364
CbcHeuristicNodeList
runNodes_
;
365
367
int
numCouldRun_
;
368
370
int
numberSolutionsFound_
;
371
372
// Input solution - so can be used as seed
373
double
*
inputSolution_
;
374
375
376
#ifdef JJF_ZERO
377
double
* lowerBoundLastNode_;
380
double
* upperBoundLastNode_;
381
#endif
382
};
386
class
CbcRounding
:
public
CbcHeuristic
{
387
public
:
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
402
CbcRounding
&
operator=
(
const
CbcRounding
& rhs);
403
405
virtual
CbcHeuristic
*
clone
()
const
;
407
virtual
void
generateCpp
( FILE * fp) ;
408
410
virtual
void
resetModel
(
CbcModel
* model);
411
413
virtual
void
setModel
(
CbcModel
* model);
414
415
using
CbcHeuristic::solution
;
421
virtual
int
solution
(
double
& objectiveValue,
422
double
* newSolution);
429
virtual
int
solution
(
double
& objectiveValue,
430
double
* newSolution,
431
double
solutionValue);
433
virtual
void
validate
();
434
435
437
void
setSeed
(
int
value) {
438
seed_
= value;
439
}
440
441
protected
:
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
468
class
CbcHeuristicPartial
:
public
CbcHeuristic
{
469
public
:
470
471
// Default Constructor
472
CbcHeuristicPartial
();
473
478
CbcHeuristicPartial
(
CbcModel
& model,
int
fixPriority = 10000,
int
numberNodes
= 200);
479
480
// Copy constructor
481
CbcHeuristicPartial
(
const
CbcHeuristicPartial
&);
482
483
// Destructor
484
~CbcHeuristicPartial
();
485
487
CbcHeuristicPartial
&
operator=
(
const
CbcHeuristicPartial
& rhs);
488
490
virtual
CbcHeuristic
*
clone
()
const
;
492
virtual
void
generateCpp
( FILE * fp) ;
493
495
virtual
void
resetModel
(
CbcModel
* model);
496
498
virtual
void
setModel
(
CbcModel
* model);
499
500
using
CbcHeuristic::solution
;
506
virtual
int
solution
(
double
& objectiveValue,
507
double
* newSolution);
509
virtual
void
validate
();
510
511
513
void
setFixPriority
(
int
value) {
514
fixPriority_
= value;
515
}
516
518
virtual
bool
shouldHeurRun
(
int
whereFrom);
519
520
protected
:
521
// Data
522
523
// All variables with abs priority <= this will be fixed
524
int
fixPriority_
;
525
};
526
531
class
CbcSerendipity
:
public
CbcHeuristic
{
532
public
:
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
548
CbcSerendipity
&
operator=
(
const
CbcSerendipity
& rhs);
549
551
virtual
CbcHeuristic
*
clone
()
const
;
553
virtual
void
generateCpp
( FILE * fp) ;
554
556
virtual
void
setModel
(
CbcModel
* model);
557
558
using
CbcHeuristic::solution
;
569
virtual
int
solution
(
double
& objectiveValue,
570
double
* newSolution);
572
virtual
void
resetModel
(
CbcModel
* model);
573
574
protected
:
575
};
576
580
class
CbcHeuristicJustOne
:
public
CbcHeuristic
{
581
public
:
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
596
virtual
CbcHeuristicJustOne
*
clone
()
const
;
597
599
CbcHeuristicJustOne
&
operator=
(
const
CbcHeuristicJustOne
& rhs);
600
602
virtual
void
generateCpp
( FILE * fp) ;
603
610
virtual
int
solution
(
double
& objectiveValue,
611
double
* newSolution);
613
virtual
void
resetModel
(
CbcModel
* model);
614
616
virtual
void
setModel
(
CbcModel
* model);
618
624
virtual
bool
selectVariableToBranch
(OsiSolverInterface*
/*solver*/
,
625
const
double
*
/*newSolution*/
,
626
int
&
/*bestColumn*/
,
627
int
&
/*bestRound*/
) {
628
return
true
;
629
}
631
virtual
void
validate
();
633
void
addHeuristic
(
const
CbcHeuristic
* heuristic,
double
probability);
635
void
normalizeProbabilities
();
636
protected
:
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
Generated on Tue Mar 1 2016 22:38:12 by
1.8.4