/home/coin/SVN-release/OS-2.0.0/Couenne/src/problem/CouenneLPtightenBoundsCLP.cpp

Go to the documentation of this file.
00001 /* $Id: CouenneLPtightenBoundsCLP.cpp 201 2009-07-07 10:28:24Z pbelotti $
00002  *
00003  * Name:    CouenneLPtightenBoundsCLP.cpp
00004  * Authors: Pietro Belotti, Carnegie Mellon University
00005  * Purpose: adaptation of OsiClpSolverInterface::tightenBounds()
00006  *
00007  * (C) Carnegie-Mellon University, 2009.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CouennePrecisions.hpp"
00012 #include "CouenneSolverInterface.hpp"
00013 
00014 //#define COIN_DEVELOP 4
00015 
00016 // Tighten bounds. Returns -1 if infeasible, otherwise number of
00017 // variables tightened.
00018 int CouenneSolverInterface::tightenBoundsCLP (int lightweight) {
00019 
00020   // Copied from OsiClpSolverInterface::tightenBounds
00021 
00022   int
00023     numberRows    = getNumRows(),
00024     numberColumns = getNumCols(),
00025     iRow, iColumn;
00026 
00027   const double * columnUpper = getColUpper();
00028   const double * columnLower = getColLower();
00029   const double * rowUpper = getRowUpper();
00030   const double * rowLower = getRowLower();
00031 
00032   // Column copy of matrix
00033   const double * element = getMatrixByCol()->getElements();
00034   const int * row = getMatrixByCol()->getIndices();
00035   const CoinBigIndex * columnStart = getMatrixByCol()->getVectorStarts();
00036   const int * columnLength = getMatrixByCol()->getVectorLengths();
00037   const double *objective = getObjCoefficients() ;
00038 
00039   double direction = getObjSense();
00040   double * down = new double [numberRows];
00041 
00042   if (lightweight)
00043     return tightenBoundsCLP_Light (lightweight);
00044 
00045   // NOT LIGHTWEIGHT /////////////////////////////////////////////////////
00046 
00047   double * up = new double [numberRows];
00048   double * sum = new double [numberRows];
00049   int * type = new int [numberRows];
00050   CoinZeroN(down,numberRows);
00051   CoinZeroN(up,numberRows);
00052   CoinZeroN(sum,numberRows);
00053   CoinZeroN(type,numberRows);
00054   double infinity = getInfinity();
00055 
00056   for (iColumn=0;iColumn<numberColumns;iColumn++) {
00057     CoinBigIndex start = columnStart[iColumn];
00058     CoinBigIndex end = start + columnLength[iColumn];
00059     double lower = columnLower[iColumn];
00060     double upper = columnUpper[iColumn];
00061     if (lower==upper) {
00062       for (CoinBigIndex j=start;j<end;j++) {
00063         int iRow = row[j];
00064         double value = element[j];
00065         sum[iRow]+=2.0*fabs(value*lower);
00066         if ((type[iRow]&1)==0)
00067           down[iRow] += value*lower;
00068         if ((type[iRow]&2)==0)
00069           up[iRow] += value*lower;
00070       }
00071     } else {
00072       for (CoinBigIndex j=start;j<end;j++) {
00073         int iRow = row[j];
00074         double value = element[j];
00075         if (value>0.0) {
00076           if ((type[iRow]&1)==0) {
00077             if (lower!=-infinity) {
00078               down[iRow] += value*lower;
00079               sum[iRow]+=fabs(value*lower);
00080             } else {
00081               type[iRow] |= 1;
00082             }
00083           }
00084           if ((type[iRow]&2)==0) {
00085             if (upper!=infinity) {
00086               up[iRow] += value*upper;
00087               sum[iRow]+=fabs(value*upper);
00088             } else {
00089               type[iRow] |= 2;
00090             }
00091           }
00092         } else {
00093           if ((type[iRow]&1)==0) {
00094             if (upper!=infinity) {
00095               down[iRow] += value*upper;
00096               sum[iRow]+=fabs(value*upper);
00097             } else {
00098               type[iRow] |= 1;
00099             }
00100           }
00101           if ((type[iRow]&2)==0) {
00102             if (lower!=-infinity) {
00103               up[iRow] += value*lower;
00104               sum[iRow]+=fabs(value*lower);
00105             } else {
00106               type[iRow] |= 2;
00107             }
00108           }
00109         }
00110       }
00111     }
00112   }
00113 
00114   int nTightened = 0;
00115   double tolerance = 1.0e-6;
00116 
00117   for (iRow=0;iRow<numberRows;iRow++) {
00118     if ((type[iRow]&1)!=0)
00119       down[iRow]=-infinity;
00120     if (down[iRow]>rowUpper[iRow]) {
00121       if (down[iRow]>rowUpper[iRow]+tolerance+1.0e-8*sum[iRow]) {
00122         // infeasible
00123 #ifdef COIN_DEVELOP
00124         printf("infeasible on row %d\n",iRow);
00125 #endif
00126         nTightened=-1;
00127         break;
00128       } else {
00129         down[iRow]=rowUpper[iRow];
00130       }
00131     }
00132     if ((type[iRow]&2)!=0)
00133       up[iRow]=infinity;
00134     if (up[iRow]<rowLower[iRow]) {
00135       if (up[iRow]<rowLower[iRow]-tolerance-1.0e-8*sum[iRow]) {
00136         // infeasible
00137 #ifdef COIN_DEVELOP
00138         printf("infeasible on row %d\n",iRow);
00139 #endif
00140         nTightened=-1;
00141         break;
00142       } else {
00143         up[iRow]=rowLower[iRow];
00144       }
00145     }
00146   }
00147 
00148   if (nTightened)
00149     numberColumns = 0; // so will skip
00150 
00151   for (iColumn=0;iColumn<numberColumns;iColumn++) {
00152     double lower = columnLower[iColumn];
00153     double upper = columnUpper[iColumn];
00154     double gap = upper-lower;
00155 
00156     if (!gap)
00157       continue;
00158 
00159     int canGo=0;
00160 
00161     CoinBigIndex
00162       start =         columnStart  [iColumn],
00163       end   = start + columnLength [iColumn];
00164 
00165     if (lower < -1.0e8 && upper > 1.0e8)
00166       continue; // Could do severe damage to accuracy
00167 
00168 
00169     // there was an ifInteger condition here. We do like tightened
00170     // bounds for continuous variables too, so we don't test for
00171     // integrality.
00172 
00173     {
00174       if (integerInformation_ && integerInformation_ [iColumn]) {
00175 
00176         if (lower < ceil (lower - COUENNE_EPS) - COUENNE_EPS) {
00177 #ifdef COIN_DEVELOP
00178           printf("increasing lower bound on %d from %e to %e\n",iColumn,
00179                  lower,ceil(lower - COUENNE_EPS));
00180 #endif
00181           lower=ceil(lower - COUENNE_EPS);
00182           gap=upper-lower;
00183           setColLower(iColumn,lower);
00184         }
00185 
00186         if (upper > floor(upper + COUENNE_EPS) + COUENNE_EPS) {
00187 #ifdef COIN_DEVELOP
00188           printf("decreasing upper bound on %d from %e to %e\n",iColumn,
00189                  upper,floor(upper + COUENNE_EPS));
00190 #endif
00191           upper=floor(upper + COUENNE_EPS);
00192           gap=upper-lower;
00193           setColUpper(iColumn,upper);
00194         }
00195       }
00196 
00197       double newLower=lower;
00198       double newUpper=upper;
00199 
00200       for (CoinBigIndex j=start;j<end;j++) {
00201         int iRow = row[j];
00202         double value = element[j];
00203         if (value>0.0) {
00204           if ((type[iRow]&1)==0) {
00205             // has to be at most something
00206             if (down[iRow] + value*gap > rowUpper[iRow]+tolerance) {
00207               double newGap = (rowUpper[iRow]-down[iRow])/value;
00208               // adjust
00209               newGap += 1.0e-10*sum[iRow];
00210               if (integerInformation_ && integerInformation_ [iColumn])
00211                 newGap = floor(newGap);
00212               if (lower+newGap<newUpper)
00213                 newUpper=lower+newGap;
00214             }
00215           }
00216           if (down[iRow]<rowLower[iRow])
00217             canGo |=1; // can't go down without affecting result
00218           if ((type[iRow]&2)==0) {
00219             // has to be at least something
00220             if (up[iRow] - value*gap < rowLower[iRow]-tolerance) {
00221               double newGap = (up[iRow]-rowLower[iRow])/value;
00222               // adjust
00223               newGap += 1.0e-10*sum[iRow];
00224               if (integerInformation_ && integerInformation_ [iColumn])
00225                 newGap = floor(newGap);
00226               if (upper-newGap>newLower)
00227                 newLower=upper-newGap;
00228             }
00229           }
00230           if (up[iRow]>rowUpper[iRow])
00231             canGo |=2; // can't go up without affecting result
00232         } else {
00233           if ((type[iRow]&1)==0) {
00234             // has to be at least something
00235             if (down[iRow] - value*gap > rowUpper[iRow]+tolerance) {
00236               double newGap = -(rowUpper[iRow]-down[iRow])/value;
00237               // adjust
00238               newGap += 1.0e-10*sum[iRow];
00239               if (integerInformation_ && integerInformation_ [iColumn])
00240                 newGap = floor(newGap);
00241               if (upper-newGap>newLower)
00242                 newLower=upper-newGap;
00243             }
00244           }
00245           if (up[iRow]>rowUpper[iRow])
00246             canGo |=1; // can't go down without affecting result
00247           if ((type[iRow]&2)==0) {
00248             // has to be at most something
00249             if (up[iRow] + value*gap < rowLower[iRow]-tolerance) {
00250               double newGap = -(up[iRow]-rowLower[iRow])/value;
00251               // adjust
00252               newGap += 1.0e-10*sum[iRow];
00253               if (integerInformation_ && integerInformation_ [iColumn])
00254                 newGap = floor(newGap);
00255               if (lower+newGap<newUpper)
00256                 newUpper=lower+newGap;
00257             }
00258           }
00259           if (down[iRow]<rowLower[iRow])
00260             canGo |=2; // can't go up without affecting result
00261         }
00262       }
00263 
00264       if (newUpper<upper || newLower>lower) {
00265         nTightened++;
00266         if (newLower>newUpper) {
00267           // infeasible
00268 #if COIN_DEVELOP>1
00269           printf("infeasible on column %d\n",iColumn);
00270 #endif
00271           nTightened=-1;
00272           break;
00273         } else {
00274           setColLower(iColumn,newLower);
00275           setColUpper(iColumn,newUpper);
00276         }
00277         for (CoinBigIndex j=start;j<end;j++) {
00278           int iRow = row[j];
00279           double value = element[j];
00280           if (value>0.0) {
00281             if ((type[iRow]&1)==0) down [iRow] += value*(newLower-lower);
00282             if ((type[iRow]&2)==0) up   [iRow] += value*(newUpper-upper);
00283           } else {
00284             if ((type[iRow]&1)==0) down [iRow] += value*(newUpper-upper);
00285             if ((type[iRow]&2)==0) up   [iRow] += value*(newLower-lower);
00286           }
00287         }
00288       } else {
00289 
00290         if (canGo!=3) {
00291 
00292           double objValue = direction*objective[iColumn];
00293 
00294           if (objValue>=0.0&&(canGo&1)==0) {
00295 #if COIN_DEVELOP>2
00296             printf("dual fix down on column %d\n",iColumn);
00297 #endif
00298             nTightened++;
00299             setColUpper(iColumn,lower);
00300           } else if (objValue<=0.0 && (canGo&2)==0) {
00301 #if COIN_DEVELOP>2
00302             printf("dual fix up on column %d\n",iColumn);
00303 #endif
00304             nTightened++;
00305             setColLower(iColumn,upper);
00306           }
00307         }           
00308       }
00309     }
00310 
00311 //     else {
00312 
00313 //       // CONTINUOUS //////////////////////////////////////////
00314 
00315 //       // just do dual tests
00316 //       for (CoinBigIndex j=start;j<end;j++) {
00317 //      int iRow = row[j];
00318 //      double value = element[j];
00319 //      if (value>0.0) {
00320 //        if (down [iRow] < rowLower [iRow]) canGo |=1; // can't go down without affecting result
00321 //        if (up   [iRow] > rowUpper [iRow]) canGo |=2; // can't go up   without affecting result
00322 //      } else {
00323 //        if (up   [iRow] > rowUpper [iRow]) canGo |=1; // can't go down without affecting result
00324 //        if (down [iRow] < rowLower [iRow]) canGo |=2; // can't go up   without affecting result
00325 //      }
00326 //       }
00327 
00328 //       if (canGo!=3) {
00329 //      double objValue = direction*objective[iColumn];
00330 //      if (objValue>=0.0&&(canGo&1)==0) {
00331 // #if COIN_DEVELOP>2
00332 //        printf("dual fix down on continuous column %d lower %g\n",
00333 //               iColumn,lower);
00334 // #endif
00335 //        // Only if won't cause numerical problems
00336 //        if (lower>-1.0e10) {
00337 //          nTightened++;;
00338 //          setColUpper(iColumn,lower);
00339 //        }
00340 //      } else if (objValue<=0.0&&(canGo&2)==0) {
00341 // #if COIN_DEVELOP>2
00342 //        printf("dual fix up on continuous column %d upper %g\n",
00343 //               iColumn,upper);
00344 // #endif
00345 //        // Only if won't cause numerical problems
00346 //        if (upper<1.0e10) {
00347 //          nTightened++;;
00348 //          setColLower(iColumn,upper);
00349 //        }
00350 //      }
00351 //       }
00352 //     }
00353 
00354   }
00355 
00356   delete [] type;
00357   delete [] down;
00358   delete [] up;
00359   delete [] sum;
00360 
00361   return nTightened;
00362 }
00363   

Generated on Mon Aug 3 03:02:21 2009 by  doxygen 1.4.7