source: stable/2.8/Cbc/src/CbcMipStartIO.cpp @ 2012

Last change on this file since 2012 was 2012, checked in by forrest, 5 years ago

mipstart mods
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.6 KB
Line 
1#include <cstdlib>
2#include <cmath>
3#include <ctime>
4#include <cassert>
5#include <cstdio>
6#include <cstring>
7#include <algorithm>
8#include <vector>
9#include <string>
10#include <map>
11#include <OsiSolverInterface.hpp>
12#include "CbcMessage.hpp"
13#include "CbcHeuristic.hpp"
14#include <CbcModel.hpp>
15#include "CbcMipStartIO.hpp"
16#include "CoinTime.hpp"
17
18using namespace std;
19
20
21bool isNumericStr( const char *str )
22{
23   const size_t l = strlen(str);
24
25   for ( size_t i=0 ; i<l ; ++i )
26     if (!(isdigit(str[i])||(str[i]=='.')||(str[i]=='-')))
27         return false;
28
29   return true;
30}
31
32int readMIPStart( CbcModel * model, const char *fileName,
33                  vector< pair< string, double > > &colValues,
34                  double &/*solObj*/ )
35{
36#define STR_SIZE 256
37   FILE *f = fopen( fileName, "r" );
38   if (!f)
39      return 1;
40   char line[STR_SIZE];
41
42   int nLine = 0;
43   char printLine[STR_SIZE];
44   while (fgets( line, STR_SIZE, f ))
45   {
46      ++nLine;
47      char col[4][STR_SIZE];
48      int nread = sscanf( line, "%s %s %s %s", col[0], col[1], col[2], col[3] );
49      if (!nread)
50         continue;
51      /* line with variable value */
52      if (strlen(col[0])&&isdigit(col[0][0])&&(nread>=3))
53      {
54         if (!isNumericStr(col[0]))
55         {
56            sprintf( printLine, "Reading: %s, line %d - first column in mipstart file should be numeric, ignoring.", fileName, nLine );
57            model->messageHandler()->message(CBC_GENERAL, model->messages())
58              << printLine << CoinMessageEol;
59            continue;
60         }
61         if (!isNumericStr(col[2]))
62         {
63            sprintf( printLine, "Reading: %s, line %d - Third column in mipstart file should be numeric, ignoring.", fileName, nLine  );
64            model->messageHandler()->message(CBC_GENERAL, model->messages())
65              << printLine << CoinMessageEol;
66            continue;
67         }
68
69         //int idx = atoi( col[0] );
70         char *name = col[1];
71         double value = atof( col[2] );
72         //double obj = 0.0;
73//         if (nread >= 4)
74//            obj = atof( col[3] );
75
76         colValues.push_back( pair<string, double>(string(name),value) );
77      }
78   }
79
80   if (colValues.size()) {
81      sprintf( printLine,"mipstart values read for %d variables.", (int)colValues.size());
82      model->messageHandler()->message(CBC_GENERAL, model->messages())
83        << printLine << CoinMessageEol;
84      if (colValues.size()<model->getNumCols()) {
85        int numberColumns = model->getNumCols();
86        OsiSolverInterface * solver = model->solver();
87        vector< pair< string, double > > fullValues;
88        /* for fast search of column names */
89        map< string, int > colIdx;
90        for (int i=0;i<numberColumns;i++) {
91          fullValues.push_back( pair<string, double>(solver->getColName(i),0.0) );
92          colIdx[solver->getColName(i)] = i;
93        }
94        for ( int i=0 ; (i<(int)colValues.size()) ; ++i )
95          {
96            map< string, int >::const_iterator mIt = colIdx.find( colValues[i].first );
97            if ( mIt != colIdx.end() ) {
98              const int idx = mIt->second;
99              double v = colValues[i].second;
100              fullValues[idx].second=v;
101            }
102          }
103        colValues=fullValues;
104      }
105   } else
106   {
107      sprintf( printLine, "No mipstart solution read from %s", fileName );
108      model->messageHandler()->message(CBC_GENERAL, model->messages())
109        << printLine << CoinMessageEol;
110      return 1;
111   }
112
113   fclose(f);
114   return 0;
115}
116
117int computeCompleteSolution( CbcModel * model,
118                             const vector< string > colNames,
119                             const std::vector< std::pair< std::string, double > > &colValues,
120                             double *sol, double &obj )
121{
122   int status = 0;
123   double compObj = COIN_DBL_MAX;
124   bool foundIntegerSol = false;
125   OsiSolverInterface *lp = model->solver()->clone();
126   map< string, int > colIdx;
127   assert( ((int)colNames.size()) == lp->getNumCols() );
128
129   /* for fast search of column names */
130   for ( int i=0 ; (i<(int)colNames.size()) ; ++i )
131      colIdx[colNames[i]] = i;
132
133   char printLine[STR_SIZE];
134   int fixed = 0;
135   int notFound = 0;
136   char colNotFound[256] = "";
137   int nContinuousFixed = 0;
138   for ( int i=0 ; (i<(int)colValues.size()) ; ++i )
139   {
140      map< string, int >::const_iterator mIt = colIdx.find( colValues[i].first );
141      if ( mIt == colIdx.end() )
142      {
143         if (!notFound)
144            strcpy( colNotFound, colValues[i].first.c_str() );
145         notFound++;
146      }
147      else
148      {
149         const int idx = mIt->second;
150         double v = colValues[i].second;
151         if (v<1e-8)
152            v = 0.0;
153         if (lp->isInteger(idx))  // just to avoid small
154            v = floor( v+0.5 );   // fractional garbage
155         else
156           nContinuousFixed++;
157         lp->setColBounds( idx, v, v );
158         ++fixed;
159      }
160   }
161
162   if (!fixed)
163   {
164      model->messageHandler()->message(CBC_GENERAL, model->messages())
165        << "Warning: MIPstart solution is not valid, ignoring it."
166        << CoinMessageEol;
167      goto TERMINATE;
168   }
169
170   if ( notFound >= ( ((double)colNames.size()) * 0.5 ) ) {
171      sprintf( printLine, "Warning: %d column names were not found (e.g. %s) while filling solution.", notFound, colNotFound );
172      model->messageHandler()->message(CBC_GENERAL, model->messages())
173        << printLine << CoinMessageEol;
174   }
175
176   lp->initialSolve();
177   if (!lp->isProvenOptimal())
178   {
179      model->messageHandler()->message(CBC_GENERAL, model->messages())
180        << "Warning: mipstart values could not be used to build a solution." << CoinMessageEol;
181      if (nContinuousFixed) {
182        model->messageHandler()->message(CBC_GENERAL, model->messages())
183          << "Trying just fixing integer variables." << CoinMessageEol;
184        int numberColumns = lp->getNumCols();
185        const double * oldLower = model->solver()->getColLower();
186        const double * oldUpper = model->solver()->getColUpper();
187        for ( int i=0 ; i<numberColumns ; ++i ) {
188          if (!lp->isInteger(i)) {
189            lp->setColLower(i,oldLower[i]);
190            lp->setColUpper(i,oldUpper[i]);
191          }
192        }
193        lp->initialSolve();
194        if (!lp->isProvenOptimal())
195          model->messageHandler()->message(CBC_GENERAL, model->messages())
196            << "Still no good." << CoinMessageEol;
197      }
198      if (!lp->isProvenOptimal()) {
199        status = 1;
200        goto TERMINATE;
201      }
202   }
203
204   /* some additional effort is needed to provide an integer solution */
205   if ( lp->getFractionalIndices().size() > 0 )
206   {
207      sprintf( printLine,"MIPStart solution provided values for %d of %d integer variables, %d variables are still fractional.", fixed, lp->getNumIntegers(), (int)lp->getFractionalIndices().size() );
208      model->messageHandler()->message(CBC_GENERAL, model->messages())
209        << printLine << CoinMessageEol;
210      double start = CoinCpuTime();
211#if 1
212      CbcSerendipity heuristic(*model);
213      heuristic.setFractionSmall(2.0);
214      heuristic.setFeasibilityPumpOptions(1008013);
215      int returnCode = heuristic.smallBranchAndBound(lp,
216                                                     1000, sol,
217                                                     compObj,
218                                                     model->getCutoff(), 
219                                                     "ReduceInMIPStart");
220      if ((returnCode&1) != 0) {
221         sprintf( printLine,"Mini branch and bound defined values for remaining variables in %.2f seconds.", 
222                  CoinCpuTime()-start);
223         model->messageHandler()->message(CBC_GENERAL, model->messages())
224           << printLine << CoinMessageEol;
225         foundIntegerSol = true;
226         obj = compObj;
227      }
228#else
229      CbcModel babModel( *lp );
230      babModel.setLogLevel( 0 );
231      babModel.setMaximumNodes( 500 );
232      babModel.setMaximumSeconds( 60 );
233      babModel.branchAndBound();
234      if (babModel.bestSolution())
235      {
236         sprintf( printLine,"Mini branch and bound defined values for remaining variables in %.2f seconds.", 
237                  CoinCpuTime()-start);
238         model->messageHandler()->message(CBC_GENERAL, model->messages())
239           << printLine << CoinMessageEol;
240         copy( babModel.bestSolution(), babModel.bestSolution()+babModel.getNumCols(), sol );
241         foundIntegerSol = true;
242         obj = compObj = babModel.getObjValue();
243      }
244#endif
245      else
246      {
247         model->messageHandler()->message(CBC_GENERAL, model->messages())
248           << "Warning: mipstart values could not be used to build a solution." << CoinMessageEol;
249         status = 1;
250         goto TERMINATE;
251      }
252   }
253   else
254   {
255      foundIntegerSol = true;
256      obj = compObj = lp->getObjValue();
257      copy( lp->getColSolution(), lp->getColSolution()+lp->getNumCols(), sol );
258   }
259
260   if ( foundIntegerSol )
261   {
262      sprintf( printLine,"mipstart provided solution with cost %g", compObj);
263      model->messageHandler()->message(CBC_GENERAL, model->messages())
264        << printLine << CoinMessageEol;
265      for ( int i=0 ; (i<lp->getNumCols()) ; ++i )
266      {
267         if (sol[i]<1e-8)
268            sol[i] = 0.0;
269         else
270            if (lp->isInteger(i))
271               sol[i] = floor( sol[i]+0.5 );
272      }
273   }
274
275TERMINATE:
276   delete lp;
277   return status;
278}
279#undef STR_SIZE
Note: See TracBrowser for help on using the repository browser.