source: stable/2.9/Cbc/src/CbcBranchCut.cpp @ 2249

Last change on this file since 2249 was 1573, checked in by lou, 9 years ago

Change to EPL license notice.

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