source: trunk/Cbc/src/CbcClique.cpp @ 2080

Last change on this file since 2080 was 1899, checked in by stefan, 7 years ago

fixup svn properties

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