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

Last change on this file since 1432 was 1432, checked in by bjarni, 9 years ago

Added extra return at end of each source file where needed, to remove possible linefeed conflicts (NightlyBuild? errors)

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