source: stable/2.8/Cbc/examples/sos.cpp @ 1856

Last change on this file since 1856 was 1574, checked in by lou, 8 years ago

Change to EPL license notice.

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