|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #include <sstream> |
|
20 #include <lemon/lp_skeleton.h> |
|
21 #include "test_tools.h" |
|
22 #include <lemon/tolerance.h> |
|
23 |
|
24 #ifdef HAVE_CONFIG_H |
|
25 #include <lemon/config.h> |
|
26 #endif |
|
27 |
|
28 #ifdef HAVE_GLPK |
|
29 #include <lemon/lp_glpk.h> |
|
30 #endif |
|
31 |
|
32 #ifdef HAVE_CPLEX |
|
33 #include <lemon/lp_cplex.h> |
|
34 #endif |
|
35 |
|
36 #ifdef HAVE_SOPLEX |
|
37 #include <lemon/lp_soplex.h> |
|
38 #endif |
|
39 |
|
40 using namespace lemon; |
|
41 |
|
42 void lpTest(LpSolverBase & lp) |
|
43 { |
|
44 |
|
45 |
|
46 |
|
47 typedef LpSolverBase LP; |
|
48 |
|
49 std::vector<LP::Col> x(10); |
|
50 // for(int i=0;i<10;i++) x.push_back(lp.addCol()); |
|
51 lp.addColSet(x); |
|
52 lp.colLowerBound(x,1); |
|
53 lp.colUpperBound(x,1); |
|
54 lp.colBounds(x,1,2); |
|
55 #ifndef GYORSITAS |
|
56 |
|
57 std::vector<LP::Col> y(10); |
|
58 lp.addColSet(y); |
|
59 |
|
60 lp.colLowerBound(y,1); |
|
61 lp.colUpperBound(y,1); |
|
62 lp.colBounds(y,1,2); |
|
63 |
|
64 std::map<int,LP::Col> z; |
|
65 |
|
66 z.insert(std::make_pair(12,INVALID)); |
|
67 z.insert(std::make_pair(2,INVALID)); |
|
68 z.insert(std::make_pair(7,INVALID)); |
|
69 z.insert(std::make_pair(5,INVALID)); |
|
70 |
|
71 lp.addColSet(z); |
|
72 |
|
73 lp.colLowerBound(z,1); |
|
74 lp.colUpperBound(z,1); |
|
75 lp.colBounds(z,1,2); |
|
76 |
|
77 { |
|
78 LP::Expr e,f,g; |
|
79 LP::Col p1,p2,p3,p4,p5; |
|
80 LP::Constr c; |
|
81 |
|
82 p1=lp.addCol(); |
|
83 p2=lp.addCol(); |
|
84 p3=lp.addCol(); |
|
85 p4=lp.addCol(); |
|
86 p5=lp.addCol(); |
|
87 |
|
88 e[p1]=2; |
|
89 e.constComp()=12; |
|
90 e[p1]+=2; |
|
91 e.constComp()+=12; |
|
92 e[p1]-=2; |
|
93 e.constComp()-=12; |
|
94 |
|
95 e=2; |
|
96 e=2.2; |
|
97 e=p1; |
|
98 e=f; |
|
99 |
|
100 e+=2; |
|
101 e+=2.2; |
|
102 e+=p1; |
|
103 e+=f; |
|
104 |
|
105 e-=2; |
|
106 e-=2.2; |
|
107 e-=p1; |
|
108 e-=f; |
|
109 |
|
110 e*=2; |
|
111 e*=2.2; |
|
112 e/=2; |
|
113 e/=2.2; |
|
114 |
|
115 e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+ |
|
116 (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+ |
|
117 (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+ |
|
118 2.2*f+f*2.2+f/2.2+ |
|
119 2*f+f*2+f/2+ |
|
120 2.2*p1+p1*2.2+p1/2.2+ |
|
121 2*p1+p1*2+p1/2 |
|
122 ); |
|
123 |
|
124 |
|
125 c = (e <= f ); |
|
126 c = (e <= 2.2); |
|
127 c = (e <= 2 ); |
|
128 c = (e <= p1 ); |
|
129 c = (2.2<= f ); |
|
130 c = (2 <= f ); |
|
131 c = (p1 <= f ); |
|
132 c = (p1 <= p2 ); |
|
133 c = (p1 <= 2.2); |
|
134 c = (p1 <= 2 ); |
|
135 c = (2.2<= p2 ); |
|
136 c = (2 <= p2 ); |
|
137 |
|
138 c = (e >= f ); |
|
139 c = (e >= 2.2); |
|
140 c = (e >= 2 ); |
|
141 c = (e >= p1 ); |
|
142 c = (2.2>= f ); |
|
143 c = (2 >= f ); |
|
144 c = (p1 >= f ); |
|
145 c = (p1 >= p2 ); |
|
146 c = (p1 >= 2.2); |
|
147 c = (p1 >= 2 ); |
|
148 c = (2.2>= p2 ); |
|
149 c = (2 >= p2 ); |
|
150 |
|
151 c = (e == f ); |
|
152 c = (e == 2.2); |
|
153 c = (e == 2 ); |
|
154 c = (e == p1 ); |
|
155 c = (2.2== f ); |
|
156 c = (2 == f ); |
|
157 c = (p1 == f ); |
|
158 //c = (p1 == p2 ); |
|
159 c = (p1 == 2.2); |
|
160 c = (p1 == 2 ); |
|
161 c = (2.2== p2 ); |
|
162 c = (2 == p2 ); |
|
163 |
|
164 c = (2 <= e <= 3); |
|
165 c = (2 <= p1<= 3); |
|
166 |
|
167 c = (2 >= e >= 3); |
|
168 c = (2 >= p1>= 3); |
|
169 |
|
170 e[x[3]]=2; |
|
171 e[x[3]]=4; |
|
172 e[x[3]]=1; |
|
173 e.constComp()=12; |
|
174 |
|
175 lp.addRow(LP::INF,e,23); |
|
176 lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23); |
|
177 lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23); |
|
178 |
|
179 lp.addRow(x[1]+x[3]<=x[5]-3); |
|
180 lp.addRow(-7<=x[1]+x[3]-12<=3); |
|
181 lp.addRow(x[1]<=x[5]); |
|
182 |
|
183 std::ostringstream buf; |
|
184 |
|
185 |
|
186 //Checking the simplify function |
|
187 |
|
188 // //How to check the simplify function? A map gives no information |
|
189 // //on the question whether a given key is or is not stored in it, or |
|
190 // //it does? |
|
191 // Yes, it does, using the find() function. |
|
192 e=((p1+p2)+(p1-p2)); |
|
193 e.simplify(); |
|
194 buf << "Coeff. of p2 should be 0"; |
|
195 // std::cout<<e[p1]<<e[p2]<<e[p3]<<std::endl; |
|
196 check(e.find(p2)==e.end(), buf.str()); |
|
197 |
|
198 |
|
199 |
|
200 |
|
201 e=((p1+p2)+(p1-0.99*p2)); |
|
202 //e.prettyPrint(std::cout); |
|
203 //(e<=2).prettyPrint(std::cout); |
|
204 double tolerance=0.001; |
|
205 e.simplify(tolerance); |
|
206 buf << "Coeff. of p2 should be 0.01"; |
|
207 check(e[p2]>0, buf.str()); |
|
208 |
|
209 tolerance=0.02; |
|
210 e.simplify(tolerance); |
|
211 buf << "Coeff. of p2 should be 0"; |
|
212 check(e.find(p2)==e.end(), buf.str()); |
|
213 |
|
214 |
|
215 } |
|
216 |
|
217 { |
|
218 LP::DualExpr e,f,g; |
|
219 LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID, |
|
220 p4 = INVALID, p5 = INVALID; |
|
221 |
|
222 e[p1]=2; |
|
223 e[p1]+=2; |
|
224 e[p1]-=2; |
|
225 |
|
226 e=p1; |
|
227 e=f; |
|
228 |
|
229 e+=p1; |
|
230 e+=f; |
|
231 |
|
232 e-=p1; |
|
233 e-=f; |
|
234 |
|
235 e*=2; |
|
236 e*=2.2; |
|
237 e/=2; |
|
238 e/=2.2; |
|
239 |
|
240 e=((p1+p2)+(p1-p2)+ |
|
241 (p1+f)+(f+p1)+(f+g)+ |
|
242 (p1-f)+(f-p1)+(f-g)+ |
|
243 2.2*f+f*2.2+f/2.2+ |
|
244 2*f+f*2+f/2+ |
|
245 2.2*p1+p1*2.2+p1/2.2+ |
|
246 2*p1+p1*2+p1/2 |
|
247 ); |
|
248 } |
|
249 |
|
250 #endif |
|
251 } |
|
252 |
|
253 void solveAndCheck(LpSolverBase& lp, LpSolverBase::SolutionStatus stat, |
|
254 double exp_opt) { |
|
255 using std::string; |
|
256 lp.solve(); |
|
257 //int decimal,sign; |
|
258 std::ostringstream buf; |
|
259 buf << "Primalstatus should be: " << int(stat); |
|
260 |
|
261 // itoa(stat,buf1, 10); |
|
262 check(lp.primalStatus()==stat, buf.str()); |
|
263 |
|
264 if (stat == LpSolverBase::OPTIMAL) { |
|
265 std::ostringstream sbuf; |
|
266 sbuf << "Wrong optimal value: the right optimum is " << exp_opt; |
|
267 check(std::abs(lp.primalValue()-exp_opt) < 1e-3, sbuf.str()); |
|
268 //+ecvt(exp_opt,2) |
|
269 } |
|
270 } |
|
271 |
|
272 void aTest(LpSolverBase & lp) |
|
273 { |
|
274 typedef LpSolverBase LP; |
|
275 |
|
276 //The following example is very simple |
|
277 |
|
278 typedef LpSolverBase::Row Row; |
|
279 typedef LpSolverBase::Col Col; |
|
280 |
|
281 |
|
282 Col x1 = lp.addCol(); |
|
283 Col x2 = lp.addCol(); |
|
284 |
|
285 |
|
286 //Constraints |
|
287 Row upright=lp.addRow(x1+x2 <=1); |
|
288 lp.addRow(x1+x2 >=-1); |
|
289 lp.addRow(x1-x2 <=1); |
|
290 lp.addRow(x1-x2 >=-1); |
|
291 //Nonnegativity of the variables |
|
292 lp.colLowerBound(x1, 0); |
|
293 lp.colLowerBound(x2, 0); |
|
294 //Objective function |
|
295 lp.obj(x1+x2); |
|
296 |
|
297 lp.max(); |
|
298 |
|
299 //Testing the problem retrieving routines |
|
300 check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!"); |
|
301 check(lp.isMax(),"This is a maximization!"); |
|
302 check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!"); |
|
303 // std::cout<<lp.colLowerBound(x1)<<std::endl; |
|
304 check( lp.colLowerBound(x1)==0, |
|
305 "The lower bound for variable x1 should be 0."); |
|
306 check( lp.colUpperBound(x1)==LpSolverBase::INF, |
|
307 "The upper bound for variable x1 should be infty."); |
|
308 LpSolverBase::Value lb,ub; |
|
309 lp.getRowBounds(upright,lb,ub); |
|
310 check( lb==-LpSolverBase::INF, |
|
311 "The lower bound for the first row should be -infty."); |
|
312 check( ub==1,"The upper bound for the first row should be 1."); |
|
313 LpSolverBase::Expr e = lp.row(upright); |
|
314 check( e.size() == 2, "The row retrieval gives back wrong expression."); |
|
315 check( e[x1] == 1, "The first coefficient should 1."); |
|
316 check( e[x2] == 1, "The second coefficient should 1."); |
|
317 |
|
318 LpSolverBase::DualExpr de = lp.col(x1); |
|
319 check( de.size() == 4, "The col retrieval gives back wrong expression."); |
|
320 check( de[upright] == 1, "The first coefficient should 1."); |
|
321 |
|
322 LpSolverBase* clp = lp.copyLp(); |
|
323 |
|
324 //Testing the problem retrieving routines |
|
325 check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!"); |
|
326 check(clp->isMax(),"This is a maximization!"); |
|
327 check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!"); |
|
328 // std::cout<<lp.colLowerBound(x1)<<std::endl; |
|
329 check( clp->colLowerBound(x1)==0, |
|
330 "The lower bound for variable x1 should be 0."); |
|
331 check( clp->colUpperBound(x1)==LpSolverBase::INF, |
|
332 "The upper bound for variable x1 should be infty."); |
|
333 |
|
334 clp->getRowBounds(upright,lb,ub); |
|
335 check( lb==-LpSolverBase::INF, |
|
336 "The lower bound for the first row should be -infty."); |
|
337 check( ub==1,"The upper bound for the first row should be 1."); |
|
338 e = clp->row(upright); |
|
339 check( e.size() == 2, "The row retrieval gives back wrong expression."); |
|
340 check( e[x1] == 1, "The first coefficient should 1."); |
|
341 check( e[x2] == 1, "The second coefficient should 1."); |
|
342 |
|
343 de = clp->col(x1); |
|
344 check( de.size() == 4, "The col retrieval gives back wrong expression."); |
|
345 check( de[upright] == 1, "The first coefficient should 1."); |
|
346 |
|
347 delete clp; |
|
348 |
|
349 //Maximization of x1+x2 |
|
350 //over the triangle with vertices (0,0) (0,1) (1,0) |
|
351 double expected_opt=1; |
|
352 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt); |
|
353 |
|
354 //Minimization |
|
355 lp.min(); |
|
356 expected_opt=0; |
|
357 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt); |
|
358 |
|
359 //Vertex (-1,0) instead of (0,0) |
|
360 lp.colLowerBound(x1, -LpSolverBase::INF); |
|
361 expected_opt=-1; |
|
362 solveAndCheck(lp, LpSolverBase::OPTIMAL, expected_opt); |
|
363 |
|
364 //Erase one constraint and return to maximization |
|
365 lp.eraseRow(upright); |
|
366 lp.max(); |
|
367 expected_opt=LpSolverBase::INF; |
|
368 solveAndCheck(lp, LpSolverBase::INFINITE, expected_opt); |
|
369 |
|
370 //Infeasibilty |
|
371 lp.addRow(x1+x2 <=-2); |
|
372 solveAndCheck(lp, LpSolverBase::INFEASIBLE, expected_opt); |
|
373 |
|
374 //Change problem and forget to solve |
|
375 lp.min(); |
|
376 check(lp.primalStatus()==LpSolverBase::UNDEFINED, |
|
377 "Primalstatus should be UNDEFINED"); |
|
378 |
|
379 |
|
380 // lp.solve(); |
|
381 // if (lp.primalStatus()==LpSolverBase::OPTIMAL){ |
|
382 // std::cout<< "Z = "<<lp.primalValue() |
|
383 // << " (error = " << lp.primalValue()-expected_opt |
|
384 // << "); x1 = "<<lp.primal(x1) |
|
385 // << "; x2 = "<<lp.primal(x2) |
|
386 // <<std::endl; |
|
387 |
|
388 // } |
|
389 // else{ |
|
390 // std::cout<<lp.primalStatus()<<std::endl; |
|
391 // std::cout<<"Optimal solution not found!"<<std::endl; |
|
392 // } |
|
393 |
|
394 |
|
395 |
|
396 } |
|
397 |
|
398 |
|
399 int main() |
|
400 { |
|
401 LpSkeleton lp_skel; |
|
402 lpTest(lp_skel); |
|
403 |
|
404 #ifdef HAVE_GLPK |
|
405 LpGlpk lp_glpk1,lp_glpk2; |
|
406 lpTest(lp_glpk1); |
|
407 aTest(lp_glpk2); |
|
408 #endif |
|
409 |
|
410 #ifdef HAVE_CPLEX |
|
411 LpCplex lp_cplex1,lp_cplex2; |
|
412 lpTest(lp_cplex1); |
|
413 aTest(lp_cplex2); |
|
414 #endif |
|
415 |
|
416 #ifdef HAVE_SOPLEX |
|
417 LpSoplex lp_soplex1,lp_soplex2; |
|
418 lpTest(lp_soplex1); |
|
419 aTest(lp_soplex2); |
|
420 #endif |
|
421 |
|
422 return 0; |
|
423 } |