source: branches/heur/Cbc/src/CbcBranchBase.cpp @ 885

Last change on this file since 885 was 833, checked in by forrest, 12 years ago

changes to heuristics and allow collection of more statistics

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.7 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#if defined(_MSC_VER)
4// Turn off compiler warning about long names
5#  pragma warning(disable:4786)
6#endif
7#include <cassert>
8#include <cmath>
9#include <cfloat>
10
11#include "OsiSolverInterface.hpp"
12#include "OsiSolverBranch.hpp"
13#include "OsiChooseVariable.hpp"
14#include "CbcModel.hpp"
15#include "CbcMessage.hpp"
16#include "CbcBranchBase.hpp"
17
18
19// Default Constructor
20CbcObject::CbcObject() 
21  : OsiObject(),
22    model_(NULL),
23   id_(-1),
24   preferredWay_(0)
25{
26}
27
28// Constructor from model
29CbcObject::CbcObject(CbcModel * model)
30  : OsiObject(),
31    model_(model),
32    id_(-1),
33    preferredWay_(0)
34{
35}
36
37
38// Destructor
39CbcObject::~CbcObject ()
40{
41}
42
43// Copy constructor
44CbcObject::CbcObject ( const CbcObject & rhs)
45  : OsiObject(rhs)
46{
47  model_ = rhs.model_;
48  id_ = rhs.id_;
49  preferredWay_ = rhs.preferredWay_;
50}
51
52// Assignment operator
53CbcObject & 
54CbcObject::operator=( const CbcObject& rhs)
55{
56  if (this!=&rhs) {
57    OsiObject::operator=(rhs);
58    model_ = rhs.model_;
59    id_ = rhs.id_;
60    preferredWay_ = rhs.preferredWay_;
61  }
62  return *this;
63}
64
65/* Returns floor and ceiling i.e. closest valid points
66 */
67void 
68CbcObject::floorCeiling(double & floorValue, double & ceilingValue, double value,
69                        double tolerance) const
70{
71  if (fabs(floor(value+0.5)-value)>tolerance) {
72    floorValue = floor(value);
73  } else {
74    floorValue = floor(value+0.5);
75  }
76  ceilingValue = floorValue+1.0;
77}
78/* Infeasibility of the object
79     
80    This is some measure of the infeasibility of the object. 0.0
81    indicates that the object is satisfied.
82 
83    The preferred branching direction is returned in way,
84 
85    This is used to prepare for strong branching but should also think of
86    case when no strong branching
87 
88    The object may also compute an estimate of cost of going "up" or "down".
89    This will probably be based on pseudo-cost ideas
90
91    This should also set mutable infeasibility_ and whichWay_
92    This is for instant re-use for speed
93*/
94double 
95CbcObject::infeasibility(const OsiSolverInterface * solver,int &preferredWay) const 
96{
97  assert (solver==model_->solver());
98  return infeasibility(preferredWay);
99}
100 
101/* For the variable(s) referenced by the object,
102      look at the current solution and set bounds to match the solution.
103      Returns measure of how much it had to move solution to make feasible
104*/
105double 
106CbcObject::feasibleRegion(OsiSolverInterface * solver) const 
107{
108  assert (solver==model_->solver());
109  CbcObject * fudge = const_cast<CbcObject *>(this);
110  fudge->feasibleRegion();
111  return 0.0;
112}
113/* Infeasibility of the object
114     
115    This is some measure of the infeasibility of the object. 0.0
116    indicates that the object is satisfied.
117 
118    The preferred branching direction is returned in way,
119 
120    This is used to prepare for strong branching but should also think of
121    case when no strong branching
122 
123    The object may also compute an estimate of cost of going "up" or "down".
124    This will probably be based on pseudo-cost ideas
125
126    This should also set mutable infeasibility_ and whichWay_
127    This is for instant re-use for speed
128*/
129double 
130CbcObject::infeasibility(const OsiBranchingInformation * info,
131                         int &preferredWay) const 
132{
133  return infeasibility(preferredWay);
134}
135 
136/* For the variable(s) referenced by the object,
137      look at the current solution and set bounds to match the solution.
138      Returns measure of how much it had to move solution to make feasible
139*/
140double 
141CbcObject::feasibleRegion(OsiSolverInterface * solver,const OsiBranchingInformation * info) const 
142{
143  assert (solver==model_->solver());
144  CbcObject * fudge = const_cast<CbcObject *>(this);
145  fudge->feasibleRegion();
146  return 0.0;
147}
148 
149/* Create a branching object and indicate which way to branch first.
150     
151      The branching object has to know how to create branches (fix
152      variables, etc.)
153*/
154OsiBranchingObject * 
155CbcObject::createBranch(OsiSolverInterface * solver, int way) const 
156{
157  assert (solver==model_->solver());
158  CbcObject * fudge = const_cast<CbcObject *>(this);
159  return fudge->createBranch(way);
160}
161/* Create a branching object and indicate which way to branch first.
162     
163      The branching object has to know how to create branches (fix
164      variables, etc.)
165*/
166OsiBranchingObject * 
167CbcObject::createBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) const 
168{
169  assert (solver==model_->solver());
170  CbcObject * fudge = const_cast<CbcObject *>(this);
171  return fudge->createBranch(way);
172}
173/* Create an OsiSolverBranch object
174   
175This returns NULL if branch not represented by bound changes
176*/
177OsiSolverBranch * 
178CbcObject::solverBranch() const
179{
180  return NULL;
181}
182/* Pass in information on branch just done and create CbcObjectUpdateData instance.
183   If object does not need data then backward pointer will be NULL.
184   Assumes can get information from solver */
185CbcObjectUpdateData
186CbcObject::createUpdateInformation(const OsiSolverInterface * solver, 
187                                                        const CbcNode * node,
188                                                        const CbcBranchingObject * branchingObject)
189{
190  return CbcObjectUpdateData();
191}
192 
193// Default Constructor
194CbcBranchingObject::CbcBranchingObject()
195  : OsiBranchingObject()
196{
197  model_=NULL;
198  originalCbcObject_=NULL;
199  variable_=-1;
200  way_=0;
201}
202
203// Useful constructor
204CbcBranchingObject::CbcBranchingObject (CbcModel * model, int variable, int way , double value)
205  : OsiBranchingObject(model->solver(),value)
206{
207  model_= model;
208  originalCbcObject_=NULL;
209  variable_=variable;
210  way_=way;
211}
212
213// Copy constructor
214CbcBranchingObject::CbcBranchingObject ( const CbcBranchingObject & rhs)
215  : OsiBranchingObject(rhs)
216{
217  model_=rhs.model_;
218  originalCbcObject_=rhs.originalCbcObject_;
219  variable_=rhs.variable_;
220  way_=rhs.way_;
221  value_=rhs.value_;
222}
223
224// Assignment operator
225CbcBranchingObject & 
226CbcBranchingObject::operator=( const CbcBranchingObject& rhs)
227{
228  if (this != &rhs) {
229    OsiBranchingObject::operator=(rhs);
230    model_=rhs.model_;
231    originalCbcObject_=rhs.originalCbcObject_;
232    variable_=rhs.variable_;
233    way_=rhs.way_;
234  }
235  return *this;
236}
237
238// Destructor
239CbcBranchingObject::~CbcBranchingObject ()
240{
241}
242// Default Constructor
243CbcBranchDecision::CbcBranchDecision ()
244  : object_(NULL),model_(NULL),chooseMethod_(NULL)
245{
246}
247
248// Copy Constructor
249CbcBranchDecision::CbcBranchDecision (const CbcBranchDecision &rhs)
250  : object_(NULL),model_(rhs.model_),chooseMethod_(NULL)
251{
252  if (rhs.chooseMethod_)
253    chooseMethod_ = rhs.chooseMethod_->clone();
254}
255
256CbcBranchDecision::~CbcBranchDecision()
257{
258  delete object_;
259  delete chooseMethod_;
260}
261/* Compare N branching objects. Return index of best
262   and sets way of branching in chosen object.
263   
264   This routine is used only after strong branching.
265   This is reccommended version as it can be more sophisticated
266*/
267
268int
269CbcBranchDecision::bestBranch (CbcBranchingObject ** objects, int numberObjects,
270                               int numberUnsatisfied,
271                               double * changeUp, int * numberInfeasibilitiesUp,
272                               double * changeDown, int * numberInfeasibilitiesDown,
273                               double objectiveValue) 
274{
275  int bestWay=0;
276  int whichObject = -1;
277  if (numberObjects) {
278    initialize(objects[0]->model()); 
279    CbcBranchingObject * bestObject = NULL;
280    for (int i = 0 ; i < numberObjects ; i++) {
281      int betterWay = betterBranch(objects[i],
282                                   bestObject,
283                                   changeUp[i],
284                                   numberInfeasibilitiesUp [i],
285                                   changeDown[i],
286                                   numberInfeasibilitiesDown[i] );
287      if (betterWay) {
288        bestObject = objects[i];
289        bestWay = betterWay;
290        whichObject=i;
291      }
292    }
293    // set way in best
294    if (whichObject>=0) 
295      objects[whichObject]->way(bestWay);
296  }
297  return whichObject;
298}
299// Set (clone) chooseMethod
300void 
301CbcBranchDecision::setChooseMethod(const OsiChooseVariable & method)
302{ 
303  delete chooseMethod_;
304  chooseMethod_ = method.clone();
305}
306// Default constructor
307CbcConsequence::CbcConsequence()
308{
309}
310
311
312// Destructor
313CbcConsequence::~CbcConsequence ()
314{
315}
316
317// Copy constructor
318CbcConsequence::CbcConsequence ( const CbcConsequence & rhs)
319{
320}
321
322// Assignment operator
323CbcConsequence & 
324CbcConsequence::operator=( const CbcConsequence& rhs)
325{
326  if (this!=&rhs) {
327  }
328  return *this;
329}
330// Default constructor
331CbcObjectUpdateData::CbcObjectUpdateData()
332  : object_(NULL),
333    way_(0),
334    objectNumber_(-1),
335    change_(0.0),
336    status_(0),
337    intDecrease_(0),
338    branchingValue_(0.0),
339    originalObjective_(COIN_DBL_MAX),
340    cutoff_(COIN_DBL_MAX)
341{
342}
343
344// Useful constructor
345CbcObjectUpdateData::CbcObjectUpdateData (CbcObject * object,
346                                          int way,
347                                          double change,
348                                          int status,
349                                          int intDecrease,
350                                          double branchingValue)
351  : object_(object),
352    way_(way),
353    objectNumber_(-1),
354    change_(change),
355    status_(status),
356    intDecrease_(intDecrease),
357    branchingValue_(branchingValue),
358    originalObjective_(COIN_DBL_MAX),
359    cutoff_(COIN_DBL_MAX)
360{
361}
362
363// Destructor
364CbcObjectUpdateData::~CbcObjectUpdateData ()
365{
366}
367
368// Copy constructor
369CbcObjectUpdateData::CbcObjectUpdateData ( const CbcObjectUpdateData & rhs)
370  : object_(rhs.object_),
371    way_(rhs.way_),
372    objectNumber_(rhs.objectNumber_),
373    change_(rhs.change_),
374    status_(rhs.status_),
375    intDecrease_(rhs.intDecrease_),
376    branchingValue_(rhs.branchingValue_),
377    originalObjective_(rhs.originalObjective_),
378    cutoff_(rhs.cutoff_)
379{
380}
381
382// Assignment operator
383CbcObjectUpdateData & 
384CbcObjectUpdateData::operator=( const CbcObjectUpdateData& rhs)
385{
386  if (this!=&rhs) {
387    object_ = rhs.object_;
388    way_ = rhs.way_;
389    objectNumber_ = rhs.objectNumber_;
390    change_ = rhs.change_;
391    status_ = rhs.status_;
392    intDecrease_ = rhs.intDecrease_;
393    branchingValue_ = rhs.branchingValue_;
394    originalObjective_ = rhs.originalObjective_;
395    cutoff_ = rhs.cutoff_;
396  }
397  return *this;
398}
399
400 
Note: See TracBrowser for help on using the repository browser.