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

Last change on this file since 1902 was 1902, checked in by stefan, 5 years ago

sync with trunk rev 1901

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.5 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 <CbcModel.hpp>
14#include "CbcMipStartIO.hpp"
15#include "CoinTime.hpp"
16
17using namespace std;
18
19
20bool isNumericStr( const char *str )
21{
22   const size_t l = strlen(str);
23
24   for ( size_t i=0 ; i<l ; ++i )
25      if (!(isdigit(str[i])||(str[i]=='.')))
26         return false;
27
28   return true;
29}
30
31int readMIPStart( CbcModel * model, const char *fileName,
32                  vector< pair< string, double > > &colValues,
33                  double &/*solObj*/ )
34{
35#define STR_SIZE 256
36   FILE *f = fopen( fileName, "r" );
37   if (!f)
38      return 1;
39   char line[STR_SIZE];
40
41   int nLine = 0;
42   char printLine[STR_SIZE];
43   while (fgets( line, STR_SIZE, f ))
44   {
45      ++nLine;
46      char col[4][STR_SIZE];
47      int nread = sscanf( line, "%s %s %s %s", col[0], col[1], col[2], col[3] );
48      if (!nread)
49         continue;
50      /* line with variable value */
51      if (strlen(col[0])&&isdigit(col[0][0])&&(nread>=3))
52      {
53         if (!isNumericStr(col[0]))
54         {
55            sprintf( printLine, "Reading: %s, line %d - first column in mipstart file should be numeric, ignoring.", fileName, nLine );
56            model->messageHandler()->message(CBC_GENERAL, model->messages())
57              << printLine << CoinMessageEol;
58            continue;
59         }
60         if (!isNumericStr(col[2]))
61         {
62            sprintf( printLine, "Reading: %s, line %d - Third column in mipstart file should be numeric, ignoring.", fileName, nLine  );
63            model->messageHandler()->message(CBC_GENERAL, model->messages())
64              << printLine << CoinMessageEol;
65            continue;
66         }
67
68         //int idx = atoi( col[0] );
69         char *name = col[1];
70         double value = atof( col[2] );
71         //double obj = 0.0;
72//         if (nread >= 4)
73//            obj = atof( col[3] );
74
75         colValues.push_back( pair<string, double>(string(name),value) );
76      }
77   }
78
79   if (colValues.size()) {
80      sprintf( printLine,"mipstart values read for %d variables.", (int)colValues.size());
81      model->messageHandler()->message(CBC_GENERAL, model->messages())
82        << printLine << CoinMessageEol;
83   } else
84   {
85      sprintf( printLine, "No mipstart solution read from %s", fileName );
86      model->messageHandler()->message(CBC_GENERAL, model->messages())
87        << printLine << CoinMessageEol;
88      return 1;
89   }
90
91   fclose(f);
92   return 0;
93}
94
95int computeCompleteSolution( CbcModel * model,
96                             const vector< string > colNames,
97                             const std::vector< std::pair< std::string, double > > &colValues,
98                             double *sol, double &obj )
99{
100   int status = 0;
101   double compObj = COIN_DBL_MAX;
102   bool foundIntegerSol = false;
103   OsiSolverInterface *lp = model->solver()->clone();
104   map< string, int > colIdx;
105   assert( ((int)colNames.size()) == lp->getNumCols() );
106
107   /* for fast search of column names */
108   for ( int i=0 ; (i<(int)colNames.size()) ; ++i )
109      colIdx[colNames[i]] = i;
110
111   char printLine[STR_SIZE];
112   int fixed = 0;
113   int notFound = 0;
114   char colNotFound[256] = "";
115   for ( int i=0 ; (i<(int)colValues.size()) ; ++i )
116   {
117      map< string, int >::const_iterator mIt = colIdx.find( colValues[i].first );
118      if ( mIt == colIdx.end() )
119      {
120         if (!notFound)
121            strcpy( colNotFound, colValues[i].first.c_str() );
122         notFound++;
123      }
124      else
125      {
126         const int idx = mIt->second;
127         double v = colValues[i].second;
128         if (v<1e-8)
129            v = 0.0;
130         if (lp->isInteger(idx))  // just to avoid small
131            v = floor( v+0.5 );   // fractional garbage
132         lp->setColBounds( idx, v, v );
133         ++fixed;
134      }
135   }
136
137   if (!fixed)
138   {
139      model->messageHandler()->message(CBC_GENERAL, model->messages())
140        << "Warning: MIPstart solution is not valid, ignoring it."
141        << CoinMessageEol;
142      goto TERMINATE;
143   }
144
145   if ( notFound >= ( ((double)colNames.size()) * 0.5 ) ) {
146      sprintf( printLine, "Warning: %d column names were not found (e.g. %s) while filling solution.", notFound, colNotFound );
147      model->messageHandler()->message(CBC_GENERAL, model->messages())
148        << printLine << CoinMessageEol;
149   }
150
151   lp->initialSolve();
152   if (!lp->isProvenOptimal())
153   {
154      model->messageHandler()->message(CBC_GENERAL, model->messages())
155        << "Warning: mipstart values could not be used to build a solution." << CoinMessageEol;
156      status = 1;
157      goto TERMINATE;
158   }
159
160   /* some additional effort is needed to provide an integer solution */
161   if ( lp->getFractionalIndices().size() > 0 )
162   {
163      sprintf( printLine,"MIPStart solution provided values for %d of %d integer variables, %d variables are still fractional.", fixed, lp->getNumIntegers(), (int)lp->getFractionalIndices().size() );
164      model->messageHandler()->message(CBC_GENERAL, model->messages())
165        << printLine << CoinMessageEol;
166      double start = CoinCpuTime();
167      CbcModel babModel( *lp );
168      babModel.setLogLevel( 0 );
169      babModel.setMaximumNodes( 500 );
170      babModel.setMaximumSeconds( 60 );
171      babModel.branchAndBound();
172      if (babModel.bestSolution())
173      {
174         sprintf( printLine,"Mini branch and bound defined values for remaining variables in %.2f seconds.", 
175                  CoinCpuTime()-start);
176         model->messageHandler()->message(CBC_GENERAL, model->messages())
177           << printLine << CoinMessageEol;
178         copy( babModel.bestSolution(), babModel.bestSolution()+babModel.getNumCols(), sol );
179         foundIntegerSol = true;
180         obj = compObj = babModel.getObjValue();
181      }
182      else
183      {
184         model->messageHandler()->message(CBC_GENERAL, model->messages())
185           << "Warning: mipstart values could not be used to build a solution." << CoinMessageEol;
186         status = 1;
187         goto TERMINATE;
188      }
189   }
190   else
191   {
192      foundIntegerSol = true;
193      obj = compObj = lp->getObjValue();
194      copy( lp->getColSolution(), lp->getColSolution()+lp->getNumCols(), sol );
195   }
196
197   if ( foundIntegerSol )
198   {
199      sprintf( printLine,"mipstart provided solution with cost %g", compObj);
200      model->messageHandler()->message(CBC_GENERAL, model->messages())
201        << printLine << CoinMessageEol;
202      for ( int i=0 ; (i<lp->getNumCols()) ; ++i )
203      {
204         if (sol[i]<1e-8)
205            sol[i] = 0.0;
206         else
207            if (lp->isInteger(i))
208               sol[i] = floor( sol[i]+0.5 );
209      }
210   }
211
212TERMINATE:
213   delete lp;
214   return status;
215}
216#undef STR_SIZE
Note: See TracBrowser for help on using the repository browser.