Changeset 2070 for trunk/Cbc/src


Ignore:
Timestamp:
Sep 8, 2014 5:24:45 AM (5 years ago)
Author:
forrest
Message:

allow sos in lp files and fix odd SOS branching

Location:
trunk/Cbc/src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcModel.cpp

    r2051 r2070  
    22132213            // If odd switch off AddIntegers
    22142214            specialOptions_ &= ~65536;
     2215            // switch off fast nodes for now
     2216            fastNodeDepth_ = -1;
     2217            moreSpecialOptions_ &= ~33554432; // no diving
    22152218        } else if (numberSOS) {
    22162219            specialOptions_ |= 128; // say can do SOS in dynamic mode
  • trunk/Cbc/src/CbcSOS.cpp

    r2040 r2070  
    3131CbcSOS::CbcSOS ()
    3232        : CbcObject(),
    33         members_(NULL),
    34         weights_(NULL),
    35         shadowEstimateDown_(1.0),
    36         shadowEstimateUp_(1.0),
    37         downDynamicPseudoRatio_(0.0),
    38         upDynamicPseudoRatio_(0.0),
    39         numberTimesDown_(0),
    40         numberTimesUp_(0),
    41         numberMembers_(0),
    42         sosType_(-1),
    43         integerValued_(false)
     33          members_(NULL),
     34          weights_(NULL),
     35          shadowEstimateDown_(1.0),
     36          shadowEstimateUp_(1.0),
     37          downDynamicPseudoRatio_(0.0),
     38          upDynamicPseudoRatio_(0.0),
     39          numberTimesDown_(0),
     40          numberTimesUp_(0),
     41          numberMembers_(0),
     42          sosType_(-1),
     43          integerValued_(false),
     44          oddValues_(false)
    4445{
    4546}
     
    5657        numberTimesUp_(0),
    5758        numberMembers_(numberMembers),
    58         sosType_(type)
     59          sosType_(type),
     60          oddValues_(false)
    5961{
    6062    id_ = identifier;
     
    7476    }
    7577    if (numberMembers_) {
     78      const OsiSolverInterface * solver = model_->solver();
     79      const double * lower = solver->getColLower();
     80      for (int i = 0; i < numberMembers_; i++) {
     81        if (lower[which[i]]<0.0) {
     82          oddValues_ = true; // mark as odd
     83        }
     84      }
     85
     86      // check >= 0.0
    7687        members_ = new int[numberMembers_];
    7788        weights_ = new double[numberMembers_];
     
    117128    sosType_ = rhs.sosType_;
    118129    integerValued_ = rhs.integerValued_;
     130    oddValues_ = rhs.oddValues_;
    119131    if (numberMembers_) {
    120132        members_ = new int[numberMembers_];
     
    152164        sosType_ = rhs.sosType_;
    153165        integerValued_ = rhs.integerValued_;
     166        oddValues_ = rhs.oddValues_;
    154167        if (numberMembers_) {
    155168            members_ = new int[numberMembers_];
     
    188201    OsiSolverInterface * solver = model_->solver();
    189202    const double * solution = model_->testSolution();
    190     //const double * lower = solver->getColLower();
     203    const double * lower = solver->getColLower();
    191204    const double * upper = solver->getColUpper();
    192205    //double largestValue=0.0;
     
    194207        model_->getDblParam(CbcModel::CbcIntegerTolerance);
    195208    double weight = 0.0;
    196     double sum = 0.0;
     209    double sum = 0.0; 
    197210
    198211    // check bounds etc
     
    207220        if (lastWeight >= weights_[j] - 1.0e-7)
    208221            throw CoinError("Weights too close together in SOS", "infeasibility", "CbcSOS");
    209         double value = CoinMax(0.0, solution[iColumn]);
     222        double value = CoinMax(lower[iColumn], solution[iColumn]);
    210223        sum += value;
    211224        /*
     
    216229          used to calculate either the return value or preferredWay.
    217230        */
    218         if (value > integerTolerance && upper[iColumn]) {
     231        if (fabs(value) > integerTolerance && (upper[iColumn] > 0.0 ||
     232                                               oddValues_)) {
    219233            // Possibly due to scaling a fixed variable might slip through
    220234            if (value > upper[iColumn]) {
     
    228242#endif
    229243            }
     244            if (value < lower[iColumn]) {
     245                value = lower[iColumn];
     246                // Could change to #ifdef CBC_DEBUG
     247#ifndef NDEBUG
     248                if (model_->messageHandler()->logLevel() > 2 &&
     249                    value < lower[iColumn] - integerTolerance)
     250                    printf("** Variable %d (%d) has value %g and lower bound of %g\n",
     251                           iColumn, j, value, lower[iColumn]);
     252#endif
     253            }
    230254            weight += weights_[j] * value;
    231255            if (firstNonZero < 0)
     
    244268    if (lastNonZero - firstNonZero >= sosType_) {
    245269        // find where to branch
    246         assert (sum > 0.0);
    247         weight /= sum;
     270        if (!oddValues_)
     271          weight /= sum;
     272        else
     273          weight = 0.5*(weights_[firstNonZero]+weights_[lastNonZero]);
    248274        if (info->defaultDual_ >= 0.0 && info->usefulRegion_ && info->columnStart_) {
    249275            assert (sosType_ == 1);
     
    443469    OsiSolverInterface * solver = model_->solver();
    444470    const double * solution = model_->testSolution();
    445     //const double * lower = solver->getColLower();
     471    const double * lower = solver->getColLower();
    446472    const double * upper = solver->getColUpper();
    447473    double integerTolerance =
     
    452478    for (j = 0; j < numberMembers_; j++) {
    453479        int iColumn = members_[j];
    454         double value = CoinMax(0.0, solution[iColumn]);
     480        double value = CoinMax(lower[iColumn], solution[iColumn]);
    455481        sum += value;
    456         if (value > integerTolerance && upper[iColumn]) {
     482        if (fabs(value) > integerTolerance && (upper[iColumn] || oddValues_)) {
    457483            weight += weights_[j] * value;
    458484            if (firstNonZero < 0)
     
    465491      for (j = 0; j < firstNonZero; j++) {
    466492        int iColumn = members_[j];
     493        solver->setColLower(iColumn, 0.0);
    467494        solver->setColUpper(iColumn, 0.0);
    468495      }
    469496      for (j = lastNonZero + 1; j < numberMembers_; j++) {
    470497        int iColumn = members_[j];
     498        solver->setColLower(iColumn, 0.0);
    471499        solver->setColUpper(iColumn, 0.0);
    472500      }
     
    474502      for (j = 0; j < numberMembers_; j++) {
    475503        int iColumn = members_[j];
    476         solver->setColUpper(iColumn, 0.0);
     504        solver->setColUpper(iColumn, 0.0); // make infeasible
    477505        solver->setColLower(iColumn, 1.0);
    478506      }
     
    510538        model_->getDblParam(CbcModel::CbcIntegerTolerance);
    511539    //OsiSolverInterface * solver = model_->solver();
     540    const double * lower = solver->getColLower();
    512541    const double * upper = solver->getColUpper();
    513542    int firstNonFixed = -1;
     
    519548    for (j = 0; j < numberMembers_; j++) {
    520549        int iColumn = members_[j];
    521         if (upper[iColumn]) {
    522             double value = CoinMax(0.0, solution[iColumn]);
     550        if (upper[iColumn] || oddValues_) {
     551            double value = CoinMax(lower[iColumn], solution[iColumn]);
    523552            sum += value;
    524553            if (firstNonFixed < 0)
    525554                firstNonFixed = j;
    526555            lastNonFixed = j;
    527             if (value > integerTolerance) {
     556            if (fabs(value) > integerTolerance) {
    528557                weight += weights_[j] * value;
    529558                if (firstNonZero < 0)
     
    535564    assert (lastNonZero - firstNonZero >= sosType_) ;
    536565    // find where to branch
    537     assert (sum > 0.0);
    538     weight /= sum;
     566    if (!oddValues_)
     567      weight /= sum;
     568    else
     569      weight = 0.5*(weights_[firstNonZero]+weights_[lastNonZero]);
    539570    int iWhere;
    540571    double separator = 0.0;
     
    542573        if (weight < weights_[iWhere+1])
    543574            break;
     575    assert (iWhere<lastNonZero);
    544576    if (sosType_ == 1) {
    545577        // SOS 1
     
    699731        fix[j] = 0.0;
    700732        which[j] = iColumn;
    701         if (upper[iColumn]) {
     733        if (upper[iColumn] || oddValues_) {
    702734            double value = CoinMax(0.0, solution[iColumn]);
    703735            sum += value;
     
    715747    assert (lastNonZero - firstNonZero >= sosType_) ;
    716748    // find where to branch
    717     assert (sum > 0.0);
    718     weight /= sum;
     749    if (!oddValues_)
     750      weight /= sum;
     751    else
     752      weight = 0.5*(weights_[firstNonZero]+weights_[lastNonZero]);
    719753    // down branch fixes ones above weight to 0
    720754    int iWhere;
     
    854888        }
    855889        assert (i < numberMembers);
    856         for (; i < numberMembers; i++)
     890        for (; i < numberMembers; i++) {
     891            solver->setColLower(which[i], 0.0);
    857892            solver->setColUpper(which[i], 0.0);
     893        }
    858894        way_ = 1;         // Swap direction
    859895    } else {
    860896        int i;
    861897        for ( i = 0; i < numberMembers; i++) {
    862             if (weights[i] >= separator_)
     898          if (weights[i] >= separator_) {
    863899                break;
    864             else
     900          } else {
     901                solver->setColLower(which[i], 0.0);
    865902                solver->setColUpper(which[i], 0.0);
     903          }
    866904        }
    867905        assert (i < numberMembers);
     
    881919void
    882920CbcSOSBranchingObject::fix(OsiSolverInterface * solver,
    883                            double * /*lower*/, double * upper,
     921                           double * lower, double * upper,
    884922                           int branchState) const
    885923{
     
    898936        assert (i < numberMembers);
    899937        for (; i < numberMembers; i++) {
     938            solver->setColLower(which[i], 0.0);
     939            lower[which[i]] = 0.0;
    900940            solver->setColUpper(which[i], 0.0);
    901941            upper[which[i]] = 0.0;
     
    907947                break;
    908948            } else {
     949                solver->setColLower(which[i], 0.0);
     950                lower[which[i]] = 0.0;
    909951                solver->setColUpper(which[i], 0.0);
    910952                upper[which[i]] = 0.0;
  • trunk/Cbc/src/CbcSOS.hpp

    r1899 r2070  
    180180    /// Whether integer valued
    181181    bool integerValued_;
     182    /// Whether odd values e.g. negative
     183    bool oddValues_;
    182184};
    183185
  • trunk/Cbc/src/CbcSolver.cpp

    r2069 r2070  
    75677567                            } else {
    75687568#ifdef KILL_ZERO_READLP
    7569                                 status = lpSolver->readLp(fileName.c_str(), lpSolver->getSmallElementValue());
     7569                                status = clpSolver->readLp(fileName.c_str(), lpSolver->getSmallElementValue());
    75707570#else
    7571                                 status = lpSolver->readLp(fileName.c_str(), 1.0e-12);
     7571                                status = clpSolver->readLp(fileName.c_str(), 1.0e-12);
    75727572#endif
    75737573                            }
     
    77697769                                    sosIndices = info.sosIndices;
    77707770                                    sosReference = info.sosReference;
    7771                                     preSolve = false;
    77727771                                    clpSolver->setSOSData(numberSOS, info.sosType, sosStart, sosIndices, sosReference);
    77737772                                }
    77747773#endif
     7774                                numberSOS = clpSolver->numberSOS();
     7775                                if (numberSOS)
     7776                                  preSolve = false;
    77757777#endif
    77767778                                if (preSolve) {
     
    78257827                                            }
    78267828                                        }
    7827                                         clpSolver->writeMpsNative(fileName.c_str(), const_cast<const char **> (rowNames), const_cast<const char **> (columnNames),
    7828                                                                   (outputFormat - 1) / 2, 1 + ((outputFormat - 1)&1));
     7829                                        // see if extension lp
     7830                                        bool writeLp=false;
     7831                                        {
     7832                                          int lengthName = strlen(fileName.c_str());
     7833                                          if (lengthName>3&&!strcmp(fileName.c_str()+lengthName-3,".lp"))
     7834                                            writeLp=true;
     7835                                        }
     7836                                        if (!writeLp) {
     7837                                          remove(fileName.c_str());
     7838                                          clpSolver->writeMpsNative(fileName.c_str(), const_cast<const char **> (rowNames), const_cast<const char **> (columnNames),
     7839                                                                    (outputFormat - 1) / 2, 1 + ((outputFormat - 1)&1));
     7840                                        } else {
     7841                                          FILE *fp = fopen(fileName.c_str(), "w");
     7842                                          assert (fp);
     7843                                          clpSolver->writeLp(fp,1.0e-12);
     7844                                        }
    78297845                                        if (rowNames) {
    78307846                                            for (iRow = 0; iRow < numberRows; iRow++) {
Note: See TracChangeset for help on using the changeset viewer.