1 | /* Copyright (C) 2003, International Business Machines Corporation |
---|
2 | and others. All Rights Reserved. |
---|
3 | |
---|
4 | This sample program is designed to illustrate programming |
---|
5 | techniques using CoinLP, has not been thoroughly tested |
---|
6 | and comes without any warranty whatsoever. |
---|
7 | |
---|
8 | You may copy, modify and distribute this sample program without |
---|
9 | any restrictions whatsoever and without any payment to anyone. |
---|
10 | */ |
---|
11 | |
---|
12 | #include "ClpSimplex.hpp" |
---|
13 | #include "ClpPresolve.hpp" |
---|
14 | #include "ClpFactorization.hpp" |
---|
15 | #include "CoinSort.hpp" |
---|
16 | #include "CoinHelperFunctions.hpp" |
---|
17 | #include "CoinTime.hpp" |
---|
18 | #include "CoinMpsIO.hpp" |
---|
19 | #include <iomanip> |
---|
20 | |
---|
21 | int main (int argc, const char *argv[]) |
---|
22 | { |
---|
23 | ClpSimplex model; |
---|
24 | int status; |
---|
25 | // Keep names |
---|
26 | if (argc<2) { |
---|
27 | status=model.readMps("small.mps",true); |
---|
28 | } else { |
---|
29 | status=model.readMps(argv[1],false); |
---|
30 | } |
---|
31 | if (status) |
---|
32 | exit(10); |
---|
33 | /* |
---|
34 | This driver implements a method of treating a problem as all cuts. |
---|
35 | So it adds in all E rows, solves and then adds in violated rows. |
---|
36 | */ |
---|
37 | |
---|
38 | double time1 = CoinCpuTime(); |
---|
39 | ClpSimplex * model2; |
---|
40 | ClpPresolve pinfo; |
---|
41 | int numberPasses=5; // can change this |
---|
42 | /* Use a tolerance of 1.0e-8 for feasibility, treat problem as |
---|
43 | not being integer, do "numberpasses" passes and throw away names |
---|
44 | in presolved model */ |
---|
45 | model2 = pinfo.presolvedModel(model,1.0e-8,false,numberPasses,false); |
---|
46 | if (!model2) { |
---|
47 | fprintf(stderr,"ClpPresolve says %s is infeasible with tolerance of %g\n", |
---|
48 | argv[1],1.0e-8); |
---|
49 | fprintf(stdout,"ClpPresolve says %s is infeasible with tolerance of %g\n", |
---|
50 | argv[1],1.0e-8); |
---|
51 | // model was infeasible - maybe try again with looser tolerances |
---|
52 | model2 = pinfo.presolvedModel(model,1.0e-7,false,numberPasses,false); |
---|
53 | if (!model2) { |
---|
54 | fprintf(stderr,"ClpPresolve says %s is infeasible with tolerance of %g\n", |
---|
55 | argv[1],1.0e-7); |
---|
56 | fprintf(stdout,"ClpPresolve says %s is infeasible with tolerance of %g\n", |
---|
57 | argv[1],1.0e-7); |
---|
58 | exit(2); |
---|
59 | } |
---|
60 | } |
---|
61 | // change factorization frequency from 200 |
---|
62 | model2->setFactorizationFrequency(100+model2->numberRows()/50); |
---|
63 | |
---|
64 | int numberColumns = model2->numberColumns(); |
---|
65 | int originalNumberRows = model2->numberRows(); |
---|
66 | |
---|
67 | // We will need arrays to choose rows to add |
---|
68 | double * weight = new double [originalNumberRows]; |
---|
69 | int * sort = new int [originalNumberRows]; |
---|
70 | int numberSort=0; |
---|
71 | char * take = new char [originalNumberRows]; |
---|
72 | |
---|
73 | const double * rowLower = model2->rowLower(); |
---|
74 | const double * rowUpper = model2->rowUpper(); |
---|
75 | int iRow,iColumn; |
---|
76 | // Set up initial list |
---|
77 | numberSort=0; |
---|
78 | for (iRow=0;iRow<originalNumberRows;iRow++) { |
---|
79 | weight[iRow]=1.123e50; |
---|
80 | if (rowLower[iRow]==rowUpper[iRow]) { |
---|
81 | sort[numberSort++] = iRow; |
---|
82 | weight[iRow]=0.0; |
---|
83 | } |
---|
84 | } |
---|
85 | numberSort /= 2; |
---|
86 | // Just add this number of rows each time in small problem |
---|
87 | int smallNumberRows = 2*numberColumns; |
---|
88 | smallNumberRows=CoinMin(smallNumberRows,originalNumberRows/20); |
---|
89 | // and pad out with random rows |
---|
90 | double ratio = ((double)(smallNumberRows-numberSort))/((double) originalNumberRows); |
---|
91 | for (iRow=0;iRow<originalNumberRows;iRow++) { |
---|
92 | if (weight[iRow]==1.123e50&&CoinDrand48()<ratio) |
---|
93 | sort[numberSort++] = iRow; |
---|
94 | } |
---|
95 | /* This is optional. |
---|
96 | The best thing to do is to miss out random rows and do a set which makes dual feasible. |
---|
97 | If that is not possible then make sure variables have bounds. |
---|
98 | |
---|
99 | One way that normally works is to automatically tighten bounds. |
---|
100 | */ |
---|
101 | #if 0 |
---|
102 | // However for some we need to do anyway |
---|
103 | double * columnLower = model2->columnLower(); |
---|
104 | double * columnUpper = model2->columnUpper(); |
---|
105 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
106 | columnLower[iColumn]=CoinMax(-1.0e6,columnLower[iColumn]); |
---|
107 | columnUpper[iColumn]=CoinMin(1.0e6,columnUpper[iColumn]); |
---|
108 | } |
---|
109 | #endif |
---|
110 | model2->tightenPrimalBounds(-1.0e4,true); |
---|
111 | printf("%d rows in initial problem\n",numberSort); |
---|
112 | double * fullSolution = model2->primalRowSolution(); |
---|
113 | |
---|
114 | // Just do this number of passes |
---|
115 | int maxPass=50; |
---|
116 | // And take out slack rows until this pass |
---|
117 | int takeOutPass=30; |
---|
118 | int iPass; |
---|
119 | |
---|
120 | const int * start = model2->clpMatrix()->getVectorStarts(); |
---|
121 | const int * length = model2->clpMatrix()->getVectorLengths(); |
---|
122 | const int * row = model2->clpMatrix()->getIndices(); |
---|
123 | int * whichColumns = new int [numberColumns]; |
---|
124 | for (iColumn=0;iColumn<numberColumns;iColumn++) |
---|
125 | whichColumns[iColumn]=iColumn; |
---|
126 | int numberSmallColumns=numberColumns; |
---|
127 | for (iPass=0;iPass<maxPass;iPass++) { |
---|
128 | printf("Start of pass %d\n",iPass); |
---|
129 | // Cleaner this way |
---|
130 | std::sort(sort,sort+numberSort); |
---|
131 | // Create small problem |
---|
132 | ClpSimplex small(model2,numberSort,sort,numberSmallColumns,whichColumns); |
---|
133 | small.setFactorizationFrequency(100+numberSort/200); |
---|
134 | //small.setPerturbation(50); |
---|
135 | //small.setLogLevel(63); |
---|
136 | // A variation is to just do N iterations |
---|
137 | //if (iPass) |
---|
138 | //small.setMaximumIterations(100); |
---|
139 | // Solve |
---|
140 | small.factorization()->messageLevel(8); |
---|
141 | if (iPass) { |
---|
142 | small.dual(); |
---|
143 | } else { |
---|
144 | small.writeMps("continf.mps"); |
---|
145 | ClpSolve solveOptions; |
---|
146 | solveOptions.setSolveType(ClpSolve::useDual); |
---|
147 | //solveOptions.setSolveType(ClpSolve::usePrimalorSprint); |
---|
148 | //solveOptions.setSpecialOption(1,2,200); // idiot |
---|
149 | small.initialSolve(solveOptions); |
---|
150 | } |
---|
151 | bool dualInfeasible = (small.status()==2); |
---|
152 | // move solution back |
---|
153 | double * solution = model2->primalColumnSolution(); |
---|
154 | const double * smallSolution = small.primalColumnSolution(); |
---|
155 | for (int j=0;j<numberSmallColumns;j++) { |
---|
156 | iColumn = whichColumns[j]; |
---|
157 | solution[iColumn]=smallSolution[j]; |
---|
158 | model2->setColumnStatus(iColumn,small.getColumnStatus(j)); |
---|
159 | } |
---|
160 | for (iRow=0;iRow<numberSort;iRow++) { |
---|
161 | int kRow = sort[iRow]; |
---|
162 | model2->setRowStatus(kRow,small.getRowStatus(iRow)); |
---|
163 | } |
---|
164 | // compute full solution |
---|
165 | memset(fullSolution,0,originalNumberRows*sizeof(double)); |
---|
166 | model2->times(1.0,model2->primalColumnSolution(),fullSolution); |
---|
167 | if (iPass!=maxPass-1) { |
---|
168 | // Mark row as not looked at |
---|
169 | for (iRow=0;iRow<originalNumberRows;iRow++) |
---|
170 | weight[iRow]=1.123e50; |
---|
171 | // Look at rows already in small problem |
---|
172 | int iSort; |
---|
173 | int numberDropped=0; |
---|
174 | int numberKept=0; |
---|
175 | int numberBinding=0; |
---|
176 | int numberInfeasibilities=0; |
---|
177 | double sumInfeasibilities=0.0; |
---|
178 | for (iSort=0;iSort<numberSort;iSort++) { |
---|
179 | iRow=sort[iSort]; |
---|
180 | //printf("%d %g %g\n",iRow,fullSolution[iRow],small.primalRowSolution()[iSort]); |
---|
181 | if (model2->getRowStatus(iRow)==ClpSimplex::basic) { |
---|
182 | // Basic - we can get rid of if early on |
---|
183 | if (iPass<takeOutPass&&!dualInfeasible) { |
---|
184 | // may have hit max iterations so check |
---|
185 | double infeasibility = CoinMax(fullSolution[iRow]-rowUpper[iRow], |
---|
186 | rowLower[iRow]-fullSolution[iRow]); |
---|
187 | weight[iRow]=-infeasibility; |
---|
188 | if (infeasibility>1.0e-8) { |
---|
189 | numberInfeasibilities++; |
---|
190 | sumInfeasibilities += infeasibility; |
---|
191 | } else { |
---|
192 | weight[iRow]=1.0; |
---|
193 | numberDropped++; |
---|
194 | } |
---|
195 | } else { |
---|
196 | // keep |
---|
197 | weight[iRow]=-1.0e40; |
---|
198 | numberKept++; |
---|
199 | } |
---|
200 | } else { |
---|
201 | // keep |
---|
202 | weight[iRow]=-1.0e50; |
---|
203 | numberKept++; |
---|
204 | numberBinding++; |
---|
205 | } |
---|
206 | } |
---|
207 | // Now rest |
---|
208 | for (iRow=0;iRow<originalNumberRows;iRow++) { |
---|
209 | sort[iRow]=iRow; |
---|
210 | if (weight[iRow]==1.123e50) { |
---|
211 | // not looked at yet |
---|
212 | double infeasibility = CoinMax(fullSolution[iRow]-rowUpper[iRow], |
---|
213 | rowLower[iRow]-fullSolution[iRow]); |
---|
214 | weight[iRow]=-infeasibility; |
---|
215 | if (infeasibility>1.0e-8) { |
---|
216 | numberInfeasibilities++; |
---|
217 | sumInfeasibilities += infeasibility; |
---|
218 | } |
---|
219 | } |
---|
220 | } |
---|
221 | // sort |
---|
222 | CoinSort_2(weight,weight+originalNumberRows,sort); |
---|
223 | numberSort = CoinMin(originalNumberRows,smallNumberRows+numberKept); |
---|
224 | memset(take,0,originalNumberRows); |
---|
225 | for (iRow=0;iRow<numberSort;iRow++) |
---|
226 | take[sort[iRow]]=1; |
---|
227 | numberSmallColumns=0; |
---|
228 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
229 | int n=0; |
---|
230 | for (int j=start[iColumn];j<start[iColumn]+length[iColumn];j++) { |
---|
231 | int iRow = row[j]; |
---|
232 | if (take[iRow]) |
---|
233 | n++; |
---|
234 | } |
---|
235 | if (n) |
---|
236 | whichColumns[numberSmallColumns++]=iColumn; |
---|
237 | } |
---|
238 | printf("%d rows binding, %d rows kept, %d rows dropped - new size %d rows, %d columns\n", |
---|
239 | numberBinding,numberKept,numberDropped,numberSort,numberSmallColumns); |
---|
240 | printf("%d rows are infeasible - sum is %g\n",numberInfeasibilities, |
---|
241 | sumInfeasibilities); |
---|
242 | if (!numberInfeasibilities) { |
---|
243 | printf("Exiting as looks optimal\n"); |
---|
244 | break; |
---|
245 | } |
---|
246 | numberInfeasibilities=0; |
---|
247 | sumInfeasibilities=0.0; |
---|
248 | for (iSort=0;iSort<numberSort;iSort++) { |
---|
249 | if (weight[iSort]>-1.0e30&&weight[iSort]<-1.0e-8) { |
---|
250 | numberInfeasibilities++; |
---|
251 | sumInfeasibilities += -weight[iSort]; |
---|
252 | } |
---|
253 | } |
---|
254 | printf("in small model %d rows are infeasible - sum is %g\n",numberInfeasibilities, |
---|
255 | sumInfeasibilities); |
---|
256 | } |
---|
257 | } |
---|
258 | delete [] weight; |
---|
259 | delete [] sort; |
---|
260 | delete [] whichColumns; |
---|
261 | delete [] take; |
---|
262 | // If problem is big you may wish to skip this |
---|
263 | model2->dual(); |
---|
264 | int numberBinding=0; |
---|
265 | for (iRow=0;iRow<originalNumberRows;iRow++) { |
---|
266 | if (model2->getRowStatus(iRow)!=ClpSimplex::basic) |
---|
267 | numberBinding++; |
---|
268 | } |
---|
269 | printf("%d binding rows at end\n",numberBinding); |
---|
270 | pinfo.postsolve(true); |
---|
271 | |
---|
272 | int numberIterations=model2->numberIterations();; |
---|
273 | delete model2; |
---|
274 | /* After this postsolve model should be optimal. |
---|
275 | We can use checkSolution and test feasibility */ |
---|
276 | model.checkSolution(); |
---|
277 | if (model.numberDualInfeasibilities()|| |
---|
278 | model.numberPrimalInfeasibilities()) |
---|
279 | printf("%g dual %g(%d) Primal %g(%d)\n", |
---|
280 | model.objectiveValue(), |
---|
281 | model.sumDualInfeasibilities(), |
---|
282 | model.numberDualInfeasibilities(), |
---|
283 | model.sumPrimalInfeasibilities(), |
---|
284 | model.numberPrimalInfeasibilities()); |
---|
285 | // But resolve for safety |
---|
286 | model.primal(1); |
---|
287 | |
---|
288 | numberIterations += model.numberIterations();; |
---|
289 | printf("Solve took %g seconds\n",CoinCpuTime()-time1); |
---|
290 | return 0; |
---|
291 | } |
---|