Changeset 3039


Ignore:
Timestamp:
May 11, 2020 1:10:42 PM (2 months ago)
Author:
forrest
Message:

try and have a faster version for symmetry

Location:
trunk/src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/CbcSymmetry.cpp

    r2995 r3039  
    3232#include "CbcSymmetry.hpp"
    3333#include "CbcBranchingObject.hpp"
     34#include "CbcSimpleInteger.hpp"
    3435#include "CoinTime.hpp"
    3536#define NAUTY_MAX_LEVEL 0
     
    4344 */
    4445static int nautyBranchCalls_ = 0;
    45 static int lastNautyBranchCalls_ = 0;
     46static int lastNautyBranchSucceeded_ = 0;
    4647static int nautyBranchSucceeded_ = 0;
    4748static int nautyFixCalls_ = 0;
    48 static int lastNautyFixCalls_ = 0;
     49static int lastNautyFixSucceeded_ = 0;
    4950static int nautyFixSucceeded_ = 0;
    5051static double nautyTime_ = 0.0;
    5152static double nautyFixes_ = 0.0;
    5253static double nautyOtherBranches_ = 0.0;
     54static char message_[100];
    5355
    5456void CbcSymmetry::Node::node(int i, double c, double l, double u, int cod, int s)
     
    7779static int calls = 0;
    7880static int maxLevel = 0;
     81static CbcSymmetry * baseSymmetry=NULL;
    7982static void
    8083userlevelproc(int *lab, int *ptn, int level, int *orbits, statsblk *stats,
     
    8487  calls++;
    8588  if (level > maxLevel) {
    86     printf("Level %d after %d calls\n", level, calls);
     89    sprintf(message_,"Nauty:: level %d after %d calls", level, calls);
    8790    maxLevel = level;
    8891  }
     
    9396  return;
    9497}
     98
     99static void userautomproc(int numGenerators,
     100                   int * perm,
     101                   int * orbits, int numorbits,
     102                   int stabvertex, int n)
     103{
     104  //printf("count %d\n",numGenerators);
     105  if (numGenerators>64)
     106    return;
     107  assert (baseSymmetry);
     108  int numberColumns = baseSymmetry->numberColumns();
     109  int * workperm = new int [n];
     110  int * orbitsX = new int [numberColumns];
     111  memset(workperm,0,n*sizeof(int));
     112  for (int i=0;i<numberColumns;i++)
     113    orbitsX[i]=-1;
     114  int numberPerms=0;
     115  int numberInPerm=-1;
     116  int firstL=-1;
     117  for (int i = 0; i < n; ++i) {
     118    if (workperm[i] == 0 && perm[i] != i) {
     119      int nRow=0;
     120      int nCol=0;
     121      int l = i;
     122      if (l<numberColumns) {
     123#ifdef PRINT_CBCAUTO
     124        printf("%d ",l);
     125#endif
     126        nCol++;
     127        firstL=l;
     128        assert (orbitsX[l]<0);
     129      } else {
     130        nRow++;
     131      }
     132      int k;
     133      do {
     134          k = l;
     135          l = perm[l];
     136          workperm[k] = 1;
     137          if (l != i) {
     138            if (l<numberColumns) {
     139#ifdef PRINT_CBCAUTO
     140              printf("%d ",l);
     141#endif
     142              nCol++;
     143              assert (orbitsX[l]<0);
     144              orbitsX[k]=l;
     145            } else {
     146              nRow++;
     147            }
     148          }
     149      } while (l != i);
     150      if (nCol) {
     151        orbitsX[k]=firstL;
     152#ifdef PRINT_CBCAUTO
     153        printf("\n");
     154#endif
     155      }
     156      assert (nCol==0||nRow==0);
     157      int nThis=nCol+nRow;
     158      if (numberInPerm<0) {
     159        numberInPerm=nThis;
     160      } else {
     161        assert (numberInPerm==nThis);
     162      }
     163      if (nCol>0)
     164        numberPerms++;
     165    }
     166  }
     167  //printf("%d permutations, %d in each\n",numberPerms,numberInPerm);
     168  delete [] workperm;
     169  if (numberPerms) {
     170    cbc_permute permute;
     171    permute.numberInPerm=numberInPerm;
     172    permute.numberPerms=numberPerms;
     173    permute.orbits=orbitsX;
     174    baseSymmetry->addPermutation(permute);
     175  } else {
     176    delete [] orbitsX;
     177  }
     178}
    95179void CbcSymmetry::Compute_Symmetry() const
    96180{
    97181
    98182  nauty_info_->options()->userlevelproc = userlevelproc;
     183  message_[0]='\0';
    99184  std::sort(node_info_.begin(), node_info_.end(), node_sort);
    100185
     
    134219  int returnCode = 0;
    135220  bool printSomething = true;
     221  if (type == 1 && (model->moreSpecialOptions2()&(131072|262144)) == 131072)
     222    return 0;
    136223  if (type) {
    137224    double branchSuccess = 0.0;
     
    141228    if (nautyFixSucceeded_)
    142229      fixSuccess = nautyFixes_ / nautyFixSucceeded_;
    143     if (nautyBranchCalls_ > lastNautyBranchCalls_ || nautyFixCalls_ > lastNautyFixCalls_) {
     230    if (nautyBranchSucceeded_ > lastNautyBranchSucceeded_ || nautyFixSucceeded_ > lastNautyFixSucceeded_) {
    144231      sprintf(general, "Orbital branching tried %d times, succeeded %d times - average extra %7.3f, fixing %d times (%d, %7.3f)",
    145232        nautyBranchCalls_, nautyBranchSucceeded_, branchSuccess,
    146233        nautyFixCalls_, nautyFixSucceeded_, fixSuccess);
    147       lastNautyBranchCalls_ = nautyBranchCalls_;
    148       lastNautyFixCalls_ = nautyFixCalls_;
     234      if ((model->moreSpecialOptions2()&(131072|262144)) == 131072) {
     235        sprintf(general, "Orbital branching succeeded %d times - average extra %7.3f, fixing (%d, %7.3f)",
     236                nautyBranchSucceeded_, branchSuccess,
     237                nautyFixSucceeded_, fixSuccess);
     238        model->messageHandler()->message(CBC_GENERAL,
     239                                         model->messages())
     240          << general << CoinMessageEol;
     241        return 0;
     242      }
     243      lastNautyBranchSucceeded_ = nautyBranchSucceeded_;
     244      lastNautyFixSucceeded_ = nautyFixSucceeded_;
    149245    } else {
    150246      printSomething = false;
     
    154250    if (!nauty_info_->errorStatus()) {
    155251      if (returnCode && numberUsefulOrbits_) {
     252        if ((model->moreSpecialOptions2()&(131072|262144)) != 131072)
     253          model->messageHandler()->message(CBC_GENERAL,
     254                                           model->messages())
     255            << message_ << CoinMessageEol;
    156256        sprintf(general, "Nauty: %d orbits (%d useful covering %d variables), %d generators, group size: %g - dense size %d, sparse %d - took %g seconds",
    157257          nauty_info_->getNumOrbits(), numberUsefulOrbits_, numberUsefulObjects_,
    158258          nauty_info_->getNumGenerators(),
    159259          nauty_info_->getGroupSize(),
    160           whichOrbit_[0], whichOrbit_[1], nautyTime_);
     260          stats_[0],stats_[1], nautyTime_);
    161261      } else {
    162         if ((model->moreSpecialOptions2() & (128 | 256)) != (128 | 256))
     262        int options2 = model->moreSpecialOptions2();
     263        if ((options2 & (128 | 256)) != (128 | 256)) {
    163264          sprintf(general, "Nauty did not find any useful orbits in time %g", nautyTime_);
    164         else
    165           sprintf(general, "Nauty did not find any useful orbits - but keeping Nauty on");
     265        } else {
     266          if ((options2 & 131072) == 0) {
     267            sprintf(general, "Nauty did not find any useful orbits - but keeping Nauty on");
     268          } else {
     269            sprintf(general, "Nauty did not find any useful orbits in time %g", nautyTime_);
     270            model->setMoreSpecialOptions2(options2 & ~(128 | 256 | 131072));
     271          }
     272        }
    166273      }
    167274    } else {
     
    176283      model->messages())
    177284      << general << CoinMessageEol;
     285  if (!type && (model->moreSpecialOptions2()&(131072|262144)) !=
     286                131072)
     287    Print_Orbits ();
     288#if 0
     289  if (!type && (model->moreSpecialOptions2()&(131072|262144)) != 0) {
     290    printf("Setting priorities on symmetric\n");
     291    int * priorities = new int [numberColumns_];
     292    for (int i=0;i<numberColumns_;i++)
     293      priorities[i] = -1;
     294    for (int iOrbit=0;iOrbit<numberColumns_;iOrbit++) {
     295      int n = 0;
     296      for (int i=0;i<numberColumns_;i++) {
     297        if (whichOrbit_[i]==iOrbit)
     298          n++;
     299      }
     300      if (!n)
     301        break;
     302      for (int i=0;i<numberColumns_;i++) {
     303        if (whichOrbit_[i]==iOrbit)
     304          priorities[i] = 1000-n;
     305      }
     306    }     
     307    OsiObject **objects = model->objects();
     308    int numberObjects = model->numberObjects();
     309    for (int iObj = 0; iObj < numberObjects; iObj++) {
     310      CbcSimpleInteger *obj = dynamic_cast< CbcSimpleInteger * >(objects[iObj]);
     311      if (!obj)
     312        continue;
     313      int iColumn = obj->columnNumber();
     314      int iPriority = priorities[iColumn];
     315      if (iPriority > 0)
     316        obj->setPriority(iPriority);
     317    }
     318    delete [] priorities;
     319  }
     320#endif
    178321  return returnCode;
    179322}
    180323
    181 void CbcSymmetry::Print_Orbits() const
     324void CbcSymmetry::Print_Orbits(int type) const
    182325{
    183326
     
    214357
    215358    std::vector< std::vector< int > > *orbits = nauty_info_->getOrbits();
    216 
    217     for (std::vector< std::vector< int > >::iterator i = orbits->begin(); i != orbits->end(); ++i) {
    218 
    219       printf("Orbit %d: ", orbCnt++);
    220 
    221       for (std::vector< int >::iterator j = i->begin(); j != i->end(); ++j)
    222         printf(" %d", *j);
    223 
    224       printf("\n");
    225     }
     359    if (type) {
     360      for (std::vector< std::vector< int > >::iterator i = orbits->begin(); i != orbits->end(); ++i) {
     361
     362        printf("Orbit %d: ", orbCnt++);
     363
     364        for (std::vector< int >::iterator j = i->begin(); j != i->end(); ++j)
     365          printf(" %d", *j);
     366       
     367        printf("\n");
     368      }
     369    } else {
     370      for (std::vector< std::vector< int > >::iterator i = orbits->begin(); i != orbits->end(); ++i) {
     371        bool useful=false;
     372        if (i->size() > 1) {
     373          for (std::vector< int >::iterator j = i->begin(); j != i->end(); ++j) {
     374            if (*j < numberColumns_) {
     375              useful = true;
     376              break;
     377            }
     378          }
     379          if (useful) {
     380            printf("Orbit %d: ", orbCnt++);
     381           
     382            for (std::vector< int >::iterator j = i->begin(); j != i->end(); ++j)
     383              printf(" %d", *j);
     384           
     385            printf("\n");
     386          }
     387        }
     388      }
     389    }
     390    delete orbits;
    226391  }
    227392#endif
     
    246411void CbcSymmetry::fillOrbits()
    247412{
    248   for (int i = 0; i < numberColumns_; i++)
     413  for (int i = 0; i < numberColumns_; i++) {
    249414    whichOrbit_[i] = -1;
     415  }
    250416  numberUsefulOrbits_ = 0;
    251417  numberUsefulObjects_ = 0;
     
    256422    int nUseful = 0;
    257423    int jColumn = -2;
     424   
    258425    for (std::vector< int >::iterator j = i->begin(); j != i->end(); ++j) {
    259426      int iColumn = *j;
     
    344511    //printf("Var %d  INPUT lower bound: %f   upper bound %f \n", i, node_info_[i].get_lb(), node_info_[i].get_ub());
    345512  }
     513}
     514/* for simple stuff - returns number if can use saved orbit (mode 1)
     515   otherwise may fix and return number (mode 0) */
     516int
     517CbcSymmetry::changeBounds(int iColumn, double * saveLower,
     518                          double * saveUpper,
     519                          OsiSolverInterface * solver,
     520                          int mode) const
     521{
     522  if (saveUpper[iColumn]>1.0e12 || whichOrbit_[iColumn]<0)
     523    return 0; // only 0-1 at present
     524  if (mode)
     525    nautyBranchCalls_++;
     526  int nFixed = 0;
     527  int * originalUpper = whichOrbit_ + numberColumns_;
     528  double * columnLower = saveLower;
     529  double * columnUpper = saveUpper;
     530  double saveUp = columnUpper[iColumn];
     531  columnUpper[iColumn] = 0.0;//solver->getColUpper()[iColumn];
     532  int * marked = originalUpper + numberColumns_;
     533  int * whichMarked = marked + numberColumns_;
     534  int * save = whichOrbit_+4*numberColumns_;
     535  memset(marked,0,numberColumns_*sizeof(int));
     536  for (int iPerm = 0;iPerm < numberPermutations_;iPerm++) {
     537    const int * orbit = permutations_[iPerm].orbits;
     538    if (orbit[iColumn]<0)
     539      continue;
     540    int nMarked = 0;
     541    int nTotalOdd = 0;
     542    int goodOddOne = -1;
     543    for (int i=0;i<numberColumns_;i++) {
     544      if (orbit[i]>=0 && !marked[i]) {
     545        // OK is all same or one fixed to 0 and rest same
     546        int oddOne = -1;
     547        int nOdd = 0;
     548        int first = i;
     549        marked[i] = 1;
     550        whichMarked[nMarked++] = i;
     551        int j = orbit[i];
     552        int lower = static_cast<int>(columnLower[i]);
     553        if (lower) nOdd=999; //temp
     554        int upper = static_cast<int>(columnUpper[i]);
     555        if (upper==0) {
     556          int upperj = static_cast<int>(columnUpper[j]);
     557          if (upperj) {
     558            oddOne = i;
     559            nOdd = 1;
     560            upper = upperj;
     561          }
     562        }
     563        while (j!=i) {
     564          marked[j] = 1;
     565          whichMarked[nMarked++] = j;
     566          int lowerj = static_cast<int>(columnLower[j]);
     567          if (lowerj) nOdd=999; //temp
     568          int upperj = static_cast<int>(columnUpper[j]);
     569          if (lower!=lowerj || upper != upperj) {
     570            if (nOdd) {
     571              // bad
     572              nOdd = numberColumns_;
     573            } else {
     574              oddOne = j;
     575              nOdd = 1;
     576            }
     577          }
     578          j = orbit[j];
     579        }
     580        if (!nOdd) {
     581        } else if (nOdd==1) {
     582          if (!nTotalOdd)
     583            goodOddOne = oddOne;
     584          nTotalOdd ++;
     585        } else {
     586          nTotalOdd = -2*numberColumns_;
     587        }
     588      }
     589    }
     590    //printf("permutation %d had %d odd\n",iPerm,nTotalOdd);
     591    for (int i=0;i<nMarked;i++)
     592      marked[whichMarked[i]]=0;
     593    if (nTotalOdd==1) {
     594      int j = orbit[goodOddOne];
     595      if (columnUpper[goodOddOne]) {
     596        save[nFixed++]=goodOddOne;
     597        if (!mode)
     598          solver->setColUpper(goodOddOne,0.0);
     599      }
     600      while (j!=goodOddOne) {
     601        if (columnUpper[j]) {
     602          //printf("setting %d to zero\n",j);
     603          if (!mode)
     604            solver->setColUpper(j,0.0);
     605          save[nFixed++]=j;
     606        }
     607        j = orbit[j];
     608      }
     609    }
     610  }
     611  columnUpper[iColumn] = saveUp;
     612  if (mode && nFixed>0) {
     613    // done in CbcOrbital nautyBranchSucceeded_++;
     614    nautyOtherBranches_+=nFixed;
     615  }
     616  return nFixed;
     617}
     618int
     619CbcSymmetry::orbitalFixing2(OsiSolverInterface * solver)
     620{
     621  int nFixed = 0;
     622  int iCheck;
     623  const double * columnLower = solver->getColLower();
     624  const double * columnUpper = solver->getColUpper();
     625  for (iCheck=0;iCheck<numberColumns_;iCheck++) {
     626    if (whichOrbit_[iCheck]>=0 && !columnUpper[iCheck])
     627      break;
     628  }
     629  if (iCheck==numberColumns_)
     630    return 0;
     631  nautyFixCalls_ ++;
     632  int * originalUpper = whichOrbit_ + numberColumns_;
     633  int * marked = originalUpper + numberColumns_;
     634  int * whichMarked = marked + numberColumns_;
     635  int * save = whichOrbit_+4*numberColumns_;
     636  memset(marked,0,numberColumns_*sizeof(int));
     637  int possibleNauty = 0;
     638  for (int iPerm = 0;iPerm < numberPermutations_;iPerm++) {
     639    const int * orbit = permutations_[iPerm].orbits;
     640    int nMarked = 0;
     641    int nTotalOdd = 0;
     642    int goodOddOne = -1;
     643    for (int i=0;i<numberColumns_;i++) {
     644      if (orbit[i]>=0 && !marked[i]) {
     645        // OK is all same or one fixed to 0 and rest same
     646        int oddOne = -1;
     647        int nOdd = 0;
     648        int first = i;
     649        marked[i] = 1;
     650        whichMarked[nMarked++] = i;
     651        int j = orbit[i];
     652        int lower = static_cast<int>(columnLower[i]);
     653        if (lower) nOdd=999; //temp
     654        int upper = static_cast<int>(columnUpper[i]);
     655        if (upper==0) {
     656          int upperj = static_cast<int>(columnUpper[j]);
     657          if (upperj) {
     658            oddOne = i;
     659            nOdd = 1;
     660            upper = upperj;
     661          }
     662        }
     663        while (j!=i) {
     664          marked[j] = 1;
     665          whichMarked[nMarked++] = j;
     666          int lowerj = static_cast<int>(columnLower[j]);
     667          if (lowerj) nOdd=999; //temp
     668          int upperj = static_cast<int>(columnUpper[j]);
     669          if (lower!=lowerj || upper != upperj) {
     670            if (nOdd) {
     671              // bad
     672              nOdd = numberColumns_;
     673            } else {
     674              oddOne = j;
     675              nOdd = 1;
     676            }
     677          }
     678          j = orbit[j];
     679        }
     680        if (!nOdd) {
     681        } else if (nOdd==1) {
     682          if (!nTotalOdd)
     683            goodOddOne = oddOne;
     684          nTotalOdd ++;
     685        } else {
     686          nTotalOdd = -2*numberColumns_;
     687        }
     688      }
     689    }
     690    //printf("permutation %d had %d odd\n",iPerm,nTotalOdd);
     691    for (int i=0;i<nMarked;i++)
     692      marked[whichMarked[i]]=0;
     693    if (nTotalOdd==1) {
     694      nautyFixSucceeded_++;
     695      int j = orbit[goodOddOne];
     696      if (columnUpper[goodOddOne]) {
     697        nautyFixes_++;
     698        save[nFixed++]=goodOddOne;
     699        solver->setColUpper(goodOddOne,0.0);
     700      }
     701      while (j!=goodOddOne) {
     702        if (columnUpper[j]) {
     703          //printf("setting %d to zero\n",j);
     704          nautyFixes_++;
     705          solver->setColUpper(j,0.0);
     706          save[nFixed++]=j;
     707        }
     708        j = orbit[j];
     709      }
     710      possibleNauty++;
     711    } else if (!nTotalOdd) {
     712      possibleNauty++;
     713    }
     714  }
     715  if (!nFixed && !possibleNauty)
     716    nFixed = -1; // say no good from here on
     717  return nFixed;
    346718}
    347719void CbcSymmetry::setupSymmetry(CbcModel * model)
     
    6341006  }
    6351007  numberColumns_ = numberColumns;
    636   whichOrbit_ = new int[2 * numberColumns_];
     1008  whichOrbit_ = new int[5*numberColumns_];
     1009  for (int i = 0; i < 2*numberColumns_; i++)
     1010    whichOrbit_[i] = -1;
    6371011  nautyBranchCalls_ = 0;
    6381012  nautyBranchSucceeded_ = 0;
     
    6421016  nautyFixes_ = 0.0;
    6431017  nautyOtherBranches_ = 0.0;
     1018  lastNautyBranchSucceeded_ = 0;
     1019  int lastNautyFixSucceeded_ = 0;
     1020  if ((model->moreSpecialOptions2()&131072)!=0) {
     1021    baseSymmetry = this;
     1022    nauty_info_->options()->userautomproc = userautomproc;
     1023  }
    6441024  try {
    6451025    Compute_Symmetry();
     
    6521032  }
    6531033  fillOrbits();
    654   //whichOrbit_[2]=numberUsefulOrbits_;
     1034  int options2 =  model->moreSpecialOptions2();
     1035  if (numberUsefulOrbits_ && (options2&131072)!=0) {
     1036    // store original bounds for integers
     1037    // only do for 0 lower bound
     1038    int nPossible = 0;
     1039    int * originalUpper = whichOrbit_ + numberColumns_;
     1040    for (int i=0;i<numberColumns_;i++) {
     1041      int kUpper = -1;
     1042      if (!columnLower[i])
     1043        kUpper = static_cast<int>(columnUpper[i]);
     1044      if (kUpper>0) {
     1045        originalUpper[i] = kUpper;
     1046        nPossible++;
     1047      } else {
     1048        originalUpper[i] = -1;
     1049      }
     1050    }
     1051    if (!nPossible)
     1052      model->setMoreSpecialOptions2(options2 & ~(128 | 256 | 131072));
     1053  } else {
     1054    if ((options2&131072)!=0)
     1055      options2 &= ~(128 | 256);
     1056    model->setMoreSpecialOptions2(options2 & ~131072);
     1057  }
    6551058  //Print_Orbits ();
    6561059  // stats in array
    6571060  if (spaceDense < COIN_INT_MAX)
    658     whichOrbit_[0] = spaceDense;
     1061    stats_[0] = spaceDense;
    6591062  else
    660     whichOrbit_[0] = COIN_INT_MAX;
    661   whichOrbit_[1] = spaceSparse;
     1063    stats_[0] = COIN_INT_MAX;
     1064  stats_[1] = spaceSparse;
    6621065  double endCPU = CoinCpuTime();
    6631066  nautyTime_ = endCPU - startCPU;
     
    7251128  return n;
    7261129}
     1130// takes ownership of cbc_permute (orbits part)
     1131void
     1132CbcSymmetry::addPermutation(cbc_permute permutation)
     1133{
     1134  cbc_permute * temp = new cbc_permute[numberPermutations_+1];
     1135  memcpy(temp,permutations_,numberPermutations_*sizeof(cbc_permute));
     1136  delete [] permutations_;
     1137  permutations_=temp;
     1138  permutations_[numberPermutations_] = permutation;
     1139  numberPermutations_++;
     1140}
    7271141// Default Constructor
    7281142CbcSymmetry::CbcSymmetry()
     
    7311145  , numberUsefulOrbits_(0)
    7321146  , numberUsefulObjects_(0)
     1147  , numberPermutations_(0)
     1148  , permutations_(NULL)
    7331149  , whichOrbit_(NULL)
    7341150{
     
    7431159  numberColumns_ = rhs.numberColumns_;
    7441160  if (rhs.whichOrbit_)
    745     whichOrbit_ = CoinCopyOfArray(rhs.whichOrbit_, numberColumns_);
     1161    whichOrbit_ = CoinCopyOfArray(rhs.whichOrbit_, 5*numberColumns_);
    7461162  else
    7471163    whichOrbit_ = NULL;
     1164  numberPermutations_ = rhs.numberPermutations_;
     1165  if (numberPermutations_) {
     1166    permutations_ = CoinCopyOfArray(rhs.permutations_, numberPermutations_);
     1167    for (int i=0;i<numberPermutations_;i++) {
     1168      permutations_[i].orbits = CoinCopyOfArray(permutations_[i].orbits,
     1169                                                numberColumns_);
     1170    }
     1171  } else {
     1172    permutations_ = NULL;
     1173  }
    7481174}
    7491175
     
    7571183    nauty_info_ = new CbcNauty(*rhs.nauty_info_);
    7581184    delete[] whichOrbit_;
     1185    if (numberPermutations_) {
     1186      for (int i=0;i<numberPermutations_;i++) {
     1187        delete [] permutations_[i].orbits;
     1188      }
     1189      delete [] permutations_;
     1190    }
    7591191    numberColumns_ = rhs.numberColumns_;
    7601192    numberUsefulOrbits_ = rhs.numberUsefulOrbits_;
    7611193    numberUsefulObjects_ = rhs.numberUsefulObjects_;
    7621194    if (rhs.whichOrbit_)
    763       whichOrbit_ = CoinCopyOfArray(rhs.whichOrbit_, numberColumns_);
     1195      whichOrbit_ = CoinCopyOfArray(rhs.whichOrbit_, 5*numberColumns_);
    7641196    else
    7651197      whichOrbit_ = NULL;
     1198    numberPermutations_ = rhs.numberPermutations_;
     1199    if (numberPermutations_) {
     1200      permutations_ = CoinCopyOfArray(rhs.permutations_, numberPermutations_);
     1201      for (int i=0;i<numberPermutations_;i++) {
     1202        permutations_[i].orbits = CoinCopyOfArray(permutations_[i].orbits,
     1203                                                  numberColumns_);
     1204      }
     1205    } else {
     1206      permutations_ = NULL;
     1207    }
    7661208  }
    7671209  return *this;
     
    7731215  delete nauty_info_;
    7741216  delete[] whichOrbit_;
     1217  if (numberPermutations_) {
     1218    for (int i=0;i<numberPermutations_;i++) {
     1219      delete [] permutations_[i].orbits;
     1220    }
     1221    delete [] permutations_;
     1222  }
    7751223}
    7761224
     
    13371785}
    13381786
     1787// Useful constructor
     1788CbcOrbitalBranchingObject::CbcOrbitalBranchingObject(CbcModel *model,
     1789                                                     int column,
     1790                                                     int nFixed)
     1791  : CbcBranchingObject(model, -1, 1, 0.5)
     1792  , column_(column)
     1793  , numberOther_(nFixed)
     1794  , numberExtra_(0)
     1795  , fixToZero_(NULL)
     1796{
     1797  CbcSymmetry *symmetryInfo = model->rootSymmetryInfo();
     1798  assert(symmetryInfo);
     1799  nautyBranchSucceeded_++;
     1800 
     1801  fixToZero_ = CoinCopyOfArray(model->rootSymmetryInfo()->fixedToZero(),
     1802                               nFixed);
     1803}
     1804
    13391805// Copy constructor
    13401806CbcOrbitalBranchingObject::CbcOrbitalBranchingObject(const CbcOrbitalBranchingObject &rhs)
     
    14641930}
    14651931#endif
    1466 
    1467 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
    1468 */
  • trunk/src/CbcSymmetry.hpp

    r2936 r3039  
    5353#endif
    5454class CbcNauty;
     55typedef struct {
     56  int numberInPerm;
     57  int numberPerms;
     58  int * orbits;
     59} cbc_permute;
    5560
    5661#define COUENNE_HACKED_EPS 1.e-07
     
    7681  public:
    7782    void node(int, double, double, double, int, int);
    78     inline void color_vertex(register int k) { color = k; }
     83    inline void color_vertex(int k) { color = k; }
    7984    inline int get_index() const { return index; }
    8085    inline double get_coeff() const { return coeff; }
     
    8489    inline int get_code() const { return code; }
    8590    inline int get_sign() const { return sign; }
    86     inline void bounds(register double a, register double b)
     91    inline void bounds(double a, double b)
    8792    {
    8893      lb = a;
     
    9297
    9398  struct myclass0 {
    94     inline bool operator()(register const Node &a, register const Node &b)
     99    inline bool operator()(const Node &a, const Node &b)
    95100    {
    96101
     
    100105
    101106  struct myclass {
    102     inline bool operator()(register const Node &a, register const Node &b)
     107    inline bool operator()(const Node &a, const Node &b)
    103108    {
    104109      return (a.get_index() < b.get_index());
     
    107112
    108113  struct less_than_str {
    109     inline bool operator()(register const char *a, register const char *b) const
     114    inline bool operator()(const char *a, const char *b) const
    110115    {
    111116      return strcmp(a, b) < 0;
     
    139144  int statsOrbits(CbcModel *model, int type) const;
    140145  //double timeNauty () const;
    141   void Print_Orbits() const;
     146  void Print_Orbits(int type=0) const;
    142147  void fillOrbits();
    143148  /// Fixes variables using orbits (returns number fixed)
    144149  int orbitalFixing(OsiSolverInterface *solver);
     150  /// Fixes variables using root orbits (returns number fixed)
     151  int orbitalFixing2(OsiSolverInterface *solver);
    145152  inline int *whichOrbit()
    146153  {
    147154    return numberUsefulOrbits_ ? whichOrbit_ : NULL;
     155  }
     156  inline int *fixedToZero() const
     157  {
     158    return whichOrbit_+4*numberColumns_;
    148159  }
    149160  inline int numberUsefulOrbits() const
     
    158169  void ChangeBounds(const double *lower, const double *upper,
    159170    int numberColumns, bool justFixedAtOne) const;
    160   inline bool compare(register Node &a, register Node &b) const;
     171  /** for simple stuff - returns number can fix if can use saved orbit (mode 1)
     172      otherwise may fix and return number can fix (mode 0) */
     173  int changeBounds(int kColumn, double * saveLower,
     174                    double * saveUpper,
     175                    OsiSolverInterface * solver,int mode) const;
     176  inline int numberColumns() const
     177  { return numberColumns_;}
     178  inline bool compare(Node &a, Node &b) const;
    161179  CbcNauty *getNtyInfo() { return nauty_info_; }
    162180
     
    167185  void setupSymmetry(CbcModel * model);
    168186
     187  /// takes ownership of cbc_permute (orbits part)
     188  void addPermutation(cbc_permute permutation);
     189  /// Number of permutation arrays
     190  inline int numberPermutations() const
     191  { return numberPermutations_;}
     192  /// Permutation arrays
     193  inline int * permutation(int which) const
     194  { return permutations_[which].orbits;}
     195  inline int numberInPermutation(int which) const
     196  { return permutations_[which].numberInPerm;}
    169197private:
    170198  mutable std::vector< Node > node_info_;
     
    173201  int numberUsefulOrbits_;
    174202  int numberUsefulObjects_;
     203  int numberPermutations_;
     204  cbc_permute * permutations_;
    175205  int *whichOrbit_;
     206  int stats_[5];
    176207};
    177208
     
    310341    int way,
    311342    int numberExtra, const int *extraToZero);
     343  // Useful constructor (uses stored list)
     344  CbcOrbitalBranchingObject(CbcModel *model, int column, int nFixed);
    312345
    313346  // Copy constructor
Note: See TracChangeset for help on using the changeset viewer.