source: trunk/Cbc/examples/sos.cpp @ 2496

Last change on this file since 2496 was 2469, checked in by unxusr, 9 months ago

formatting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.6 KB
Line 
1// $Id: sos.cpp 2469 2019-01-06 23:17:46Z forrest $
2// Copyright (C) 2005, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#include <cassert>
7#include <iomanip>
8
9#include "CoinPragma.hpp"
10
11// For Branch and bound
12#include "CbcModel.hpp"
13#include "CbcBranchActual.hpp"
14#include "OsiClpSolverInterface.hpp"
15
16// Time
17#include "CoinTime.hpp"
18
19/************************************************************************
20
21This main program reads in an integer model from an mps file.
22
23It then tries to find SOS structure
24
25*************************************************************************/
26int main(int argc, const char *argv[])
27{
28
29  // Define your favorite OsiSolver
30
31  OsiClpSolverInterface solver1;
32
33  // Read in model using argv[1]
34  // and assert that it is a clean model
35  std::string mpsFileName;
36#if defined(MIPLIB3DIR)
37  mpsFileName = MIPLIB3DIR "/10teams";
38#else
39  if (argc < 2) {
40    fprintf(stderr, "Do not know where to find miplib3 MPS files.\n");
41    exit(1);
42  }
43#endif
44  if (argc >= 2)
45    mpsFileName = argv[1];
46  int numMpsReadErrors = solver1.readMps(mpsFileName.c_str(), "");
47  if (numMpsReadErrors != 0) {
48    printf("%d errors reading MPS file\n", numMpsReadErrors);
49    return numMpsReadErrors;
50  }
51
52  int iRow, iColumn;
53  int numberColumns = solver1.getNumCols();
54  int numberRows = solver1.getNumRows();
55  // get row copy
56  const CoinPackedMatrix *matrix = solver1.getMatrixByRow();
57  const double *element = matrix->getElements();
58  const int *column = matrix->getIndices();
59  const CoinBigIndex *rowStart = matrix->getVectorStarts();
60  const int *rowLength = matrix->getVectorLengths();
61  const double *rowLower = solver1.getRowLower();
62  const double *rowUpper = solver1.getRowUpper();
63  const double *columnLower = solver1.getColLower();
64
65  // Look for possible SOS
66  int numberSOS = 0;
67  int *mark = new int[numberColumns];
68  CoinFillN(mark, numberColumns, -1);
69  for (iRow = 0; iRow < numberRows; iRow++) {
70    if (rowLower[iRow] == 1.0 && rowUpper[iRow] == 1.0) {
71      bool goodRow = true;
72      for (int j = rowStart[iRow]; j < rowStart[iRow] + rowLength[iRow]; j++) {
73        int iColumn = column[j];
74        if (element[j] != 1.0 || !solver1.isInteger(iColumn) || mark[iColumn] >= 0 || columnLower[iColumn]) {
75          goodRow = false;
76          break;
77        }
78      }
79      if (goodRow) {
80        // mark all
81        for (int j = rowStart[iRow]; j < rowStart[iRow] + rowLength[iRow]; j++) {
82          int iColumn = column[j];
83          mark[iColumn] = numberSOS;
84        }
85        numberSOS++;
86      }
87    }
88  }
89  std::cout << numberSOS << " SOS" << std::endl;
90  if (!numberSOS)
91    return 0;
92    /*  This example does not look to find the correct order.  SOS are much more
93      powerful if there is a genuine order e.g. size or time.
94
95      There are two pieces of code here.
96      1) Leave integrality conditions and add SOS as extra.  They should have
97      a higher priority.
98      2) Take off integrality conditions and do as SOS of type 2.  This is artificial
99      in this case.
100  */
101    //#define SOS2
102#ifndef SOS2
103  CbcModel model(solver1);
104  // Do sets and priorities
105  CbcObject **objects = new CbcObject *[numberSOS];
106  int numberIntegers = model.numberIntegers();
107  /* model may not have created objects
108     If none then create
109  */
110  if (!numberIntegers || !model.numberObjects()) {
111    model.findIntegers(true);
112    numberIntegers = model.numberIntegers();
113  }
114  int *priority = new int[numberSOS];
115  // Set SOS priorities high
116  CoinFillN(priority, numberSOS, 1);
117  // Set up SOS
118  int *which = new int[numberColumns];
119  for (int iSOS = 0; iSOS < numberSOS; iSOS++) {
120    int n = 0;
121    for (iColumn = 0; iColumn < numberColumns; iColumn++) {
122      if (mark[iColumn] == iSOS)
123        which[n++] = iColumn;
124    }
125    // NULL uses 0,1,2 .. as weights
126    objects[iSOS] = new CbcSOS(&model, n, which, NULL, iSOS, 1);
127  }
128#else
129  // take off integers
130  for (iColumn = 0; iColumn < numberColumns; iColumn++)
131    solver1.setContinuous(iColumn);
132  CbcModel model(solver1);
133  // Do sets and priorities
134  CbcObject **objects = new CbcObject *[numberSOS];
135  // Set up SOS
136  int *which = new int[numberColumns];
137  for (int iSOS = 0; iSOS < numberSOS; iSOS++) {
138    int n = 0;
139    for (iColumn = 0; iColumn < numberColumns; iColumn++) {
140      if (mark[iColumn] == iSOS)
141        which[n++] = iColumn;
142    }
143    // NULL uses 0,1,2 .. as weights
144    objects[iSOS] = new CbcSOS(&model, n, which, NULL, iSOS, 2);
145  }
146#endif
147  delete[] mark;
148  delete[] which;
149  model.addObjects(numberSOS, objects);
150  for (iColumn = 0; iColumn < numberSOS; iColumn++)
151    delete objects[iColumn];
152  delete[] objects;
153#ifndef SOS2
154  model.passInPriorities(priority, true);
155  delete[] priority;
156#endif
157
158  // If time is given then stop after that number of minutes
159  if (argc > 2) {
160    int minutes = atoi(argv[2]);
161    std::cout << "Stopping after " << minutes << " minutes" << std::endl;
162    assert(minutes >= 0);
163    model.setDblParam(CbcModel::CbcMaximumSeconds, 60.0 * minutes);
164  }
165  // Switch off most output
166  model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
167  if (model.getNumCols() < 3000) {
168    model.messageHandler()->setLogLevel(1);
169    //model.solver()->messageHandler()->setLogLevel(0);
170  } else {
171    model.messageHandler()->setLogLevel(2);
172    model.solver()->messageHandler()->setLogLevel(1);
173  }
174  model.messageHandler()->setLogLevel(1);
175
176  double time1 = CoinCpuTime();
177
178  // Do complete search
179
180  model.branchAndBound();
181
182  std::cout << mpsFileName << " took " << CoinCpuTime() - time1 << " seconds, "
183            << model.getNodeCount() << " nodes with objective "
184            << model.getObjValue()
185            << (!model.status() ? " Finished" : " Not finished")
186            << std::endl;
187
188  // Print solution - we can't get names from Osi!
189
190  if (model.getMinimizationObjValue() < 1.0e50) {
191    int numberColumns = model.solver()->getNumCols();
192
193    const double *solution = model.solver()->getColSolution();
194
195    int iColumn;
196    std::cout << std::setiosflags(std::ios::fixed | std::ios::showpoint) << std::setw(14);
197
198    std::cout << "--------------------------------------" << std::endl;
199    for (iColumn = 0; iColumn < numberColumns; iColumn++) {
200      double value = solution[iColumn];
201#ifndef SOS2
202      if (fabs(value) > 1.0e-7 && model.solver()->isInteger(iColumn))
203        std::cout << std::setw(6) << iColumn << " " << value << std::endl;
204#else
205      if (fabs(value) > 1.0e-7)
206        std::cout << std::setw(6) << iColumn << " " << value << std::endl;
207#endif
208    }
209    std::cout << "--------------------------------------" << std::endl;
210
211    std::cout << std::resetiosflags(std::ios::fixed | std::ios::showpoint | std::ios::scientific);
212  }
213  return 0;
214}
Note: See TracBrowser for help on using the repository browser.