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

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