source: branches/devel/Cbc/examples/sos.cpp @ 425

Last change on this file since 425 was 333, checked in by andreasw, 14 years ago

finished examples subdir

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