Changeset 1128


Ignore:
Timestamp:
Oct 8, 2007 8:16:53 AM (13 years ago)
Author:
forrest
Message:

fixes for various ideas

Location:
trunk/Clp/src
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/Clp/src/CbcOrClpParam.cpp

    r1115 r1128  
    20432043  parameters[numberParameters++]=
    20442044    CbcOrClpParam("passC!uts","Number of cut passes at root node",
    2045                   -999999,999999,CUTPASS);
     2045                  -9999999,9999999,CUTPASS);
    20462046  parameters[numberParameters-1].setLonghelp
    20472047    (
  • trunk/Clp/src/ClpModel.cpp

    r1121 r1128  
    33883388  if (mode!=scalingFlag_)
    33893389    whatsChanged_ &= ~(2+4+8);
    3390   if (mode>0&&mode<4) {
     3390  if (mode>0&&mode<5) {
    33913391    scalingFlag_=mode;
    33923392  } else if (!mode) {
  • trunk/Clp/src/ClpModel.hpp

    r1121 r1128  
    5050  /** Copy constructor. May scale depending on mode
    5151      -1 leave mode as is
    52       0 -off, 1 equilibrium, 2 geometric, 3, auto, 4 dynamic(later)
     52      0 -off, 1 equilibrium, 2 geometric, 3, auto, 4 auto-but-as-initialSolve-in-bab
    5353  */
    5454    ClpModel(const ClpModel & rhs, int scalingMode=-1);
     
    525525  inline void setRhsScale(double value)
    526526          { rhsScale_ = value;}
    527    /// Sets or unsets scaling, 0 -off, 1 equilibrium, 2 geometric, 3, auto, 4 dynamic(later)
     527   /// Sets or unsets scaling, 0 -off, 1 equilibrium, 2 geometric, 3 auto, 4 auto-but-as-initialSolve-in-bab
    528528   void scaling(int mode=1);
    529529  /** If we constructed a "really" scaled model then this reverses the operation.
  • trunk/Clp/src/ClpPackedMatrix.cpp

    r1050 r1128  
    21282128  // mark empty and fixed columns
    21292129  // also see if worth scaling
    2130   assert (model->scalingFlag()<4); // dynamic not implemented
     2130  assert (model->scalingFlag()<=4);
    21312131  double largest=0.0;
    21322132  double smallest=1.0e50;
     
    21742174      // need to scale
    21752175    int scalingMethod = model->scalingFlag();
     2176    if (scalingMethod==4) {
     2177      // Aas auto
     2178      scalingMethod=3;
     2179    }
    21762180    // and see if there any empty rows
    21772181    for (iRow=0;iRow<numberRows;iRow++) {
     
    23542358      } else {
    23552359        assert (scalingMethod==4);
    2356         if (overallSmallest>2.0*savedOverallRatio)
     2360        if (overallSmallest>2.0*savedOverallRatio) {
    23572361          finished=true; // geometric was better
    2358         else
     2362          if (model->scalingFlag()==4) {
     2363            // If in Branch and bound change
     2364            if ((model->specialOptions()&1024)!=0) {
     2365              model->scaling(2);
     2366            }
     2367          }
     2368        } else {
    23592369          scalingMethod=1; // redo equilibrium
     2370          if (model->scalingFlag()==4) {
     2371            // If in Branch and bound change
     2372            if ((model->specialOptions()&1024)!=0) {
     2373              model->scaling(1);
     2374            }
     2375          }
     2376        }
    23602377#if 0
    23612378        if (model->logLevel()>2) {
  • trunk/Clp/src/ClpSimplex.cpp

    r1125 r1128  
    73337333ClpSimplex::statusOfProblem(bool initial)
    73347334{
    7335   createRim(7+8+16+32);
     7335  bool goodMatrix=createRim(7+8+16+32);
     7336  if (!goodMatrix) {
     7337    problemStatus_=4;
     7338    return false;
     7339  }
    73367340  // is factorization okay?
    73377341  if (initial) {
  • trunk/Clp/src/ClpSimplexOther.cpp

    r1111 r1128  
    27852785  }
    27862786}
     2787/* Expands out all possible combinations for a knapsack
     2788   If buildObj NULL then just computes space needed - returns number elements
     2789   On entry numberOutput is maximum allowed, on exit it is number needed or
     2790   -1 (as will be number elements) if maximum exceeded.  numberOutput will have at
     2791   least space to return values which reconstruct input.
     2792   Rows returned will be original rows but no entries will be returned for
     2793   any rows all of whose entries are in knapsack.  So up to user to allow for this.
     2794   If reConstruct >=0 then returns number of entrie which make up item "reConstruct"
     2795   in expanded knapsack.  Values in buildRow and buildElement;
     2796*/
     2797int
     2798ClpSimplexOther::expandKnapsack(int knapsackRow, int & numberOutput,
     2799                                double * buildObj, CoinBigIndex * buildStart,
     2800                                int * buildRow, double * buildElement,int reConstruct) const
     2801{
     2802  int iRow;
     2803  int iColumn;
     2804  // Get column copy
     2805  CoinPackedMatrix * columnCopy = matrix();
     2806  // Get a row copy in standard format
     2807  CoinPackedMatrix matrixByRow;
     2808  matrixByRow.reverseOrderedCopyOf(*columnCopy);
     2809  const double * elementByRow = matrixByRow.getElements();
     2810  const int * column = matrixByRow.getIndices();
     2811  const CoinBigIndex * rowStart = matrixByRow.getVectorStarts();
     2812  const int * rowLength = matrixByRow.getVectorLengths();
     2813  CoinBigIndex j;
     2814  int * whichColumn = new int [numberColumns_];
     2815  int * whichRow = new int [numberRows_];
     2816  int numJ=0;
     2817  // Get what other columns can compensate for
     2818  double * lo = new double [numberRows_];
     2819  double * high = new double [numberRows_];
     2820  {
     2821    // Use to get tight column bounds
     2822    ClpSimplex tempModel(*this);
     2823    tempModel.tightenPrimalBounds(0.0,0,true);
     2824    // Now another model without knapsacks
     2825    int nCol=0;
     2826    for (iRow=0;iRow<numberRows_;iRow++) {
     2827      whichRow[iRow]=iRow;
     2828    }
     2829    for (iColumn=0;iColumn<numberColumns_;iColumn++)
     2830      whichColumn[iColumn]=-1;
     2831    for (j=rowStart[knapsackRow];j<rowStart[knapsackRow]+rowLength[knapsackRow];j++) {
     2832      int iColumn = column[j];
     2833      if (columnUpper_[iColumn]>columnLower_[iColumn]) {
     2834        whichColumn[iColumn]=0;
     2835      } else {
     2836        assert (!columnLower_[iColumn]); // fix later
     2837      }
     2838    }
     2839    for (iColumn=0;iColumn<numberColumns_;iColumn++) {
     2840      if (whichColumn[iColumn]<0)
     2841        whichColumn[nCol++]=iColumn;
     2842    }
     2843    ClpSimplex tempModel2(&tempModel,numberRows_,whichRow,nCol,whichColumn,false,false,false);
     2844    // Row copy
     2845    CoinPackedMatrix matrixByRow;
     2846    matrixByRow.reverseOrderedCopyOf(*tempModel2.matrix());
     2847    const double * elementByRow = matrixByRow.getElements();
     2848    const int * column = matrixByRow.getIndices();
     2849    const CoinBigIndex * rowStart = matrixByRow.getVectorStarts();
     2850    const int * rowLength = matrixByRow.getVectorLengths();
     2851    const double * columnLower = tempModel2.getColLower();
     2852    const double * columnUpper = tempModel2.getColUpper();
     2853    for (iRow = 0; iRow < numberRows_; iRow++) {
     2854      lo[iRow]=-COIN_DBL_MAX;
     2855      high[iRow]=COIN_DBL_MAX;
     2856      if (rowLower_[iRow]>-1.0e20||rowUpper_[iRow]<1.0e20) {
     2857       
     2858        // possible row
     2859        int infiniteUpper = 0;
     2860        int infiniteLower = 0;
     2861        double maximumUp = 0.0;
     2862        double maximumDown = 0.0;
     2863        CoinBigIndex rStart = rowStart[iRow];
     2864        CoinBigIndex rEnd = rowStart[iRow]+rowLength[iRow];
     2865        CoinBigIndex j;
     2866        // Compute possible lower and upper ranges
     2867       
     2868        for (j = rStart; j < rEnd; ++j) {
     2869          double value=elementByRow[j];
     2870          iColumn = column[j];
     2871          if (value > 0.0) {
     2872            if (columnUpper[iColumn] >= 1.0e20) {
     2873              ++infiniteUpper;
     2874            } else {
     2875              maximumUp += columnUpper[iColumn] * value;
     2876            }
     2877            if (columnLower[iColumn] <= -1.0e20) {
     2878              ++infiniteLower;
     2879            } else {
     2880              maximumDown += columnLower[iColumn] * value;
     2881            }
     2882          } else if (value<0.0) {
     2883            if (columnUpper[iColumn] >= 1.0e20) {
     2884              ++infiniteLower;
     2885            } else {
     2886              maximumDown += columnUpper[iColumn] * value;
     2887            }
     2888            if (columnLower[iColumn] <= -1.0e20) {
     2889              ++infiniteUpper;
     2890            } else {
     2891              maximumUp += columnLower[iColumn] * value;
     2892            }
     2893          }
     2894        }
     2895        // Build in a margin of error
     2896        maximumUp += 1.0e-8*fabs(maximumUp)+1.0e-7;
     2897        maximumDown -= 1.0e-8*fabs(maximumDown)+1.0e-7;
     2898        // we want to save effective rhs
     2899        double up = (infiniteUpper) ? COIN_DBL_MAX : maximumUp;
     2900        double down = (infiniteLower) ? -COIN_DBL_MAX : maximumDown;
     2901        if (up==COIN_DBL_MAX||rowLower_[iRow]==-COIN_DBL_MAX) {
     2902          // However low we go it doesn't matter
     2903          lo[iRow]=-COIN_DBL_MAX;
     2904        } else {
     2905          // If we go below this then can not be feasible
     2906          lo[iRow]=rowLower_[iRow]-up;
     2907        }
     2908        if (down==-COIN_DBL_MAX||rowUpper_[iRow]==COIN_DBL_MAX) {
     2909          // However high we go it doesn't matter
     2910          high[iRow]=COIN_DBL_MAX;
     2911        } else {
     2912          // If we go above this then can not be feasible
     2913          high[iRow]=rowUpper_[iRow]-down;
     2914        }
     2915      }
     2916    }
     2917  }
     2918  numJ =0;
     2919  for (iColumn=0;iColumn<numberColumns_;iColumn++)
     2920    whichColumn[iColumn]=-1;
     2921  int * markRow = new int [numberRows_];
     2922  for (iRow=0;iRow<numberRows_;iRow++)
     2923    markRow[iRow]=1;
     2924  for (j=rowStart[knapsackRow];j<rowStart[knapsackRow]+rowLength[knapsackRow];j++) {
     2925    int iColumn = column[j];
     2926    if (columnUpper_[iColumn]>columnLower_[iColumn]) {
     2927      whichColumn[iColumn]=numJ;
     2928      numJ++;
     2929    }
     2930  }
     2931  /* mark rows
     2932     -n in knapsack and n other variables
     2933     1 no entries
     2934     n+1000 not involved in knapsack but n entries
     2935     0 only in knapsack
     2936  */
     2937  for (iRow=0;iRow<numberRows_;iRow++) {
     2938    int type=1;
     2939    for (j=rowStart[iRow];j<rowStart[iRow]+rowLength[iRow];j++) {
     2940      int iColumn = column[j];
     2941      if (whichColumn[iColumn]>=0) {
     2942        if (type==1) {
     2943          type=0;
     2944        } else if (type>0) {
     2945          assert (type>1000);
     2946          type = -(type-1000);
     2947        }
     2948      } else if (type==1) {
     2949        type = 1001;
     2950      } else if (type<0) {
     2951        type --;
     2952      } else if (type==0) {
     2953        type = -1;
     2954      } else {
     2955        assert (type>1000);
     2956        type++;
     2957      }
     2958    }
     2959    markRow[iRow]=type;
     2960    if (type<0&&type>-30&&false)
     2961      printf("markrow on row %d is %d\n",iRow,markRow[iRow]);
     2962  }
     2963  int * bound = new int [numberColumns_+1];
     2964  int * stack = new int [numberColumns_+1];
     2965  int * flip = new int [numberColumns_+1];
     2966  double * offset = new double[numberColumns_+1];
     2967  double * size = new double [numberColumns_+1];
     2968  double * rhsOffset = new double[numberRows_];
     2969  int * build = new int[numberColumns_];
     2970  int maxNumber=numberOutput;
     2971  numJ=0;
     2972  double minSize = rowLower_[knapsackRow];
     2973  double maxSize = rowUpper_[knapsackRow];
     2974  double knapsackOffset=0.0;
     2975  for (j=rowStart[knapsackRow];j<rowStart[knapsackRow]+rowLength[knapsackRow];j++) {
     2976    int iColumn = column[j];
     2977    double lowerColumn=columnLower_[iColumn];
     2978    double upperColumn=columnUpper_[iColumn];
     2979    if (lowerColumn==upperColumn)
     2980      continue;
     2981    double gap = upperColumn-lowerColumn;
     2982    if (gap>1.0e8)
     2983      gap=1.0e8;
     2984    assert (fabs(floor(gap+0.5)-gap)<1.0e-5);
     2985    whichColumn[numJ]=iColumn;
     2986    bound[numJ]=(int) gap;
     2987    if (elementByRow[j]>0.0) {
     2988      flip[numJ]=1;
     2989      offset[numJ]=lowerColumn;
     2990      size[numJ++]=elementByRow[j];
     2991    } else {
     2992      flip[numJ]=-1;
     2993      offset[numJ]=upperColumn;
     2994      size[numJ++]=-elementByRow[j];
     2995      lowerColumn = upperColumn;
     2996    }
     2997    knapsackOffset += elementByRow[j]*lowerColumn;
     2998  } 
     2999  int jRow;
     3000  for (iRow=0;iRow<numberRows_;iRow++)
     3001    whichRow[iRow]=iRow;
     3002  ClpSimplex smallModel(this,numberRows_,whichRow,numJ,whichColumn,true,true,true);
     3003  // modify rhs to allow for nonzero lower bounds
     3004  //double * rowLower = smallModel.rowLower();
     3005  //double * rowUpper = smallModel.rowUpper();
     3006  const double * columnLower = smallModel.columnLower();
     3007  //const double * columnUpper = smallModel.columnUpper();
     3008  const CoinPackedMatrix * matrix = smallModel.matrix();
     3009  const double * element = matrix->getElements();
     3010  const int * row = matrix->getIndices();
     3011  const CoinBigIndex * columnStart = matrix->getVectorStarts();
     3012  const int * columnLength = matrix->getVectorLengths();
     3013  const double * objective = smallModel.objective();
     3014  double objectiveOffset=0.0;
     3015  // would use for fixed?
     3016  CoinZeroN(rhsOffset,numberRows_);
     3017  double * rowActivity = smallModel.primalRowSolution();
     3018  CoinZeroN(rowActivity,numberRows_);
     3019  maxSize -= knapsackOffset;
     3020  minSize -= knapsackOffset;
     3021  // now generate
     3022  int i;
     3023  int iStack=numJ;
     3024  for (i=0;i<numJ;i++) {
     3025    stack[i]=0;
     3026  }
     3027  double tooMuch = 10.0*maxSize+10000;
     3028  stack[numJ]=1;
     3029  size[numJ]=tooMuch;
     3030  bound[numJ]=0;
     3031  double sum=tooMuch;
     3032  // allow for all zero being OK
     3033  stack[numJ-1]=-1;
     3034  sum -= size[numJ-1];
     3035  numberOutput=0;
     3036  int nelCreate=0;
     3037  /* typeRun is - 0 for initial sizes
     3038                  1 for build
     3039                  2 for reconstruct
     3040  */
     3041  int typeRun = buildObj ? 1 : 0;
     3042  if (reConstruct>=0) {
     3043    assert (buildRow&&buildElement);
     3044    typeRun=2;
     3045  }
     3046  if (typeRun==1)
     3047    buildStart[0]=0;
     3048  while (iStack>=0) {
     3049    if (sum>=minSize&&sum<=maxSize) {
     3050      double checkSize =0.0;
     3051      bool good=true;
     3052      int nRow=0;
     3053      double obj=0.0;
     3054      CoinZeroN(rowActivity,nRow);
     3055      for (iColumn=0;iColumn<numJ;iColumn++) {
     3056        int iValue = stack[iColumn];
     3057        if (iValue>bound[iColumn]) {
     3058          good=false;
     3059          break;
     3060        } else {
     3061          double realValue = offset[iColumn] + flip[iColumn]*iValue;
     3062          if (realValue) {
     3063            obj += objective[iColumn]*realValue;
     3064            for (CoinBigIndex j=columnStart[iColumn];
     3065                 j<columnStart[iColumn]+columnLength[iColumn];j++) {
     3066              double value = element[j]*realValue;
     3067              int kRow = row[j];
     3068              if (rowActivity[kRow]) {
     3069                rowActivity[kRow] += value;
     3070                if (!rowActivity[kRow])
     3071                  rowActivity[kRow]=1.0e-100;
     3072              } else {
     3073                build[nRow++]=kRow;
     3074                rowActivity[kRow]=value;
     3075              }
     3076            }
     3077          }
     3078        }
     3079      }
     3080      if (good) {
     3081        for (jRow=0;jRow<nRow;jRow++) {
     3082          int kRow=build[jRow];
     3083          double value = rowActivity[kRow];
     3084          if (value>high[kRow]||value<lo[kRow]) {
     3085            good=false;
     3086            break;
     3087          }
     3088        }
     3089      }
     3090      if (good) {
     3091        if (typeRun==1) {
     3092          buildObj[numberOutput]=obj;
     3093          for (jRow=0;jRow<nRow;jRow++) {
     3094            int kRow=build[jRow];
     3095            double value = rowActivity[kRow];
     3096            if (markRow[kRow]<0&&fabs(value)>1.0e-13) {
     3097              buildElement[nelCreate]=value;
     3098              buildRow[nelCreate++]=kRow;
     3099            }
     3100          }
     3101          buildStart[numberOutput+1]=nelCreate;
     3102        } else if (!typeRun) {
     3103          for (jRow=0;jRow<nRow;jRow++) {
     3104            int kRow=build[jRow];
     3105            double value = rowActivity[kRow];
     3106            if (markRow[kRow]<0&&fabs(value)>1.0e-13) {
     3107              nelCreate++;
     3108            }
     3109          }
     3110        }
     3111        if (typeRun==2&&reConstruct==numberOutput) {
     3112          // build and exit
     3113          nelCreate=0;
     3114          for (iColumn=0;iColumn<numJ;iColumn++) {
     3115            int iValue = stack[iColumn];
     3116            double realValue = offset[iColumn] + flip[iColumn]*iValue;
     3117            if (realValue) {
     3118              buildRow[nelCreate]=whichColumn[iColumn];
     3119              buildElement[nelCreate++]=realValue;
     3120            }
     3121          }
     3122          numberOutput=1;
     3123          for (i=0;i<numJ;i++) {
     3124            bound[i]=0;
     3125          }
     3126          break;
     3127        }
     3128        numberOutput++;
     3129        if (numberOutput>maxNumber) {
     3130          nelCreate=-numberOutput;
     3131          numberOutput=-1;
     3132          for (i=0;i<numJ;i++) {
     3133            bound[i]=0;
     3134          }
     3135          break;
     3136        } else if (typeRun==1&&numberOutput==maxNumber) {
     3137          // On second run
     3138          for (i=0;i<numJ;i++) {
     3139            bound[i]=0;
     3140          }
     3141          break;
     3142        }
     3143        for (int j=0;j<numJ;j++) {
     3144          checkSize += stack[j]*size[j];
     3145        }
     3146        assert (fabs(sum-checkSize)<1.0e-3);
     3147      }
     3148      for (jRow=0;jRow<nRow;jRow++) {
     3149        int kRow=build[jRow];
     3150        rowActivity[kRow]=0.0;
     3151      }
     3152    }
     3153    if (sum>maxSize||stack[iStack]>bound[iStack]) {
     3154      sum -= size[iStack]*stack[iStack];
     3155      stack[iStack--]=0;
     3156      if (iStack>=0) {
     3157        stack[iStack] ++;
     3158        sum += size[iStack];
     3159      }
     3160    } else {
     3161      // must be less
     3162      // add to last possible
     3163      iStack = numJ-1;
     3164      sum += size[iStack];
     3165      stack[iStack]++;
     3166    }
     3167  }
     3168  //printf("%d will be created\n",numberOutput);
     3169  delete [] whichColumn;
     3170  delete [] whichRow;
     3171  delete [] bound;
     3172  delete [] stack;
     3173  delete [] flip;
     3174  delete [] size;
     3175  delete [] offset;
     3176  delete [] rhsOffset;
     3177  delete [] build;
     3178  delete [] markRow;
     3179  delete [] lo;
     3180  delete [] high;
     3181  return nelCreate;
     3182}
  • trunk/Clp/src/ClpSimplexOther.hpp

    r1111 r1128  
    187187  */
    188188  int tightenIntegerBounds(double * rhsSpace);
     189  /** Expands out all possible combinations for a knapsack
     190      If buildObj NULL then just computes space needed - returns number elements
     191      On entry numberOutput is maximum allowed, on exit it is number needed or
     192      -1 (as will be number elements) if maximum exceeded.  numberOutput will have at
     193      least space to return values which reconstruct input.
     194      Rows returned will be original rows but no entries will be returned for
     195      any rows all of whose entries are in knapsack.  So up to user to allow for this.
     196      If reConstruct >=0 then returns number of entrie which make up item "reConstruct"
     197      in expanded knapsack.  Values in buildRow and buildElement;
     198  */
     199  int expandKnapsack(int knapsackRow, int & numberOutput,
     200                     double * buildObj, CoinBigIndex * buildStart,
     201                     int * buildRow, double * buildElement,int reConstruct=-1) const;
    189202  //@}
    190203};
Note: See TracChangeset for help on using the changeset viewer.