source: trunk/Cbc/src/CbcBranchCut.cpp @ 2464

Last change on this file since 2464 was 2464, checked in by unxusr, 6 months ago

.clang-format with proposal for formatting code

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.5 KB
Line 
1/* $Id: CbcBranchCut.cpp 2464 2019-01-03 19:03:23Z unxusr $ */
2// Copyright (C) 2004, 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#if defined(_MSC_VER)
7// Turn off compiler warning about long names
8#pragma warning(disable : 4786)
9#endif
10#include <cassert>
11#include <cstdlib>
12#include <cmath>
13#include <cfloat>
14//#define CBC_DEBUG
15
16#include "OsiSolverInterface.hpp"
17#include "CbcModel.hpp"
18#include "CbcMessage.hpp"
19#include "CbcBranchCut.hpp"
20#include "CoinSort.hpp"
21#include "CoinError.hpp"
22
23/** Default Constructor
24
25*/
26CbcBranchCut::CbcBranchCut()
27  : CbcObject()
28{
29}
30
31/* Constructor so model can be passed up
32*/
33CbcBranchCut::CbcBranchCut(CbcModel *model)
34  : CbcObject(model)
35{
36}
37// Copy constructor
38CbcBranchCut::CbcBranchCut(const CbcBranchCut &rhs)
39  : CbcObject(rhs)
40
41{
42}
43
44// Clone
45CbcObject *
46CbcBranchCut::clone() const
47{
48  return new CbcBranchCut(*this);
49}
50
51// Assignment operator
52CbcBranchCut &
53CbcBranchCut::operator=(const CbcBranchCut & /*rhs*/)
54{
55  return *this;
56}
57
58// Destructor
59CbcBranchCut::~CbcBranchCut()
60{
61}
62double
63CbcBranchCut::infeasibility(const OsiBranchingInformation * /*info*/,
64  int &preferredWay) const
65{
66  throw CoinError("Use of base class", "infeasibility", "CbcBranchCut");
67  preferredWay = -1;
68  return 0.0;
69}
70
71// This looks at solution and sets bounds to contain solution
72/** More precisely: it first forces the variable within the existing
73    bounds, and then tightens the bounds to fix the variable at the
74    nearest integer value.
75*/
76void CbcBranchCut::feasibleRegion()
77{
78}
79/* Return true if branch created by object should fix variables
80 */
81bool CbcBranchCut::boundBranch() const
82{
83  return false;
84}
85CbcBranchingObject *
86CbcBranchCut::createCbcBranch(OsiSolverInterface * /*solver*/, const OsiBranchingInformation * /*info*/, int /*way*/)
87{
88  throw CoinError("Use of base class", "createCbcBranch", "CbcBranchCut");
89  return new CbcCutBranchingObject();
90}
91
92/* Given valid solution (i.e. satisfied) and reduced costs etc
93   returns a branching object which would give a new feasible
94   point in direction reduced cost says would be cheaper.
95   If no feasible point returns null
96*/
97CbcBranchingObject *
98CbcBranchCut::preferredNewFeasible() const
99{
100  throw CoinError("Use of base class", "preferredNewFeasible", "CbcBranchCut");
101  return new CbcCutBranchingObject();
102}
103
104/* Given valid solution (i.e. satisfied) and reduced costs etc
105   returns a branching object which would give a new feasible
106   point in direction opposite to one reduced cost says would be cheaper.
107   If no feasible point returns null
108*/
109CbcBranchingObject *
110CbcBranchCut::notPreferredNewFeasible() const
111{
112  throw CoinError("Use of base class", "notPreferredNewFeasible", "CbcBranchCut");
113  return new CbcCutBranchingObject();
114}
115
116/*
117  Bounds may be tightened, so it may be good to be able to refresh the local
118  copy of the original bounds.
119 */
120void CbcBranchCut::resetBounds()
121{
122}
123
124// Default Constructor
125CbcCutBranchingObject::CbcCutBranchingObject()
126  : CbcBranchingObject()
127{
128  down_ = OsiRowCut();
129  up_ = OsiRowCut();
130  canFix_ = false;
131}
132
133// Useful constructor
134CbcCutBranchingObject::CbcCutBranchingObject(CbcModel *model,
135  OsiRowCut &down,
136  OsiRowCut &up,
137  bool canFix)
138  : CbcBranchingObject(model, 0, -1, 0.0)
139{
140  down_ = down;
141  up_ = up;
142  canFix_ = canFix;
143}
144
145// Copy constructor
146CbcCutBranchingObject::CbcCutBranchingObject(const CbcCutBranchingObject &rhs)
147  : CbcBranchingObject(rhs)
148{
149  down_ = rhs.down_;
150  up_ = rhs.up_;
151  canFix_ = rhs.canFix_;
152}
153
154// Assignment operator
155CbcCutBranchingObject &
156CbcCutBranchingObject::operator=(const CbcCutBranchingObject &rhs)
157{
158  if (this != &rhs) {
159    CbcBranchingObject::operator=(rhs);
160    down_ = rhs.down_;
161    up_ = rhs.up_;
162    canFix_ = rhs.canFix_;
163  }
164  return *this;
165}
166CbcBranchingObject *
167CbcCutBranchingObject::clone() const
168{
169  return (new CbcCutBranchingObject(*this));
170}
171
172// Destructor
173CbcCutBranchingObject::~CbcCutBranchingObject()
174{
175}
176
177/*
178  Perform a branch by adjusting bounds and/or adding a cut. Note
179  that each arm of the branch advances the object to the next arm by
180  advancing the value of way_.
181
182  Returns change in guessed objective on next branch
183*/
184double
185CbcCutBranchingObject::branch()
186{
187  decrementNumberBranchesLeft();
188  OsiRowCut *cut;
189  if (way_ < 0) {
190    cut = &down_;
191    way_ = 1;
192  } else {
193    cut = &up_;
194    way_ = -1; // Swap direction
195  }
196  printf("CUT %s ", (way_ == -1) ? "up" : "down");
197  cut->print();
198  // See if cut just fixes variables
199  double lb = cut->lb();
200  double ub = cut->ub();
201  int n = cut->row().getNumElements();
202  const int *column = cut->row().getIndices();
203  const double *element = cut->row().getElements();
204  OsiSolverInterface *solver = model_->solver();
205  const double *upper = solver->getColUpper();
206  const double *lower = solver->getColLower();
207  double low = 0.0;
208  double high = 0.0;
209  for (int i = 0; i < n; i++) {
210    int iColumn = column[i];
211    double value = element[i];
212    if (value > 0.0) {
213      high += upper[iColumn] * value;
214      low += lower[iColumn] * value;
215    } else {
216      high += lower[iColumn] * value;
217      low += upper[iColumn] * value;
218    }
219  }
220  // leave as cut
221  //model_->setNextRowCut(*cut);
222  //return 0.0;
223  // assume cut was cunningly constructed so we need not worry too much about tolerances
224  if (low + 1.0e-8 >= ub && canFix_) {
225    // fix
226    for (int i = 0; i < n; i++) {
227      int iColumn = column[i];
228      double value = element[i];
229      if (value > 0.0) {
230        solver->setColUpper(iColumn, lower[iColumn]);
231      } else {
232        solver->setColLower(iColumn, upper[iColumn]);
233      }
234    }
235  } else if (high - 1.0e-8 <= lb && canFix_) {
236    // fix
237    for (int i = 0; i < n; i++) {
238      int iColumn = column[i];
239      double value = element[i];
240      if (value > 0.0) {
241        solver->setColLower(iColumn, upper[iColumn]);
242      } else {
243        solver->setColUpper(iColumn, lower[iColumn]);
244      }
245    }
246  } else {
247    // leave as cut
248    model_->setNextRowCut(*cut);
249  }
250  return 0.0;
251}
252// Print what would happen
253void CbcCutBranchingObject::print()
254{
255  OsiRowCut *cut;
256  if (way_ < 0) {
257    cut = &down_;
258    printf("CbcCut would branch down");
259  } else {
260    cut = &up_;
261    printf("CbcCut would branch up");
262  }
263  double lb = cut->lb();
264  double ub = cut->ub();
265  int n = cut->row().getNumElements();
266  const int *column = cut->row().getIndices();
267  const double *element = cut->row().getElements();
268  if (n > 5) {
269    printf(" - %d elements, lo=%g, up=%g\n", n, lb, ub);
270  } else {
271    printf(" - %g <=", lb);
272    for (int i = 0; i < n; i++) {
273      int iColumn = column[i];
274      double value = element[i];
275      printf(" (%d,%g)", iColumn, value);
276    }
277    printf(" <= %g\n", ub);
278  }
279}
280
281// Return true if branch should fix variables
282bool CbcCutBranchingObject::boundBranch() const
283{
284  return false;
285}
286
287/** Compare the original object of \c this with the original object of \c
288    brObj. Assumes that there is an ordering of the original objects.
289    This method should be invoked only if \c this and brObj are of the same
290    type.
291    Return negative/0/positive depending on whether \c this is
292    smaller/same/larger than the argument.
293*/
294int CbcCutBranchingObject::compareOriginalObject(const CbcBranchingObject *brObj) const
295{
296  const CbcCutBranchingObject *br = dynamic_cast<const CbcCutBranchingObject *>(brObj);
297  assert(br);
298  const OsiRowCut &r0 = way_ == -1 ? down_ : up_;
299  const OsiRowCut &r1 = br->way_ == -1 ? br->down_ : br->up_;
300  return r0.row().compare(r1.row());
301}
302
303/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
304    same type and must have the same original object, but they may have
305    different feasible regions.
306    Return the appropriate CbcRangeCompare value (first argument being the
307    sub/superset if that's the case). In case of overlap (and if \c
308    replaceIfOverlap is true) replace the current branching object with one
309    whose feasible region is the overlap.
310*/
311
312CbcRangeCompare
313CbcCutBranchingObject::compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap)
314{
315  const CbcCutBranchingObject *br = dynamic_cast<const CbcCutBranchingObject *>(brObj);
316  assert(br);
317  OsiRowCut &r0 = way_ == -1 ? down_ : up_;
318  const OsiRowCut &r1 = br->way_ == -1 ? br->down_ : br->up_;
319  double thisBd[2];
320  thisBd[0] = r0.lb();
321  thisBd[1] = r0.ub();
322  double otherBd[2];
323  otherBd[0] = r1.lb();
324  otherBd[1] = r1.ub();
325  CbcRangeCompare comp = CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
326  if (comp != CbcRangeOverlap || (comp == CbcRangeOverlap && !replaceIfOverlap)) {
327    return comp;
328  }
329  r0.setLb(thisBd[0]);
330  r0.setUb(thisBd[1]);
331  return comp;
332}
Note: See TracBrowser for help on using the repository browser.