Ignore:
Timestamp:
Dec 3, 2009 2:36:52 PM (10 years ago)
Author:
EdwinStraver
Message:

Combined CbcClique? with CbcCliqueBranchingObject? and CbcLongCliqueBranchingObject?.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/sandbox/Cbc/src/CbcClique.cpp

    r1293 r1344  
    330330    return branch;
    331331}
     332
     333// Default Constructor
     334CbcCliqueBranchingObject::CbcCliqueBranchingObject()
     335        : CbcBranchingObject()
     336{
     337    clique_ = NULL;
     338    downMask_[0] = 0;
     339    downMask_[1] = 0;
     340    upMask_[0] = 0;
     341    upMask_[1] = 0;
     342}
     343
     344// Useful constructor
     345CbcCliqueBranchingObject::CbcCliqueBranchingObject (CbcModel * model,
     346        const CbcClique * clique,
     347        int way ,
     348        int numberOnDownSide, const int * down,
     349        int numberOnUpSide, const int * up)
     350        : CbcBranchingObject(model, clique->id(), way, 0.5)
     351{
     352    clique_ = clique;
     353    downMask_[0] = 0;
     354    downMask_[1] = 0;
     355    upMask_[0] = 0;
     356    upMask_[1] = 0;
     357    int i;
     358    for (i = 0; i < numberOnDownSide; i++) {
     359        int sequence = down[i];
     360        int iWord = sequence >> 5;
     361        int iBit = sequence - 32 * iWord;
     362        unsigned int k = 1 << iBit;
     363        downMask_[iWord] |= k;
     364    }
     365    for (i = 0; i < numberOnUpSide; i++) {
     366        int sequence = up[i];
     367        int iWord = sequence >> 5;
     368        int iBit = sequence - 32 * iWord;
     369        unsigned int k = 1 << iBit;
     370        upMask_[iWord] |= k;
     371    }
     372}
     373
     374// Copy constructor
     375CbcCliqueBranchingObject::CbcCliqueBranchingObject ( const CbcCliqueBranchingObject & rhs) : CbcBranchingObject(rhs)
     376{
     377    clique_ = rhs.clique_;
     378    downMask_[0] = rhs.downMask_[0];
     379    downMask_[1] = rhs.downMask_[1];
     380    upMask_[0] = rhs.upMask_[0];
     381    upMask_[1] = rhs.upMask_[1];
     382}
     383
     384// Assignment operator
     385CbcCliqueBranchingObject &
     386CbcCliqueBranchingObject::operator=( const CbcCliqueBranchingObject & rhs)
     387{
     388    if (this != &rhs) {
     389        CbcBranchingObject::operator=(rhs);
     390        clique_ = rhs.clique_;
     391        downMask_[0] = rhs.downMask_[0];
     392        downMask_[1] = rhs.downMask_[1];
     393        upMask_[0] = rhs.upMask_[0];
     394        upMask_[1] = rhs.upMask_[1];
     395    }
     396    return *this;
     397}
     398CbcBranchingObject *
     399CbcCliqueBranchingObject::clone() const
     400{
     401    return (new CbcCliqueBranchingObject(*this));
     402}
     403
     404
     405// Destructor
     406CbcCliqueBranchingObject::~CbcCliqueBranchingObject ()
     407{
     408}
     409double
     410CbcCliqueBranchingObject::branch()
     411{
     412    decrementNumberBranchesLeft();
     413    int iWord;
     414    int numberMembers = clique_->numberMembers();
     415    const int * which = clique_->members();
     416    const int * integerVariables = model_->integerVariable();
     417    int numberWords = (numberMembers + 31) >> 5;
     418    // *** for way - up means fix all those in down section
     419    if (way_ < 0) {
     420#ifdef FULL_PRINT
     421        printf("Down Fix ");
     422#endif
     423        for (iWord = 0; iWord < numberWords; iWord++) {
     424            int i;
     425            for (i = 0; i < 32; i++) {
     426                unsigned int k = 1 << i;
     427                if ((upMask_[iWord]&k) != 0) {
     428                    int iColumn = which[i+32*iWord];
     429#ifdef FULL_PRINT
     430                    printf("%d ", i + 32*iWord);
     431#endif
     432                    // fix weak way
     433                    if (clique_->type(i + 32*iWord))
     434                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
     435                    else
     436                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
     437                }
     438            }
     439        }
     440        way_ = 1;         // Swap direction
     441    } else {
     442#ifdef FULL_PRINT
     443        printf("Up Fix ");
     444#endif
     445        for (iWord = 0; iWord < numberWords; iWord++) {
     446            int i;
     447            for (i = 0; i < 32; i++) {
     448                unsigned int k = 1 << i;
     449                if ((downMask_[iWord]&k) != 0) {
     450                    int iColumn = which[i+32*iWord];
     451#ifdef FULL_PRINT
     452                    printf("%d ", i + 32*iWord);
     453#endif
     454                    // fix weak way
     455                    if (clique_->type(i + 32*iWord))
     456                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
     457                    else
     458                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
     459                }
     460            }
     461        }
     462        way_ = -1;        // Swap direction
     463    }
     464#ifdef FULL_PRINT
     465    printf("\n");
     466#endif
     467    return 0.0;
     468}
     469// Print what would happen
     470void
     471CbcCliqueBranchingObject::print()
     472{
     473    int iWord;
     474    int numberMembers = clique_->numberMembers();
     475    const int * which = clique_->members();
     476    const int * integerVariables = model_->integerVariable();
     477    int numberWords = (numberMembers + 31) >> 5;
     478    // *** for way - up means fix all those in down section
     479    if (way_ < 0) {
     480        printf("Clique - Down Fix ");
     481        for (iWord = 0; iWord < numberWords; iWord++) {
     482            int i;
     483            for (i = 0; i < 32; i++) {
     484                unsigned int k = 1 << i;
     485                if ((upMask_[iWord]&k) != 0) {
     486                    int iColumn = which[i+32*iWord];
     487                    printf("%d ", integerVariables[iColumn]);
     488                }
     489            }
     490        }
     491    } else {
     492        printf("Clique - Up Fix ");
     493        for (iWord = 0; iWord < numberWords; iWord++) {
     494            int i;
     495            for (i = 0; i < 32; i++) {
     496                unsigned int k = 1 << i;
     497                if ((downMask_[iWord]&k) != 0) {
     498                    int iColumn = which[i+32*iWord];
     499                    printf("%d ", integerVariables[iColumn]);
     500                }
     501            }
     502        }
     503    }
     504    printf("\n");
     505}
     506
     507static inline int
     508CbcCompareCliques(const CbcClique* cl0, const CbcClique* cl1)
     509{
     510    if (cl0->cliqueType() < cl1->cliqueType()) {
     511        return -1;
     512    }
     513    if (cl0->cliqueType() > cl1->cliqueType()) {
     514        return 1;
     515    }
     516    if (cl0->numberMembers() != cl1->numberMembers()) {
     517        return cl0->numberMembers() - cl1->numberMembers();
     518    }
     519    if (cl0->numberNonSOSMembers() != cl1->numberNonSOSMembers()) {
     520        return cl0->numberNonSOSMembers() - cl1->numberNonSOSMembers();
     521    }
     522    return memcmp(cl0->members(), cl1->members(),
     523                  cl0->numberMembers() * sizeof(int));
     524}
     525
     526/** Compare the original object of \c this with the original object of \c
     527    brObj. Assumes that there is an ordering of the original objects.
     528    This method should be invoked only if \c this and brObj are of the same
     529    type.
     530    Return negative/0/positive depending on whether \c this is
     531    smaller/same/larger than the argument.
     532*/
     533int
     534CbcCliqueBranchingObject::compareOriginalObject
     535(const CbcBranchingObject* brObj) const
     536{
     537    const CbcCliqueBranchingObject* br =
     538        dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
     539    assert(br);
     540    return CbcCompareCliques(clique_, br->clique_);
     541}
     542
     543/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     544    same type and must have the same original object, but they may have
     545    different feasible regions.
     546    Return the appropriate CbcRangeCompare value (first argument being the
     547    sub/superset if that's the case). In case of overlap (and if \c
     548    replaceIfOverlap is true) replace the current branching object with one
     549    whose feasible region is the overlap.
     550*/
     551CbcRangeCompare
     552CbcCliqueBranchingObject::compareBranchingObject
     553(const CbcBranchingObject* brObj, const bool /*replaceIfOverlap*/)
     554{
     555    const CbcCliqueBranchingObject* br =
     556        dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
     557    assert(br);
     558    unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
     559    const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
     560    const CoinUInt64 cl0 =
     561        (static_cast<CoinUInt64>(thisMask[0]) << 32) | thisMask[1];
     562    const CoinUInt64 cl1 =
     563        (static_cast<CoinUInt64>(otherMask[0]) << 32) | otherMask[1];
     564    if (cl0 == cl1) {
     565        return CbcRangeSame;
     566    }
     567    const CoinUInt64 cl_intersection = (cl0 & cl1);
     568    if (cl_intersection == cl0) {
     569        return CbcRangeSuperset;
     570    }
     571    if (cl_intersection == cl1) {
     572        return CbcRangeSubset;
     573    }
     574    const CoinUInt64 cl_xor = (cl0 ^ cl1);
     575    if (cl_intersection == 0 && cl_xor == 0) {
     576        return CbcRangeDisjoint;
     577    }
     578    const CoinUInt64 cl_union = (cl0 | cl1);
     579    thisMask[0] = static_cast<unsigned int>(cl_union >> 32);
     580    thisMask[1] = static_cast<unsigned int>(cl_union & 0xffffffff);
     581    return CbcRangeOverlap;
     582}
     583
     584//##############################################################################
     585
     586// Default Constructor
     587CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject()
     588        : CbcBranchingObject()
     589{
     590    clique_ = NULL;
     591    downMask_ = NULL;
     592    upMask_ = NULL;
     593}
     594
     595// Useful constructor
     596CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject (CbcModel * model,
     597        const CbcClique * clique,
     598        int way ,
     599        int numberOnDownSide, const int * down,
     600        int numberOnUpSide, const int * up)
     601        : CbcBranchingObject(model, clique->id(), way, 0.5)
     602{
     603    clique_ = clique;
     604    int numberMembers = clique_->numberMembers();
     605    int numberWords = (numberMembers + 31) >> 5;
     606    downMask_ = new unsigned int [numberWords];
     607    upMask_ = new unsigned int [numberWords];
     608    memset(downMask_, 0, numberWords*sizeof(unsigned int));
     609    memset(upMask_, 0, numberWords*sizeof(unsigned int));
     610    int i;
     611    for (i = 0; i < numberOnDownSide; i++) {
     612        int sequence = down[i];
     613        int iWord = sequence >> 5;
     614        int iBit = sequence - 32 * iWord;
     615        unsigned int k = 1 << iBit;
     616        downMask_[iWord] |= k;
     617    }
     618    for (i = 0; i < numberOnUpSide; i++) {
     619        int sequence = up[i];
     620        int iWord = sequence >> 5;
     621        int iBit = sequence - 32 * iWord;
     622        unsigned int k = 1 << iBit;
     623        upMask_[iWord] |= k;
     624    }
     625}
     626
     627// Copy constructor
     628CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject & rhs) : CbcBranchingObject(rhs)
     629{
     630    clique_ = rhs.clique_;
     631    if (rhs.downMask_) {
     632        int numberMembers = clique_->numberMembers();
     633        int numberWords = (numberMembers + 31) >> 5;
     634        downMask_ = new unsigned int [numberWords];
     635        memcpy(downMask_, rhs.downMask_, numberWords*sizeof(unsigned int));
     636        upMask_ = new unsigned int [numberWords];
     637        memcpy(upMask_, rhs.upMask_, numberWords*sizeof(unsigned int));
     638    } else {
     639        downMask_ = NULL;
     640        upMask_ = NULL;
     641    }
     642}
     643
     644// Assignment operator
     645CbcLongCliqueBranchingObject &
     646CbcLongCliqueBranchingObject::operator=( const CbcLongCliqueBranchingObject & rhs)
     647{
     648    if (this != &rhs) {
     649        CbcBranchingObject::operator=(rhs);
     650        clique_ = rhs.clique_;
     651        delete [] downMask_;
     652        delete [] upMask_;
     653        if (rhs.downMask_) {
     654            int numberMembers = clique_->numberMembers();
     655            int numberWords = (numberMembers + 31) >> 5;
     656            downMask_ = new unsigned int [numberWords];
     657            memcpy(downMask_, rhs.downMask_, numberWords*sizeof(unsigned int));
     658            upMask_ = new unsigned int [numberWords];
     659            memcpy(upMask_, rhs.upMask_, numberWords*sizeof(unsigned int));
     660        } else {
     661            downMask_ = NULL;
     662            upMask_ = NULL;
     663        }
     664    }
     665    return *this;
     666}
     667CbcBranchingObject *
     668CbcLongCliqueBranchingObject::clone() const
     669{
     670    return (new CbcLongCliqueBranchingObject(*this));
     671}
     672
     673
     674// Destructor
     675CbcLongCliqueBranchingObject::~CbcLongCliqueBranchingObject ()
     676{
     677    delete [] downMask_;
     678    delete [] upMask_;
     679}
     680double
     681CbcLongCliqueBranchingObject::branch()
     682{
     683    decrementNumberBranchesLeft();
     684    int iWord;
     685    int numberMembers = clique_->numberMembers();
     686    const int * which = clique_->members();
     687    const int * integerVariables = model_->integerVariable();
     688    int numberWords = (numberMembers + 31) >> 5;
     689    // *** for way - up means fix all those in down section
     690    if (way_ < 0) {
     691#ifdef FULL_PRINT
     692        printf("Down Fix ");
     693#endif
     694        for (iWord = 0; iWord < numberWords; iWord++) {
     695            int i;
     696            for (i = 0; i < 32; i++) {
     697                unsigned int k = 1 << i;
     698                if ((upMask_[iWord]&k) != 0) {
     699                    int iColumn = which[i+32*iWord];
     700#ifdef FULL_PRINT
     701                    printf("%d ", i + 32*iWord);
     702#endif
     703                    // fix weak way
     704                    if (clique_->type(i + 32*iWord))
     705                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
     706                    else
     707                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
     708                }
     709            }
     710        }
     711        way_ = 1;         // Swap direction
     712    } else {
     713#ifdef FULL_PRINT
     714        printf("Up Fix ");
     715#endif
     716        for (iWord = 0; iWord < numberWords; iWord++) {
     717            int i;
     718            for (i = 0; i < 32; i++) {
     719                unsigned int k = 1 << i;
     720                if ((downMask_[iWord]&k) != 0) {
     721                    int iColumn = which[i+32*iWord];
     722#ifdef FULL_PRINT
     723                    printf("%d ", i + 32*iWord);
     724#endif
     725                    // fix weak way
     726                    if (clique_->type(i + 32*iWord))
     727                        model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
     728                    else
     729                        model_->solver()->setColLower(integerVariables[iColumn], 1.0);
     730                }
     731            }
     732        }
     733        way_ = -1;        // Swap direction
     734    }
     735#ifdef FULL_PRINT
     736    printf("\n");
     737#endif
     738    return 0.0;
     739}
     740void
     741CbcLongCliqueBranchingObject::print()
     742{
     743    int iWord;
     744    int numberMembers = clique_->numberMembers();
     745    const int * which = clique_->members();
     746    const int * integerVariables = model_->integerVariable();
     747    int numberWords = (numberMembers + 31) >> 5;
     748    // *** for way - up means fix all those in down section
     749    if (way_ < 0) {
     750        printf("Clique - Down Fix ");
     751        for (iWord = 0; iWord < numberWords; iWord++) {
     752            int i;
     753            for (i = 0; i < 32; i++) {
     754                unsigned int k = 1 << i;
     755                if ((upMask_[iWord]&k) != 0) {
     756                    int iColumn = which[i+32*iWord];
     757                    printf("%d ", integerVariables[iColumn]);
     758                }
     759            }
     760        }
     761    } else {
     762        printf("Clique - Up Fix ");
     763        for (iWord = 0; iWord < numberWords; iWord++) {
     764            int i;
     765            for (i = 0; i < 32; i++) {
     766                unsigned int k = 1 << i;
     767                if ((downMask_[iWord]&k) != 0) {
     768                    int iColumn = which[i+32*iWord];
     769                    printf("%d ", integerVariables[iColumn]);
     770                }
     771            }
     772        }
     773    }
     774    printf("\n");
     775}
     776
     777/** Compare the original object of \c this with the original object of \c
     778    brObj. Assumes that there is an ordering of the original objects.
     779    This method should be invoked only if \c this and brObj are of the same
     780    type.
     781    Return negative/0/positive depending on whether \c this is
     782    smaller/same/larger than the argument.
     783*/
     784int
     785CbcLongCliqueBranchingObject::compareOriginalObject
     786(const CbcBranchingObject* brObj) const
     787{
     788    const CbcLongCliqueBranchingObject* br =
     789        dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
     790    assert(br);
     791    return CbcCompareCliques(clique_, br->clique_);
     792}
     793
     794/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     795    same type and must have the same original object, but they may have
     796    different feasible regions.
     797    Return the appropriate CbcRangeCompare value (first argument being the
     798    sub/superset if that's the case). In case of overlap (and if \c
     799    replaceIfOverlap is true) replace the current branching object with one
     800    whose feasible region is the overlap.
     801*/
     802CbcRangeCompare
     803CbcLongCliqueBranchingObject::compareBranchingObject
     804(const CbcBranchingObject* brObj, const bool /*replaceIfOverlap*/)
     805{
     806    const CbcLongCliqueBranchingObject* br =
     807        dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
     808    assert(br);
     809    const int numberMembers = clique_->numberMembers();
     810    const int numberWords = (numberMembers + 31) >> 5;
     811    unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
     812    const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
     813
     814    if (memcmp(thisMask, otherMask, numberWords * sizeof(unsigned int)) == 0) {
     815        return CbcRangeSame;
     816    }
     817    bool canBeSuperset = true;
     818    bool canBeSubset = true;
     819    int i;
     820    for (i = numberWords - 1; i >= 0 && (canBeSuperset || canBeSubset); --i) {
     821        const unsigned int both = (thisMask[i] & otherMask[i]);
     822        canBeSuperset &= (both == thisMask[i]);
     823        canBeSubset &= (both == otherMask[i]);
     824    }
     825    if (canBeSuperset) {
     826        return CbcRangeSuperset;
     827    }
     828    if (canBeSubset) {
     829        return CbcRangeSubset;
     830    }
     831
     832    for (i = numberWords - 1; i >= 0; --i) {
     833        if ((thisMask[i] ^ otherMask[i]) != 0) {
     834            break;
     835        }
     836    }
     837    if (i == -1) { // complement
     838        return CbcRangeDisjoint;
     839    }
     840    // must be overlap
     841    for (i = numberWords - 1; i >= 0; --i) {
     842        thisMask[i] |= otherMask[i];
     843    }
     844    return CbcRangeOverlap;
     845}
Note: See TracChangeset for help on using the changeset viewer.