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 | |
---|
18 | using namespace std; |
---|
19 | |
---|
20 | |
---|
21 | bool 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 | |
---|
32 | int 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 | |
---|
117 | int 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 | |
---|
275 | TERMINATE: |
---|
276 | delete lp; |
---|
277 | return status; |
---|
278 | } |
---|
279 | #undef STR_SIZE |
---|