alpar@1390
|
1 |
#include<lemon/lp_skeleton.h>
|
athos@1473
|
2 |
#include "test_tools.h"
|
alpar@1390
|
3 |
|
ladanyi@1387
|
4 |
#ifdef HAVE_CONFIG_H
|
ladanyi@1387
|
5 |
#include <config.h>
|
ladanyi@1387
|
6 |
#endif
|
ladanyi@1387
|
7 |
|
ladanyi@1387
|
8 |
#ifdef HAVE_GLPK
|
ladanyi@1387
|
9 |
#include <lemon/lp_glpk.h>
|
ladanyi@1437
|
10 |
#endif
|
ladanyi@1437
|
11 |
|
ladanyi@1437
|
12 |
#ifdef HAVE_CPLEX
|
ladanyi@1387
|
13 |
#include <lemon/lp_cplex.h>
|
ladanyi@1387
|
14 |
#endif
|
alpar@1254
|
15 |
|
alpar@1254
|
16 |
using namespace lemon;
|
alpar@1254
|
17 |
|
alpar@1263
|
18 |
void lpTest(LpSolverBase & lp)
|
alpar@1254
|
19 |
{
|
athos@1508
|
20 |
|
athos@1508
|
21 |
|
athos@1508
|
22 |
|
alpar@1263
|
23 |
typedef LpSolverBase LP;
|
alpar@1256
|
24 |
|
alpar@1309
|
25 |
std::vector<LP::Col> x(10);
|
alpar@1309
|
26 |
// for(int i=0;i<10;i++) x.push_back(lp.addCol());
|
alpar@1309
|
27 |
lp.addColSet(x);
|
alpar@1256
|
28 |
|
athos@1508
|
29 |
#ifndef GYORSITAS
|
athos@1508
|
30 |
|
alpar@1256
|
31 |
std::vector<LP::Col> y(10);
|
alpar@1256
|
32 |
lp.addColSet(y);
|
alpar@1256
|
33 |
|
alpar@1256
|
34 |
std::map<int,LP::Col> z;
|
alpar@1256
|
35 |
|
alpar@1256
|
36 |
z.insert(std::make_pair(12,INVALID));
|
alpar@1256
|
37 |
z.insert(std::make_pair(2,INVALID));
|
alpar@1256
|
38 |
z.insert(std::make_pair(7,INVALID));
|
alpar@1256
|
39 |
z.insert(std::make_pair(5,INVALID));
|
alpar@1256
|
40 |
|
alpar@1256
|
41 |
lp.addColSet(z);
|
alpar@1256
|
42 |
|
alpar@1445
|
43 |
{
|
alpar@1445
|
44 |
LP::Expr e,f,g;
|
alpar@1445
|
45 |
LP::Col p1,p2,p3,p4,p5;
|
alpar@1445
|
46 |
LP::Constr c;
|
alpar@1445
|
47 |
|
alpar@1484
|
48 |
p1=lp.addCol();
|
alpar@1484
|
49 |
p2=lp.addCol();
|
alpar@1484
|
50 |
p3=lp.addCol();
|
alpar@1484
|
51 |
p4=lp.addCol();
|
alpar@1484
|
52 |
p5=lp.addCol();
|
alpar@1484
|
53 |
|
alpar@1445
|
54 |
e[p1]=2;
|
alpar@1445
|
55 |
e.constComp()=12;
|
alpar@1445
|
56 |
e[p1]+=2;
|
alpar@1445
|
57 |
e.constComp()+=12;
|
alpar@1445
|
58 |
e[p1]-=2;
|
alpar@1445
|
59 |
e.constComp()-=12;
|
alpar@1445
|
60 |
|
alpar@1445
|
61 |
e=2;
|
alpar@1445
|
62 |
e=2.2;
|
alpar@1445
|
63 |
e=p1;
|
alpar@1445
|
64 |
e=f;
|
alpar@1445
|
65 |
|
alpar@1445
|
66 |
e+=2;
|
alpar@1445
|
67 |
e+=2.2;
|
alpar@1445
|
68 |
e+=p1;
|
alpar@1445
|
69 |
e+=f;
|
alpar@1445
|
70 |
|
alpar@1445
|
71 |
e-=2;
|
alpar@1445
|
72 |
e-=2.2;
|
alpar@1445
|
73 |
e-=p1;
|
alpar@1445
|
74 |
e-=f;
|
alpar@1445
|
75 |
|
alpar@1445
|
76 |
e*=2;
|
alpar@1445
|
77 |
e*=2.2;
|
alpar@1445
|
78 |
e/=2;
|
alpar@1445
|
79 |
e/=2.2;
|
alpar@1445
|
80 |
|
alpar@1445
|
81 |
e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
|
alpar@1445
|
82 |
(f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
|
alpar@1445
|
83 |
(f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
|
alpar@1445
|
84 |
2.2*f+f*2.2+f/2.2+
|
alpar@1445
|
85 |
2*f+f*2+f/2+
|
alpar@1445
|
86 |
2.2*p1+p1*2.2+p1/2.2+
|
alpar@1445
|
87 |
2*p1+p1*2+p1/2
|
alpar@1445
|
88 |
);
|
alpar@1256
|
89 |
|
alpar@1445
|
90 |
|
alpar@1445
|
91 |
c = (e <= f );
|
alpar@1445
|
92 |
c = (e <= 2.2);
|
alpar@1445
|
93 |
c = (e <= 2 );
|
alpar@1445
|
94 |
c = (e <= p1 );
|
alpar@1445
|
95 |
c = (2.2<= f );
|
alpar@1445
|
96 |
c = (2 <= f );
|
alpar@1445
|
97 |
c = (p1 <= f );
|
alpar@1445
|
98 |
c = (p1 <= p2 );
|
alpar@1445
|
99 |
c = (p1 <= 2.2);
|
alpar@1445
|
100 |
c = (p1 <= 2 );
|
alpar@1445
|
101 |
c = (2.2<= p2 );
|
alpar@1445
|
102 |
c = (2 <= p2 );
|
alpar@1445
|
103 |
|
alpar@1445
|
104 |
c = (e >= f );
|
alpar@1445
|
105 |
c = (e >= 2.2);
|
alpar@1445
|
106 |
c = (e >= 2 );
|
alpar@1445
|
107 |
c = (e >= p1 );
|
alpar@1445
|
108 |
c = (2.2>= f );
|
alpar@1445
|
109 |
c = (2 >= f );
|
alpar@1445
|
110 |
c = (p1 >= f );
|
alpar@1445
|
111 |
c = (p1 >= p2 );
|
alpar@1445
|
112 |
c = (p1 >= 2.2);
|
alpar@1445
|
113 |
c = (p1 >= 2 );
|
alpar@1445
|
114 |
c = (2.2>= p2 );
|
alpar@1445
|
115 |
c = (2 >= p2 );
|
alpar@1445
|
116 |
|
alpar@1445
|
117 |
c = (e == f );
|
alpar@1445
|
118 |
c = (e == 2.2);
|
alpar@1445
|
119 |
c = (e == 2 );
|
alpar@1445
|
120 |
c = (e == p1 );
|
alpar@1445
|
121 |
c = (2.2== f );
|
alpar@1445
|
122 |
c = (2 == f );
|
alpar@1445
|
123 |
c = (p1 == f );
|
alpar@1445
|
124 |
//c = (p1 == p2 );
|
alpar@1445
|
125 |
c = (p1 == 2.2);
|
alpar@1445
|
126 |
c = (p1 == 2 );
|
alpar@1445
|
127 |
c = (2.2== p2 );
|
alpar@1445
|
128 |
c = (2 == p2 );
|
alpar@1445
|
129 |
|
alpar@1445
|
130 |
c = (2 <= e <= 3);
|
alpar@1445
|
131 |
c = (2 <= p1<= 3);
|
alpar@1445
|
132 |
|
alpar@1445
|
133 |
c = (2 >= e >= 3);
|
alpar@1445
|
134 |
c = (2 >= p1>= 3);
|
alpar@1445
|
135 |
|
alpar@1445
|
136 |
e[x[3]]=2;
|
alpar@1445
|
137 |
e[x[3]]=4;
|
alpar@1445
|
138 |
e[x[3]]=1;
|
alpar@1445
|
139 |
e.constComp()=12;
|
alpar@1445
|
140 |
|
alpar@1445
|
141 |
lp.addRow(LP::INF,e,23);
|
alpar@1445
|
142 |
lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
|
alpar@1445
|
143 |
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
|
144 |
|
alpar@1445
|
145 |
lp.addRow(x[1]+x[3]<=x[5]-3);
|
alpar@1445
|
146 |
lp.addRow(-7<=x[1]+x[3]-12<=3);
|
alpar@1445
|
147 |
lp.addRow(x[1]<=x[5]);
|
alpar@1445
|
148 |
}
|
alpar@1272
|
149 |
|
alpar@1445
|
150 |
{
|
alpar@1445
|
151 |
LP::DualExpr e,f,g;
|
alpar@1445
|
152 |
LP::Row p1,p2,p3,p4,p5;
|
alpar@1445
|
153 |
|
alpar@1445
|
154 |
e[p1]=2;
|
alpar@1445
|
155 |
e[p1]+=2;
|
alpar@1445
|
156 |
e[p1]-=2;
|
alpar@1445
|
157 |
|
alpar@1445
|
158 |
e=p1;
|
alpar@1445
|
159 |
e=f;
|
alpar@1445
|
160 |
|
alpar@1445
|
161 |
e+=p1;
|
alpar@1445
|
162 |
e+=f;
|
alpar@1445
|
163 |
|
alpar@1445
|
164 |
e-=p1;
|
alpar@1445
|
165 |
e-=f;
|
alpar@1445
|
166 |
|
alpar@1445
|
167 |
e*=2;
|
alpar@1445
|
168 |
e*=2.2;
|
alpar@1445
|
169 |
e/=2;
|
alpar@1445
|
170 |
e/=2.2;
|
alpar@1445
|
171 |
|
alpar@1493
|
172 |
e=((p1+p2)+(p1-p2)+
|
alpar@1445
|
173 |
(p1+f)+(f+p1)+(f+g)+
|
alpar@1445
|
174 |
(p1-f)+(f-p1)+(f-g)+
|
alpar@1445
|
175 |
2.2*f+f*2.2+f/2.2+
|
alpar@1445
|
176 |
2*f+f*2+f/2+
|
alpar@1445
|
177 |
2.2*p1+p1*2.2+p1/2.2+
|
alpar@1445
|
178 |
2*p1+p1*2+p1/2
|
alpar@1445
|
179 |
);
|
alpar@1445
|
180 |
}
|
alpar@1272
|
181 |
|
athos@1508
|
182 |
#endif
|
alpar@1264
|
183 |
}
|
alpar@1264
|
184 |
|
athos@1473
|
185 |
void aTest(LpSolverBase & lp)
|
athos@1473
|
186 |
{
|
athos@1473
|
187 |
typedef LpSolverBase LP;
|
athos@1473
|
188 |
|
athos@1473
|
189 |
//The following example is taken from the book by Gáspár and Temesi, page 39.
|
athos@1473
|
190 |
|
athos@1473
|
191 |
typedef LpSolverBase::Row Row;
|
athos@1473
|
192 |
typedef LpSolverBase::Col Col;
|
athos@1473
|
193 |
|
athos@1473
|
194 |
|
athos@1473
|
195 |
Col x1 = lp.addCol();
|
athos@1473
|
196 |
Col x2 = lp.addCol();
|
athos@1473
|
197 |
|
athos@1473
|
198 |
|
athos@1473
|
199 |
//Constraints
|
athos@1473
|
200 |
lp.addRow(3*x1+2*x2 >=6);
|
athos@1473
|
201 |
lp.addRow(-1*x1+x2<=4);
|
athos@1473
|
202 |
lp.addRow(5*x1+8*x2<=40);
|
athos@1473
|
203 |
lp.addRow(x1-2*x2<=4);
|
athos@1473
|
204 |
//Nonnegativity of the variables
|
athos@1473
|
205 |
lp.colLowerBound(x1, 0);
|
athos@1473
|
206 |
lp.colLowerBound(x2, 0);
|
athos@1473
|
207 |
//Objective function
|
athos@1473
|
208 |
lp.setObj(2*x1+x2);
|
athos@1473
|
209 |
|
athos@1473
|
210 |
lp.max();
|
athos@1473
|
211 |
lp.solve();
|
athos@1473
|
212 |
|
alpar@1484
|
213 |
double opt=122.0/9.0;
|
alpar@1484
|
214 |
|
athos@1473
|
215 |
if (lp.primalStatus()==LpSolverBase::OPTIMAL){
|
alpar@1484
|
216 |
std::cout<< "Z = "<<lp.primalValue()
|
alpar@1484
|
217 |
<< " (error = " << lp.primalValue()-opt
|
alpar@1484
|
218 |
<< "); x1 = "<<lp.primal(x1)
|
alpar@1484
|
219 |
<< "; x2 = "<<lp.primal(x2)
|
alpar@1484
|
220 |
<<std::endl;
|
alpar@1484
|
221 |
|
athos@1473
|
222 |
}
|
athos@1473
|
223 |
else{
|
athos@1473
|
224 |
std::cout<<"Optimal solution not found!"<<std::endl;
|
athos@1473
|
225 |
}
|
athos@1473
|
226 |
|
athos@1473
|
227 |
check(lp.primalStatus()==LpSolverBase::OPTIMAL,"Primalstatus should be OPTIMAL");
|
athos@1473
|
228 |
|
alpar@1484
|
229 |
check(std::abs(lp.primalValue()-opt)<1e-3,
|
alpar@1484
|
230 |
"Wrong optimal value: the right optimum is 122/9 (13.555555...)");
|
athos@1473
|
231 |
|
athos@1473
|
232 |
|
athos@1473
|
233 |
}
|
athos@1473
|
234 |
|
athos@1473
|
235 |
|
alpar@1263
|
236 |
int main()
|
alpar@1263
|
237 |
{
|
alpar@1390
|
238 |
LpSkeleton lp_skel;
|
alpar@1390
|
239 |
lpTest(lp_skel);
|
alpar@1390
|
240 |
|
ladanyi@1437
|
241 |
#ifdef HAVE_GLPK
|
alpar@1484
|
242 |
LpGlpk lp_glpk1,lp_glpk2;
|
alpar@1484
|
243 |
lpTest(lp_glpk1);
|
alpar@1484
|
244 |
aTest(lp_glpk2);
|
ladanyi@1437
|
245 |
#endif
|
alpar@1263
|
246 |
|
ladanyi@1437
|
247 |
#ifdef HAVE_CPLEX
|
athos@1508
|
248 |
LpCplex lp_cplex;
|
athos@1508
|
249 |
lpTest(lp_cplex);
|
athos@1508
|
250 |
aTest(lp_cplex);
|
ladanyi@1437
|
251 |
#endif
|
alpar@1264
|
252 |
|
alpar@1309
|
253 |
return 0;
|
alpar@1263
|
254 |
}
|