Changeset 1350 for branches/sandbox


Ignore:
Timestamp:
Dec 4, 2009 10:01:00 AM (10 years ago)
Author:
EdwinStraver
Message:

Combined CbcSOS with CbcSOSBranchingObject
Combined CbcNWay with CbcNWayBranchingObject
Combined CbcFollowOn? with CbcFixingBranchingObject?

Location:
branches/sandbox/Cbc
Files:
6 deleted
10 edited

Legend:

Unmodified
Added
Removed
  • branches/sandbox/Cbc/MSVisualStudio/v9/libCbc/libCbc.vcproj

    r1347 r1350  
    456456                        </File>
    457457                        <File
    458                                 RelativePath="..\..\..\src\CbcFixingBranchingObject.cpp"
    459                                 >
    460                         </File>
    461                         <File
    462458                                RelativePath="..\..\..\src\CbcFixVariable.cpp"
    463459                                >
     
    908904                        </File>
    909905                        <File
    910                                 RelativePath="..\..\..\src\CbcNWayBranchingObject.cpp"
    911                                 >
    912                         </File>
    913                         <File
    914906                                RelativePath="..\..\..\src\CbcObject.cpp"
    915907                                >
     
    966958                        <File
    967959                                RelativePath="..\..\..\src\CbcSOS.cpp"
    968                                 >
    969                         </File>
    970                         <File
    971                                 RelativePath="..\..\..\src\CbcSOSBranchingObject.cpp"
    972960                                >
    973961                        </File>
     
    12181206                        </File>
    12191207                        <File
    1220                                 RelativePath="..\..\..\src\CbcFixingBranchingObject.hpp"
    1221                                 >
    1222                         </File>
    1223                         <File
    12241208                                RelativePath="..\..\..\src\CbcFixVariable.hpp"
    12251209                                >
     
    13301314                        </File>
    13311315                        <File
    1332                                 RelativePath="..\..\..\src\CbcNWayBranchingObject.hpp"
    1333                                 >
    1334                         </File>
    1335                         <File
    13361316                                RelativePath="..\..\..\src\CbcObject.hpp"
    13371317                                >
     
    13671347                        <File
    13681348                                RelativePath="..\..\..\src\CbcSOS.hpp"
    1369                                 >
    1370                         </File>
    1371                         <File
    1372                                 RelativePath="..\..\..\src\CbcSOSBranchingObject.hpp"
    13731349                                >
    13741350                        </File>
  • branches/sandbox/Cbc/src/CbcBranchActual.hpp

    r1347 r1350  
    1212#include "CbcNWay.hpp"
    1313#include "CbcSimpleIntegerPseudoCost.hpp"
    14 #include "CbcSOSBranchingObject.hpp"
    15 #include "CbcNWayBranchingObject.hpp"
    1614#include "CbcBranchDefaultDecision.hpp"
    1715#include "CbcFollowOn.hpp"
    18 #include "CbcFixingBranchingObject.hpp"
    1916#include "CbcFixVariable.hpp"
    2017#include "CbcDummyBranchingObject.hpp"
  • branches/sandbox/Cbc/src/CbcFollowOn.cpp

    r1293 r1350  
    357357    return branch;
    358358}
     359
     360//##############################################################################
     361
     362// Default Constructor
     363CbcFixingBranchingObject::CbcFixingBranchingObject()
     364        : CbcBranchingObject()
     365{
     366    numberDown_ = 0;
     367    numberUp_ = 0;
     368    downList_ = NULL;
     369    upList_ = NULL;
     370}
     371
     372// Useful constructor
     373CbcFixingBranchingObject::CbcFixingBranchingObject (CbcModel * model,
     374        int way ,
     375        int numberOnDownSide, const int * down,
     376        int numberOnUpSide, const int * up)
     377        : CbcBranchingObject(model, 0, way, 0.5)
     378{
     379    numberDown_ = numberOnDownSide;
     380    numberUp_ = numberOnUpSide;
     381    downList_ = CoinCopyOfArray(down, numberDown_);
     382    upList_ = CoinCopyOfArray(up, numberUp_);
     383}
     384
     385// Copy constructor
     386CbcFixingBranchingObject::CbcFixingBranchingObject ( const CbcFixingBranchingObject & rhs) : CbcBranchingObject(rhs)
     387{
     388    numberDown_ = rhs.numberDown_;
     389    numberUp_ = rhs.numberUp_;
     390    downList_ = CoinCopyOfArray(rhs.downList_, numberDown_);
     391    upList_ = CoinCopyOfArray(rhs.upList_, numberUp_);
     392}
     393
     394// Assignment operator
     395CbcFixingBranchingObject &
     396CbcFixingBranchingObject::operator=( const CbcFixingBranchingObject & rhs)
     397{
     398    if (this != &rhs) {
     399        CbcBranchingObject::operator=(rhs);
     400        delete [] downList_;
     401        delete [] upList_;
     402        numberDown_ = rhs.numberDown_;
     403        numberUp_ = rhs.numberUp_;
     404        downList_ = CoinCopyOfArray(rhs.downList_, numberDown_);
     405        upList_ = CoinCopyOfArray(rhs.upList_, numberUp_);
     406    }
     407    return *this;
     408}
     409CbcBranchingObject *
     410CbcFixingBranchingObject::clone() const
     411{
     412    return (new CbcFixingBranchingObject(*this));
     413}
     414
     415
     416// Destructor
     417CbcFixingBranchingObject::~CbcFixingBranchingObject ()
     418{
     419    delete [] downList_;
     420    delete [] upList_;
     421}
     422double
     423CbcFixingBranchingObject::branch()
     424{
     425    decrementNumberBranchesLeft();
     426    OsiSolverInterface * solver = model_->solver();
     427    const double * columnLower = solver->getColLower();
     428    int i;
     429    // *** for way - up means fix all those in up section
     430    if (way_ < 0) {
     431#ifdef FULL_PRINT
     432        printf("Down Fix ");
     433#endif
     434        //printf("Down Fix %d\n",numberDown_);
     435        for (i = 0; i < numberDown_; i++) {
     436            int iColumn = downList_[i];
     437            model_->solver()->setColUpper(iColumn, columnLower[iColumn]);
     438#ifdef FULL_PRINT
     439            printf("Setting bound on %d to lower bound\n", iColumn);
     440#endif
     441        }
     442        way_ = 1;         // Swap direction
     443    } else {
     444#ifdef FULL_PRINT
     445        printf("Up Fix ");
     446#endif
     447        //printf("Up Fix %d\n",numberUp_);
     448        for (i = 0; i < numberUp_; i++) {
     449            int iColumn = upList_[i];
     450            model_->solver()->setColUpper(iColumn, columnLower[iColumn]);
     451#ifdef FULL_PRINT
     452            printf("Setting bound on %d to lower bound\n", iColumn);
     453#endif
     454        }
     455        way_ = -1;        // Swap direction
     456    }
     457#ifdef FULL_PRINT
     458    printf("\n");
     459#endif
     460    return 0.0;
     461}
     462void
     463CbcFixingBranchingObject::print()
     464{
     465    int i;
     466    // *** for way - up means fix all those in up section
     467    if (way_ < 0) {
     468        printf("Down Fix ");
     469        for (i = 0; i < numberDown_; i++) {
     470            int iColumn = downList_[i];
     471            printf("%d ", iColumn);
     472        }
     473    } else {
     474        printf("Up Fix ");
     475        for (i = 0; i < numberUp_; i++) {
     476            int iColumn = upList_[i];
     477            printf("%d ", iColumn);
     478        }
     479    }
     480    printf("\n");
     481}
     482
     483/** Compare the original object of \c this with the original object of \c
     484    brObj. Assumes that there is an ordering of the original objects.
     485    This method should be invoked only if \c this and brObj are of the same
     486    type.
     487    Return negative/0/positive depending on whether \c this is
     488    smaller/same/larger than the argument.
     489*/
     490int
     491CbcFixingBranchingObject::compareOriginalObject
     492(const CbcBranchingObject* /*brObj*/) const
     493{
     494    throw("must implement");
     495}
     496
     497/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     498    same type and must have the same original object, but they may have
     499    different feasible regions.
     500    Return the appropriate CbcRangeCompare value (first argument being the
     501    sub/superset if that's the case). In case of overlap (and if \c
     502    replaceIfOverlap is true) replace the current branching object with one
     503    whose feasible region is the overlap.
     504   */
     505CbcRangeCompare
     506CbcFixingBranchingObject::compareBranchingObject
     507(const CbcBranchingObject* /*brObj*/, const bool /*replaceIfOverlap*/)
     508{
     509#if 0 //ndef NDEBUG
     510    const CbcFixingBranchingObject* br =
     511        dynamic_cast<const CbcFixingBranchingObject*>(brObj);
     512    assert(br);
     513#endif
     514    // If two FixingBranchingObject's have the same base object then it's pretty
     515    // much guaranteed
     516    throw("must implement");
     517}
     518
     519//##############################################################################
  • branches/sandbox/Cbc/src/CbcFollowOn.hpp

    r1293 r1350  
    6161};
    6262
     63/** General Branching Object class.
     64    Each way fixes some variables to lower bound
     65 */
     66class CbcFixingBranchingObject : public CbcBranchingObject {
     67
     68public:
     69
     70    // Default Constructor
     71    CbcFixingBranchingObject ();
     72
     73    // Useful constructor
     74    CbcFixingBranchingObject (CbcModel * model,
     75                              int way,
     76                              int numberOnDownSide, const int * down,
     77                              int numberOnUpSide, const int * up);
     78
     79    // Copy constructor
     80    CbcFixingBranchingObject ( const CbcFixingBranchingObject &);
     81
     82    // Assignment operator
     83    CbcFixingBranchingObject & operator=( const CbcFixingBranchingObject& rhs);
     84
     85    /// Clone
     86    virtual CbcBranchingObject * clone() const;
     87
     88    // Destructor
     89    virtual ~CbcFixingBranchingObject ();
     90
     91    using CbcBranchingObject::branch ;
     92    /// Does next branch and updates state
     93    virtual double branch();
     94
     95#if 0
     96    // No need to override. Default works fine.
     97    /** Reset every information so that the branching object appears to point to
     98        the previous child. This method does not need to modify anything in any
     99        solver. */
     100    virtual void previousBranch();
    63101#endif
     102
     103    using CbcBranchingObject::print ;
     104    /** \brief Print something about branch - only if log level high
     105    */
     106    virtual void print();
     107
     108    /** Return the type (an integer identifier) of \c this */
     109    virtual int type() const {
     110        return 106;
     111    }
     112
     113    /** Compare the original object of \c this with the original object of \c
     114        brObj. Assumes that there is an ordering of the original objects.
     115        This method should be invoked only if \c this and brObj are of the same
     116        type.
     117        Return negative/0/positive depending on whether \c this is
     118        smaller/same/larger than the argument.
     119    */
     120    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     121
     122    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     123        same type and must have the same original object, but they may have
     124        different feasible regions.
     125        Return the appropriate CbcRangeCompare value (first argument being the
     126        sub/superset if that's the case). In case of overlap (and if \c
     127        replaceIfOverlap is true) replace the current branching object with one
     128        whose feasible region is the overlap.
     129     */
     130    virtual CbcRangeCompare compareBranchingObject
     131    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     132
     133private:
     134    /// data
     135    /// Number on down list
     136    int numberDown_;
     137    /// Number on up list
     138    int numberUp_;
     139    /// downList - variables to fix to lb on down branch
     140    int * downList_;
     141    /// upList - variables to fix to lb on up branch
     142    int * upList_;
     143};
     144
     145#endif
  • branches/sandbox/Cbc/src/CbcNWay.cpp

    r1293 r1350  
    267267    return branch;
    268268}
     269
     270// Default Constructor
     271CbcNWayBranchingObject::CbcNWayBranchingObject()
     272        : CbcBranchingObject()
     273{
     274    order_ = NULL;
     275    object_ = NULL;
     276    numberInSet_ = 0;
     277    way_ = 0;
     278}
     279
     280// Useful constructor
     281CbcNWayBranchingObject::CbcNWayBranchingObject (CbcModel * model,
     282        const CbcNWay * nway,
     283        int number, const int * order)
     284        : CbcBranchingObject(model, nway->id(), -1, 0.5)
     285{
     286    numberBranches_ = number;
     287    order_ = new int [number];
     288    object_ = nway;
     289    numberInSet_ = number;
     290    memcpy(order_, order, number*sizeof(int));
     291}
     292
     293// Copy constructor
     294CbcNWayBranchingObject::CbcNWayBranchingObject ( const CbcNWayBranchingObject & rhs) : CbcBranchingObject(rhs)
     295{
     296    numberInSet_ = rhs.numberInSet_;
     297    object_ = rhs.object_;
     298    if (numberInSet_) {
     299        order_ = new int [numberInSet_];
     300        memcpy(order_, rhs.order_, numberInSet_*sizeof(int));
     301    } else {
     302        order_ = NULL;
     303    }
     304}
     305
     306// Assignment operator
     307CbcNWayBranchingObject &
     308CbcNWayBranchingObject::operator=( const CbcNWayBranchingObject & rhs)
     309{
     310    if (this != &rhs) {
     311        CbcBranchingObject::operator=(rhs);
     312        object_ = rhs.object_;
     313        delete [] order_;
     314        numberInSet_ = rhs.numberInSet_;
     315        if (numberInSet_) {
     316            order_ = new int [numberInSet_];
     317            memcpy(order_, rhs.order_, numberInSet_*sizeof(int));
     318        } else {
     319            order_ = NULL;
     320        }
     321    }
     322    return *this;
     323}
     324CbcBranchingObject *
     325CbcNWayBranchingObject::clone() const
     326{
     327    return (new CbcNWayBranchingObject(*this));
     328}
     329
     330
     331// Destructor
     332CbcNWayBranchingObject::~CbcNWayBranchingObject ()
     333{
     334    delete [] order_;
     335}
     336double
     337CbcNWayBranchingObject::branch()
     338{
     339    int which = branchIndex_;
     340    branchIndex_++;
     341    assert (numberBranchesLeft() >= 0);
     342    if (which == 0) {
     343        // first branch so way_ may mean something
     344        assert (way_ == -1 || way_ == 1);
     345        if (way_ == -1)
     346            which++;
     347    } else if (which == 1) {
     348        // second branch so way_ may mean something
     349        assert (way_ == -1 || way_ == 1);
     350        if (way_ == -1)
     351            which--;
     352        // switch way off
     353        way_ = 0;
     354    }
     355    const double * lower = model_->solver()->getColLower();
     356    const double * upper = model_->solver()->getColUpper();
     357    const int * members = object_->members();
     358    for (int j = 0; j < numberInSet_; j++) {
     359        int iSequence = order_[j];
     360        int iColumn = members[iSequence];
     361        if (j != which) {
     362            model_->solver()->setColUpper(iColumn, lower[iColumn]);
     363            //model_->solver()->setColLower(iColumn,lower[iColumn]);
     364            assert (lower[iColumn] > -1.0e20);
     365            // apply any consequences
     366            object_->applyConsequence(iSequence, -9999);
     367        } else {
     368            model_->solver()->setColLower(iColumn, upper[iColumn]);
     369            //model_->solver()->setColUpper(iColumn,upper[iColumn]);
     370#ifdef FULL_PRINT
     371            printf("Up Fix %d to %g\n", iColumn, upper[iColumn]);
     372#endif
     373            assert (upper[iColumn] < 1.0e20);
     374            // apply any consequences
     375            object_->applyConsequence(iSequence, 9999);
     376        }
     377    }
     378    return 0.0;
     379}
     380void
     381CbcNWayBranchingObject::print()
     382{
     383    printf("NWay - Up Fix ");
     384    const int * members = object_->members();
     385    for (int j = 0; j < way_; j++) {
     386        int iColumn = members[order_[j]];
     387        printf("%d ", iColumn);
     388    }
     389    printf("\n");
     390}
     391
     392/** Compare the original object of \c this with the original object of \c
     393    brObj. Assumes that there is an ordering of the original objects.
     394    This method should be invoked only if \c this and brObj are of the same
     395    type.
     396    Return negative/0/positive depending on whether \c this is
     397    smaller/same/larger than the argument.
     398*/
     399int
     400CbcNWayBranchingObject::compareOriginalObject
     401(const CbcBranchingObject* /*brObj*/) const
     402{
     403    throw("must implement");
     404}
     405
     406/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     407    same type and must have the same original object, but they may have
     408    different feasible regions.
     409    Return the appropriate CbcRangeCompare value (first argument being the
     410    sub/superset if that's the case). In case of overlap (and if \c
     411    replaceIfOverlap is true) replace the current branching object with one
     412    whose feasible region is the overlap.
     413*/
     414CbcRangeCompare
     415CbcNWayBranchingObject::compareBranchingObject
     416(const CbcBranchingObject* /*brObj*/, const bool /*replaceIfOverlap*/)
     417{
     418    throw("must implement");
     419}
  • branches/sandbox/Cbc/src/CbcNWay.hpp

    r1293 r1350  
    7070    CbcConsequence ** consequence_;
    7171};
     72/** N way branching Object class.
     73    Variable is number of set.
     74 */
     75class CbcNWayBranchingObject : public CbcBranchingObject {
     76
     77public:
     78
     79    // Default Constructor
     80    CbcNWayBranchingObject ();
     81
     82    /** Useful constructor - order had matrix indices
     83        way_ -1 corresponds to setting first, +1 to second, +3 etc.
     84        this is so -1 and +1 have similarity to normal
     85    */
     86    CbcNWayBranchingObject (CbcModel * model,  const CbcNWay * nway,
     87                            int numberBranches, const int * order);
     88
     89    // Copy constructor
     90    CbcNWayBranchingObject ( const CbcNWayBranchingObject &);
     91
     92    // Assignment operator
     93    CbcNWayBranchingObject & operator=( const CbcNWayBranchingObject& rhs);
     94
     95    /// Clone
     96    virtual CbcBranchingObject * clone() const;
     97
     98    // Destructor
     99    virtual ~CbcNWayBranchingObject ();
     100
     101    using CbcBranchingObject::branch ;
     102    /// Does next branch and updates state
     103    virtual double branch();
     104
     105#if 0
     106    // FIXME: what do we need to do here?
     107    /** Reset every information so that the branching object appears to point to
     108        the previous child. This method does not need to modify anything in any
     109        solver. */
     110    virtual void previousBranch();
    72111#endif
     112
     113    using CbcBranchingObject::print ;
     114    /** \brief Print something about branch - only if log level high
     115    */
     116    virtual void print();
     117    /** The number of branch arms created for this branching object
     118    */
     119    virtual int numberBranches() const {
     120        return numberInSet_;
     121    }
     122    /// Is this a two way object (-1 down, +1 up)
     123    virtual bool twoWay() const {
     124        return false;
     125    }
     126
     127    /** Return the type (an integer identifier) of \c this */
     128    virtual int type() const {
     129        return 105;
     130    }
     131
     132    /** Compare the original object of \c this with the original object of \c
     133        brObj. Assumes that there is an ordering of the original objects.
     134        This method should be invoked only if \c this and brObj are of the same
     135        type.
     136        Return negative/0/positive depending on whether \c this is
     137        smaller/same/larger than the argument.
     138    */
     139    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     140
     141    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     142        same type and must have the same original object, but they may have
     143        different feasible regions.
     144        Return the appropriate CbcRangeCompare value (first argument being the
     145        sub/superset if that's the case). In case of overlap (and if \c
     146        replaceIfOverlap is true) replace the current branching object with one
     147        whose feasible region is the overlap.
     148     */
     149    virtual CbcRangeCompare compareBranchingObject
     150    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     151
     152private:
     153    /// order of branching - points back to CbcNWay
     154    int * order_;
     155    /// Points back to object
     156    const CbcNWay * object_;
     157    /// Number in set
     158    int numberInSet_;
     159};
     160#endif
  • branches/sandbox/Cbc/src/CbcSOS.cpp

    r1293 r1350  
    691691    return obj;
    692692}
     693
     694// Default Constructor
     695CbcSOSBranchingObject::CbcSOSBranchingObject()
     696        : CbcBranchingObject(),
     697        firstNonzero_(-1),
     698        lastNonzero_(-1)
     699{
     700    set_ = NULL;
     701    separator_ = 0.0;
     702}
     703
     704// Useful constructor
     705CbcSOSBranchingObject::CbcSOSBranchingObject (CbcModel * model,
     706        const CbcSOS * set,
     707        int way ,
     708        double separator)
     709        : CbcBranchingObject(model, set->id(), way, 0.5)
     710{
     711    set_ = set;
     712    separator_ = separator;
     713    computeNonzeroRange();
     714}
     715
     716// Copy constructor
     717CbcSOSBranchingObject::CbcSOSBranchingObject (const CbcSOSBranchingObject & rhs)
     718        : CbcBranchingObject(rhs),
     719        firstNonzero_(rhs.firstNonzero_),
     720        lastNonzero_(rhs.lastNonzero_)
     721{
     722    set_ = rhs.set_;
     723    separator_ = rhs.separator_;
     724}
     725
     726// Assignment operator
     727CbcSOSBranchingObject &
     728CbcSOSBranchingObject::operator=( const CbcSOSBranchingObject & rhs)
     729{
     730    if (this != &rhs) {
     731        CbcBranchingObject::operator=(rhs);
     732        set_ = rhs.set_;
     733        separator_ = rhs.separator_;
     734        firstNonzero_ = rhs.firstNonzero_;
     735        lastNonzero_ = rhs.lastNonzero_;
     736    }
     737    return *this;
     738}
     739CbcBranchingObject *
     740CbcSOSBranchingObject::clone() const
     741{
     742    return (new CbcSOSBranchingObject(*this));
     743}
     744
     745
     746// Destructor
     747CbcSOSBranchingObject::~CbcSOSBranchingObject ()
     748{
     749}
     750
     751void
     752CbcSOSBranchingObject::computeNonzeroRange()
     753{
     754    const int numberMembers = set_->numberMembers();
     755    const double * weights = set_->weights();
     756    int i = 0;
     757    if (way_ < 0) {
     758        for ( i = 0; i < numberMembers; i++) {
     759            if (weights[i] > separator_)
     760                break;
     761        }
     762        assert (i < numberMembers);
     763        firstNonzero_ = 0;
     764        lastNonzero_ = i;
     765    } else {
     766        for ( i = 0; i < numberMembers; i++) {
     767            if (weights[i] >= separator_)
     768                break;
     769        }
     770        assert (i < numberMembers);
     771        firstNonzero_ = i;
     772        lastNonzero_ = numberMembers;
     773    }
     774}
     775
     776double
     777CbcSOSBranchingObject::branch()
     778{
     779    decrementNumberBranchesLeft();
     780    int numberMembers = set_->numberMembers();
     781    const int * which = set_->members();
     782    const double * weights = set_->weights();
     783    OsiSolverInterface * solver = model_->solver();
     784    //const double * lower = solver->getColLower();
     785    //const double * upper = solver->getColUpper();
     786    // *** for way - up means fix all those in down section
     787    if (way_ < 0) {
     788        int i;
     789        for ( i = 0; i < numberMembers; i++) {
     790            if (weights[i] > separator_)
     791                break;
     792        }
     793        assert (i < numberMembers);
     794        for (; i < numberMembers; i++)
     795            solver->setColUpper(which[i], 0.0);
     796        way_ = 1;         // Swap direction
     797    } else {
     798        int i;
     799        for ( i = 0; i < numberMembers; i++) {
     800            if (weights[i] >= separator_)
     801                break;
     802            else
     803                solver->setColUpper(which[i], 0.0);
     804        }
     805        assert (i < numberMembers);
     806        way_ = -1;        // Swap direction
     807    }
     808    computeNonzeroRange();
     809    return 0.0;
     810}
     811/* Update bounds in solver as in 'branch' and update given bounds.
     812   branchState is -1 for 'down' +1 for 'up' */
     813void
     814CbcSOSBranchingObject::fix(OsiSolverInterface * solver,
     815                           double * /*lower*/, double * upper,
     816                           int branchState) const
     817{
     818    int numberMembers = set_->numberMembers();
     819    const int * which = set_->members();
     820    const double * weights = set_->weights();
     821    //const double * lower = solver->getColLower();
     822    //const double * upper = solver->getColUpper();
     823    // *** for way - up means fix all those in down section
     824    if (branchState < 0) {
     825        int i;
     826        for ( i = 0; i < numberMembers; i++) {
     827            if (weights[i] > separator_)
     828                break;
     829        }
     830        assert (i < numberMembers);
     831        for (; i < numberMembers; i++) {
     832            solver->setColUpper(which[i], 0.0);
     833            upper[which[i]] = 0.0;
     834        }
     835    } else {
     836        int i;
     837        for ( i = 0; i < numberMembers; i++) {
     838            if (weights[i] >= separator_) {
     839                break;
     840            } else {
     841                solver->setColUpper(which[i], 0.0);
     842                upper[which[i]] = 0.0;
     843            }
     844        }
     845        assert (i < numberMembers);
     846    }
     847}
     848// Print what would happen
     849void
     850CbcSOSBranchingObject::print()
     851{
     852    int numberMembers = set_->numberMembers();
     853    const int * which = set_->members();
     854    const double * weights = set_->weights();
     855    OsiSolverInterface * solver = model_->solver();
     856    //const double * lower = solver->getColLower();
     857    const double * upper = solver->getColUpper();
     858    int first = numberMembers;
     859    int last = -1;
     860    int numberFixed = 0;
     861    int numberOther = 0;
     862    int i;
     863    for ( i = 0; i < numberMembers; i++) {
     864        double bound = upper[which[i]];
     865        if (bound) {
     866            first = CoinMin(first, i);
     867            last = CoinMax(last, i);
     868        }
     869    }
     870    // *** for way - up means fix all those in down section
     871    if (way_ < 0) {
     872        printf("SOS Down");
     873        for ( i = 0; i < numberMembers; i++) {
     874            double bound = upper[which[i]];
     875            if (weights[i] > separator_)
     876                break;
     877            else if (bound)
     878                numberOther++;
     879        }
     880        assert (i < numberMembers);
     881        for (; i < numberMembers; i++) {
     882            double bound = upper[which[i]];
     883            if (bound)
     884                numberFixed++;
     885        }
     886    } else {
     887        printf("SOS Up");
     888        for ( i = 0; i < numberMembers; i++) {
     889            double bound = upper[which[i]];
     890            if (weights[i] >= separator_)
     891                break;
     892            else if (bound)
     893                numberFixed++;
     894        }
     895        assert (i < numberMembers);
     896        for (; i < numberMembers; i++) {
     897            double bound = upper[which[i]];
     898            if (bound)
     899                numberOther++;
     900        }
     901    }
     902    printf(" - at %g, free range %d (%g) => %d (%g), %d would be fixed, %d other way\n",
     903           separator_, which[first], weights[first], which[last], weights[last], numberFixed, numberOther);
     904}
     905
     906/** Compare the original object of \c this with the original object of \c
     907    brObj. Assumes that there is an ordering of the original objects.
     908    This method should be invoked only if \c this and brObj are of the same
     909    type.
     910    Return negative/0/positive depending on whether \c this is
     911    smaller/same/larger than the argument.
     912*/
     913int
     914CbcSOSBranchingObject::compareOriginalObject
     915(const CbcBranchingObject* brObj) const
     916{
     917    const CbcSOSBranchingObject* br =
     918        dynamic_cast<const CbcSOSBranchingObject*>(brObj);
     919    assert(br);
     920    const CbcSOS* s0 = set_;
     921    const CbcSOS* s1 = br->set_;
     922    if (s0->sosType() != s1->sosType()) {
     923        return s0->sosType() - s1->sosType();
     924    }
     925    if (s0->numberMembers() != s1->numberMembers()) {
     926        return s0->numberMembers() - s1->numberMembers();
     927    }
     928    const int memberCmp = memcmp(s0->members(), s1->members(),
     929                                 s0->numberMembers() * sizeof(int));
     930    if (memberCmp != 0) {
     931        return memberCmp;
     932    }
     933    return memcmp(s0->weights(), s1->weights(),
     934                  s0->numberMembers() * sizeof(double));
     935}
     936
     937/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     938    same type and must have the same original object, but they may have
     939    different feasible regions.
     940    Return the appropriate CbcRangeCompare value (first argument being the
     941    sub/superset if that's the case). In case of overlap (and if \c
     942    replaceIfOverlap is true) replace the current branching object with one
     943    whose feasible region is the overlap.
     944*/
     945CbcRangeCompare
     946CbcSOSBranchingObject::compareBranchingObject
     947(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     948{
     949    const CbcSOSBranchingObject* br =
     950        dynamic_cast<const CbcSOSBranchingObject*>(brObj);
     951    assert(br);
     952    if (firstNonzero_ < br->firstNonzero_) {
     953        if (lastNonzero_ >= br->lastNonzero_) {
     954            return CbcRangeSuperset;
     955        } else if (lastNonzero_ <= br->firstNonzero_) {
     956            return CbcRangeDisjoint;
     957        } else {
     958            // overlap
     959            if (replaceIfOverlap) {
     960                firstNonzero_ = br->firstNonzero_;
     961            }
     962            return CbcRangeOverlap;
     963        }
     964    } else if (firstNonzero_ > br->firstNonzero_) {
     965        if (lastNonzero_ <= br->lastNonzero_) {
     966            return CbcRangeSubset;
     967        } else if (firstNonzero_ >= br->lastNonzero_) {
     968            return CbcRangeDisjoint;
     969        } else {
     970            // overlap
     971            if (replaceIfOverlap) {
     972                lastNonzero_ = br->lastNonzero_;
     973            }
     974            return CbcRangeOverlap;
     975        }
     976    } else {
     977        if (lastNonzero_ == br->lastNonzero_) {
     978            return CbcRangeSame;
     979        }
     980        return lastNonzero_ < br->lastNonzero_ ? CbcRangeSubset : CbcRangeSuperset;
     981    }
     982    return CbcRangeSame; // fake return
     983}
  • branches/sandbox/Cbc/src/CbcSOS.hpp

    r1293 r1350  
    147147    bool integerValued_;
    148148};
     149
     150/** Branching object for Special ordered sets
     151
     152    Variable_ is the set id number (redundant, as the object also holds a
     153    pointer to the set.
     154 */
     155class CbcSOSBranchingObject : public CbcBranchingObject {
     156
     157public:
     158
     159    // Default Constructor
     160    CbcSOSBranchingObject ();
     161
     162    // Useful constructor
     163    CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
     164                           int way,
     165                           double separator);
     166
     167    // Copy constructor
     168    CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
     169
     170    // Assignment operator
     171    CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
     172
     173    /// Clone
     174    virtual CbcBranchingObject * clone() const;
     175
     176    // Destructor
     177    virtual ~CbcSOSBranchingObject ();
     178
     179    using CbcBranchingObject::branch ;
     180    /// Does next branch and updates state
     181    virtual double branch();
     182    /** Update bounds in solver as in 'branch' and update given bounds.
     183        branchState is -1 for 'down' +1 for 'up' */
     184    virtual void fix(OsiSolverInterface * solver,
     185                     double * lower, double * upper,
     186                     int branchState) const ;
     187
     188    /** Reset every information so that the branching object appears to point to
     189        the previous child. This method does not need to modify anything in any
     190        solver. */
     191    virtual void previousBranch() {
     192        CbcBranchingObject::previousBranch();
     193        computeNonzeroRange();
     194    }
     195
     196    using CbcBranchingObject::print ;
     197    /** \brief Print something about branch - only if log level high
     198    */
     199    virtual void print();
     200
     201    /** Return the type (an integer identifier) of \c this */
     202    virtual int type() const {
     203        return 104;
     204    }
     205
     206    /** Compare the original object of \c this with the original object of \c
     207        brObj. Assumes that there is an ordering of the original objects.
     208        This method should be invoked only if \c this and brObj are of the same
     209        type.
     210        Return negative/0/positive depending on whether \c this is
     211        smaller/same/larger than the argument.
     212    */
     213    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     214
     215    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     216        same type and must have the same original object, but they may have
     217        different feasible regions.
     218        Return the appropriate CbcRangeCompare value (first argument being the
     219        sub/superset if that's the case). In case of overlap (and if \c
     220        replaceIfOverlap is true) replace the current branching object with one
     221        whose feasible region is the overlap.
     222     */
     223    virtual CbcRangeCompare compareBranchingObject
     224    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     225
     226    /** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */
     227    void computeNonzeroRange();
     228
     229private:
     230    /// data
     231    const CbcSOS * set_;
     232    /// separator
     233    double separator_;
     234    /** The following two members describe the range in the members_ of the
     235        original object that whose upper bound is not fixed to 0. This is not
     236        necessary for Cbc to function correctly, this is there for heuristics so
     237        that separate branching decisions on the same object can be pooled into
     238        one branching object. */
     239    int firstNonzero_;
     240    int lastNonzero_;
     241};
    149242#endif
  • branches/sandbox/Cbc/src/Makefile.am

    r1347 r1350  
    5252        CbcFathomDynamicProgramming.cpp CbcFathomDynamicProgramming.hpp \
    5353        CbcFeasibilityBase.hpp \
    54         CbcFixingBranchingObject.cpp CbcFixingBranchingObject.hpp \
    5554        CbcFixVariable.cpp CbcFixVariable.hpp \
    5655        CbcFullNodeInfo.cpp CbcFullNodeInfo.hpp \
     
    7877        CbcNodeInfo.cpp CbcNodeInfo.hpp \
    7978        CbcNWay.cpp CbcNWay.hpp \
    80         CbcNWayBranchingObject.cpp CbcNWayBranchingObject.hpp \
    8179        CbcObject.cpp CbcObject.hpp \
    8280        CbcObjectUpdateData.cpp CbcObjectUpdateData.hpp \
     
    8684        CbcSimpleIntegerPseudoCost.cpp CbcSimpleIntegerPseudoCost.hpp \
    8785        CbcSOS.cpp CbcSOS.hpp \
    88         CbcSOSBranchingObject.cpp CbcSOSBranchingObject.hpp \
    8986        CbcStatistics.cpp CbcStatistics.hpp \
    9087        CbcStrategy.cpp CbcStrategy.hpp \
     
    372369        CbcEventHandler.hpp \
    373370        CbcFeasibilityBase.hpp \
    374         CbcFixingBranchingObject.hpp \
    375371        CbcFixVariable.hpp \
    376372        CbcFollowOn.hpp \
     
    398394        CbcNodeInfo.hpp \
    399395        CbcNWay.hpp \
    400         CbcNWayBranchingObject.hpp \
    401396        CbcObject.hpp \
    402397        CbcObjectUpdateData.hpp \
     
    408403        CbcSolver.hpp \
    409404        CbcSOS.hpp \
    410         CbcSOSBranchingObject.hpp \
    411405        CbcSubProblem.hpp \
    412406        CbcTree.hpp \
  • branches/sandbox/Cbc/src/Makefile.in

    r1347 r1350  
    171171        CbcDummyBranchingObject.lo \
    172172        CbcDynamicPseudoCostBranchingObject.lo CbcEventHandler.lo \
    173         CbcFathom.lo CbcFathomDynamicProgramming.lo \
    174         CbcFixingBranchingObject.lo CbcFixVariable.lo \
     173        CbcFathom.lo CbcFathomDynamicProgramming.lo CbcFixVariable.lo \
    175174        CbcFullNodeInfo.lo CbcFollowOn.lo CbcGeneral.lo \
    176175        CbcGeneralDepth.lo CbcHeuristic.lo CbcHeuristicDive.lo \
     
    182181        CbcHeuristicRandRound.lo CbcHeuristicRINS.lo CbcLotsize.lo \
    183182        CbcMessage.lo CbcModel.lo CbcNode.lo CbcNodeInfo.lo CbcNWay.lo \
    184         CbcNWayBranchingObject.lo CbcObject.lo CbcObjectUpdateData.lo \
    185         CbcPartialNodeInfo.lo CbcSimpleInteger.lo \
    186         CbcSimpleIntegerDynamicPseudoCost.lo \
    187         CbcSimpleIntegerPseudoCost.lo CbcSOS.lo \
    188         CbcSOSBranchingObject.lo CbcStatistics.lo CbcStrategy.lo \
    189         CbcSubProblem.lo CbcTree.lo CbcTreeLocal.lo
     183        CbcObject.lo CbcObjectUpdateData.lo CbcPartialNodeInfo.lo \
     184        CbcSimpleInteger.lo CbcSimpleIntegerDynamicPseudoCost.lo \
     185        CbcSimpleIntegerPseudoCost.lo CbcSOS.lo CbcStatistics.lo \
     186        CbcStrategy.lo CbcSubProblem.lo CbcTree.lo CbcTreeLocal.lo
    190187libCbc_la_OBJECTS = $(am_libCbc_la_OBJECTS)
    191188libCbcSolver_la_LIBADD =
     
    552549        CbcFathomDynamicProgramming.cpp CbcFathomDynamicProgramming.hpp \
    553550        CbcFeasibilityBase.hpp \
    554         CbcFixingBranchingObject.cpp CbcFixingBranchingObject.hpp \
    555551        CbcFixVariable.cpp CbcFixVariable.hpp \
    556552        CbcFullNodeInfo.cpp CbcFullNodeInfo.hpp \
     
    578574        CbcNodeInfo.cpp CbcNodeInfo.hpp \
    579575        CbcNWay.cpp CbcNWay.hpp \
    580         CbcNWayBranchingObject.cpp CbcNWayBranchingObject.hpp \
    581576        CbcObject.cpp CbcObject.hpp \
    582577        CbcObjectUpdateData.cpp CbcObjectUpdateData.hpp \
     
    586581        CbcSimpleIntegerPseudoCost.cpp CbcSimpleIntegerPseudoCost.hpp \
    587582        CbcSOS.cpp CbcSOS.hpp \
    588         CbcSOSBranchingObject.cpp CbcSOSBranchingObject.hpp \
    589583        CbcStatistics.cpp CbcStatistics.hpp \
    590584        CbcStrategy.cpp CbcStrategy.hpp \
     
    735729        CbcEventHandler.hpp \
    736730        CbcFeasibilityBase.hpp \
    737         CbcFixingBranchingObject.hpp \
    738731        CbcFixVariable.hpp \
    739732        CbcFollowOn.hpp \
     
    761754        CbcNodeInfo.hpp \
    762755        CbcNWay.hpp \
    763         CbcNWayBranchingObject.hpp \
    764756        CbcObject.hpp \
    765757        CbcObjectUpdateData.hpp \
     
    771763        CbcSolver.hpp \
    772764        CbcSOS.hpp \
    773         CbcSOSBranchingObject.hpp \
    774765        CbcSubProblem.hpp \
    775766        CbcTree.hpp \
     
    917908@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcFathomDynamicProgramming.Plo@am__quote@
    918909@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcFixVariable.Plo@am__quote@
    919 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcFixingBranchingObject.Plo@am__quote@
    920910@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcFollowOn.Plo@am__quote@
    921911@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcFullNodeInfo.Plo@am__quote@
     
    953943@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcModel.Plo@am__quote@
    954944@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcNWay.Plo@am__quote@
    955 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcNWayBranchingObject.Plo@am__quote@
    956945@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcNode.Plo@am__quote@
    957946@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcNodeInfo.Plo@am__quote@
     
    960949@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcPartialNodeInfo.Plo@am__quote@
    961950@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcSOS.Plo@am__quote@
    962 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcSOSBranchingObject.Plo@am__quote@
    963951@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcSimpleInteger.Plo@am__quote@
    964952@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcSimpleIntegerDynamicPseudoCost.Plo@am__quote@
Note: See TracChangeset for help on using the changeset viewer.