Changeset 1395


Ignore:
Timestamp:
Dec 10, 2009 9:43:19 PM (9 years ago)
Author:
bjarni
Message:

Extracted analyze() from CbcSolver?.cpp and placed it in CbcSolverAnalyze?.cpp, updated libCbc.vcproj (v9) to include CbcSolverAnalyze?.cpp

Location:
branches/sandbox/Cbc
Files:
2 added
2 edited

Legend:

Unmodified
Added
Removed
  • branches/sandbox/Cbc/MSVisualStudio/v9/libCbc/libCbc.vcproj

    r1388 r1395  
    944944                        </File>
    945945                        <File
     946                                RelativePath="..\..\..\src\CbcSolverAnalyze.cpp"
     947                                >
     948                        </File>
     949                        <File
    946950                                RelativePath="..\..\..\src\CbcSolverHeuristics.cpp"
    947951                                >
     
    13331337                        </File>
    13341338                        <File
     1339                                RelativePath="..\..\..\src\CbcSolverAnalyze.hpp"
     1340                                >
     1341                        </File>
     1342                        <File
    13351343                                RelativePath="..\..\..\src\CbcSolverHeuristics.hpp"
    13361344                                >
  • branches/sandbox/Cbc/src/CbcSolver.cpp

    r1394 r1395  
    200200
    201201#include "OsiClpSolverInterface.hpp"
     202
     203#include "CbcSolverAnalyze.hpp"
    202204
    203205#include "CbcSolver.hpp"
     
    796798#endif
    797799
    798 /*
    799   Global parameters for command processing.
    800 
    801   These will need to be moved into an object of some sort in order to make
    802   this set of calls thread-safe.
    803 */
    804 
    805 #ifndef CBC_OTHER_SOLVER
    806 /*
    807   Look to see if a constraint is all-integer (variables & coeffs), or could be
    808   all integer. Consider whether one or two continuous variables can be declared
    809   integer. John's comment is that integer preprocessing might do a better job,
    810   so we should consider whether this routine should stay.
    811 
    812   No hurry to get rid of it, in my opinion  -- lh, 091210 --
    813 */
    814 static int * analyze(OsiClpSolverInterface * solverMod, int & numberChanged,
    815                      double & increment, bool changeInt,
    816                      CoinMessageHandler * generalMessageHandler, bool noPrinting)
    817 {
    818     bool noPrinting_ = noPrinting;
    819     OsiSolverInterface * solver = solverMod->clone();
    820     char generalPrint[200];
    821     if (0) {
    822         // just get increment
    823         CbcModel model(*solver);
    824         model.analyzeObjective();
    825         double increment2 = model.getCutoffIncrement();
    826         printf("initial cutoff increment %g\n", increment2);
    827     }
    828     const double *objective = solver->getObjCoefficients() ;
    829     const double *lower = solver->getColLower() ;
    830     const double *upper = solver->getColUpper() ;
    831     int numberColumns = solver->getNumCols() ;
    832     int numberRows = solver->getNumRows();
    833     double direction = solver->getObjSense();
    834     int iRow, iColumn;
    835 
    836     // Row copy
    837     CoinPackedMatrix matrixByRow(*solver->getMatrixByRow());
    838     const double * elementByRow = matrixByRow.getElements();
    839     const int * column = matrixByRow.getIndices();
    840     const CoinBigIndex * rowStart = matrixByRow.getVectorStarts();
    841     const int * rowLength = matrixByRow.getVectorLengths();
    842 
    843     // Column copy
    844     CoinPackedMatrix  matrixByCol(*solver->getMatrixByCol());
    845     const double * element = matrixByCol.getElements();
    846     const int * row = matrixByCol.getIndices();
    847     const CoinBigIndex * columnStart = matrixByCol.getVectorStarts();
    848     const int * columnLength = matrixByCol.getVectorLengths();
    849 
    850     const double * rowLower = solver->getRowLower();
    851     const double * rowUpper = solver->getRowUpper();
    852 
    853     char * ignore = new char [numberRows];
    854     int * changed = new int[numberColumns];
    855     int * which = new int[numberRows];
    856     double * changeRhs = new double[numberRows];
    857     memset(changeRhs, 0, numberRows*sizeof(double));
    858     memset(ignore, 0, numberRows);
    859     numberChanged = 0;
    860     int numberInteger = 0;
    861     for (iColumn = 0; iColumn < numberColumns; iColumn++) {
    862         if (upper[iColumn] > lower[iColumn] + 1.0e-8 && solver->isInteger(iColumn))
    863             numberInteger++;
    864     }
    865     bool finished = false;
    866     while (!finished) {
    867         int saveNumberChanged = numberChanged;
    868         for (iRow = 0; iRow < numberRows; iRow++) {
    869             int numberContinuous = 0;
    870             double value1 = 0.0, value2 = 0.0;
    871             bool allIntegerCoeff = true;
    872             double sumFixed = 0.0;
    873             int jColumn1 = -1, jColumn2 = -1;
    874             for (CoinBigIndex j = rowStart[iRow]; j < rowStart[iRow] + rowLength[iRow]; j++) {
    875                 int jColumn = column[j];
    876                 double value = elementByRow[j];
    877                 if (upper[jColumn] > lower[jColumn] + 1.0e-8) {
    878                     if (!solver->isInteger(jColumn)) {
    879                         if (numberContinuous == 0) {
    880                             jColumn1 = jColumn;
    881                             value1 = value;
    882                         } else {
    883                             jColumn2 = jColumn;
    884                             value2 = value;
    885                         }
    886                         numberContinuous++;
    887                     } else {
    888                         if (fabs(value - floor(value + 0.5)) > 1.0e-12)
    889                             allIntegerCoeff = false;
    890                     }
    891                 } else {
    892                     sumFixed += lower[jColumn] * value;
    893                 }
    894             }
    895             double low = rowLower[iRow];
    896             if (low > -1.0e20) {
    897                 low -= sumFixed;
    898                 if (fabs(low - floor(low + 0.5)) > 1.0e-12)
    899                     allIntegerCoeff = false;
    900             }
    901             double up = rowUpper[iRow];
    902             if (up < 1.0e20) {
    903                 up -= sumFixed;
    904                 if (fabs(up - floor(up + 0.5)) > 1.0e-12)
    905                     allIntegerCoeff = false;
    906             }
    907             if (!allIntegerCoeff)
    908                 continue; // can't do
    909             if (numberContinuous == 1) {
    910                 // see if really integer
    911                 // This does not allow for complicated cases
    912                 if (low == up) {
    913                     if (fabs(value1) > 1.0e-3) {
    914                         value1 = 1.0 / value1;
    915                         if (fabs(value1 - floor(value1 + 0.5)) < 1.0e-12) {
    916                             // integer
    917                             changed[numberChanged++] = jColumn1;
    918                             solver->setInteger(jColumn1);
    919                             if (upper[jColumn1] > 1.0e20)
    920                                 solver->setColUpper(jColumn1, 1.0e20);
    921                             if (lower[jColumn1] < -1.0e20)
    922                                 solver->setColLower(jColumn1, -1.0e20);
    923                         }
    924                     }
    925                 } else {
    926                     if (fabs(value1) > 1.0e-3) {
    927                         value1 = 1.0 / value1;
    928                         if (fabs(value1 - floor(value1 + 0.5)) < 1.0e-12) {
    929                             // This constraint will not stop it being integer
    930                             ignore[iRow] = 1;
    931                         }
    932                     }
    933                 }
    934             } else if (numberContinuous == 2) {
    935                 if (low == up) {
    936                     /* need general theory - for now just look at 2 cases -
    937                        1 - +- 1 one in column and just costs i.e. matching objective
    938                        2 - +- 1 two in column but feeds into G/L row which will try and minimize
    939                     */
    940                     if (fabs(value1) == 1.0 && value1*value2 == -1.0 && !lower[jColumn1]
    941                             && !lower[jColumn2]) {
    942                         int n = 0;
    943                         int i;
    944                         double objChange = direction * (objective[jColumn1] + objective[jColumn2]);
    945                         double bound = CoinMin(upper[jColumn1], upper[jColumn2]);
    946                         bound = CoinMin(bound, 1.0e20);
    947                         for ( i = columnStart[jColumn1]; i < columnStart[jColumn1] + columnLength[jColumn1]; i++) {
    948                             int jRow = row[i];
    949                             double value = element[i];
    950                             if (jRow != iRow) {
    951                                 which[n++] = jRow;
    952                                 changeRhs[jRow] = value;
    953                             }
    954                         }
    955                         for ( i = columnStart[jColumn1]; i < columnStart[jColumn1] + columnLength[jColumn1]; i++) {
    956                             int jRow = row[i];
    957                             double value = element[i];
    958                             if (jRow != iRow) {
    959                                 if (!changeRhs[jRow]) {
    960                                     which[n++] = jRow;
    961                                     changeRhs[jRow] = value;
    962                                 } else {
    963                                     changeRhs[jRow] += value;
    964                                 }
    965                             }
    966                         }
    967                         if (objChange >= 0.0) {
    968                             // see if all rows OK
    969                             bool good = true;
    970                             for (i = 0; i < n; i++) {
    971                                 int jRow = which[i];
    972                                 double value = changeRhs[jRow];
    973                                 if (value) {
    974                                     value *= bound;
    975                                     if (rowLength[jRow] == 1) {
    976                                         if (value > 0.0) {
    977                                             double rhs = rowLower[jRow];
    978                                             if (rhs > 0.0) {
    979                                                 double ratio = rhs / value;
    980                                                 if (fabs(ratio - floor(ratio + 0.5)) > 1.0e-12)
    981                                                     good = false;
    982                                             }
    983                                         } else {
    984                                             double rhs = rowUpper[jRow];
    985                                             if (rhs < 0.0) {
    986                                                 double ratio = rhs / value;
    987                                                 if (fabs(ratio - floor(ratio + 0.5)) > 1.0e-12)
    988                                                     good = false;
    989                                             }
    990                                         }
    991                                     } else if (rowLength[jRow] == 2) {
    992                                         if (value > 0.0) {
    993                                             if (rowLower[jRow] > -1.0e20)
    994                                                 good = false;
    995                                         } else {
    996                                             if (rowUpper[jRow] < 1.0e20)
    997                                                 good = false;
    998                                         }
    999                                     } else {
    1000                                         good = false;
    1001                                     }
    1002                                 }
    1003                             }
    1004                             if (good) {
    1005                                 // both can be integer
    1006                                 changed[numberChanged++] = jColumn1;
    1007                                 solver->setInteger(jColumn1);
    1008                                 if (upper[jColumn1] > 1.0e20)
    1009                                     solver->setColUpper(jColumn1, 1.0e20);
    1010                                 if (lower[jColumn1] < -1.0e20)
    1011                                     solver->setColLower(jColumn1, -1.0e20);
    1012                                 changed[numberChanged++] = jColumn2;
    1013                                 solver->setInteger(jColumn2);
    1014                                 if (upper[jColumn2] > 1.0e20)
    1015                                     solver->setColUpper(jColumn2, 1.0e20);
    1016                                 if (lower[jColumn2] < -1.0e20)
    1017                                     solver->setColLower(jColumn2, -1.0e20);
    1018                             }
    1019                         }
    1020                         // clear
    1021                         for (i = 0; i < n; i++) {
    1022                             changeRhs[which[i]] = 0.0;
    1023                         }
    1024                     }
    1025                 }
    1026             }
    1027         }
    1028         for (iColumn = 0; iColumn < numberColumns; iColumn++) {
    1029             if (upper[iColumn] > lower[iColumn] + 1.0e-8 && !solver->isInteger(iColumn)) {
    1030                 double value;
    1031                 value = upper[iColumn];
    1032                 if (value < 1.0e20 && fabs(value - floor(value + 0.5)) > 1.0e-12)
    1033                     continue;
    1034                 value = lower[iColumn];
    1035                 if (value > -1.0e20 && fabs(value - floor(value + 0.5)) > 1.0e-12)
    1036                     continue;
    1037                 bool integer = true;
    1038                 for (CoinBigIndex j = columnStart[iColumn]; j < columnStart[iColumn] + columnLength[iColumn]; j++) {
    1039                     int iRow = row[j];
    1040                     if (!ignore[iRow]) {
    1041                         integer = false;
    1042                         break;
    1043                     }
    1044                 }
    1045                 if (integer) {
    1046                     // integer
    1047                     changed[numberChanged++] = iColumn;
    1048                     solver->setInteger(iColumn);
    1049                     if (upper[iColumn] > 1.0e20)
    1050                         solver->setColUpper(iColumn, 1.0e20);
    1051                     if (lower[iColumn] < -1.0e20)
    1052                         solver->setColLower(iColumn, -1.0e20);
    1053                 }
    1054             }
    1055         }
    1056         finished = numberChanged == saveNumberChanged;
    1057     }
    1058     delete [] which;
    1059     delete [] changeRhs;
    1060     delete [] ignore;
    1061     //if (numberInteger&&!noPrinting_)
    1062     //printf("%d integer variables",numberInteger);
    1063     if (changeInt) {
    1064         //if (!noPrinting_) {
    1065         //if (numberChanged)
    1066         //  printf(" and %d variables made integer\n",numberChanged);
    1067         //else
    1068         //  printf("\n");
    1069         //}
    1070         delete [] ignore;
    1071         //increment=0.0;
    1072         if (!numberChanged) {
    1073             delete [] changed;
    1074             delete solver;
    1075             return NULL;
    1076         } else {
    1077             for (iColumn = 0; iColumn < numberColumns; iColumn++) {
    1078                 if (solver->isInteger(iColumn))
    1079                     solverMod->setInteger(iColumn);
    1080             }
    1081             delete solver;
    1082             return changed;
    1083         }
    1084     } else {
    1085         //if (!noPrinting_) {
    1086         //if (numberChanged)
    1087         //  printf(" and %d variables could be made integer\n",numberChanged);
    1088         //else
    1089         //  printf("\n");
    1090         //}
    1091         // just get increment
    1092         int logLevel = generalMessageHandler->logLevel();
    1093         CbcModel model(*solver);
    1094         model.passInMessageHandler(generalMessageHandler);
    1095         if (noPrinting_)
    1096             model.setLogLevel(0);
    1097         model.analyzeObjective();
    1098         generalMessageHandler->setLogLevel(logLevel);
    1099         double increment2 = model.getCutoffIncrement();
    1100         if (increment2 > increment && increment2 > 0.0) {
    1101             if (!noPrinting_) {
    1102                 sprintf(generalPrint, "Cutoff increment increased from %g to %g", increment, increment2);
    1103                 CoinMessages generalMessages = solverMod->getModelPtr()->messages();
    1104                 generalMessageHandler->message(CLP_GENERAL, generalMessages)
    1105                 << generalPrint
    1106                 << CoinMessageEol;
    1107             }
    1108             increment = increment2;
    1109         }
    1110         delete solver;
    1111         numberChanged = 0;
    1112         delete [] changed;
    1113         return NULL;
    1114     }
    1115 }
    1116 #endif  // ifndef CBC_OTHER_SOLVER
    1117 
    1118800
    1119801
     
    17351417}
    17361418
     1419
     1420/*
     1421  Global parameters for command processing.
     1422
     1423  These will need to be moved into an object of some sort in order to make
     1424  this set of calls thread-safe.
     1425*/
    17371426
    17381427int CbcOrClpRead_mode = 1;
Note: See TracChangeset for help on using the changeset viewer.