source: branches/sandbox/Cbc/src/CbcSOSBranchingObject.cpp @ 1293

Last change on this file since 1293 was 1293, checked in by EdwinStraver, 10 years ago
File size: 9.6 KB
Line 
1// Edwin 11/10/2009-- carved out of CbcBranchActual
2//##############################################################################
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 <cstdlib>
9#include <cmath>
10#include <cfloat>
11//#define CBC_DEBUG
12
13#include "CoinTypes.hpp"
14#include "OsiSolverInterface.hpp"
15#include "OsiSolverBranch.hpp"
16#include "CbcModel.hpp"
17#include "CbcMessage.hpp"
18#include "CbcSOSBranchingObject.hpp"
19#include "CbcBranchActual.hpp"
20#include "CoinSort.hpp"
21#include "CoinError.hpp"
22
23// Default Constructor
24CbcSOSBranchingObject::CbcSOSBranchingObject()
25        : CbcBranchingObject(),
26        firstNonzero_(-1),
27        lastNonzero_(-1)
28{
29    set_ = NULL;
30    separator_ = 0.0;
31}
32
33// Useful constructor
34CbcSOSBranchingObject::CbcSOSBranchingObject (CbcModel * model,
35        const CbcSOS * set,
36        int way ,
37        double separator)
38        : CbcBranchingObject(model, set->id(), way, 0.5)
39{
40    set_ = set;
41    separator_ = separator;
42    computeNonzeroRange();
43}
44
45// Copy constructor
46CbcSOSBranchingObject::CbcSOSBranchingObject (const CbcSOSBranchingObject & rhs)
47        : CbcBranchingObject(rhs),
48        firstNonzero_(rhs.firstNonzero_),
49        lastNonzero_(rhs.lastNonzero_)
50{
51    set_ = rhs.set_;
52    separator_ = rhs.separator_;
53}
54
55// Assignment operator
56CbcSOSBranchingObject &
57CbcSOSBranchingObject::operator=( const CbcSOSBranchingObject & rhs)
58{
59    if (this != &rhs) {
60        CbcBranchingObject::operator=(rhs);
61        set_ = rhs.set_;
62        separator_ = rhs.separator_;
63        firstNonzero_ = rhs.firstNonzero_;
64        lastNonzero_ = rhs.lastNonzero_;
65    }
66    return *this;
67}
68CbcBranchingObject *
69CbcSOSBranchingObject::clone() const
70{
71    return (new CbcSOSBranchingObject(*this));
72}
73
74
75// Destructor
76CbcSOSBranchingObject::~CbcSOSBranchingObject ()
77{
78}
79
80void
81CbcSOSBranchingObject::computeNonzeroRange()
82{
83    const int numberMembers = set_->numberMembers();
84    const double * weights = set_->weights();
85    int i = 0;
86    if (way_ < 0) {
87        for ( i = 0; i < numberMembers; i++) {
88            if (weights[i] > separator_)
89                break;
90        }
91        assert (i < numberMembers);
92        firstNonzero_ = 0;
93        lastNonzero_ = i;
94    } else {
95        for ( i = 0; i < numberMembers; i++) {
96            if (weights[i] >= separator_)
97                break;
98        }
99        assert (i < numberMembers);
100        firstNonzero_ = i;
101        lastNonzero_ = numberMembers;
102    }
103}
104
105double
106CbcSOSBranchingObject::branch()
107{
108    decrementNumberBranchesLeft();
109    int numberMembers = set_->numberMembers();
110    const int * which = set_->members();
111    const double * weights = set_->weights();
112    OsiSolverInterface * solver = model_->solver();
113    //const double * lower = solver->getColLower();
114    //const double * upper = solver->getColUpper();
115    // *** for way - up means fix all those in down section
116    if (way_ < 0) {
117        int i;
118        for ( i = 0; i < numberMembers; i++) {
119            if (weights[i] > separator_)
120                break;
121        }
122        assert (i < numberMembers);
123        for (; i < numberMembers; i++)
124            solver->setColUpper(which[i], 0.0);
125        way_ = 1;         // Swap direction
126    } else {
127        int i;
128        for ( i = 0; i < numberMembers; i++) {
129            if (weights[i] >= separator_)
130                break;
131            else
132                solver->setColUpper(which[i], 0.0);
133        }
134        assert (i < numberMembers);
135        way_ = -1;        // Swap direction
136    }
137    computeNonzeroRange();
138    return 0.0;
139}
140/* Update bounds in solver as in 'branch' and update given bounds.
141   branchState is -1 for 'down' +1 for 'up' */
142void
143CbcSOSBranchingObject::fix(OsiSolverInterface * solver,
144                           double * /*lower*/, double * upper,
145                           int branchState) const
146{
147    int numberMembers = set_->numberMembers();
148    const int * which = set_->members();
149    const double * weights = set_->weights();
150    //const double * lower = solver->getColLower();
151    //const double * upper = solver->getColUpper();
152    // *** for way - up means fix all those in down section
153    if (branchState < 0) {
154        int i;
155        for ( i = 0; i < numberMembers; i++) {
156            if (weights[i] > separator_)
157                break;
158        }
159        assert (i < numberMembers);
160        for (; i < numberMembers; i++) {
161            solver->setColUpper(which[i], 0.0);
162            upper[which[i]] = 0.0;
163        }
164    } else {
165        int i;
166        for ( i = 0; i < numberMembers; i++) {
167            if (weights[i] >= separator_) {
168                break;
169            } else {
170                solver->setColUpper(which[i], 0.0);
171                upper[which[i]] = 0.0;
172            }
173        }
174        assert (i < numberMembers);
175    }
176}
177// Print what would happen
178void
179CbcSOSBranchingObject::print()
180{
181    int numberMembers = set_->numberMembers();
182    const int * which = set_->members();
183    const double * weights = set_->weights();
184    OsiSolverInterface * solver = model_->solver();
185    //const double * lower = solver->getColLower();
186    const double * upper = solver->getColUpper();
187    int first = numberMembers;
188    int last = -1;
189    int numberFixed = 0;
190    int numberOther = 0;
191    int i;
192    for ( i = 0; i < numberMembers; i++) {
193        double bound = upper[which[i]];
194        if (bound) {
195            first = CoinMin(first, i);
196            last = CoinMax(last, i);
197        }
198    }
199    // *** for way - up means fix all those in down section
200    if (way_ < 0) {
201        printf("SOS Down");
202        for ( i = 0; i < numberMembers; i++) {
203            double bound = upper[which[i]];
204            if (weights[i] > separator_)
205                break;
206            else if (bound)
207                numberOther++;
208        }
209        assert (i < numberMembers);
210        for (; i < numberMembers; i++) {
211            double bound = upper[which[i]];
212            if (bound)
213                numberFixed++;
214        }
215    } else {
216        printf("SOS Up");
217        for ( i = 0; i < numberMembers; i++) {
218            double bound = upper[which[i]];
219            if (weights[i] >= separator_)
220                break;
221            else if (bound)
222                numberFixed++;
223        }
224        assert (i < numberMembers);
225        for (; i < numberMembers; i++) {
226            double bound = upper[which[i]];
227            if (bound)
228                numberOther++;
229        }
230    }
231    printf(" - at %g, free range %d (%g) => %d (%g), %d would be fixed, %d other way\n",
232           separator_, which[first], weights[first], which[last], weights[last], numberFixed, numberOther);
233}
234
235/** Compare the original object of \c this with the original object of \c
236    brObj. Assumes that there is an ordering of the original objects.
237    This method should be invoked only if \c this and brObj are of the same
238    type.
239    Return negative/0/positive depending on whether \c this is
240    smaller/same/larger than the argument.
241*/
242int
243CbcSOSBranchingObject::compareOriginalObject
244(const CbcBranchingObject* brObj) const
245{
246    const CbcSOSBranchingObject* br =
247        dynamic_cast<const CbcSOSBranchingObject*>(brObj);
248    assert(br);
249    const CbcSOS* s0 = set_;
250    const CbcSOS* s1 = br->set_;
251    if (s0->sosType() != s1->sosType()) {
252        return s0->sosType() - s1->sosType();
253    }
254    if (s0->numberMembers() != s1->numberMembers()) {
255        return s0->numberMembers() - s1->numberMembers();
256    }
257    const int memberCmp = memcmp(s0->members(), s1->members(),
258                                 s0->numberMembers() * sizeof(int));
259    if (memberCmp != 0) {
260        return memberCmp;
261    }
262    return memcmp(s0->weights(), s1->weights(),
263                  s0->numberMembers() * sizeof(double));
264}
265
266/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
267    same type and must have the same original object, but they may have
268    different feasible regions.
269    Return the appropriate CbcRangeCompare value (first argument being the
270    sub/superset if that's the case). In case of overlap (and if \c
271    replaceIfOverlap is true) replace the current branching object with one
272    whose feasible region is the overlap.
273*/
274CbcRangeCompare
275CbcSOSBranchingObject::compareBranchingObject
276(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
277{
278    const CbcSOSBranchingObject* br =
279        dynamic_cast<const CbcSOSBranchingObject*>(brObj);
280    assert(br);
281    if (firstNonzero_ < br->firstNonzero_) {
282        if (lastNonzero_ >= br->lastNonzero_) {
283            return CbcRangeSuperset;
284        } else if (lastNonzero_ <= br->firstNonzero_) {
285            return CbcRangeDisjoint;
286        } else {
287            // overlap
288            if (replaceIfOverlap) {
289                firstNonzero_ = br->firstNonzero_;
290            }
291            return CbcRangeOverlap;
292        }
293    } else if (firstNonzero_ > br->firstNonzero_) {
294        if (lastNonzero_ <= br->lastNonzero_) {
295            return CbcRangeSubset;
296        } else if (firstNonzero_ >= br->lastNonzero_) {
297            return CbcRangeDisjoint;
298        } else {
299            // overlap
300            if (replaceIfOverlap) {
301                lastNonzero_ = br->lastNonzero_;
302            }
303            return CbcRangeOverlap;
304        }
305    } else {
306        if (lastNonzero_ == br->lastNonzero_) {
307            return CbcRangeSame;
308        }
309        return lastNonzero_ < br->lastNonzero_ ? CbcRangeSubset : CbcRangeSuperset;
310    }
311    return CbcRangeSame; // fake return
312}
Note: See TracBrowser for help on using the repository browser.