Changeset 2048


Ignore:
Timestamp:
Jul 16, 2014 5:29:16 AM (5 years ago)
Author:
forrest
Message:

First try at orbital branching

Location:
trunk/Cbc/src
Files:
8 edited

Legend:

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

    r1951 r2048  
    134134      return;
    135135    // branch - do bounds
    136     assert (active_ == 7 || active_ == 15);
     136    assert ((active_&~16) == 7 || (active_&~16) == 15);
    137137    int i;
    138138    solver->setColLower(lower_);
  • trunk/Cbc/src/CbcModel.cpp

    r2043 r2048  
    6262#include "CbcFathom.hpp"
    6363#include "CbcFullNodeInfo.hpp"
     64#ifdef COIN_HAS_NTY
     65#include "CbcSymmetry.hpp"
     66#endif
    6467// include Probing
    6568#include "CglProbing.hpp"
     
    22812284    */
    22822285    continuousSolver_ = solver_->clone() ;
     2286#ifdef COIN_HAS_NTY
     2287    // maybe allow on fix and restart later
     2288    if ((moreSpecialOptions2_&(128|256))!=0&&!parentModel_) {
     2289      symmetryInfo_ = new CbcSymmetry();
     2290      symmetryInfo_->setupSymmetry(*continuousSolver_);
     2291      int numberGenerators = symmetryInfo_->statsOrbits(this,0);
     2292      if (!numberGenerators) {
     2293        delete symmetryInfo_;
     2294        symmetryInfo_=NULL;
     2295        moreSpecialOptions2_ &= ~128;
     2296      }
     2297    }
     2298#endif
    22832299
    22842300    // add cutoff as constraint if wanted
     
    25652581        rootModels[i]->setMoreSpecialOptions(moreSpecialOptions_ &
    25662582                                             (~134217728));
     2583        rootModels[i]->setMoreSpecialOptions2(moreSpecialOptions2_ &
     2584                                             (~128));
    25672585        rootModels[i]->solver_->setWarmStart(basis);
    25682586#ifdef COIN_HAS_CLP
     
    38563874        if (toZero[number01]) {
    38573875            CglTreeProbingInfo info(*probingInfo_);
    3858             if ((moreSpecialOptions_&1048576)!=0&&!parentModel_) {
     3876            if ((moreSpecialOptions2_&64)!=0&&!parentModel_) {
    38593877              /*
    38603878                Marginal idea. Further exploration probably good. Build some extra
     
    45234541                << CoinMessageEol ;
    45244542            }
     4543#ifdef COIN_HAS_NTY
     4544            if (symmetryInfo_)
     4545              symmetryInfo_->statsOrbits(this,1);
     4546#endif
    45254547            if (eventHandler && !eventHandler->event(CbcEventHandler::treeStatus)) {
    45264548                eventHappened_ = true; // exit
     
    47624784        << numberDJFixed_ << numberExtraNodes_ << numberExtraIterations_
    47634785        << CoinMessageEol ;
     4786#ifdef COIN_HAS_NTY
     4787    if (symmetryInfo_)
     4788      symmetryInfo_->statsOrbits(this,1);
     4789#endif
    47644790    if (doStatistics == 100) {
    47654791        for (int i = 0; i < numberObjects_; i++) {
     
    52795305        fastNodeDepth_(-1),
    52805306        eventHandler_(NULL),
     5307#ifdef COIN_HAS_NTY
     5308        symmetryInfo_(NULL),
     5309#endif
    52815310        numberObjects_(0),
    52825311        object_(NULL),
     
    54445473        fastNodeDepth_(-1),
    54455474        eventHandler_(NULL),
     5475#ifdef COIN_HAS_NTY
     5476        symmetryInfo_(NULL),
     5477#endif
    54465478        numberObjects_(0),
    54475479        object_(NULL),
     
    59625994        lastCut_ = NULL;
    59635995    }
     5996#ifdef COIN_HAS_NTY
     5997    if (rhs.symmetryInfo_)
     5998      symmetryInfo_ = new CbcSymmetry(*rhs.symmetryInfo_);
     5999    else
     6000      symmetryInfo_ = NULL;
     6001#endif
    59646002    synchronizeModel();
    59656003    if (cloneHandler && !defaultHandler_) {
     
    62966334            lastCut_ = NULL;
    62976335        }
     6336#ifdef COIN_HAS_NTY
     6337        if (rhs.symmetryInfo_)
     6338          symmetryInfo_ = new CbcSymmetry(*rhs.symmetryInfo_);
     6339        else
     6340          symmetryInfo_ = NULL;
     6341#endif
    62986342        synchronizeModel();
    62996343        cbcColLower_ = NULL;
     
    63876431    topOfTree_ = NULL;
    63886432    resetModel();
     6433#ifdef COIN_HAS_NTY
     6434    delete symmetryInfo_;
     6435    symmetryInfo_ = NULL;
     6436#endif
    63896437}
    63906438// Clears out enough to reset CbcModel
     
    66126660    messageHandler()->setLogLevel(rhs.messageHandler()->logLevel());
    66136661    whenCuts_ = rhs.whenCuts_;
     6662#ifdef COIN_HAS_NTY
     6663    if (rhs.symmetryInfo_)
     6664      symmetryInfo_ = new CbcSymmetry (*rhs.symmetryInfo_);
     6665    else
     6666      symmetryInfo_ = NULL;
     6667#endif
    66146668    synchronizeModel();
    66156669}
     
    1181211866        // Can trust solution
    1181311867        int numberColumns = solver_->getNumCols();
     11868#ifdef COIN_HAS_CLP
     11869        OsiClpSolverInterface * clpContinuousSolver
     11870          = dynamic_cast<OsiClpSolverInterface *> (continuousSolver_);
     11871        int modifiedTolerances=0;
     11872#ifndef CBC_LEAVE_PERTURBATION_ON_CHECK_SOLUTION
     11873        int savePerturbation=-1;
     11874#endif
     11875#ifndef CBC_LEAVE_TOLERANCE_ON_CHECK_SOLUTION
     11876        double savePrimalTolerance=0.0;
     11877#endif
     11878#ifndef CBC_LEAVE_SCALING_ON_CHECK_SOLUTION
     11879        int saveScaling=-1;
     11880#endif
     11881        if (clpContinuousSolver ) {
     11882          // be more accurate if possible
     11883          ClpSimplex * clp = clpContinuousSolver->getModelPtr();
     11884#ifndef CBC_LEAVE_PERTURBATION_ON_CHECK_SOLUTION
     11885          savePerturbation=clp->perturbation();
     11886#endif
     11887#ifndef CBC_LEAVE_TOLERANCE_ON_CHECK_SOLUTION
     11888          savePrimalTolerance=clp->primalTolerance();
     11889#endif
     11890#ifndef CBC_LEAVE_SCALING_ON_CHECK_SOLUTION
     11891          saveScaling=clp->scalingFlag();
     11892#endif
     11893#ifndef CBC_LEAVE_TOLERANCE_ON_CHECK_SOLUTION
     11894          if (savePrimalTolerance>0.9999999e-7) {
     11895            modifiedTolerances |= 1;
     11896            clp->setPrimalTolerance(1.0e-8);
     11897          }
     11898#endif
     11899#ifndef CBC_LEAVE_PERTURBATION_ON_CHECK_SOLUTION
     11900          if (savePerturbation<100) {
     11901            modifiedTolerances |= 2;
     11902            clp->setPerturbation(100);
     11903          }
     11904#endif
     11905#ifndef CBC_LEAVE_SCALING_ON_CHECK_SOLUTION
     11906          if (saveScaling) {
     11907            modifiedTolerances |= 4;
     11908            clp->scaling(0);
     11909          }
     11910#endif
     11911        }
     11912#endif
    1181411913
    1181511914        /*
     
    1216812267#endif
    1216912268                    solver_->initialSolve();
     12269#ifdef COIN_HAS_CLP
     12270                    if (!solver_->isProvenOptimal()&&modifiedTolerances) {
     12271                      // Restore
     12272                      ClpSimplex * clp = clpContinuousSolver->getModelPtr();
     12273#ifndef CBC_LEAVE_TOLERANCE_ON_CHECK_SOLUTION
     12274                      clp->setPrimalTolerance(savePrimalTolerance);
     12275#endif
     12276#ifndef CBC_LEAVE_PERTURBATION_ON_CHECK_SOLUTION
     12277                      clp->setPerturbation(savePerturbation);
     12278#endif
     12279#ifndef CBC_LEAVE_SCALING_ON_CHECK_SOLUTION
     12280                      clp->scaling(saveScaling);
     12281#endif
     12282                      solver_->resolve();
     12283                    }
     12284#endif
    1217012285#if COIN_DEVELOP>1
    1217112286                    if (!solver_->isProvenOptimal()) {
     
    1236112476                objectiveValue = objValue;
    1236212477                //}
    12363 #ifdef CLP_INVESTIGATE
     12478#if 1 //def CLP_INVESTIGATE
    1236412479                if (largestInfeasibility > 10.0*primalTolerance)
    12365                     printf("largest infeasibility is %g\n", largestInfeasibility);
     12480                    printf("XX largest infeasibility is %g\n", largestInfeasibility);
    1236612481#endif
    1236712482                if (largestInfeasibility > 200.0*primalTolerance) {
     
    1239712512        solver_ = saveSolver;
    1239812513        testSolution_ = save;
     12514#ifdef COIN_HAS_CLP
     12515        if (modifiedTolerances) {
     12516          // Restore
     12517          ClpSimplex * clp = clpContinuousSolver->getModelPtr();
     12518#ifndef CBC_LEAVE_TOLERANCE_ON_CHECK_SOLUTION
     12519          clp->setPrimalTolerance(savePrimalTolerance);
     12520#endif
     12521#ifndef CBC_LEAVE_PERTURBATION_ON_CHECK_SOLUTION
     12522          clp->setPerturbation(savePerturbation);
     12523#endif
     12524#ifndef CBC_LEAVE_SCALING_ON_CHECK_SOLUTION
     12525          clp->scaling(saveScaling);
     12526#endif
     12527        }
     12528#endif
    1239912529        return objectiveValue;
    1240012530    } else {
     
    1447814608            }
    1447914609#endif
     14610#ifdef COIN_HAS_NTY
     14611            if (symmetryInfo_) {
     14612              CbcNodeInfo * infoX = oldNode ? oldNode->nodeInfo() : NULL;
     14613              bool worthTrying = false;
     14614              if (infoX) {
     14615                CbcNodeInfo * info = infoX;
     14616                for (int i=0;i<NTY_BAD_DEPTH;i++) {
     14617                  if (!info->parent()) {
     14618                    worthTrying = true;
     14619                    break;
     14620                  }
     14621                  info = info->parent();
     14622                  if (info->symmetryWorked()) {
     14623                    worthTrying = true;
     14624                    break;
     14625                  }
     14626                }
     14627              } else {
     14628                worthTrying=true;
     14629              }
     14630              if (worthTrying) {
     14631                int n=symmetryInfo_->orbitalFixing(solver_);
     14632                if (n) {
     14633#if PRINT_MORE==0
     14634                  if (logLevel()>1)
     14635                    printf("%d orbital fixes\n",n);
     14636#endif
     14637                  solver_->resolve();
     14638                  if(!isProvenOptimal()) {
     14639                    if (logLevel()>1)
     14640                      printf("infeasible after orbital fixing\n");
     14641                  }
     14642                }
     14643              }
     14644            }
     14645#endif
    1448014646            if (numberBeforeTrust_ == 0 ) {
    1448114647                anyAction = newNode->chooseBranch(this, oldNode, numberPassesLeft) ;
     
    1691917085                             * dblParam_[CbcAllowableFractionGap]);
    1692017086    returnCode = (bestObjective_ - bestPossibleObjective_ < testGap && getCutoffIncrement() >= 0.0);
    16921   }
     17087  }
     17088#if 1
     17089  if (returnCode) {
     17090    if (fabs(bestObjective_+1469650.0)<1.0) {
     17091      fprintf(stderr,"BAD - cr to continue\n");
     17092      fflush(stdout);
     17093      char xx;
     17094      xx=getc(stdin);
     17095    }
     17096  }
     17097#endif
    1692217098  return returnCode;
    1692317099}
  • trunk/Cbc/src/CbcModel.hpp

    r2040 r2048  
    3434class CbcTree;
    3535class CbcStrategy;
     36class CbcSymmetry;
    3637class CbcFeasibilityBase;
    3738class CbcStatistics;
     
    18601861        4 bit (16) - very lightweight preprocessing in smallB&B
    18611862        5 bit (32) - event handler needs to be cloned when parallel
     1863        6 bit (64) - testing - use probing to make cliques
     1864        7/8 bit (128) - try orbital branching (if nauty)
     1865        9 bit (512) - branching on objective (later)
     1866        10 bit (1024) - branching on constraints (later)
    18621867    */
    18631868    inline void setMoreSpecialOptions2(int value) {
     
    23062311        maximumNumberIterations_ = value;
    23072312    }
     2313#ifdef COIN_HAS_NTY
     2314    /// Symmetry information
     2315    inline CbcSymmetry * symmetryInfo() const
     2316    { return symmetryInfo_;} 
     2317#endif
    23082318    /// Set depth for fast nodes
    23092319    inline void setFastNodeDepth(int value) {
     
    26342644        4 bit (16) - very lightweight preprocessing in smallB&B
    26352645        5 bit (32) - event handler needs to be cloned when parallel
     2646        6 bit (64) - testing - use probing to make cliques
     2647        7 bit (128) - try orbital branching (if nauty)
     2648        8 bit (256) - branching on objective (later)
     2649        9 bit (512) - branching on constraints (later)
    26362650    */
    26372651    int moreSpecialOptions2_;
     
    27392753    CbcEventHandler *eventHandler_ ;
    27402754# endif
    2741 
     2755#ifdef COIN_HAS_NTY
     2756  /// Symmetry information
     2757  CbcSymmetry * symmetryInfo_;
     2758#endif
    27422759    /// Total number of objects
    27432760    int numberObjects_;
  • trunk/Cbc/src/CbcNode.cpp

    r2040 r2048  
    1010
    1111#include "CbcConfig.h"
     12#ifdef COIN_HAS_NTY
     13#include "CbcSymmetry.hpp"
     14#endif
    1215//#define DEBUG_SOLUTION
    1316#ifdef DEBUG_SOLUTION
     
    19561959    choice.possibleBranch = choiceObject;
    19571960    numberPassesLeft = CoinMax(numberPassesLeft, 2);
     1961#ifdef COIN_HAS_NTY
     1962    // 1 after, 2 strong, 3 subset
     1963    int orbitOption = (model->moreSpecialOptions2()&(128|256))>>7;
     1964#endif
    19581965    //#define DEBUG_SOLUTION
    19591966#ifdef DEBUG_SOLUTION
     
    28152822            }
    28162823#endif
     2824#ifdef COIN_HAS_NTY
     2825            const int * orbits = NULL;
     2826#endif
     2827#ifdef COIN_HAS_NTY
     2828            if (orbitOption>1) {
     2829              CbcSymmetry * symmetryInfo = model->symmetryInfo();
     2830              CbcNodeInfo * infoX = lastNode ? lastNode->nodeInfo() : NULL;
     2831              bool worthTrying = false;
     2832              if (infoX) {
     2833                CbcNodeInfo * info = infoX;
     2834                for (int i=0;i<NTY_BAD_DEPTH;i++) {
     2835                  if (!info->parent()) {
     2836                    worthTrying = true;
     2837                    break;
     2838                  }
     2839                  info = info->parent();
     2840                  if (info->symmetryWorked()) {
     2841                    worthTrying = true;
     2842                    break;
     2843                  }
     2844                }
     2845              } else {
     2846                worthTrying=true;
     2847              }
     2848              if (symmetryInfo && worthTrying) {
     2849                symmetryInfo->ChangeBounds(solver->getColLower(),
     2850                                            solver->getColUpper(),
     2851                                            solver->getNumCols(),false);
     2852                symmetryInfo->Compute_Symmetry();
     2853                symmetryInfo->fillOrbits();
     2854                orbits = symmetryInfo->whichOrbit();
     2855                int iColumn=-1;
     2856                if (orbits && symmetryInfo->numberUsefulObjects()) {
     2857                  bool doBranch=true;
     2858                  int numberUsefulOrbits = symmetryInfo->numberUsefulObjects();
     2859                  if (numberUsefulOrbits<2) {
     2860                    assert (numberUsefulOrbits);
     2861                    double largest=-1.0;
     2862                    for (int i=0;i<numberColumns;i++) {
     2863                      if (orbits[i]>=0) {
     2864                        if (saveSolution[i]>largest) {
     2865                          largest=saveSolution[i];
     2866                          iColumn=i;
     2867                        }
     2868                      }
     2869                    }
     2870                  } else {
     2871#if COIN_HAS_NTY2 == 1
     2872                    // take largest
     2873                    int iOrbit=symmetryInfo->largestOrbit(solver->getColLower(),
     2874                                                          solver->getColUpper());
     2875                    double largest=-1.0;
     2876                    for (int i=0;i<numberColumns;i++) {
     2877                      if (orbits[i]==iOrbit) {
     2878                        if (saveSolution[i]>largest) {
     2879                          largest=saveSolution[i];
     2880                          iColumn=i;
     2881                        }
     2882                      }
     2883                    }
     2884#endif
     2885                    if (orbitOption==2) {
     2886                      // strong
     2887                      int nDo=0;
     2888                      const double * lower = solver->getColLower();
     2889                      const double * upper = solver->getColUpper();
     2890                      for (int iOrbit = 0; iOrbit < numberUsefulOrbits; iOrbit++) {
     2891                        double distance=1.0;
     2892                        int iColumn = -1;
     2893                        for (int i=0;i<numberColumns;i++) {
     2894                          if (orbits[i]==iOrbit &&lower[i]==0.0&&upper[i]==1.0) {
     2895                            double away = fabs(saveSolution[i]-0.5);
     2896                            if (away<distance&&away<0.4999) {
     2897                              distance=away;
     2898                              iColumn=i;
     2899                            }
     2900                          }
     2901                        }
     2902                        if (iColumn>=0)
     2903                          whichObject[nDo++]=iColumn;
     2904                      }
     2905                      if (nDo)
     2906                        numberToDo=nDo;
     2907                      doBranch=false;
     2908                    } else if (orbitOption==3) {
     2909                      // subset
     2910                      int nDo=0;
     2911                      for (int iDo = 0; iDo < numberToDo; iDo++) {
     2912                        int iObject = whichObject[iDo];
     2913                        OsiObject * object = model->modifiableObject(iObject);
     2914                        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
     2915                          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
     2916                        int iColumn = dynamicObject ? dynamicObject->columnNumber() : -1;
     2917                        if (iColumn<0||orbits[iColumn]>=0)
     2918                          whichObject[nDo++]=whichObject[iDo];
     2919                      }
     2920                      assert(nDo);
     2921                      //printf("nDo %d\n",nDo);
     2922                      numberToDo=nDo;
     2923                      doBranch=false;
     2924                      /* need NULL as if two in same orbit and strong branching fixes
     2925                         then we may be in trouble.
     2926                         Strong option should be OK as only one in set done.
     2927                       */
     2928                      orbits=NULL;
     2929                    }
     2930                  }
     2931                  if(doBranch) {
     2932                    orbitOption=0;
     2933                    branch_ = new CbcOrbitalBranchingObject(model,iColumn,1,0,NULL);
     2934                    if (infoX)
     2935                      infoX->setSymmetryWorked();
     2936                    numberToDo=0;
     2937                  }
     2938                }
     2939              }
     2940            }
     2941#endif
    28172942            for ( iDo = 0; iDo < numberToDo; iDo++) {
    28182943                int iObject = whichObject[iDo];
     
    28622987                  choice.downMovement = 0.1;
    28632988                }
    2864                   assert (choice.upMovement >= 0.0);
    2865                   assert (choice.downMovement >= 0.0);
     2989                assert (choice.upMovement >= 0.0);
     2990                assert (choice.downMovement >= 0.0);
    28662991                choice.fix = 0; // say not fixed
    28672992                // see if can skip strong branching
     
    29163041                    choice.possibleBranch->way(-1) ;
    29173042                    predictedChange = choice.possibleBranch->branch() ;
     3043#ifdef COIN_HAS_NTY
     3044                    if (orbits) {
     3045                      // can fix all in orbit
     3046                      int fixOrbit = orbits[iObject];
     3047                      if (fixOrbit>=0) {
     3048                        //printf("fixing all in orbit %d for column %d\n",fixOrbit,iObject);
     3049                        for (int i=0;i<numberColumns;i++) {
     3050                          if (orbits[i]==fixOrbit)
     3051                            solver->setColUpper(i,0.0);
     3052                        }
     3053                      }
     3054                    }
     3055#endif
    29183056                    solver->solveFromHotStart() ;
    29193057                    bool needHotStartUpdate = false;
     
    36933831      }
    36943832    }
     3833#ifdef COIN_HAS_NTY
     3834    if (orbitOption&&kColumn>=0) {
     3835      CbcSymmetry * symmetryInfo = model->symmetryInfo();
     3836      CbcNodeInfo * infoX = lastNode ? lastNode->nodeInfo() : NULL;
     3837      bool worthTrying = false;
     3838      if (infoX) {
     3839        CbcNodeInfo * info = infoX;
     3840        for (int i=0;i<NTY_BAD_DEPTH;i++) {
     3841          if (!info->parent()) {
     3842            worthTrying = true;
     3843            break;
     3844          }
     3845          info = info->parent();
     3846          if (info->symmetryWorked()) {
     3847            worthTrying = true;
     3848            break;
     3849          }
     3850        }
     3851      } else {
     3852        worthTrying=true;
     3853      }
     3854      if (symmetryInfo && worthTrying) {
     3855        if (orbitOption==1) {
     3856          symmetryInfo->ChangeBounds(solver->getColLower(),
     3857                                     solver->getColUpper(),
     3858                                     solver->getNumCols(),false);
     3859          symmetryInfo->Compute_Symmetry();
     3860          symmetryInfo->fillOrbits();
     3861        }
     3862        const int * orbits = symmetryInfo->whichOrbit();
     3863        if (orbits && orbits[kColumn]>=0) {
     3864          int numberUsefulOrbits = symmetryInfo->numberUsefulObjects();
     3865          if (numberUsefulOrbits<1000) {
     3866            delete branch_;
     3867            branch_ = new CbcOrbitalBranchingObject(model,kColumn,1,0,NULL);
     3868            if (infoX)
     3869              infoX->setSymmetryWorked();
     3870          }
     3871        }
     3872      }
     3873    }
     3874#endif
    36953875    if (model->logLevel()>1)
    36963876    printf ("Node %d depth %d unsatisfied %d sum %g obj %g guess %g branching on %d\n",
  • trunk/Cbc/src/CbcNodeInfo.hpp

    r1899 r2048  
    257257        2 - cuts
    258258        4 - basis!
     259        8 - just marked
     260        16 - symmetry branching worked
    259261    */
    260262    void deactivate(int mode = 3);
    261263    /// Say if normal
    262264    inline bool allActivated() const {
    263         return (active_ == 7);
     265        return ((active_&7) == 7);
    264266    }
    265267    /// Say if marked
     
    275277        active_ &= ~8;
    276278    }
     279    /// Get symmetry value (true worked at this node)
     280    inline bool symmetryWorked() const
     281    { return (active_&16) !=0;}
     282    /// Say symmetry worked at this node)
     283    inline void setSymmetryWorked()
     284    { active_ |= 16;}
    277285
    278286    /// Branching object for the parent
  • trunk/Cbc/src/CbcSolver.cpp

    r2043 r2048  
    32863286                            int logLevel = parameters_[slog].intValue();
    32873287                            int truncateColumns=COIN_INT_MAX;
     3288                            int truncateRows=-1;
     3289                            double * truncatedRhsLower=NULL;
     3290                            double * truncatedRhsUpper=NULL;
    32883291                            int * newPriorities=NULL;
    32893292                            // Reduce printout
     
    41614164                                int threshold =
    41624165                                  parameters_[whichParam(CBC_PARAM_INT_EXTRA_VARIABLES, numberParameters_, parameters_)].intValue();
    4163                                 if (threshold) {
     4166                                int more2 = parameters_[whichParam(CBC_PARAM_INT_MOREMOREMIPOPTIONS, numberParameters_, parameters_)].intValue();
     4167                                if (threshold || (more2&(512|1024)) != 0) {
    41644168                                  int numberColumns = solver2->getNumCols();
     4169                                  truncateRows = solver2->getNumRows();
     4170                                  bool modifiedModel=false;
    41654171                                  int highPriority=0;
    41664172                                  /*
     
    43664372                                                       lowerNew, upperNew);
    43674373                                      sprintf(generalPrint,"Replacing model - %d new variables",numberDifferentObj);
    4368                                       generalMessageHandler->message(CLP_GENERAL, generalMessages)
    4369                                         << generalPrint
    4370                                         << CoinMessageEol;
    4371                                       truncateColumns=numberColumns;
     4374                                      modifiedModel=true;
    43724375                                    }
    43734376                                    delete [] columnAdd;
     
    43784381                                  delete [] which;
    43794382                                  delete [] obj;
     4383                                  if ((more2&(512|1024)) != 0) {
     4384                                    // try for row slacks etc
     4385                                    // later do row branching
     4386                                    int iRow, iColumn;
     4387                                    int numberColumns = solver2->getNumCols();
     4388                                    int numberRows = solver2->getNumRows();
     4389                                    int fudgeObjective = more2&512;
     4390                                    int addSlacks = more2&1024;
     4391                                    if (fudgeObjective) {
     4392                                      bool moveObj = false;
     4393                                      fudgeObjective = 0;
     4394                                      const double * objective = solver2->getObjCoefficients();
     4395                                      const double * columnLower = solver2->getColLower();
     4396                                      const double * columnUpper = solver2->getColUpper();
     4397                                      double * newValues = new double [numberColumns+1];
     4398                                      int * newColumn = new int [numberColumns+1];
     4399                                      bool allInteger=true;
     4400                                      int n=0;
     4401                                      double newLower = 0.0;
     4402                                      double newUpper = 0.0;
     4403                                      for (iColumn=0;iColumn<numberColumns;iColumn++) {
     4404                                        if (objective[iColumn]) {
     4405                                          if (!solver2->isInteger(iColumn)) {
     4406                                            allInteger=false;
     4407                                            break;
     4408                                          } else {
     4409                                            double value = objective[iColumn];
     4410                                            double nearest = floor(value+0.5);
     4411                                            if (fabs(value-nearest)>1.0e-8) {
     4412                                              allInteger=false;
     4413                                              break;
     4414                                            } else {
     4415                                              newValues[n]=nearest;
     4416                                              newColumn[n++]=iColumn;
     4417                                              if (nearest>0.0) {
     4418                                                newLower += CoinMax(columnLower[iColumn],-1.0e20)*nearest;
     4419                                                newUpper += CoinMin(columnUpper[iColumn],1.0e20)*nearest;
     4420                                              } else {
     4421                                                newUpper += CoinMax(columnLower[iColumn],-1.0e20)*nearest;
     4422                                                newLower += CoinMin(columnUpper[iColumn],1.0e20)*nearest;
     4423                                              }
     4424                                            }
     4425                                          }
     4426                                        }
     4427                                      }
     4428                                      if (allInteger && n) {
     4429                                        fudgeObjective = n;
     4430                                        solver2->addCol(0,NULL,NULL,newLower,newUpper,0.0,"obj_col");
     4431                                        solver2->setInteger(numberColumns);
     4432                                        newValues[n]=-1.0;
     4433                                        newColumn[n++]=numberColumns;
     4434                                        solver2->addRow(n,newColumn,newValues,0.0,0.0);
     4435                                        if (moveObj) {
     4436                                          memset(newValues,0,numberColumns*sizeof(double));
     4437                                          newValues[numberColumns]=1.0;
     4438                                          solver2->setObjective(newValues);
     4439                                        }
     4440                                        numberRows++;
     4441                                        numberColumns++;
     4442                                      }
     4443                                      delete [] newValues;
     4444                                      delete [] newColumn;
     4445                                    }
     4446                                    if (addSlacks) {
     4447                                      bool moveObj = false;
     4448                                      addSlacks=0;
     4449                                      // get row copy
     4450                                      const CoinPackedMatrix * matrix = solver2->getMatrixByRow();
     4451                                      const double * element = matrix->getElements();
     4452                                      const int * column = matrix->getIndices();
     4453                                      const CoinBigIndex * rowStart = matrix->getVectorStarts();
     4454                                      const int * rowLength = matrix->getVectorLengths();
     4455                                      const double * rowLower = solver2->getRowLower();
     4456                                      const double * rowUpper = solver2->getRowUpper();
     4457                                      const double * columnLower = solver2->getColLower();
     4458                                      const double * columnUpper = solver2->getColUpper();
     4459                                     
     4460                                      // maximum space for additional columns
     4461                                      CoinBigIndex * newColumnStart = new CoinBigIndex[numberRows+1];
     4462                                      newColumnStart[0]=0;
     4463                                      int * newRow = new int [numberRows];
     4464                                      double * newElement = new double [numberRows];
     4465                                      double * newObjective = new double [numberRows];
     4466                                      double * newColumnLower = new double [numberRows];
     4467                                      double * newColumnUpper = new double [numberRows];
     4468                                      double * oldObjective = CoinCopyOfArray(solver2->getObjCoefficients(),
     4469                                                                              numberColumns);
     4470                                      for (iRow=0;iRow<numberRows;iRow++) {
     4471                                        if (rowLower[iRow]!=rowUpper[iRow]) {
     4472                                          bool allInteger=true;
     4473                                          double newLower = 0.0;
     4474                                          double newUpper = 0.0;
     4475                                          double constantObjective=0.0;
     4476                                          for (int j=rowStart[iRow];j<rowStart[iRow]+rowLength[iRow];j++) {
     4477                                            int iColumn = column[j];
     4478                                            if (!solver2->isInteger(iColumn)) {
     4479                                              allInteger=false;
     4480                                              break;
     4481                                            } else {
     4482                                              double value = element[j];
     4483                                              double nearest = floor(value+0.5);
     4484                                              if (fabs(value-nearest)>1.0e-8) {
     4485                                                allInteger=false;
     4486                                                break;
     4487                                              } else {
     4488                                                if (!oldObjective[iColumn])
     4489                                                  constantObjective=COIN_DBL_MAX;
     4490                                                if (!constantObjective) {
     4491                                                  constantObjective=oldObjective[iColumn]/nearest;
     4492                                                } else if (constantObjective!=COIN_DBL_MAX) {
     4493                                                  double newConstant=oldObjective[iColumn]/nearest;
     4494                                                  if (constantObjective>0.0) {
     4495                                                    if (newConstant<=0.0)
     4496                                                      constantObjective=COIN_DBL_MAX;
     4497                                                    else
     4498                                                      constantObjective=CoinMin(constantObjective,newConstant);
     4499                                                  } else {
     4500                                                    if (newConstant>=0.0)
     4501                                                      constantObjective=COIN_DBL_MAX;
     4502                                                    else
     4503                                                      constantObjective=CoinMax(constantObjective,newConstant);
     4504                                                  }
     4505                                                }
     4506                                                if (nearest>0.0) {
     4507                                                  newLower += CoinMax(columnLower[iColumn],-1.0e20)*nearest;
     4508                                                  newUpper += CoinMin(columnUpper[iColumn],1.0e20)*nearest;
     4509                                                } else {
     4510                                                  newUpper += CoinMax(columnLower[iColumn],-1.0e20)*nearest;
     4511                                                  newLower += CoinMin(columnUpper[iColumn],1.0e20)*nearest;
     4512                                                }
     4513                                              }
     4514                                            }
     4515                                          }
     4516                                          if (allInteger) {
     4517                                            newColumnStart[addSlacks+1]=addSlacks+1;
     4518                                            newRow[addSlacks]=iRow;
     4519                                            newElement[addSlacks]=-1.0;
     4520                                            newObjective[addSlacks] = 0.0;
     4521                                            if (moveObj && constantObjective != COIN_DBL_MAX) {
     4522                                              // move some of objective here if looks constant
     4523                                              newObjective[addSlacks]=constantObjective;
     4524                                              for (int j=rowStart[iRow];j<rowStart[iRow]+rowLength[iRow];j++) {
     4525                                                int iColumn = column[j];
     4526                                                double value = element[j];
     4527                                                double nearest = floor(value+0.5);
     4528                                                oldObjective[iColumn] -= nearest*constantObjective;
     4529                                              }
     4530                                            }
     4531                                            newColumnLower[addSlacks] = CoinMax(newLower,ceil(rowLower[iRow]));;
     4532                                            newColumnUpper[addSlacks] = CoinMin(newUpper,floor(rowUpper[iRow]));
     4533                                            addSlacks++;
     4534                                          }
     4535                                        }
     4536                                      }
     4537                                      if (addSlacks) {
     4538                                        solver2->setObjective(oldObjective);
     4539                                        solver2->addCols(addSlacks,newColumnStart,newRow,newElement,
     4540                                                         newColumnLower,newColumnUpper,newObjective);
     4541                                        truncatedRhsLower = CoinCopyOfArray(solver2->getRowLower(),numberRows);
     4542                                        truncatedRhsUpper = CoinCopyOfArray(solver2->getRowUpper(),numberRows);
     4543                                        for (int j=0;j<addSlacks;j++) {
     4544                                          int iRow = newRow[j];
     4545                                          solver2->setRowLower(iRow,0.0);
     4546                                          solver2->setRowUpper(iRow,0.0);
     4547                                          int iColumn = j+numberColumns;
     4548                                          solver2->setInteger(iColumn);
     4549                                          std::string name = solver2->getRowName(iRow);
     4550                                          name += "_int";
     4551                                          solver2->setColName(iColumn,name);
     4552                                        }
     4553                                      }
     4554                                    }
     4555                                    if (fudgeObjective||addSlacks) {
     4556                                      modifiedModel=true;
     4557                                      if (fudgeObjective && addSlacks) {
     4558                                        sprintf(generalPrint,"Objective integer added with %d elements and %d Integer slacks added",
     4559                                                fudgeObjective,addSlacks);
     4560                                      } else if (fudgeObjective) {
     4561                                        // just objective
     4562                                        sprintf(generalPrint,"Objective integer added with %d elements",
     4563                                               fudgeObjective);
     4564                                        more2 &= ~1024;
     4565                                      } else {
     4566                                        // just slacks
     4567                                        sprintf(generalPrint,"%d Integer slacks added",addSlacks);
     4568                                        more2 &= ~512;
     4569                                      }
     4570                                    } else {
     4571                                      more2 &= ~(512|1024);
     4572                                    }
     4573                                    parameters_[whichParam(CBC_PARAM_INT_MOREMOREMIPOPTIONS, numberParameters_, parameters_)].setIntValue(more2);
     4574                                  }
     4575                                  if (modifiedModel) {
     4576                                    generalMessageHandler->message(CLP_GENERAL, generalMessages)
     4577                                      << generalPrint
     4578                                      << CoinMessageEol;
     4579                                    truncateColumns=numberColumns;
     4580                                  }
    43804581                                }
    43814582                                babModel_->assignSolver(solver2);
     
    62496450                                }
    62506451                                // We may have priorities from extra variables
     6452                                int more2 = parameters_[whichParam(CBC_PARAM_INT_MOREMOREMIPOPTIONS, numberParameters_, parameters_)].intValue();
    62516453                                if(newPriorities ) {
    62526454                                  if (truncateColumns<babModel_->getNumCols()) {
     
    62546456                                    babModel_->passInPriorities(newPriorities,false);
    62556457                                  }
     6458                                  delete [] newPriorities;
     6459                                } else if ((more2&(512|1024)) != 0) {
     6460                                  babModel_->findIntegers(true);
     6461                                  int numberIntegers = babModel_->numberIntegers();
     6462                                  int * newPriorities = new int [numberIntegers];
     6463                                  int n = numberIntegers - (babModel_->getNumCols()-truncateColumns);
     6464                                  for (int i=0;i<n;i++)
     6465                                    newPriorities[i]=babModel_->priority(i);
     6466#if 1
     6467                                  int ixxxxxx =
     6468                                    parameters_[whichParam(CBC_PARAM_INT_MAXNODES, numberParameters_, parameters_)].intValue();
     6469                                  int obj_priority=1000;
     6470                                  int slack_priority=1000;
     6471                                  if (ixxxxxx>=1000000&&ixxxxxx<1010000) {
     6472                                    ixxxxxx -= 1000000;
     6473                                    if (ixxxxxx == 0) {
     6474                                      obj_priority=1000;
     6475                                      slack_priority=1000;
     6476                                    } else if(ixxxxxx == 1) {
     6477                                      obj_priority=10000;
     6478                                      slack_priority=10000;
     6479                                    } else if(ixxxxxx == 2) {
     6480                                      obj_priority=100;
     6481                                      slack_priority=100;
     6482                                    } else if(ixxxxxx == 3) {
     6483                                      obj_priority=100;
     6484                                      slack_priority=10000;
     6485                                    } else if(ixxxxxx == 4) {
     6486                                      obj_priority=10000;
     6487                                      slack_priority=100;
     6488                                    } else if(ixxxxxx == 5) {
     6489                                      obj_priority=100;
     6490                                      slack_priority=200;
     6491                                    } else if(ixxxxxx == 6) {
     6492                                      obj_priority=200;
     6493                                      slack_priority=100;
     6494                                    } else {
     6495                                      abort();
     6496                                    }
     6497                                  }
     6498                                  if ((more2&512)!=0) {
     6499                                    newPriorities[n++]=obj_priority;
     6500                                  }
     6501                                  if ((more2&1024)!=0) {
     6502                                    for (int i=n;i<numberIntegers;i++)
     6503                                      newPriorities[i]=slack_priority;
     6504                                  }
     6505#else
     6506#define PRIORITY_TRY 0
     6507#if PRIORITY_TRY == 0
     6508#define OBJ_PRIORITY 1000
     6509#define SLACK_PRIORITY 1000
     6510#elif PRIORITY_TRY == 1
     6511#define OBJ_PRIORITY 10000
     6512#define SLACK_PRIORITY 10000
     6513#elif PRIORITY_TRY == 2
     6514#define OBJ_PRIORITY 100
     6515#define SLACK_PRIORITY 100
     6516#elif PRIORITY_TRY == 3
     6517#define OBJ_PRIORITY 100
     6518#define SLACK_PRIORITY 10000
     6519#elif PRIORITY_TRY == 4
     6520#define OBJ_PRIORITY 10000
     6521#define SLACK_PRIORITY 100
     6522#elif PRIORITY_TRY == 5
     6523#define OBJ_PRIORITY 100
     6524#define SLACK_PRIORITY 200
     6525#elif PRIORITY_TRY == 6
     6526#define OBJ_PRIORITY 200
     6527#define SLACK_PRIORITY 100
     6528#endif
     6529                                  if ((more2&512)!=0) {
     6530                                    newPriorities[n++]=OBJ_PRIORITY;
     6531                                  }
     6532                                  if ((more2&1024)!=0) {
     6533                                    for (int i=n;i<numberIntegers;i++)
     6534                                      newPriorities[i]=SLACK_PRIORITY;
     6535                                  }
     6536#endif
     6537                                  babModel_->passInPriorities(newPriorities,false);
    62566538                                  delete [] newPriorities;
    62576539                                }
     
    63696651                                  babModel_->setSpecialOptions(babModel_->specialOptions() &(~(512|32768)));
    63706652                                babModel_->setMoreSpecialOptions2(parameters_[whichParam(CBC_PARAM_INT_MOREMOREMIPOPTIONS, numberParameters_, parameters_)].intValue());
     6653                                {
     6654                                  int jParam = whichParam(CBC_PARAM_STR_ORBITAL,
     6655                                                        numberParameters_, parameters_);
     6656                                  if(parameters_[jParam].currentOptionAsInteger()) {
     6657                                    int k = parameters_[jParam].currentOptionAsInteger();
     6658                                    babModel_->setMoreSpecialOptions2(babModel_->moreSpecialOptions2() | (k*128));
     6659                                  }
     6660                                }
    63716661                                babModel_->branchAndBound(statistics);
    63726662                                if (truncateColumns<babModel_->solver()->getNumCols()) {
     
    63796669                                    delStuff[i]=i+truncateColumns;
    63806670                                  solverX->deleteCols(numberDelete,delStuff);
     6671                                  numberDelete = numberRows-truncateRows;
    63816672                                  for (int i=0;i<numberDelete;i++)
    6382                                     delStuff[i]=i+numberRows-numberDelete;
     6673                                    delStuff[i]=i+truncateRows;
    63836674                                  solverX->deleteRows(numberDelete,delStuff);
    63846675                                  delete [] delStuff;
     6676                                  if (truncatedRhsLower) {
     6677                                    numberRows=solverX->getNumRows();
     6678                                    for (int i=0;i<numberRows;i++) {
     6679                                      solverX->setRowLower(i,truncatedRhsLower[i]);
     6680                                      solverX->setRowUpper(i,truncatedRhsUpper[i]);
     6681                                    }
     6682                                    delete [] truncatedRhsLower;
     6683                                    delete [] truncatedRhsUpper;
     6684                                  }
    63856685                                }
    63866686                                //#define CLP_FACTORIZATION_INSTRUMENT
  • trunk/Cbc/src/Makefile.am

    r2016 r2048  
    8888        CbcStrategy.cpp CbcStrategy.hpp \
    8989        CbcSubProblem.cpp CbcSubProblem.hpp \
     90        CbcSymmetry.cpp CbcSymmetry.hpp \
    9091        CbcThread.cpp CbcThread.hpp \
    9192        CbcTree.cpp CbcTree.hpp \
  • trunk/Cbc/src/Makefile.in

    r2016 r2048  
    115115        CbcSimpleIntegerDynamicPseudoCost.lo \
    116116        CbcSimpleIntegerPseudoCost.lo CbcSOS.lo CbcStatistics.lo \
    117         CbcStrategy.lo CbcSubProblem.lo CbcThread.lo CbcTree.lo \
    118         CbcTreeLocal.lo
     117        CbcStrategy.lo CbcSubProblem.lo CbcSymmetry.lo CbcThread.lo \
     118        CbcTree.lo CbcTreeLocal.lo
    119119libCbc_la_OBJECTS = $(am_libCbc_la_OBJECTS)
    120120@DEPENDENCY_LINKING_TRUE@libCbcSolver_la_DEPENDENCIES =  \
     
    325325GRB_LIBS = @GRB_LIBS@
    326326GRB_LIBS_INSTALLED = @GRB_LIBS_INSTALLED@
     327GREP = @GREP@
    327328HAVE_EXTERNALS_FALSE = @HAVE_EXTERNALS_FALSE@
    328329HAVE_EXTERNALS_TRUE = @HAVE_EXTERNALS_TRUE@
     
    402403PACKAGE_STRING = @PACKAGE_STRING@
    403404PACKAGE_TARNAME = @PACKAGE_TARNAME@
     405PACKAGE_URL = @PACKAGE_URL@
    404406PACKAGE_VERSION = @PACKAGE_VERSION@
    405407PATH_SEPARATOR = @PATH_SEPARATOR@
     
    445447abs_source_dir = @abs_source_dir@
    446448ac_c_preproc_warn_flag = @ac_c_preproc_warn_flag@
    447 ac_ct_AR = @ac_ct_AR@
    448449ac_ct_CC = @ac_ct_CC@
    449450ac_ct_CXX = @ac_ct_CXX@
    450451ac_ct_F77 = @ac_ct_F77@
    451 ac_ct_PKG_CONFIG = @ac_ct_PKG_CONFIG@
    452 ac_ct_RANLIB = @ac_ct_RANLIB@
    453 ac_ct_STRIP = @ac_ct_STRIP@
    454452ac_cxx_preproc_warn_flag = @ac_cxx_preproc_warn_flag@
    455453am__fastdepCC_FALSE = @am__fastdepCC_FALSE@
     
    475473coin_have_doxygen = @coin_have_doxygen@
    476474datadir = @datadir@
     475datarootdir = @datarootdir@
     476docdir = @docdir@
     477dvidir = @dvidir@
    477478exec_prefix = @exec_prefix@
    478479have_autoconf = @have_autoconf@
     
    485486host_os = @host_os@
    486487host_vendor = @host_vendor@
     488htmldir = @htmldir@
    487489includedir = @includedir@
    488490infodir = @infodir@
     
    490492libdir = @libdir@
    491493libexecdir = @libexecdir@
     494localedir = @localedir@
    492495localstatedir = @localstatedir@
    493496mandir = @mandir@
    494497mkdir_p = @mkdir_p@
    495498oldincludedir = @oldincludedir@
     499pdfdir = @pdfdir@
    496500prefix = @prefix@
    497501program_transform_name = @program_transform_name@
     502psdir = @psdir@
    498503sbindir = @sbindir@
    499504sharedstatedir = @sharedstatedir@
     
    582587        CbcStrategy.cpp CbcStrategy.hpp \
    583588        CbcSubProblem.cpp CbcSubProblem.hpp \
     589        CbcSymmetry.cpp CbcSymmetry.hpp \
    584590        CbcThread.cpp CbcThread.hpp \
    585591        CbcTree.cpp CbcTree.hpp \
     
    935941@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcStrategy.Plo@am__quote@
    936942@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcSubProblem.Plo@am__quote@
     943@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcSymmetry.Plo@am__quote@
    937944@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcThread.Plo@am__quote@
    938945@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CbcTree.Plo@am__quote@
Note: See TracChangeset for help on using the changeset viewer.