source: trunk/Cbc/src/CbcNWay.cpp

Last change on this file was 2465, checked in by unxusr, 9 months ago

script to format sources

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.2 KB
Line 
1// $Id: CbcNWay.cpp 2465 2019-01-03 19:26:52Z tkr $
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// Edwin 11/9/2009-- carved out of CbcBranchActual
7
8#if defined(_MSC_VER)
9// Turn off compiler warning about long names
10#pragma warning(disable : 4786)
11#endif
12#include <cassert>
13#include <cstdlib>
14#include <cmath>
15#include <cfloat>
16//#define CBC_DEBUG
17
18#include "CoinTypes.hpp"
19#include "OsiSolverInterface.hpp"
20#include "OsiSolverBranch.hpp"
21#include "CbcModel.hpp"
22#include "CbcMessage.hpp"
23#include "CbcNWay.hpp"
24#include "CbcBranchActual.hpp"
25#include "CoinSort.hpp"
26#include "CoinError.hpp"
27
28//##############################################################################
29
30// Default Constructor
31CbcNWay::CbcNWay()
32  : CbcObject()
33  , numberMembers_(0)
34  , members_(NULL)
35  , consequence_(NULL)
36{
37}
38
39// Useful constructor (which are integer indices)
40CbcNWay::CbcNWay(CbcModel *model, int numberMembers,
41  const int *which, int identifier)
42  : CbcObject(model)
43{
44  id_ = identifier;
45  numberMembers_ = numberMembers;
46  if (numberMembers_) {
47    members_ = new int[numberMembers_];
48    memcpy(members_, which, numberMembers_ * sizeof(int));
49  } else {
50    members_ = NULL;
51  }
52  consequence_ = NULL;
53}
54
55// Copy constructor
56CbcNWay::CbcNWay(const CbcNWay &rhs)
57  : CbcObject(rhs)
58{
59  numberMembers_ = rhs.numberMembers_;
60  consequence_ = NULL;
61  if (numberMembers_) {
62    members_ = new int[numberMembers_];
63    memcpy(members_, rhs.members_, numberMembers_ * sizeof(int));
64    if (rhs.consequence_) {
65      consequence_ = new CbcConsequence *[numberMembers_];
66      for (int i = 0; i < numberMembers_; i++) {
67        if (rhs.consequence_[i])
68          consequence_[i] = rhs.consequence_[i]->clone();
69        else
70          consequence_[i] = NULL;
71      }
72    }
73  } else {
74    members_ = NULL;
75  }
76}
77
78// Clone
79CbcObject *
80CbcNWay::clone() const
81{
82  return new CbcNWay(*this);
83}
84
85// Assignment operator
86CbcNWay &
87CbcNWay::operator=(const CbcNWay &rhs)
88{
89  if (this != &rhs) {
90    CbcObject::operator=(rhs);
91    delete[] members_;
92    numberMembers_ = rhs.numberMembers_;
93    if (consequence_) {
94      for (int i = 0; i < numberMembers_; i++)
95        delete consequence_[i];
96      delete[] consequence_;
97      consequence_ = NULL;
98    }
99    if (numberMembers_) {
100      members_ = new int[numberMembers_];
101      memcpy(members_, rhs.members_, numberMembers_ * sizeof(int));
102    } else {
103      members_ = NULL;
104    }
105    if (rhs.consequence_) {
106      consequence_ = new CbcConsequence *[numberMembers_];
107      for (int i = 0; i < numberMembers_; i++) {
108        if (rhs.consequence_[i])
109          consequence_[i] = rhs.consequence_[i]->clone();
110        else
111          consequence_[i] = NULL;
112      }
113    }
114  }
115  return *this;
116}
117
118// Destructor
119CbcNWay::~CbcNWay()
120{
121  delete[] members_;
122  if (consequence_) {
123    for (int i = 0; i < numberMembers_; i++)
124      delete consequence_[i];
125    delete[] consequence_;
126  }
127}
128// Set up a consequence for a single member
129void CbcNWay::setConsequence(int iColumn, const CbcConsequence &consequence)
130{
131  if (!consequence_) {
132    consequence_ = new CbcConsequence *[numberMembers_];
133    for (int i = 0; i < numberMembers_; i++)
134      consequence_[i] = NULL;
135  }
136  for (int i = 0; i < numberMembers_; i++) {
137    if (members_[i] == iColumn) {
138      consequence_[i] = consequence.clone();
139      break;
140    }
141  }
142}
143
144// Applies a consequence for a single member
145void CbcNWay::applyConsequence(int iSequence, int state) const
146{
147  assert(state == -9999 || state == 9999);
148  if (consequence_) {
149    CbcConsequence *consequence = consequence_[iSequence];
150    if (consequence)
151      consequence->applyToSolver(model_->solver(), state);
152  }
153}
154double
155CbcNWay::infeasibility(const OsiBranchingInformation * /*info*/,
156  int &preferredWay) const
157{
158  int numberUnsatis = 0;
159  int j;
160  OsiSolverInterface *solver = model_->solver();
161  const double *solution = model_->testSolution();
162  const double *lower = solver->getColLower();
163  const double *upper = solver->getColUpper();
164  double largestValue = 0.0;
165
166  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
167
168  for (j = 0; j < numberMembers_; j++) {
169    int iColumn = members_[j];
170    double value = solution[iColumn];
171    value = CoinMax(value, lower[iColumn]);
172    value = CoinMin(value, upper[iColumn]);
173    double distance = CoinMin(value - lower[iColumn], upper[iColumn] - value);
174    if (distance > integerTolerance) {
175      numberUnsatis++;
176      largestValue = CoinMax(distance, largestValue);
177    }
178  }
179  preferredWay = 1;
180  if (numberUnsatis) {
181    return largestValue;
182  } else {
183    return 0.0; // satisfied
184  }
185}
186
187// This looks at solution and sets bounds to contain solution
188void CbcNWay::feasibleRegion()
189{
190  int j;
191  OsiSolverInterface *solver = model_->solver();
192  const double *solution = model_->testSolution();
193  const double *lower = solver->getColLower();
194  const double *upper = solver->getColUpper();
195  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
196  for (j = 0; j < numberMembers_; j++) {
197    int iColumn = members_[j];
198    double value = solution[iColumn];
199    value = CoinMax(value, lower[iColumn]);
200    value = CoinMin(value, upper[iColumn]);
201    if (value >= upper[iColumn] - integerTolerance) {
202      solver->setColLower(iColumn, upper[iColumn]);
203    } else {
204      assert(value <= lower[iColumn] + integerTolerance);
205      solver->setColUpper(iColumn, lower[iColumn]);
206    }
207  }
208}
209// Redoes data when sequence numbers change
210void CbcNWay::redoSequenceEtc(CbcModel *model, int numberColumns, const int *originalColumns)
211{
212  model_ = model;
213  int n2 = 0;
214  for (int j = 0; j < numberMembers_; j++) {
215    int iColumn = members_[j];
216    int i;
217    for (i = 0; i < numberColumns; i++) {
218      if (originalColumns[i] == iColumn)
219        break;
220    }
221    if (i < numberColumns) {
222      members_[n2] = i;
223      consequence_[n2++] = consequence_[j];
224    } else {
225      delete consequence_[j];
226    }
227  }
228  if (n2 < numberMembers_) {
229    printf("** NWay number of members reduced from %d to %d!\n", numberMembers_, n2);
230    numberMembers_ = n2;
231  }
232}
233CbcBranchingObject *
234CbcNWay::createCbcBranch(OsiSolverInterface *solver, const OsiBranchingInformation * /*info*/, int /*way*/)
235{
236  int numberFree = 0;
237  int j;
238
239  //OsiSolverInterface * solver = model_->solver();
240  const double *solution = model_->testSolution();
241  const double *lower = solver->getColLower();
242  const double *upper = solver->getColUpper();
243  int *list = new int[numberMembers_];
244  double *sort = new double[numberMembers_];
245
246  for (j = 0; j < numberMembers_; j++) {
247    int iColumn = members_[j];
248    double value = solution[iColumn];
249    value = CoinMax(value, lower[iColumn]);
250    value = CoinMin(value, upper[iColumn]);
251    if (upper[iColumn] > lower[iColumn]) {
252      double distance = upper[iColumn] - value;
253      list[numberFree] = j;
254      sort[numberFree++] = distance;
255    }
256  }
257  assert(numberFree);
258  // sort
259  CoinSort_2(sort, sort + numberFree, list);
260  // create object
261  CbcBranchingObject *branch;
262  branch = new CbcNWayBranchingObject(model_, this, numberFree, list);
263  branch->setOriginalObject(this);
264  delete[] list;
265  delete[] sort;
266  return branch;
267}
268
269// Default Constructor
270CbcNWayBranchingObject::CbcNWayBranchingObject()
271  : CbcBranchingObject()
272{
273  order_ = NULL;
274  object_ = NULL;
275  numberInSet_ = 0;
276  way_ = 0;
277}
278
279// Useful constructor
280CbcNWayBranchingObject::CbcNWayBranchingObject(CbcModel *model,
281  const CbcNWay *nway,
282  int number, const int *order)
283  : CbcBranchingObject(model, nway->id(), -1, 0.5)
284{
285  numberBranches_ = number;
286  order_ = new int[number];
287  object_ = nway;
288  numberInSet_ = number;
289  memcpy(order_, order, number * sizeof(int));
290}
291
292// Copy constructor
293CbcNWayBranchingObject::CbcNWayBranchingObject(const CbcNWayBranchingObject &rhs)
294  : CbcBranchingObject(rhs)
295{
296  numberInSet_ = rhs.numberInSet_;
297  object_ = rhs.object_;
298  if (numberInSet_) {
299    order_ = new int[numberInSet_];
300    memcpy(order_, rhs.order_, numberInSet_ * sizeof(int));
301  } else {
302    order_ = NULL;
303  }
304}
305
306// Assignment operator
307CbcNWayBranchingObject &
308CbcNWayBranchingObject::operator=(const CbcNWayBranchingObject &rhs)
309{
310  if (this != &rhs) {
311    CbcBranchingObject::operator=(rhs);
312    object_ = rhs.object_;
313    delete[] order_;
314    numberInSet_ = rhs.numberInSet_;
315    if (numberInSet_) {
316      order_ = new int[numberInSet_];
317      memcpy(order_, rhs.order_, numberInSet_ * sizeof(int));
318    } else {
319      order_ = NULL;
320    }
321  }
322  return *this;
323}
324CbcBranchingObject *
325CbcNWayBranchingObject::clone() const
326{
327  return (new CbcNWayBranchingObject(*this));
328}
329
330// Destructor
331CbcNWayBranchingObject::~CbcNWayBranchingObject()
332{
333  delete[] order_;
334}
335double
336CbcNWayBranchingObject::branch()
337{
338  int which = branchIndex_;
339  branchIndex_++;
340  assert(numberBranchesLeft() >= 0);
341  if (which == 0) {
342    // first branch so way_ may mean something
343    assert(way_ == -1 || way_ == 1);
344    if (way_ == -1)
345      which++;
346  } else if (which == 1) {
347    // second branch so way_ may mean something
348    assert(way_ == -1 || way_ == 1);
349    if (way_ == -1)
350      which--;
351    // switch way off
352    way_ = 0;
353  }
354  const double *lower = model_->solver()->getColLower();
355  const double *upper = model_->solver()->getColUpper();
356  const int *members = object_->members();
357  for (int j = 0; j < numberInSet_; j++) {
358    int iSequence = order_[j];
359    int iColumn = members[iSequence];
360    if (j != which) {
361      model_->solver()->setColUpper(iColumn, lower[iColumn]);
362      //model_->solver()->setColLower(iColumn,lower[iColumn]);
363      assert(lower[iColumn] > -1.0e20);
364      // apply any consequences
365      object_->applyConsequence(iSequence, -9999);
366    } else {
367      model_->solver()->setColLower(iColumn, upper[iColumn]);
368      //model_->solver()->setColUpper(iColumn,upper[iColumn]);
369#ifdef FULL_PRINT
370      printf("Up Fix %d to %g\n", iColumn, upper[iColumn]);
371#endif
372      assert(upper[iColumn] < 1.0e20);
373      // apply any consequences
374      object_->applyConsequence(iSequence, 9999);
375    }
376  }
377  return 0.0;
378}
379void CbcNWayBranchingObject::print()
380{
381  printf("NWay - Up Fix ");
382  const int *members = object_->members();
383  for (int j = 0; j < way_; j++) {
384    int iColumn = members[order_[j]];
385    printf("%d ", iColumn);
386  }
387  printf("\n");
388}
389
390/** Compare the original object of \c this with the original object of \c
391    brObj. Assumes that there is an ordering of the original objects.
392    This method should be invoked only if \c this and brObj are of the same
393    type.
394    Return negative/0/positive depending on whether \c this is
395    smaller/same/larger than the argument.
396*/
397int CbcNWayBranchingObject::compareOriginalObject(const CbcBranchingObject * /*brObj*/) const
398{
399  throw("must implement");
400}
401
402/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
403    same type and must have the same original object, but they may have
404    different feasible regions.
405    Return the appropriate CbcRangeCompare value (first argument being the
406    sub/superset if that's the case). In case of overlap (and if \c
407    replaceIfOverlap is true) replace the current branching object with one
408    whose feasible region is the overlap.
409*/
410CbcRangeCompare
411CbcNWayBranchingObject::compareBranchingObject(const CbcBranchingObject * /*brObj*/, const bool /*replaceIfOverlap*/)
412{
413  throw("must implement");
414}
415
416/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
417*/
Note: See TracBrowser for help on using the repository browser.