source: branches/sandbox/Cbc/src/CbcClique.cpp @ 1344

Last change on this file since 1344 was 1344, checked in by EdwinStraver, 10 years ago

Combined CbcClique? with CbcCliqueBranchingObject? and CbcLongCliqueBranchingObject?.

File size: 27.1 KB
Line 
1// Edwin 11/9/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 "CbcClique.hpp"
18#include "CbcBranchActual.hpp"
19#include "CoinSort.hpp"
20#include "CoinError.hpp"
21//##############################################################################
22
23// Default Constructor
24CbcClique::CbcClique ()
25        : CbcObject(),
26        numberMembers_(0),
27        numberNonSOSMembers_(0),
28        members_(NULL),
29        type_(NULL),
30        cliqueType_(-1),
31        slack_(-1)
32{
33}
34
35// Useful constructor (which are integer indices)
36CbcClique::CbcClique (CbcModel * model, int cliqueType, int numberMembers,
37                      const int * which, const char * type, int identifier, int slack)
38        : CbcObject(model)
39{
40    id_ = identifier;
41    numberMembers_ = numberMembers;
42    if (numberMembers_) {
43        members_ = new int[numberMembers_];
44        memcpy(members_, which, numberMembers_*sizeof(int));
45        type_ = new char[numberMembers_];
46        if (type) {
47            memcpy(type_, type, numberMembers_*sizeof(char));
48        } else {
49            for (int i = 0; i < numberMembers_; i++)
50                type_[i] = 1;
51        }
52    } else {
53        members_ = NULL;
54        type_ = NULL;
55    }
56    // Find out how many non sos
57    int i;
58    numberNonSOSMembers_ = 0;
59    for (i = 0; i < numberMembers_; i++)
60        if (!type_[i])
61            numberNonSOSMembers_++;
62    cliqueType_ = cliqueType;
63    slack_ = slack;
64}
65
66// Copy constructor
67CbcClique::CbcClique ( const CbcClique & rhs)
68        : CbcObject(rhs)
69{
70    numberMembers_ = rhs.numberMembers_;
71    numberNonSOSMembers_ = rhs.numberNonSOSMembers_;
72    if (numberMembers_) {
73        members_ = new int[numberMembers_];
74        memcpy(members_, rhs.members_, numberMembers_*sizeof(int));
75        type_ = new char[numberMembers_];
76        memcpy(type_, rhs.type_, numberMembers_*sizeof(char));
77    } else {
78        members_ = NULL;
79        type_ = NULL;
80    }
81    cliqueType_ = rhs.cliqueType_;
82    slack_ = rhs.slack_;
83}
84
85// Clone
86CbcObject *
87CbcClique::clone() const
88{
89    return new CbcClique(*this);
90}
91
92// Assignment operator
93CbcClique &
94CbcClique::operator=( const CbcClique & rhs)
95{
96    if (this != &rhs) {
97        CbcObject::operator=(rhs);
98        delete [] members_;
99        delete [] type_;
100        numberMembers_ = rhs.numberMembers_;
101        numberNonSOSMembers_ = rhs.numberNonSOSMembers_;
102        if (numberMembers_) {
103            members_ = new int[numberMembers_];
104            memcpy(members_, rhs.members_, numberMembers_*sizeof(int));
105            type_ = new char[numberMembers_];
106            memcpy(type_, rhs.type_, numberMembers_*sizeof(char));
107        } else {
108            members_ = NULL;
109            type_ = NULL;
110        }
111        cliqueType_ = rhs.cliqueType_;
112        slack_ = rhs.slack_;
113    }
114    return *this;
115}
116
117// Destructor
118CbcClique::~CbcClique ()
119{
120    delete [] members_;
121    delete [] type_;
122}
123double
124CbcClique::infeasibility(const OsiBranchingInformation * /*info*/,
125                         int &preferredWay) const
126{
127    int numberUnsatis = 0, numberFree = 0;
128    int j;
129    const int * integer = model_->integerVariable();
130    OsiSolverInterface * solver = model_->solver();
131    const double * solution = model_->testSolution();
132    const double * lower = solver->getColLower();
133    const double * upper = solver->getColUpper();
134    double largestValue = 0.0;
135    double integerTolerance =
136        model_->getDblParam(CbcModel::CbcIntegerTolerance);
137    double * sort = new double[numberMembers_];
138
139    double slackValue = 0.0;
140    for (j = 0; j < numberMembers_; j++) {
141        int sequence = members_[j];
142        int iColumn = integer[sequence];
143        double value = solution[iColumn];
144        value = CoinMax(value, lower[iColumn]);
145        value = CoinMin(value, upper[iColumn]);
146        double nearest = floor(value + 0.5);
147        double distance = fabs(value - nearest);
148        if (distance > integerTolerance) {
149            if (!type_[j])
150                value = 1.0 - value; // non SOS
151            // if slack then choose that
152            if (j == slack_ && value > 0.05)
153                slackValue = value;
154            largestValue = CoinMax(value, largestValue);
155            sort[numberUnsatis++] = -value;
156        } else if (upper[iColumn] > lower[iColumn]) {
157            numberFree++;
158        }
159    }
160    preferredWay = 1;
161    double otherWay = 0.0;
162    if (numberUnsatis) {
163        // sort
164        std::sort(sort, sort + numberUnsatis);
165        for (j = 0; j < numberUnsatis; j++) {
166            if ((j&1) != 0)
167                otherWay += -sort[j];
168        }
169        // Need to think more
170        double value = 0.2 * numberUnsatis + 0.01 * (numberMembers_ - numberFree);
171        if (fabs(largestValue - 0.5) < 0.1) {
172            // close to half
173            value += 0.1;
174        }
175        if (slackValue) {
176            // branching on slack
177            value += slackValue;
178        }
179        // scale other way
180        otherWay *= value / (1.0 - otherWay);
181        delete [] sort;
182        return value;
183    } else {
184        delete [] sort;
185        return 0.0; // satisfied
186    }
187}
188
189// This looks at solution and sets bounds to contain solution
190void
191CbcClique::feasibleRegion()
192{
193    int j;
194    const int * integer = model_->integerVariable();
195    OsiSolverInterface * solver = model_->solver();
196    const double * solution = model_->testSolution();
197    const double * lower = solver->getColLower();
198    const double * upper = solver->getColUpper();
199#ifndef NDEBUG
200    double integerTolerance =
201        model_->getDblParam(CbcModel::CbcIntegerTolerance);
202#endif
203    for (j = 0; j < numberMembers_; j++) {
204        int sequence = members_[j];
205        int iColumn = integer[sequence];
206        double value = solution[iColumn];
207        value = CoinMax(value, lower[iColumn]);
208        value = CoinMin(value, upper[iColumn]);
209        double nearest = floor(value + 0.5);
210#ifndef NDEBUG
211        double distance = fabs(value - nearest);
212        assert(distance <= integerTolerance);
213#endif
214        solver->setColLower(iColumn, nearest);
215        solver->setColUpper(iColumn, nearest);
216    }
217}
218// Redoes data when sequence numbers change
219void
220CbcClique::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns)
221{
222    model_ = model;
223    int n2 = 0;
224    for (int j = 0; j < numberMembers_; j++) {
225        int iColumn = members_[j];
226        int i;
227        for (i = 0; i < numberColumns; i++) {
228            if (originalColumns[i] == iColumn)
229                break;
230        }
231        if (i < numberColumns) {
232            members_[n2] = i;
233            type_[n2++] = type_[j];
234        }
235    }
236    if (n2 < numberMembers_) {
237        //printf("** SOS number of members reduced from %d to %d!\n",numberMembers_,n2);
238        numberMembers_ = n2;
239    }
240    // Find out how many non sos
241    int i;
242    numberNonSOSMembers_ = 0;
243    for (i = 0; i < numberMembers_; i++)
244        if (!type_[i])
245            numberNonSOSMembers_++;
246}
247CbcBranchingObject *
248CbcClique::createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * /*info*/, int way)
249{
250    int numberUnsatis = 0;
251    int j;
252    int nUp = 0;
253    int nDown = 0;
254    int numberFree = numberMembers_;
255    const int * integer = model_->integerVariable();
256    //OsiSolverInterface * solver = model_->solver();
257    const double * solution = model_->testSolution();
258    const double * lower = solver->getColLower();
259    const double * upper = solver->getColUpper();
260    int * upList = new int[numberMembers_];
261    int * downList = new int[numberMembers_];
262    double * sort = new double[numberMembers_];
263    double integerTolerance =
264        model_->getDblParam(CbcModel::CbcIntegerTolerance);
265
266    double slackValue = 0.0;
267    for (j = 0; j < numberMembers_; j++) {
268        int sequence = members_[j];
269        int iColumn = integer[sequence];
270        double value = solution[iColumn];
271        value = CoinMax(value, lower[iColumn]);
272        value = CoinMin(value, upper[iColumn]);
273        double nearest = floor(value + 0.5);
274        double distance = fabs(value - nearest);
275        if (distance > integerTolerance) {
276            if (!type_[j])
277                value = 1.0 - value; // non SOS
278            // if slack then choose that
279            if (j == slack_ && value > 0.05)
280                slackValue = value;
281            value = -value; // for sort
282            upList[numberUnsatis] = j;
283            sort[numberUnsatis++] = value;
284        } else if (upper[iColumn] > lower[iColumn]) {
285            upList[--numberFree] = j;
286        }
287    }
288    assert (numberUnsatis);
289    if (!slackValue) {
290        // sort
291        CoinSort_2(sort, sort + numberUnsatis, upList);
292        // put first in up etc
293        int kWay = 1;
294        for (j = 0; j < numberUnsatis; j++) {
295            if (kWay > 0)
296                upList[nUp++] = upList[j];
297            else
298                downList[nDown++] = upList[j];
299            kWay = -kWay;
300        }
301        for (j = numberFree; j < numberMembers_; j++) {
302            if (kWay > 0)
303                upList[nUp++] = upList[j];
304            else
305                downList[nDown++] = upList[j];
306            kWay = -kWay;
307        }
308    } else {
309        // put slack to 0 in first way
310        nUp = 1;
311        upList[0] = slack_;
312        for (j = 0; j < numberUnsatis; j++) {
313            downList[nDown++] = upList[j];
314        }
315        for (j = numberFree; j < numberMembers_; j++) {
316            downList[nDown++] = upList[j];
317        }
318    }
319    // create object
320    CbcBranchingObject * branch;
321    if (numberMembers_ <= 64)
322        branch = new CbcCliqueBranchingObject(model_, this, way,
323                                              nDown, downList, nUp, upList);
324    else
325        branch = new CbcLongCliqueBranchingObject(model_, this, way,
326                nDown, downList, nUp, upList);
327    delete [] upList;
328    delete [] downList;
329    delete [] sort;
330    return branch;
331}
332
333// Default Constructor
334CbcCliqueBranchingObject::CbcCliqueBranchingObject()
335        : CbcBranchingObject()
336{
337    clique_ = NULL;
338    downMask_[0] = 0;
339    downMask_[1] = 0;
340    upMask_[0] = 0;
341    upMask_[1] = 0;
342}
343
344// Useful constructor
345CbcCliqueBranchingObject::CbcCliqueBranchingObject (CbcModel * model,
346        const CbcClique * clique,
347        int way ,
348        int numberOnDownSide, const int * down,
349        int numberOnUpSide, const int * up)
350        : CbcBranchingObject(model, clique->id(), way, 0.5)
351{
352    clique_ = clique;
353    downMask_[0] = 0;
354    downMask_[1] = 0;
355    upMask_[0] = 0;
356    upMask_[1] = 0;
357    int i;
358    for (i = 0; i < numberOnDownSide; i++) {
359        int sequence = down[i];
360        int iWord = sequence >> 5;
361        int iBit = sequence - 32 * iWord;
362        unsigned int k = 1 << iBit;
363        downMask_[iWord] |= k;
364    }
365    for (i = 0; i < numberOnUpSide; i++) {
366        int sequence = up[i];
367        int iWord = sequence >> 5;
368        int iBit = sequence - 32 * iWord;
369        unsigned int k = 1 << iBit;
370        upMask_[iWord] |= k;
371    }
372}
373
374// Copy constructor
375CbcCliqueBranchingObject::CbcCliqueBranchingObject ( const CbcCliqueBranchingObject & rhs) : CbcBranchingObject(rhs)
376{
377    clique_ = rhs.clique_;
378    downMask_[0] = rhs.downMask_[0];
379    downMask_[1] = rhs.downMask_[1];
380    upMask_[0] = rhs.upMask_[0];
381    upMask_[1] = rhs.upMask_[1];
382}
383
384// Assignment operator
385CbcCliqueBranchingObject &
386CbcCliqueBranchingObject::operator=( const CbcCliqueBranchingObject & rhs)
387{
388    if (this != &rhs) {
389        CbcBranchingObject::operator=(rhs);
390        clique_ = rhs.clique_;
391        downMask_[0] = rhs.downMask_[0];
392        downMask_[1] = rhs.downMask_[1];
393        upMask_[0] = rhs.upMask_[0];
394        upMask_[1] = rhs.upMask_[1];
395    }
396    return *this;
397}
398CbcBranchingObject *
399CbcCliqueBranchingObject::clone() const
400{
401    return (new CbcCliqueBranchingObject(*this));
402}
403
404
405// Destructor
406CbcCliqueBranchingObject::~CbcCliqueBranchingObject ()
407{
408}
409double
410CbcCliqueBranchingObject::branch()
411{
412    decrementNumberBranchesLeft();
413    int iWord;
414    int numberMembers = clique_->numberMembers();
415    const int * which = clique_->members();
416    const int * integerVariables = model_->integerVariable();
417    int numberWords = (numberMembers + 31) >> 5;
418    // *** for way - up means fix all those in down section
419    if (way_ < 0) {
420#ifdef FULL_PRINT
421        printf("Down Fix ");
422#endif
423        for (iWord = 0; iWord < numberWords; iWord++) {
424            int i;
425            for (i = 0; i < 32; i++) {
426                unsigned int k = 1 << i;
427                if ((upMask_[iWord]&k) != 0) {
428                    int iColumn = which[i+32*iWord];
429#ifdef FULL_PRINT
430                    printf("%d ", i + 32*iWord);
431#endif
432                    // fix weak way
433                    if (clique_->type(i + 32*iWord))
434                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
435                    else
436                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
437                }
438            }
439        }
440        way_ = 1;         // Swap direction
441    } else {
442#ifdef FULL_PRINT
443        printf("Up Fix ");
444#endif
445        for (iWord = 0; iWord < numberWords; iWord++) {
446            int i;
447            for (i = 0; i < 32; i++) {
448                unsigned int k = 1 << i;
449                if ((downMask_[iWord]&k) != 0) {
450                    int iColumn = which[i+32*iWord];
451#ifdef FULL_PRINT
452                    printf("%d ", i + 32*iWord);
453#endif
454                    // fix weak way
455                    if (clique_->type(i + 32*iWord))
456                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
457                    else
458                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
459                }
460            }
461        }
462        way_ = -1;        // Swap direction
463    }
464#ifdef FULL_PRINT
465    printf("\n");
466#endif
467    return 0.0;
468}
469// Print what would happen
470void
471CbcCliqueBranchingObject::print()
472{
473    int iWord;
474    int numberMembers = clique_->numberMembers();
475    const int * which = clique_->members();
476    const int * integerVariables = model_->integerVariable();
477    int numberWords = (numberMembers + 31) >> 5;
478    // *** for way - up means fix all those in down section
479    if (way_ < 0) {
480        printf("Clique - Down Fix ");
481        for (iWord = 0; iWord < numberWords; iWord++) {
482            int i;
483            for (i = 0; i < 32; i++) {
484                unsigned int k = 1 << i;
485                if ((upMask_[iWord]&k) != 0) {
486                    int iColumn = which[i+32*iWord];
487                    printf("%d ", integerVariables[iColumn]);
488                }
489            }
490        }
491    } else {
492        printf("Clique - Up Fix ");
493        for (iWord = 0; iWord < numberWords; iWord++) {
494            int i;
495            for (i = 0; i < 32; i++) {
496                unsigned int k = 1 << i;
497                if ((downMask_[iWord]&k) != 0) {
498                    int iColumn = which[i+32*iWord];
499                    printf("%d ", integerVariables[iColumn]);
500                }
501            }
502        }
503    }
504    printf("\n");
505}
506
507static inline int
508CbcCompareCliques(const CbcClique* cl0, const CbcClique* cl1)
509{
510    if (cl0->cliqueType() < cl1->cliqueType()) {
511        return -1;
512    }
513    if (cl0->cliqueType() > cl1->cliqueType()) {
514        return 1;
515    }
516    if (cl0->numberMembers() != cl1->numberMembers()) {
517        return cl0->numberMembers() - cl1->numberMembers();
518    }
519    if (cl0->numberNonSOSMembers() != cl1->numberNonSOSMembers()) {
520        return cl0->numberNonSOSMembers() - cl1->numberNonSOSMembers();
521    }
522    return memcmp(cl0->members(), cl1->members(),
523                  cl0->numberMembers() * sizeof(int));
524}
525
526/** Compare the original object of \c this with the original object of \c
527    brObj. Assumes that there is an ordering of the original objects.
528    This method should be invoked only if \c this and brObj are of the same
529    type.
530    Return negative/0/positive depending on whether \c this is
531    smaller/same/larger than the argument.
532*/
533int
534CbcCliqueBranchingObject::compareOriginalObject
535(const CbcBranchingObject* brObj) const
536{
537    const CbcCliqueBranchingObject* br =
538        dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
539    assert(br);
540    return CbcCompareCliques(clique_, br->clique_);
541}
542
543/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
544    same type and must have the same original object, but they may have
545    different feasible regions.
546    Return the appropriate CbcRangeCompare value (first argument being the
547    sub/superset if that's the case). In case of overlap (and if \c
548    replaceIfOverlap is true) replace the current branching object with one
549    whose feasible region is the overlap.
550*/
551CbcRangeCompare
552CbcCliqueBranchingObject::compareBranchingObject
553(const CbcBranchingObject* brObj, const bool /*replaceIfOverlap*/)
554{
555    const CbcCliqueBranchingObject* br =
556        dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
557    assert(br);
558    unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
559    const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
560    const CoinUInt64 cl0 =
561        (static_cast<CoinUInt64>(thisMask[0]) << 32) | thisMask[1];
562    const CoinUInt64 cl1 =
563        (static_cast<CoinUInt64>(otherMask[0]) << 32) | otherMask[1];
564    if (cl0 == cl1) {
565        return CbcRangeSame;
566    }
567    const CoinUInt64 cl_intersection = (cl0 & cl1);
568    if (cl_intersection == cl0) {
569        return CbcRangeSuperset;
570    }
571    if (cl_intersection == cl1) {
572        return CbcRangeSubset;
573    }
574    const CoinUInt64 cl_xor = (cl0 ^ cl1);
575    if (cl_intersection == 0 && cl_xor == 0) {
576        return CbcRangeDisjoint;
577    }
578    const CoinUInt64 cl_union = (cl0 | cl1);
579    thisMask[0] = static_cast<unsigned int>(cl_union >> 32);
580    thisMask[1] = static_cast<unsigned int>(cl_union & 0xffffffff);
581    return CbcRangeOverlap;
582}
583
584//##############################################################################
585
586// Default Constructor
587CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject()
588        : CbcBranchingObject()
589{
590    clique_ = NULL;
591    downMask_ = NULL;
592    upMask_ = NULL;
593}
594
595// Useful constructor
596CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject (CbcModel * model,
597        const CbcClique * clique,
598        int way ,
599        int numberOnDownSide, const int * down,
600        int numberOnUpSide, const int * up)
601        : CbcBranchingObject(model, clique->id(), way, 0.5)
602{
603    clique_ = clique;
604    int numberMembers = clique_->numberMembers();
605    int numberWords = (numberMembers + 31) >> 5;
606    downMask_ = new unsigned int [numberWords];
607    upMask_ = new unsigned int [numberWords];
608    memset(downMask_, 0, numberWords*sizeof(unsigned int));
609    memset(upMask_, 0, numberWords*sizeof(unsigned int));
610    int i;
611    for (i = 0; i < numberOnDownSide; i++) {
612        int sequence = down[i];
613        int iWord = sequence >> 5;
614        int iBit = sequence - 32 * iWord;
615        unsigned int k = 1 << iBit;
616        downMask_[iWord] |= k;
617    }
618    for (i = 0; i < numberOnUpSide; i++) {
619        int sequence = up[i];
620        int iWord = sequence >> 5;
621        int iBit = sequence - 32 * iWord;
622        unsigned int k = 1 << iBit;
623        upMask_[iWord] |= k;
624    }
625}
626
627// Copy constructor
628CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject & rhs) : CbcBranchingObject(rhs)
629{
630    clique_ = rhs.clique_;
631    if (rhs.downMask_) {
632        int numberMembers = clique_->numberMembers();
633        int numberWords = (numberMembers + 31) >> 5;
634        downMask_ = new unsigned int [numberWords];
635        memcpy(downMask_, rhs.downMask_, numberWords*sizeof(unsigned int));
636        upMask_ = new unsigned int [numberWords];
637        memcpy(upMask_, rhs.upMask_, numberWords*sizeof(unsigned int));
638    } else {
639        downMask_ = NULL;
640        upMask_ = NULL;
641    }
642}
643
644// Assignment operator
645CbcLongCliqueBranchingObject &
646CbcLongCliqueBranchingObject::operator=( const CbcLongCliqueBranchingObject & rhs)
647{
648    if (this != &rhs) {
649        CbcBranchingObject::operator=(rhs);
650        clique_ = rhs.clique_;
651        delete [] downMask_;
652        delete [] upMask_;
653        if (rhs.downMask_) {
654            int numberMembers = clique_->numberMembers();
655            int numberWords = (numberMembers + 31) >> 5;
656            downMask_ = new unsigned int [numberWords];
657            memcpy(downMask_, rhs.downMask_, numberWords*sizeof(unsigned int));
658            upMask_ = new unsigned int [numberWords];
659            memcpy(upMask_, rhs.upMask_, numberWords*sizeof(unsigned int));
660        } else {
661            downMask_ = NULL;
662            upMask_ = NULL;
663        }
664    }
665    return *this;
666}
667CbcBranchingObject *
668CbcLongCliqueBranchingObject::clone() const
669{
670    return (new CbcLongCliqueBranchingObject(*this));
671}
672
673
674// Destructor
675CbcLongCliqueBranchingObject::~CbcLongCliqueBranchingObject ()
676{
677    delete [] downMask_;
678    delete [] upMask_;
679}
680double
681CbcLongCliqueBranchingObject::branch()
682{
683    decrementNumberBranchesLeft();
684    int iWord;
685    int numberMembers = clique_->numberMembers();
686    const int * which = clique_->members();
687    const int * integerVariables = model_->integerVariable();
688    int numberWords = (numberMembers + 31) >> 5;
689    // *** for way - up means fix all those in down section
690    if (way_ < 0) {
691#ifdef FULL_PRINT
692        printf("Down Fix ");
693#endif
694        for (iWord = 0; iWord < numberWords; iWord++) {
695            int i;
696            for (i = 0; i < 32; i++) {
697                unsigned int k = 1 << i;
698                if ((upMask_[iWord]&k) != 0) {
699                    int iColumn = which[i+32*iWord];
700#ifdef FULL_PRINT
701                    printf("%d ", i + 32*iWord);
702#endif
703                    // fix weak way
704                    if (clique_->type(i + 32*iWord))
705                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
706                    else
707                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
708                }
709            }
710        }
711        way_ = 1;         // Swap direction
712    } else {
713#ifdef FULL_PRINT
714        printf("Up Fix ");
715#endif
716        for (iWord = 0; iWord < numberWords; iWord++) {
717            int i;
718            for (i = 0; i < 32; i++) {
719                unsigned int k = 1 << i;
720                if ((downMask_[iWord]&k) != 0) {
721                    int iColumn = which[i+32*iWord];
722#ifdef FULL_PRINT
723                    printf("%d ", i + 32*iWord);
724#endif
725                    // fix weak way
726                    if (clique_->type(i + 32*iWord))
727                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
728                    else
729                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
730                }
731            }
732        }
733        way_ = -1;        // Swap direction
734    }
735#ifdef FULL_PRINT
736    printf("\n");
737#endif
738    return 0.0;
739}
740void
741CbcLongCliqueBranchingObject::print()
742{
743    int iWord;
744    int numberMembers = clique_->numberMembers();
745    const int * which = clique_->members();
746    const int * integerVariables = model_->integerVariable();
747    int numberWords = (numberMembers + 31) >> 5;
748    // *** for way - up means fix all those in down section
749    if (way_ < 0) {
750        printf("Clique - Down Fix ");
751        for (iWord = 0; iWord < numberWords; iWord++) {
752            int i;
753            for (i = 0; i < 32; i++) {
754                unsigned int k = 1 << i;
755                if ((upMask_[iWord]&k) != 0) {
756                    int iColumn = which[i+32*iWord];
757                    printf("%d ", integerVariables[iColumn]);
758                }
759            }
760        }
761    } else {
762        printf("Clique - Up Fix ");
763        for (iWord = 0; iWord < numberWords; iWord++) {
764            int i;
765            for (i = 0; i < 32; i++) {
766                unsigned int k = 1 << i;
767                if ((downMask_[iWord]&k) != 0) {
768                    int iColumn = which[i+32*iWord];
769                    printf("%d ", integerVariables[iColumn]);
770                }
771            }
772        }
773    }
774    printf("\n");
775}
776
777/** Compare the original object of \c this with the original object of \c
778    brObj. Assumes that there is an ordering of the original objects.
779    This method should be invoked only if \c this and brObj are of the same
780    type.
781    Return negative/0/positive depending on whether \c this is
782    smaller/same/larger than the argument.
783*/
784int
785CbcLongCliqueBranchingObject::compareOriginalObject
786(const CbcBranchingObject* brObj) const
787{
788    const CbcLongCliqueBranchingObject* br =
789        dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
790    assert(br);
791    return CbcCompareCliques(clique_, br->clique_);
792}
793
794/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
795    same type and must have the same original object, but they may have
796    different feasible regions.
797    Return the appropriate CbcRangeCompare value (first argument being the
798    sub/superset if that's the case). In case of overlap (and if \c
799    replaceIfOverlap is true) replace the current branching object with one
800    whose feasible region is the overlap.
801*/
802CbcRangeCompare
803CbcLongCliqueBranchingObject::compareBranchingObject
804(const CbcBranchingObject* brObj, const bool /*replaceIfOverlap*/)
805{
806    const CbcLongCliqueBranchingObject* br =
807        dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
808    assert(br);
809    const int numberMembers = clique_->numberMembers();
810    const int numberWords = (numberMembers + 31) >> 5;
811    unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
812    const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
813
814    if (memcmp(thisMask, otherMask, numberWords * sizeof(unsigned int)) == 0) {
815        return CbcRangeSame;
816    }
817    bool canBeSuperset = true;
818    bool canBeSubset = true;
819    int i;
820    for (i = numberWords - 1; i >= 0 && (canBeSuperset || canBeSubset); --i) {
821        const unsigned int both = (thisMask[i] & otherMask[i]);
822        canBeSuperset &= (both == thisMask[i]);
823        canBeSubset &= (both == otherMask[i]);
824    }
825    if (canBeSuperset) {
826        return CbcRangeSuperset;
827    }
828    if (canBeSubset) {
829        return CbcRangeSubset;
830    }
831
832    for (i = numberWords - 1; i >= 0; --i) {
833        if ((thisMask[i] ^ otherMask[i]) != 0) {
834            break;
835        }
836    }
837    if (i == -1) { // complement
838        return CbcRangeDisjoint;
839    }
840    // must be overlap
841    for (i = numberWords - 1; i >= 0; --i) {
842        thisMask[i] |= otherMask[i];
843    }
844    return CbcRangeOverlap;
845}
Note: See TracBrowser for help on using the repository browser.