[1574] | 1 | // $Id: nway.cpp 2469 2019-01-06 23:17:46Z forrest $ |
---|
[215] | 2 | // Copyright (C) 2005, International Business Machines |
---|
| 3 | // Corporation and others. All Rights Reserved. |
---|
[1574] | 4 | // This code is licensed under the terms of the Eclipse Public License (EPL). |
---|
| 5 | |
---|
[215] | 6 | #include <cassert> |
---|
| 7 | #include <iomanip> |
---|
| 8 | |
---|
[1898] | 9 | #include "CoinPragma.hpp" |
---|
[215] | 10 | // For Branch and bound |
---|
| 11 | #include "CbcModel.hpp" |
---|
| 12 | #include "CbcBranchActual.hpp" |
---|
| 13 | #include "OsiClpSolverInterface.hpp" |
---|
| 14 | |
---|
| 15 | // Time |
---|
| 16 | #include "CoinTime.hpp" |
---|
| 17 | |
---|
| 18 | /************************************************************************ |
---|
| 19 | |
---|
| 20 | This main program reads in an integer model from an mps file. |
---|
| 21 | |
---|
| 22 | It then tries to find SOS structure and solves using N-way variables |
---|
| 23 | |
---|
| 24 | *************************************************************************/ |
---|
[2469] | 25 | int main(int argc, const char *argv[]) |
---|
[215] | 26 | { |
---|
[2469] | 27 | |
---|
[215] | 28 | // Define your favorite OsiSolver |
---|
[2469] | 29 | |
---|
[215] | 30 | OsiClpSolverInterface solver1; |
---|
[2469] | 31 | |
---|
[215] | 32 | // Read in model using argv[1] |
---|
| 33 | // and assert that it is a clean model |
---|
[1464] | 34 | std::string mpsFileName; |
---|
[1468] | 35 | #if defined(MIPLIB3DIR) |
---|
[1464] | 36 | mpsFileName = MIPLIB3DIR "/10teams"; |
---|
| 37 | #else |
---|
| 38 | if (argc < 2) { |
---|
| 39 | fprintf(stderr, "Do not know where to find miplib3 MPS files.\n"); |
---|
| 40 | exit(1); |
---|
| 41 | } |
---|
| 42 | #endif |
---|
[2469] | 43 | if (argc >= 2) |
---|
| 44 | mpsFileName = argv[1]; |
---|
| 45 | int numMpsReadErrors = solver1.readMps(mpsFileName.c_str(), ""); |
---|
| 46 | if (numMpsReadErrors != 0) { |
---|
| 47 | printf("%d errors reading MPS file\n", numMpsReadErrors); |
---|
| 48 | return numMpsReadErrors; |
---|
[1898] | 49 | } |
---|
[2469] | 50 | |
---|
[215] | 51 | int iRow, iColumn; |
---|
| 52 | int numberColumns = solver1.getNumCols(); |
---|
| 53 | int numberRows = solver1.getNumRows(); |
---|
| 54 | // get row copy |
---|
[2469] | 55 | const CoinPackedMatrix *matrix = solver1.getMatrixByRow(); |
---|
| 56 | const double *element = matrix->getElements(); |
---|
| 57 | const int *column = matrix->getIndices(); |
---|
| 58 | const CoinBigIndex *rowStart = matrix->getVectorStarts(); |
---|
| 59 | const int *rowLength = matrix->getVectorLengths(); |
---|
| 60 | const double *rowLower = solver1.getRowLower(); |
---|
| 61 | const double *rowUpper = solver1.getRowUpper(); |
---|
| 62 | const double *columnLower = solver1.getColLower(); |
---|
| 63 | |
---|
[215] | 64 | // Look for possible SOS |
---|
[2469] | 65 | int numberSOS = 0; |
---|
| 66 | int *mark = new int[numberColumns]; |
---|
| 67 | CoinFillN(mark, numberColumns, -1); |
---|
| 68 | for (iRow = 0; iRow < numberRows; iRow++) { |
---|
| 69 | if (rowLower[iRow] == 1.0 && rowUpper[iRow] == 1.0) { |
---|
| 70 | bool goodRow = true; |
---|
| 71 | for (int j = rowStart[iRow]; j < rowStart[iRow] + rowLength[iRow]; j++) { |
---|
[215] | 72 | int iColumn = column[j]; |
---|
[2469] | 73 | if (element[j] != 1.0 || !solver1.isInteger(iColumn) || mark[iColumn] >= 0 || columnLower[iColumn]) { |
---|
| 74 | goodRow = false; |
---|
[215] | 75 | break; |
---|
| 76 | } |
---|
| 77 | } |
---|
| 78 | if (goodRow) { |
---|
| 79 | // mark all |
---|
[2469] | 80 | for (int j = rowStart[iRow]; j < rowStart[iRow] + rowLength[iRow]; j++) { |
---|
[215] | 81 | int iColumn = column[j]; |
---|
[2469] | 82 | mark[iColumn] = numberSOS; |
---|
[215] | 83 | } |
---|
| 84 | numberSOS++; |
---|
| 85 | } |
---|
| 86 | } |
---|
| 87 | } |
---|
[2469] | 88 | std::cout << numberSOS << " SOS" << std::endl; |
---|
[215] | 89 | if (!numberSOS) |
---|
| 90 | return 0; |
---|
| 91 | CbcModel model(solver1); |
---|
| 92 | // Do sets and priorities |
---|
[2469] | 93 | CbcObject **objects = new CbcObject *[numberSOS]; |
---|
[215] | 94 | int numberIntegers = model.numberIntegers(); |
---|
| 95 | /* model may not have created objects |
---|
| 96 | If none then create |
---|
| 97 | */ |
---|
[2469] | 98 | if (!numberIntegers || !model.numberObjects()) { |
---|
[215] | 99 | model.findIntegers(true); |
---|
| 100 | numberIntegers = model.numberIntegers(); |
---|
| 101 | } |
---|
[2469] | 102 | int *priority = new int[numberSOS]; |
---|
[215] | 103 | // Set SOS priorities high |
---|
[2469] | 104 | CoinFillN(priority, numberSOS, 1); |
---|
[215] | 105 | // Set up SOS |
---|
[2469] | 106 | int *which = new int[numberColumns]; |
---|
| 107 | for (int iSOS = 0; iSOS < numberSOS; iSOS++) { |
---|
| 108 | int n = 0; |
---|
| 109 | for (iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 110 | if (mark[iColumn] == iSOS) |
---|
| 111 | which[n++] = iColumn; |
---|
[215] | 112 | } |
---|
| 113 | // NULL uses 0,1,2 .. as weights |
---|
[2469] | 114 | objects[iSOS] = new CbcNWay(&model, n, which, iSOS); |
---|
[215] | 115 | } |
---|
[2469] | 116 | delete[] mark; |
---|
| 117 | delete[] which; |
---|
| 118 | model.addObjects(numberSOS, objects); |
---|
| 119 | for (iColumn = 0; iColumn < numberSOS; iColumn++) |
---|
[215] | 120 | delete objects[iColumn]; |
---|
[2469] | 121 | delete[] objects; |
---|
| 122 | model.passInPriorities(priority, true); |
---|
| 123 | delete[] priority; |
---|
[215] | 124 | |
---|
| 125 | // If time is given then stop after that number of minutes |
---|
[2469] | 126 | if (argc > 2) { |
---|
[215] | 127 | int minutes = atoi(argv[2]); |
---|
[2469] | 128 | std::cout << "Stopping after " << minutes << " minutes" << std::endl; |
---|
| 129 | assert(minutes >= 0); |
---|
| 130 | model.setDblParam(CbcModel::CbcMaximumSeconds, 60.0 * minutes); |
---|
[215] | 131 | } |
---|
| 132 | // Switch off most output |
---|
[2469] | 133 | model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry); |
---|
| 134 | if (model.getNumCols() < 3000) { |
---|
[215] | 135 | model.messageHandler()->setLogLevel(1); |
---|
| 136 | //model.solver()->messageHandler()->setLogLevel(0); |
---|
| 137 | } else { |
---|
| 138 | model.messageHandler()->setLogLevel(2); |
---|
| 139 | //model.solver()->messageHandler()->setLogLevel(1); |
---|
| 140 | } |
---|
| 141 | //model.messageHandler()->setLogLevel(1); |
---|
[2469] | 142 | |
---|
[215] | 143 | double time1 = CoinCpuTime(); |
---|
| 144 | |
---|
| 145 | // Do complete search |
---|
[2469] | 146 | |
---|
[215] | 147 | model.branchAndBound(); |
---|
| 148 | |
---|
[2469] | 149 | std::cout << mpsFileName << " took " << CoinCpuTime() - time1 << " seconds, " |
---|
| 150 | << model.getNodeCount() << " nodes with objective " |
---|
| 151 | << model.getObjValue() |
---|
| 152 | << (!model.status() ? " Finished" : " Not finished") |
---|
| 153 | << std::endl; |
---|
[215] | 154 | |
---|
| 155 | // Print solution - we can't get names from Osi! |
---|
| 156 | |
---|
[2469] | 157 | if (model.getMinimizationObjValue() < 1.0e50) { |
---|
[215] | 158 | int numberColumns = model.solver()->getNumCols(); |
---|
[2469] | 159 | |
---|
| 160 | const double *solution = model.solver()->getColSolution(); |
---|
| 161 | |
---|
[215] | 162 | int iColumn; |
---|
[2469] | 163 | std::cout << std::setiosflags(std::ios::fixed | std::ios::showpoint) << std::setw(14); |
---|
| 164 | |
---|
| 165 | std::cout << "--------------------------------------" << std::endl; |
---|
| 166 | for (iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 167 | double value = solution[iColumn]; |
---|
| 168 | if (fabs(value) > 1.0e-7 && model.solver()->isInteger(iColumn)) |
---|
| 169 | std::cout << std::setw(6) << iColumn << " " << value << std::endl; |
---|
[215] | 170 | } |
---|
[2469] | 171 | std::cout << "--------------------------------------" << std::endl; |
---|
| 172 | |
---|
| 173 | std::cout << std::resetiosflags(std::ios::fixed | std::ios::showpoint | std::ios::scientific); |
---|
[215] | 174 | } |
---|
| 175 | return 0; |
---|
[2469] | 176 | } |
---|