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