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

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