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

Last change on this file since 2094 was 2094, checked in by forrest, 4 years ago

for memory leaks and heuristics and some experimental stuff

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