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

Last change on this file since 1389 was 1357, checked in by coin, 10 years ago

run 'astyle -A4 -p' and dos2unix

File size: 27.3 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}
123/*
124  Unfortunately, that comment is untrue. And there are other issues. This
125  routine is clearly an unfinished work.
126*/
127double
128CbcClique::infeasibility(const OsiBranchingInformation * /*info*/,
129                         int &preferredWay) const
130{
131    int numberUnsatis = 0, numberFree = 0;
132    int j;
133    const int * integer = model_->integerVariable();
134    OsiSolverInterface * solver = model_->solver();
135    const double * solution = model_->testSolution();
136    const double * lower = solver->getColLower();
137    const double * upper = solver->getColUpper();
138    double largestValue = 0.0;
139    double integerTolerance =
140        model_->getDblParam(CbcModel::CbcIntegerTolerance);
141    double * sort = new double[numberMembers_];
142    /*
143      Calculate integer infeasibility and fill an array. Pick off the infeasibility
144      of the slack and the max infeasibility while we're at it. You can see here
145      the conversion of `non-SOS' (strong value of 0, negative coefficient) to
146      `SOS' (strong value of 1, positive coefficient). Also count the number of
147      variables that have integral values but are not fixed.
148    */
149    double slackValue = 0.0;
150    for (j = 0; j < numberMembers_; j++) {
151        int sequence = members_[j];
152        int iColumn = integer[sequence];
153        double value = solution[iColumn];
154        value = CoinMax(value, lower[iColumn]);
155        value = CoinMin(value, upper[iColumn]);
156        double nearest = floor(value + 0.5);
157        double distance = fabs(value - nearest);
158        if (distance > integerTolerance) {
159            if (!type_[j])
160                value = 1.0 - value; // non SOS
161            // if slack then choose that
162            if (j == slack_ && value > 0.05)
163                slackValue = value;
164            largestValue = CoinMax(value, largestValue);
165            sort[numberUnsatis++] = -value;
166        } else if (upper[iColumn] > lower[iColumn]) {
167            numberFree++;
168        }
169    }
170    /*
171      preferredWay will not change. The calculation of otherWay is an expensive
172      noop --- value is ultimately unused. Same for the sort of sort. It looks like
173      there was some notion of branching by splitting the set using even and odd
174      indices (as opposed to first and second half).
175    */
176    preferredWay = 1;
177    double otherWay = 0.0;
178    if (numberUnsatis) {
179        // sort
180        std::sort(sort, sort + numberUnsatis);
181        for (j = 0; j < numberUnsatis; j++) {
182            if ((j&1) != 0)
183                otherWay += -sort[j];
184        }
185        // Need to think more
186        /*
187          Here we have the actual infeasibility calculation. Most previous work is
188          discarded, and we calculate a value using various counts, adjusted by the
189          max value and slack value. This is not scaled to [0, .5].
190        */
191
192        double value = 0.2 * numberUnsatis + 0.01 * (numberMembers_ - numberFree);
193        if (fabs(largestValue - 0.5) < 0.1) {
194            // close to half
195            value += 0.1;
196        }
197        if (slackValue) {
198            // branching on slack
199            value += slackValue;
200        }
201        // scale other way
202        otherWay *= value / (1.0 - otherWay);
203        delete [] sort;
204        return value;
205    } else {
206        delete [] sort;
207        return 0.0; // satisfied
208    }
209}
210
211// This looks at solution and sets bounds to contain solution
212void
213CbcClique::feasibleRegion()
214{
215    int j;
216    const int * integer = model_->integerVariable();
217    OsiSolverInterface * solver = model_->solver();
218    const double * solution = model_->testSolution();
219    const double * lower = solver->getColLower();
220    const double * upper = solver->getColUpper();
221#ifndef NDEBUG
222    double integerTolerance =
223        model_->getDblParam(CbcModel::CbcIntegerTolerance);
224#endif
225    for (j = 0; j < numberMembers_; j++) {
226        int sequence = members_[j];
227        int iColumn = integer[sequence];
228        double value = solution[iColumn];
229        value = CoinMax(value, lower[iColumn]);
230        value = CoinMin(value, upper[iColumn]);
231        double nearest = floor(value + 0.5);
232#ifndef NDEBUG
233        double distance = fabs(value - nearest);
234        assert(distance <= integerTolerance);
235#endif
236        solver->setColLower(iColumn, nearest);
237        solver->setColUpper(iColumn, nearest);
238    }
239}
240// Redoes data when sequence numbers change
241void
242CbcClique::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns)
243{
244    model_ = model;
245    int n2 = 0;
246    for (int j = 0; j < numberMembers_; j++) {
247        int iColumn = members_[j];
248        int i;
249        for (i = 0; i < numberColumns; i++) {
250            if (originalColumns[i] == iColumn)
251                break;
252        }
253        if (i < numberColumns) {
254            members_[n2] = i;
255            type_[n2++] = type_[j];
256        }
257    }
258    if (n2 < numberMembers_) {
259        //printf("** SOS number of members reduced from %d to %d!\n",numberMembers_,n2);
260        numberMembers_ = n2;
261    }
262    // Find out how many non sos
263    int i;
264    numberNonSOSMembers_ = 0;
265    for (i = 0; i < numberMembers_; i++)
266        if (!type_[i])
267            numberNonSOSMembers_++;
268}
269CbcBranchingObject *
270CbcClique::createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * /*info*/, int way)
271{
272    int numberUnsatis = 0;
273    int j;
274    int nUp = 0;
275    int nDown = 0;
276    int numberFree = numberMembers_;
277    const int * integer = model_->integerVariable();
278    //OsiSolverInterface * solver = model_->solver();
279    const double * solution = model_->testSolution();
280    const double * lower = solver->getColLower();
281    const double * upper = solver->getColUpper();
282    int * upList = new int[numberMembers_];
283    int * downList = new int[numberMembers_];
284    double * sort = new double[numberMembers_];
285    double integerTolerance =
286        model_->getDblParam(CbcModel::CbcIntegerTolerance);
287
288    double slackValue = 0.0;
289    for (j = 0; j < numberMembers_; j++) {
290        int sequence = members_[j];
291        int iColumn = integer[sequence];
292        double value = solution[iColumn];
293        value = CoinMax(value, lower[iColumn]);
294        value = CoinMin(value, upper[iColumn]);
295        double nearest = floor(value + 0.5);
296        double distance = fabs(value - nearest);
297        if (distance > integerTolerance) {
298            if (!type_[j])
299                value = 1.0 - value; // non SOS
300            // if slack then choose that
301            if (j == slack_ && value > 0.05)
302                slackValue = value;
303            value = -value; // for sort
304            upList[numberUnsatis] = j;
305            sort[numberUnsatis++] = value;
306        } else if (upper[iColumn] > lower[iColumn]) {
307            upList[--numberFree] = j;
308        }
309    }
310    assert (numberUnsatis);
311    if (!slackValue) {
312        // sort
313        CoinSort_2(sort, sort + numberUnsatis, upList);
314        // put first in up etc
315        int kWay = 1;
316        for (j = 0; j < numberUnsatis; j++) {
317            if (kWay > 0)
318                upList[nUp++] = upList[j];
319            else
320                downList[nDown++] = upList[j];
321            kWay = -kWay;
322        }
323        for (j = numberFree; j < numberMembers_; j++) {
324            if (kWay > 0)
325                upList[nUp++] = upList[j];
326            else
327                downList[nDown++] = upList[j];
328            kWay = -kWay;
329        }
330    } else {
331        // put slack to 0 in first way
332        nUp = 1;
333        upList[0] = slack_;
334        for (j = 0; j < numberUnsatis; j++) {
335            downList[nDown++] = upList[j];
336        }
337        for (j = numberFree; j < numberMembers_; j++) {
338            downList[nDown++] = upList[j];
339        }
340    }
341    // create object
342    CbcBranchingObject * branch;
343    if (numberMembers_ <= 64)
344        branch = new CbcCliqueBranchingObject(model_, this, way,
345                                              nDown, downList, nUp, upList);
346    else
347        branch = new CbcLongCliqueBranchingObject(model_, this, way,
348                nDown, downList, nUp, upList);
349    delete [] upList;
350    delete [] downList;
351    delete [] sort;
352    return branch;
353}
354
355// Default Constructor
356CbcCliqueBranchingObject::CbcCliqueBranchingObject()
357        : CbcBranchingObject()
358{
359    clique_ = NULL;
360    downMask_[0] = 0;
361    downMask_[1] = 0;
362    upMask_[0] = 0;
363    upMask_[1] = 0;
364}
365
366// Useful constructor
367CbcCliqueBranchingObject::CbcCliqueBranchingObject (CbcModel * model,
368        const CbcClique * clique,
369        int way ,
370        int numberOnDownSide, const int * down,
371        int numberOnUpSide, const int * up)
372        : CbcBranchingObject(model, clique->id(), way, 0.5)
373{
374    clique_ = clique;
375    downMask_[0] = 0;
376    downMask_[1] = 0;
377    upMask_[0] = 0;
378    upMask_[1] = 0;
379    int i;
380    for (i = 0; i < numberOnDownSide; i++) {
381        int sequence = down[i];
382        int iWord = sequence >> 5;
383        int iBit = sequence - 32 * iWord;
384        unsigned int k = 1 << iBit;
385        downMask_[iWord] |= k;
386    }
387    for (i = 0; i < numberOnUpSide; i++) {
388        int sequence = up[i];
389        int iWord = sequence >> 5;
390        int iBit = sequence - 32 * iWord;
391        unsigned int k = 1 << iBit;
392        upMask_[iWord] |= k;
393    }
394}
395
396// Copy constructor
397CbcCliqueBranchingObject::CbcCliqueBranchingObject ( const CbcCliqueBranchingObject & rhs) : CbcBranchingObject(rhs)
398{
399    clique_ = rhs.clique_;
400    downMask_[0] = rhs.downMask_[0];
401    downMask_[1] = rhs.downMask_[1];
402    upMask_[0] = rhs.upMask_[0];
403    upMask_[1] = rhs.upMask_[1];
404}
405
406// Assignment operator
407CbcCliqueBranchingObject &
408CbcCliqueBranchingObject::operator=( const CbcCliqueBranchingObject & rhs)
409{
410    if (this != &rhs) {
411        CbcBranchingObject::operator=(rhs);
412        clique_ = rhs.clique_;
413        downMask_[0] = rhs.downMask_[0];
414        downMask_[1] = rhs.downMask_[1];
415        upMask_[0] = rhs.upMask_[0];
416        upMask_[1] = rhs.upMask_[1];
417    }
418    return *this;
419}
420CbcBranchingObject *
421CbcCliqueBranchingObject::clone() const
422{
423    return (new CbcCliqueBranchingObject(*this));
424}
425
426
427// Destructor
428CbcCliqueBranchingObject::~CbcCliqueBranchingObject ()
429{
430}
431double
432CbcCliqueBranchingObject::branch()
433{
434    decrementNumberBranchesLeft();
435    int iWord;
436    int numberMembers = clique_->numberMembers();
437    const int * which = clique_->members();
438    const int * integerVariables = model_->integerVariable();
439    int numberWords = (numberMembers + 31) >> 5;
440    // *** for way - up means fix all those in down section
441    if (way_ < 0) {
442#ifdef FULL_PRINT
443        printf("Down 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 ((upMask_[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    } else {
464#ifdef FULL_PRINT
465        printf("Up Fix ");
466#endif
467        for (iWord = 0; iWord < numberWords; iWord++) {
468            int i;
469            for (i = 0; i < 32; i++) {
470                unsigned int k = 1 << i;
471                if ((downMask_[iWord]&k) != 0) {
472                    int iColumn = which[i+32*iWord];
473#ifdef FULL_PRINT
474                    printf("%d ", i + 32*iWord);
475#endif
476                    // fix weak way
477                    if (clique_->type(i + 32*iWord))
478                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
479                    else
480                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
481                }
482            }
483        }
484        way_ = -1;        // Swap direction
485    }
486#ifdef FULL_PRINT
487    printf("\n");
488#endif
489    return 0.0;
490}
491// Print what would happen
492void
493CbcCliqueBranchingObject::print()
494{
495    int iWord;
496    int numberMembers = clique_->numberMembers();
497    const int * which = clique_->members();
498    const int * integerVariables = model_->integerVariable();
499    int numberWords = (numberMembers + 31) >> 5;
500    // *** for way - up means fix all those in down section
501    if (way_ < 0) {
502        printf("Clique - Down Fix ");
503        for (iWord = 0; iWord < numberWords; iWord++) {
504            int i;
505            for (i = 0; i < 32; i++) {
506                unsigned int k = 1 << i;
507                if ((upMask_[iWord]&k) != 0) {
508                    int iColumn = which[i+32*iWord];
509                    printf("%d ", integerVariables[iColumn]);
510                }
511            }
512        }
513    } else {
514        printf("Clique - Up Fix ");
515        for (iWord = 0; iWord < numberWords; iWord++) {
516            int i;
517            for (i = 0; i < 32; i++) {
518                unsigned int k = 1 << i;
519                if ((downMask_[iWord]&k) != 0) {
520                    int iColumn = which[i+32*iWord];
521                    printf("%d ", integerVariables[iColumn]);
522                }
523            }
524        }
525    }
526    printf("\n");
527}
528
529static inline int
530CbcCompareCliques(const CbcClique* cl0, const CbcClique* cl1)
531{
532    if (cl0->cliqueType() < cl1->cliqueType()) {
533        return -1;
534    }
535    if (cl0->cliqueType() > cl1->cliqueType()) {
536        return 1;
537    }
538    if (cl0->numberMembers() != cl1->numberMembers()) {
539        return cl0->numberMembers() - cl1->numberMembers();
540    }
541    if (cl0->numberNonSOSMembers() != cl1->numberNonSOSMembers()) {
542        return cl0->numberNonSOSMembers() - cl1->numberNonSOSMembers();
543    }
544    return memcmp(cl0->members(), cl1->members(),
545                  cl0->numberMembers() * sizeof(int));
546}
547
548/** Compare the original object of \c this with the original object of \c
549    brObj. Assumes that there is an ordering of the original objects.
550    This method should be invoked only if \c this and brObj are of the same
551    type.
552    Return negative/0/positive depending on whether \c this is
553    smaller/same/larger than the argument.
554*/
555int
556CbcCliqueBranchingObject::compareOriginalObject
557(const CbcBranchingObject* brObj) const
558{
559    const CbcCliqueBranchingObject* br =
560        dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
561    assert(br);
562    return CbcCompareCliques(clique_, br->clique_);
563}
564
565/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
566    same type and must have the same original object, but they may have
567    different feasible regions.
568    Return the appropriate CbcRangeCompare value (first argument being the
569    sub/superset if that's the case). In case of overlap (and if \c
570    replaceIfOverlap is true) replace the current branching object with one
571    whose feasible region is the overlap.
572*/
573CbcRangeCompare
574CbcCliqueBranchingObject::compareBranchingObject
575(const CbcBranchingObject* brObj, const bool /*replaceIfOverlap*/)
576{
577    const CbcCliqueBranchingObject* br =
578        dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
579    assert(br);
580    unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
581    const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
582    const CoinUInt64 cl0 =
583        (static_cast<CoinUInt64>(thisMask[0]) << 32) | thisMask[1];
584    const CoinUInt64 cl1 =
585        (static_cast<CoinUInt64>(otherMask[0]) << 32) | otherMask[1];
586    if (cl0 == cl1) {
587        return CbcRangeSame;
588    }
589    const CoinUInt64 cl_intersection = (cl0 & cl1);
590    if (cl_intersection == cl0) {
591        return CbcRangeSuperset;
592    }
593    if (cl_intersection == cl1) {
594        return CbcRangeSubset;
595    }
596    const CoinUInt64 cl_xor = (cl0 ^ cl1);
597    if (cl_intersection == 0 && cl_xor == 0) {
598        return CbcRangeDisjoint;
599    }
600    const CoinUInt64 cl_union = (cl0 | cl1);
601    thisMask[0] = static_cast<unsigned int>(cl_union >> 32);
602    thisMask[1] = static_cast<unsigned int>(cl_union & 0xffffffff);
603    return CbcRangeOverlap;
604}
605
606//##############################################################################
607
608// Default Constructor
609CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject()
610        : CbcBranchingObject()
611{
612    clique_ = NULL;
613    downMask_ = NULL;
614    upMask_ = NULL;
615}
616
617// Useful constructor
618CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject (CbcModel * model,
619        const CbcClique * clique,
620        int way ,
621        int numberOnDownSide, const int * down,
622        int numberOnUpSide, const int * up)
623        : CbcBranchingObject(model, clique->id(), way, 0.5)
624{
625    clique_ = clique;
626    int numberMembers = clique_->numberMembers();
627    int numberWords = (numberMembers + 31) >> 5;
628    downMask_ = new unsigned int [numberWords];
629    upMask_ = new unsigned int [numberWords];
630    memset(downMask_, 0, numberWords*sizeof(unsigned int));
631    memset(upMask_, 0, numberWords*sizeof(unsigned int));
632    int i;
633    for (i = 0; i < numberOnDownSide; i++) {
634        int sequence = down[i];
635        int iWord = sequence >> 5;
636        int iBit = sequence - 32 * iWord;
637        unsigned int k = 1 << iBit;
638        downMask_[iWord] |= k;
639    }
640    for (i = 0; i < numberOnUpSide; i++) {
641        int sequence = up[i];
642        int iWord = sequence >> 5;
643        int iBit = sequence - 32 * iWord;
644        unsigned int k = 1 << iBit;
645        upMask_[iWord] |= k;
646    }
647}
648
649// Copy constructor
650CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject & rhs) : CbcBranchingObject(rhs)
651{
652    clique_ = rhs.clique_;
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
666// Assignment operator
667CbcLongCliqueBranchingObject &
668CbcLongCliqueBranchingObject::operator=( const CbcLongCliqueBranchingObject & rhs)
669{
670    if (this != &rhs) {
671        CbcBranchingObject::operator=(rhs);
672        clique_ = rhs.clique_;
673        delete [] downMask_;
674        delete [] upMask_;
675        if (rhs.downMask_) {
676            int numberMembers = clique_->numberMembers();
677            int numberWords = (numberMembers + 31) >> 5;
678            downMask_ = new unsigned int [numberWords];
679            memcpy(downMask_, rhs.downMask_, numberWords*sizeof(unsigned int));
680            upMask_ = new unsigned int [numberWords];
681            memcpy(upMask_, rhs.upMask_, numberWords*sizeof(unsigned int));
682        } else {
683            downMask_ = NULL;
684            upMask_ = NULL;
685        }
686    }
687    return *this;
688}
689CbcBranchingObject *
690CbcLongCliqueBranchingObject::clone() const
691{
692    return (new CbcLongCliqueBranchingObject(*this));
693}
694
695
696// Destructor
697CbcLongCliqueBranchingObject::~CbcLongCliqueBranchingObject ()
698{
699    delete [] downMask_;
700    delete [] upMask_;
701}
702double
703CbcLongCliqueBranchingObject::branch()
704{
705    decrementNumberBranchesLeft();
706    int iWord;
707    int numberMembers = clique_->numberMembers();
708    const int * which = clique_->members();
709    const int * integerVariables = model_->integerVariable();
710    int numberWords = (numberMembers + 31) >> 5;
711    // *** for way - up means fix all those in down section
712    if (way_ < 0) {
713#ifdef FULL_PRINT
714        printf("Down 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 ((upMask_[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    } else {
735#ifdef FULL_PRINT
736        printf("Up Fix ");
737#endif
738        for (iWord = 0; iWord < numberWords; iWord++) {
739            int i;
740            for (i = 0; i < 32; i++) {
741                unsigned int k = 1 << i;
742                if ((downMask_[iWord]&k) != 0) {
743                    int iColumn = which[i+32*iWord];
744#ifdef FULL_PRINT
745                    printf("%d ", i + 32*iWord);
746#endif
747                    // fix weak way
748                    if (clique_->type(i + 32*iWord))
749                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
750                    else
751                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
752                }
753            }
754        }
755        way_ = -1;        // Swap direction
756    }
757#ifdef FULL_PRINT
758    printf("\n");
759#endif
760    return 0.0;
761}
762void
763CbcLongCliqueBranchingObject::print()
764{
765    int iWord;
766    int numberMembers = clique_->numberMembers();
767    const int * which = clique_->members();
768    const int * integerVariables = model_->integerVariable();
769    int numberWords = (numberMembers + 31) >> 5;
770    // *** for way - up means fix all those in down section
771    if (way_ < 0) {
772        printf("Clique - Down Fix ");
773        for (iWord = 0; iWord < numberWords; iWord++) {
774            int i;
775            for (i = 0; i < 32; i++) {
776                unsigned int k = 1 << i;
777                if ((upMask_[iWord]&k) != 0) {
778                    int iColumn = which[i+32*iWord];
779                    printf("%d ", integerVariables[iColumn]);
780                }
781            }
782        }
783    } else {
784        printf("Clique - Up Fix ");
785        for (iWord = 0; iWord < numberWords; iWord++) {
786            int i;
787            for (i = 0; i < 32; i++) {
788                unsigned int k = 1 << i;
789                if ((downMask_[iWord]&k) != 0) {
790                    int iColumn = which[i+32*iWord];
791                    printf("%d ", integerVariables[iColumn]);
792                }
793            }
794        }
795    }
796    printf("\n");
797}
798
799/** Compare the original object of \c this with the original object of \c
800    brObj. Assumes that there is an ordering of the original objects.
801    This method should be invoked only if \c this and brObj are of the same
802    type.
803    Return negative/0/positive depending on whether \c this is
804    smaller/same/larger than the argument.
805*/
806int
807CbcLongCliqueBranchingObject::compareOriginalObject
808(const CbcBranchingObject* brObj) const
809{
810    const CbcLongCliqueBranchingObject* br =
811        dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
812    assert(br);
813    return CbcCompareCliques(clique_, br->clique_);
814}
815
816/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
817    same type and must have the same original object, but they may have
818    different feasible regions.
819    Return the appropriate CbcRangeCompare value (first argument being the
820    sub/superset if that's the case). In case of overlap (and if \c
821    replaceIfOverlap is true) replace the current branching object with one
822    whose feasible region is the overlap.
823*/
824CbcRangeCompare
825CbcLongCliqueBranchingObject::compareBranchingObject
826(const CbcBranchingObject* brObj, const bool /*replaceIfOverlap*/)
827{
828    const CbcLongCliqueBranchingObject* br =
829        dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
830    assert(br);
831    const int numberMembers = clique_->numberMembers();
832    const int numberWords = (numberMembers + 31) >> 5;
833    unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
834    const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
835
836    if (memcmp(thisMask, otherMask, numberWords * sizeof(unsigned int)) == 0) {
837        return CbcRangeSame;
838    }
839    bool canBeSuperset = true;
840    bool canBeSubset = true;
841    int i;
842    for (i = numberWords - 1; i >= 0 && (canBeSuperset || canBeSubset); --i) {
843        const unsigned int both = (thisMask[i] & otherMask[i]);
844        canBeSuperset &= (both == thisMask[i]);
845        canBeSubset &= (both == otherMask[i]);
846    }
847    if (canBeSuperset) {
848        return CbcRangeSuperset;
849    }
850    if (canBeSubset) {
851        return CbcRangeSubset;
852    }
853
854    for (i = numberWords - 1; i >= 0; --i) {
855        if ((thisMask[i] ^ otherMask[i]) != 0) {
856            break;
857        }
858    }
859    if (i == -1) { // complement
860        return CbcRangeDisjoint;
861    }
862    // must be overlap
863    for (i = numberWords - 1; i >= 0; --i) {
864        thisMask[i] |= otherMask[i];
865    }
866    return CbcRangeOverlap;
867}
Note: See TracBrowser for help on using the repository browser.