Main Page
Related Pages
Namespaces
Classes
Files
File List
File Members
opt
build
coinor-cbc
coinor-cbc-2.5.0
debian
tmp
usr
include
coin
CbcTreeLocal.hpp
Go to the documentation of this file.
1
/* $Id: CbcTreeLocal.hpp 1286 2009-11-09 23:33:07Z EdwinStraver $ */
2
// Copyright (C) 2004, International Business Machines
3
// Corporation and others. All Rights Reserved.
4
#ifndef CbcTreeLocal_H
5
#define CbcTreeLocal_H
6
7
//#############################################################################
8
/* This implements (approximately) local branching as in the 2002 paper by
9
Matteo Fischetti and Andrea Lodi.
10
11
The very simple version of the algorithm for problems with
12
0-1 variables and continuous is as follows:
13
14
Obtain a feasible solution (one can be passed in).
15
16
Add a cut which limits search to a k neighborhood of this solution.
17
(At most k 0-1 variables may change value)
18
Do branch and bound on this problem.
19
20
If finished search and proven optimal then we can reverse cut so
21
any solutions must be at least k+1 away from solution and we can
22
add a new cut limiting search to a k neighborhood of new solution
23
repeat.
24
25
If finished search and no new solution then the simplest version
26
would reverse last cut and complete search. The version implemented
27
here can use time and node limits and can widen search (increase effective k)
28
.... and more
29
30
*/
31
32
#include "
CbcTree.hpp
"
33
#include "
CbcNode.hpp
"
34
#include "OsiRowCut.hpp"
35
class
CbcModel
;
36
37
38
class
CbcTreeLocal
:
public
CbcTree
{
39
40
public
:
41
42
// Default Constructor
43
CbcTreeLocal
();
44
45
/* Constructor with solution.
46
If solution NULL no solution, otherwise must be integer
47
range is initial upper bound (k) on difference from given solution.
48
typeCuts -
49
0 means just 0-1 cuts and will need to refine 0-1 solution
50
1 uses weaker cuts on all integer variables
51
maxDiversification is maximum number of range widenings to try
52
timeLimit is seconds in subTree
53
nodeLimit is nodes in subTree
54
refine is whether to see if we can prove current solution is optimal
55
when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
56
if false then no refinement but reverse cuts weaker
57
*/
58
CbcTreeLocal
(
CbcModel
* model,
const
double
* solution ,
int
range
= 10,
59
int
typeCuts
= 0,
int
maxDiversification
= 0,
60
int
timeLimit
= 1000000,
int
nodeLimit
= 1000000,
bool
refine
=
true
);
61
// Copy constructor
62
CbcTreeLocal
(
const
CbcTreeLocal
& rhs);
63
64
// = operator
65
CbcTreeLocal
&
operator=
(
const
CbcTreeLocal
& rhs);
66
67
virtual
~CbcTreeLocal
();
68
70
virtual
CbcTree
*
clone
()
const
;
72
virtual
void
generateCpp
( FILE * fp) ;
73
76
78
virtual
CbcNode
*
top
()
const
;
79
81
virtual
void
push
(
CbcNode
* x);
82
84
virtual
void
pop
() ;
85
87
89
91
int
createCut
(
const
double
* solution, OsiRowCut & cut);
92
94
virtual
bool
empty
() ;
95
97
virtual
void
endSearch
() ;
99
void
reverseCut
(
int
state,
double
bias = 0.0);
101
void
deleteCut
(OsiRowCut & cut);
103
void
passInSolution
(
const
double
* solution,
double
solutionValue);
104
// range i.e. k
105
inline
int
range
()
const
{
106
return
range_
;
107
}
108
// setrange i.e. k
109
inline
void
setRange
(
int
value) {
110
range_
= value;
111
}
112
// Type of cuts - 0=just 0-1, 1=all
113
inline
int
typeCuts
()
const
{
114
return
typeCuts_
;
115
}
116
// Type of cuts - 0=just 0-1, 1=all
117
inline
void
setTypeCuts
(
int
value) {
118
typeCuts_
= value;
119
}
120
// maximum number of diversifications
121
inline
int
maxDiversification
()
const
{
122
return
maxDiversification_
;
123
}
124
// maximum number of diversifications
125
inline
void
setMaxDiversification
(
int
value) {
126
maxDiversification_
= value;
127
}
128
// time limit per subtree
129
inline
int
timeLimit
()
const
{
130
return
timeLimit_
;
131
}
132
// time limit per subtree
133
inline
void
setTimeLimit
(
int
value) {
134
timeLimit_
= value;
135
}
136
// node limit for subtree
137
inline
int
nodeLimit
()
const
{
138
return
nodeLimit_
;
139
}
140
// node limit for subtree
141
inline
void
setNodeLimit
(
int
value) {
142
nodeLimit_
= value;
143
}
144
// Whether to do refinement step
145
inline
bool
refine
()
const
{
146
return
refine_
;
147
}
148
// Whether to do refinement step
149
inline
void
setRefine
(
bool
yesNo) {
150
refine_
= yesNo;
151
}
152
154
private
:
155
// Node for local cuts
156
CbcNode
*
localNode_
;
157
// best solution
158
double
*
bestSolution_
;
159
// saved solution
160
double
*
savedSolution_
;
161
// solution number at start of pass
162
int
saveNumberSolutions_
;
163
/* Cut. If zero size then no solution yet. Otherwise is left hand branch */
164
OsiRowCut
cut_
;
165
// This cut fixes all 0-1 variables
166
OsiRowCut
fixedCut_
;
167
// Model
168
CbcModel
*
model_
;
169
// Original lower bounds
170
double
*
originalLower_
;
171
// Original upper bounds
172
double
*
originalUpper_
;
173
// range i.e. k
174
int
range_
;
175
// Type of cuts - 0=just 0-1, 1=all
176
int
typeCuts_
;
177
// maximum number of diversifications
178
int
maxDiversification_
;
179
// current diversification
180
int
diversification_
;
181
// Whether next will be strong diversification
182
bool
nextStrong_
;
183
// Current rhs
184
double
rhs_
;
185
// Save allowable gap
186
double
savedGap_
;
187
// Best solution
188
double
bestCutoff_
;
189
// time limit per subtree
190
int
timeLimit_
;
191
// time when subtree started
192
int
startTime_
;
193
// node limit for subtree
194
int
nodeLimit_
;
195
// node count when subtree started
196
int
startNode_
;
197
// -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
198
int
searchType_
;
199
// Whether to do refinement step
200
bool
refine_
;
201
202
};
203
204
class
CbcTreeVariable
:
public
CbcTree
{
205
206
public
:
207
208
// Default Constructor
209
CbcTreeVariable
();
210
211
/* Constructor with solution.
212
If solution NULL no solution, otherwise must be integer
213
range is initial upper bound (k) on difference from given solution.
214
typeCuts -
215
0 means just 0-1 cuts and will need to refine 0-1 solution
216
1 uses weaker cuts on all integer variables
217
maxDiversification is maximum number of range widenings to try
218
timeLimit is seconds in subTree
219
nodeLimit is nodes in subTree
220
refine is whether to see if we can prove current solution is optimal
221
when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
222
if false then no refinement but reverse cuts weaker
223
*/
224
CbcTreeVariable
(
CbcModel
* model,
const
double
* solution ,
int
range
= 10,
225
int
typeCuts
= 0,
int
maxDiversification
= 0,
226
int
timeLimit
= 1000000,
int
nodeLimit
= 1000000,
bool
refine
=
true
);
227
// Copy constructor
228
CbcTreeVariable
(
const
CbcTreeVariable
& rhs);
229
230
// = operator
231
CbcTreeVariable
&
operator=
(
const
CbcTreeVariable
& rhs);
232
233
virtual
~CbcTreeVariable
();
234
236
virtual
CbcTree
*
clone
()
const
;
238
virtual
void
generateCpp
( FILE * fp) ;
239
242
244
virtual
CbcNode
*
top
()
const
;
245
247
virtual
void
push
(
CbcNode
* x);
248
250
virtual
void
pop
() ;
251
253
255
257
int
createCut
(
const
double
* solution, OsiRowCut & cut);
258
260
virtual
bool
empty
() ;
261
263
virtual
void
endSearch
() ;
265
void
reverseCut
(
int
state,
double
bias = 0.0);
267
void
deleteCut
(OsiRowCut & cut);
269
void
passInSolution
(
const
double
* solution,
double
solutionValue);
270
// range i.e. k
271
inline
int
range
()
const
{
272
return
range_
;
273
}
274
// setrange i.e. k
275
inline
void
setRange
(
int
value) {
276
range_
= value;
277
}
278
// Type of cuts - 0=just 0-1, 1=all
279
inline
int
typeCuts
()
const
{
280
return
typeCuts_
;
281
}
282
// Type of cuts - 0=just 0-1, 1=all
283
inline
void
setTypeCuts
(
int
value) {
284
typeCuts_
= value;
285
}
286
// maximum number of diversifications
287
inline
int
maxDiversification
()
const
{
288
return
maxDiversification_
;
289
}
290
// maximum number of diversifications
291
inline
void
setMaxDiversification
(
int
value) {
292
maxDiversification_
= value;
293
}
294
// time limit per subtree
295
inline
int
timeLimit
()
const
{
296
return
timeLimit_
;
297
}
298
// time limit per subtree
299
inline
void
setTimeLimit
(
int
value) {
300
timeLimit_
= value;
301
}
302
// node limit for subtree
303
inline
int
nodeLimit
()
const
{
304
return
nodeLimit_
;
305
}
306
// node limit for subtree
307
inline
void
setNodeLimit
(
int
value) {
308
nodeLimit_
= value;
309
}
310
// Whether to do refinement step
311
inline
bool
refine
()
const
{
312
return
refine_
;
313
}
314
// Whether to do refinement step
315
inline
void
setRefine
(
bool
yesNo) {
316
refine_
= yesNo;
317
}
318
320
private
:
321
// Node for local cuts
322
CbcNode
*
localNode_
;
323
// best solution
324
double
*
bestSolution_
;
325
// saved solution
326
double
*
savedSolution_
;
327
// solution number at start of pass
328
int
saveNumberSolutions_
;
329
/* Cut. If zero size then no solution yet. Otherwise is left hand branch */
330
OsiRowCut
cut_
;
331
// This cut fixes all 0-1 variables
332
OsiRowCut
fixedCut_
;
333
// Model
334
CbcModel
*
model_
;
335
// Original lower bounds
336
double
*
originalLower_
;
337
// Original upper bounds
338
double
*
originalUpper_
;
339
// range i.e. k
340
int
range_
;
341
// Type of cuts - 0=just 0-1, 1=all
342
int
typeCuts_
;
343
// maximum number of diversifications
344
int
maxDiversification_
;
345
// current diversification
346
int
diversification_
;
347
// Whether next will be strong diversification
348
bool
nextStrong_
;
349
// Current rhs
350
double
rhs_
;
351
// Save allowable gap
352
double
savedGap_
;
353
// Best solution
354
double
bestCutoff_
;
355
// time limit per subtree
356
int
timeLimit_
;
357
// time when subtree started
358
int
startTime_
;
359
// node limit for subtree
360
int
nodeLimit_
;
361
// node count when subtree started
362
int
startNode_
;
363
// -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
364
int
searchType_
;
365
// Whether to do refinement step
366
bool
refine_
;
367
368
};
369
#endif
370
Generated on Tue Mar 1 2016 22:38:13 by
1.8.4