source: branches/devel/Cbc/examples/CbcBranchLotsizeSimple.cpp @ 425

Last change on this file since 425 was 403, checked in by forrest, 13 years ago

adding some examples

File size: 9.7 KB
Line 
1// Copyright (C) 2006, 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 "CbcModel.hpp"
13#include "CbcMessage.hpp"
14#include "CbcBranchLotsizeSimple.hpp"
15#include "CoinSort.hpp"
16#include "CoinError.hpp"
17#include "CoinHelperFunctions.hpp"
18/** Default Constructor
19
20*/
21CbcLotsizeSimple::CbcLotsizeSimple ()
22  : CbcObject(),
23    columnNumber_(-1),
24    numberRanges_(0),
25    largestGap_(0),
26    bound_(NULL),
27    range_(0)
28{
29}
30
31/** Useful constructor
32
33  Loads actual upper & lower bounds for the specified variable.
34*/
35CbcLotsizeSimple::CbcLotsizeSimple (CbcModel * model, 
36                                    int iColumn, int numberPoints,
37                                    const double * points)
38  : CbcObject(model)
39{
40  columnNumber_ = iColumn ;
41  // and set id so can be used for branching
42  id_=iColumn;
43  // sort ranges (just for safety)
44  int * sort = new int[numberPoints];
45  double * weight = new double [numberPoints];
46  int i;
47  for (i=0;i<numberPoints;i++) {
48    sort[i]=i;
49    weight[i]=points[i];
50  }
51  CoinSort_2(weight,weight+numberPoints,sort);
52  numberRanges_=1;
53  largestGap_=0;
54  bound_ = new double[numberPoints+1];
55  bound_[0]=weight[0];
56  for (i=1;i<numberPoints;i++) {
57    if (weight[i]!=weight[i-1]) 
58      bound_[numberRanges_++]=weight[i]; // only different values for points
59  }
60  // and for safety add an extra
61  bound_[numberRanges_]=bound_[numberRanges_-1];
62  // Find largest gap (for averaging infeasibility)
63  for (i=1;i<numberRanges_;i++) 
64    largestGap_ = CoinMax(largestGap_,bound_[i]-bound_[i-1]);
65  delete [] sort;
66  delete [] weight;
67  range_=0;
68}
69
70// Copy constructor
71CbcLotsizeSimple::CbcLotsizeSimple ( const CbcLotsizeSimple & rhs)
72  :CbcObject(rhs)
73
74{
75  columnNumber_ = rhs.columnNumber_;
76  numberRanges_ = rhs.numberRanges_;
77  range_ = rhs.range_;
78  largestGap_ = rhs.largestGap_;
79  bound_ = CoinCopyOfArray(rhs.bound_,numberRanges_+1);
80}
81
82// Clone
83CbcObject *
84CbcLotsizeSimple::clone() const
85{
86  return new CbcLotsizeSimple(*this);
87}
88
89// Assignment operator
90CbcLotsizeSimple & 
91CbcLotsizeSimple::operator=( const CbcLotsizeSimple& rhs)
92{
93  if (this!=&rhs) {
94    CbcObject::operator=(rhs);
95    columnNumber_ = rhs.columnNumber_;
96    numberRanges_ = rhs.numberRanges_;
97    largestGap_ = rhs.largestGap_;
98    delete [] bound_;
99    range_ = rhs.range_;
100    bound_ = CoinCopyOfArray(rhs.bound_,numberRanges_+1);
101  }
102  return *this;
103}
104
105// Destructor
106CbcLotsizeSimple::~CbcLotsizeSimple ()
107{
108  delete [] bound_;
109}
110/* Finds range of interest so value is feasible in range range_ or infeasible
111   between bound_[range_] and bound_[range_+1].  Returns true if feasible.
112*/
113bool 
114CbcLotsizeSimple::findRange(double value) const
115{
116  assert (range_>=0&&range_<numberRanges_+1);
117  double integerTolerance = 
118    model_->getDblParam(CbcModel::CbcIntegerTolerance);
119  int iLo;
120  int iHi;
121  double infeasibility=0.0;
122  // see where we need to search
123  if (value<bound_[range_]-integerTolerance) {
124    // lower than current range
125    iLo=0;
126    iHi=range_-1;
127  } else if (value<bound_[range_]+integerTolerance) {
128    // feasible as close enough
129    return true;
130  } else if (value<bound_[range_+1]-integerTolerance) {
131    // in this range - so infeasible
132    return false;
133  } else {
134    // higher than current range
135    iLo=range_+1;
136    iHi=numberRanges_-1;
137  }
138  // check whether at one end of possible range
139  if (value>bound_[iLo]-integerTolerance&&value<bound_[iLo+1]+integerTolerance) {
140    range_=iLo;
141  } else if (value>bound_[iHi]-integerTolerance&&value<bound_[iHi+1]+integerTolerance) {
142    range_=iHi;
143  } else {
144    // do binary search to find range
145    range_ = (iLo+iHi)>>1;
146    while (true) {
147      if (value<bound_[range_]) {
148        if (value>=bound_[range_-1]) {
149          // found
150          range_--;
151          break;
152        } else {
153          iHi = range_;
154        }
155      } else {
156        if (value<bound_[range_+1]) {
157          // found
158          break;
159        } else {
160          iLo = range_;
161        }
162      }
163      range_ = (iLo+iHi)>>1;
164    }
165  }
166  // got range - see if feasible and find infeasibility
167  if (value-bound_[range_]<=bound_[range_+1]-value) {
168    infeasibility = value-bound_[range_];
169  } else {
170    infeasibility = bound_[range_+1]-value;
171    if (infeasibility<integerTolerance)
172      range_++; // feasible above - so move to that point
173  }
174  return (infeasibility<integerTolerance);
175}
176/* Returns floor and ceiling
177   hardly necessary with this simple case
178 */
179void 
180CbcLotsizeSimple::floorCeiling(double & floorLotsizeSimple, double & ceilingLotsizeSimple, double value,
181                         double tolerance) const
182{
183  bool feasible=findRange(value);
184  floorLotsizeSimple=bound_[range_];
185  ceilingLotsizeSimple=bound_[range_+1];
186  // may be able to adjust (only needed for fancy branching)
187  if (feasible&&fabs(value-floorLotsizeSimple)>fabs(value-ceilingLotsizeSimple)) {
188    floorLotsizeSimple=bound_[range_+1];
189    ceilingLotsizeSimple=bound_[range_+2];
190  }
191}
192// Simple function to return a solution value strictly feasible
193double 
194CbcLotsizeSimple::cleanValue() const
195{
196  // Get standard stuff
197  OsiSolverInterface * solver = model_->solver();
198  const double * solution = model_->testSolution();
199  const double * lower = solver->getColLower();
200  const double * upper = solver->getColUpper();
201  // Get value and clean it
202  double value = solution[columnNumber_];
203  value = CoinMax(value, lower[columnNumber_]);
204  value = CoinMin(value, upper[columnNumber_]);
205  return value;
206}
207
208// Infeasibility - large is 0.5
209double 
210CbcLotsizeSimple::infeasibility(int & preferredWay) const
211{
212  // Get value and clean it
213  double value = cleanValue();
214  double integerTolerance = 
215    model_->getDblParam(CbcModel::CbcIntegerTolerance);
216  assert (value>=bound_[0]-integerTolerance
217          &&value<=bound_[numberRanges_-1]+integerTolerance);
218  double infeasibility=0.0;
219  bool feasible = findRange(value);
220  if (!feasible) {
221    if (value-bound_[range_]<bound_[range_+1]-value) {
222      preferredWay=-1;
223      infeasibility = value-bound_[range_];
224    } else {
225      preferredWay=1;
226      infeasibility = bound_[range_+1]-value;
227    }
228    // normalize
229    infeasibility /= largestGap_;
230    return infeasibility;
231  } else {
232    // satisfied
233    preferredWay=-1;
234    return 0.0;
235  }
236}
237/* This looks at solution and sets bounds to contain solution
238   More precisely: it first forces the variable within the existing
239   bounds, and then tightens the bounds to make sure the variable is feasible
240*/
241void 
242CbcLotsizeSimple::feasibleRegion()
243{
244  // Get value and clean it
245  double value = cleanValue();
246  findRange(value);
247  double nearest;
248  nearest = bound_[range_];
249  // fix to nearest
250  OsiSolverInterface * solver = model_->solver();
251  solver->setColLower(columnNumber_,nearest);
252  solver->setColUpper(columnNumber_,nearest);
253  // Scaling may have moved it a bit
254  // Lotsizing variables could be a lot larger
255#ifndef NDEBUG
256  double integerTolerance = 
257    model_->getDblParam(CbcModel::CbcIntegerTolerance);
258  assert (fabs(value-nearest)<=(100.0+10.0*fabs(nearest))*integerTolerance);
259#endif
260}
261
262// Creates a branching object
263CbcBranchingObject * 
264CbcLotsizeSimple::createBranch(int way) 
265{
266  // Get value and clean it
267  double value = cleanValue();
268  assert (!findRange(value)); // If it was feasible we would not be here
269  return new CbcLotsizeSimpleBranchingObject(model_,columnNumber_,way,
270                                             value,this);
271}
272
273// Default Constructor
274CbcLotsizeSimpleBranchingObject::CbcLotsizeSimpleBranchingObject()
275  :CbcBranchingObject()
276{
277  down_[0] = 0.0;
278  down_[1] = 0.0;
279  up_[0] = 0.0;
280  up_[1] = 0.0;
281}
282
283// Useful constructor
284CbcLotsizeSimpleBranchingObject::CbcLotsizeSimpleBranchingObject (CbcModel * model, 
285                                                      int variable, int way , double value,
286                                                      const CbcLotsizeSimple * lotsize)
287  :CbcBranchingObject(model,variable,way,value)
288{
289  int iColumn = lotsize->modelSequence();
290  assert (variable==iColumn);
291  down_[0] = model_->solver()->getColLower()[iColumn];
292  double integerTolerance = 
293    model_->getDblParam(CbcModel::CbcIntegerTolerance);
294  lotsize->floorCeiling(down_[1],up_[0],value,integerTolerance);
295  up_[1] = model->getColUpper()[iColumn];
296}
297
298// Copy constructor
299CbcLotsizeSimpleBranchingObject::CbcLotsizeSimpleBranchingObject ( const CbcLotsizeSimpleBranchingObject & rhs) :CbcBranchingObject(rhs)
300{
301  down_[0] = rhs.down_[0];
302  down_[1] = rhs.down_[1];
303  up_[0] = rhs.up_[0];
304  up_[1] = rhs.up_[1];
305}
306
307// Assignment operator
308CbcLotsizeSimpleBranchingObject & 
309CbcLotsizeSimpleBranchingObject::operator=( const CbcLotsizeSimpleBranchingObject& rhs)
310{
311  if (this != &rhs) {
312    CbcBranchingObject::operator=(rhs);
313    down_[0] = rhs.down_[0];
314    down_[1] = rhs.down_[1];
315    up_[0] = rhs.up_[0];
316    up_[1] = rhs.up_[1];
317  }
318  return *this;
319}
320// Clone
321CbcBranchingObject * 
322CbcLotsizeSimpleBranchingObject::clone() const
323{ 
324  return (new CbcLotsizeSimpleBranchingObject(*this));
325}
326
327
328// Destructor
329CbcLotsizeSimpleBranchingObject::~CbcLotsizeSimpleBranchingObject ()
330{
331}
332
333/*
334  Perform a branch by adjusting the bounds of the specified variable. Note
335  that each arm of the branch advances the object to the next arm by
336  advancing the value of way_.
337
338  Providing new values for the variable's lower and upper bounds for each
339  branching direction gives a little bit of additional flexibility and will
340  be easily extensible to multi-way branching.
341*/
342double
343CbcLotsizeSimpleBranchingObject::branch(bool normalBranch)
344{
345  numberBranchesLeft_--;
346  int iColumn = variable_;
347  if (way_<0) {
348    model_->solver()->setColLower(iColumn,down_[0]);
349    model_->solver()->setColUpper(iColumn,down_[1]);
350    way_=1;
351  } else {
352    model_->solver()->setColLower(iColumn,up_[0]);
353    model_->solver()->setColUpper(iColumn,up_[1]);
354    way_=-1;      // Swap direction
355  }
356  return 0.0;
357}
Note: See TracBrowser for help on using the repository browser.