1 #include"lp_solver_skeleton.h" |
|
2 #include"lp_cplex.h" |
|
3 #include<lemon/list_graph.h> |
|
4 |
|
5 using namespace lemon; |
|
6 |
|
7 void lpTest(LpSolverBase & lp) |
|
8 { |
|
9 typedef LpSolverBase LP; |
|
10 |
|
11 std::vector<LP::Col> x; |
|
12 for(int i=0;i<10;i++) x.push_back(lp.addCol()); |
|
13 |
|
14 std::vector<LP::Col> y(10); |
|
15 lp.addColSet(y); |
|
16 |
|
17 std::map<int,LP::Col> z; |
|
18 |
|
19 z.insert(std::make_pair(12,INVALID)); |
|
20 z.insert(std::make_pair(2,INVALID)); |
|
21 z.insert(std::make_pair(7,INVALID)); |
|
22 z.insert(std::make_pair(5,INVALID)); |
|
23 |
|
24 lp.addColSet(z); |
|
25 |
|
26 |
|
27 LP::Expr e,f,g; |
|
28 LP::Col p1,p2,p3,p4,p5; |
|
29 LP::Constr c; |
|
30 |
|
31 e[p1]=2; |
|
32 e.constComp()=12; |
|
33 e[p1]+=2; |
|
34 e.constComp()+=12; |
|
35 e[p1]-=2; |
|
36 e.constComp()-=12; |
|
37 |
|
38 e=2; |
|
39 e=2.2; |
|
40 e=p1; |
|
41 e=f; |
|
42 |
|
43 e+=2; |
|
44 e+=2.2; |
|
45 e+=p1; |
|
46 e+=f; |
|
47 |
|
48 e-=2; |
|
49 e-=2.2; |
|
50 e-=p1; |
|
51 e-=f; |
|
52 |
|
53 e*=2; |
|
54 e*=2.2; |
|
55 e/=2; |
|
56 e/=2.2; |
|
57 |
|
58 e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+ |
|
59 (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+ |
|
60 (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+ |
|
61 2.2*f+f*2.2+f/2.2+ |
|
62 2*f+f*2+f/2+ |
|
63 2.2*p1+p1*2.2+p1/2.2+ |
|
64 2*p1+p1*2+p1/2 |
|
65 ); |
|
66 |
|
67 |
|
68 c = (e <= f ); |
|
69 c = (e <= 2.2); |
|
70 c = (e <= 2 ); |
|
71 c = (e <= p1 ); |
|
72 c = (2.2<= f ); |
|
73 c = (2 <= f ); |
|
74 c = (p1 <= f ); |
|
75 c = (p1 <= p2 ); |
|
76 c = (p1 <= 2.2); |
|
77 c = (p1 <= 2 ); |
|
78 c = (2.2<= p2 ); |
|
79 c = (2 <= p2 ); |
|
80 |
|
81 c = (e >= f ); |
|
82 c = (e >= 2.2); |
|
83 c = (e >= 2 ); |
|
84 c = (e >= p1 ); |
|
85 c = (2.2>= f ); |
|
86 c = (2 >= f ); |
|
87 c = (p1 >= f ); |
|
88 c = (p1 >= p2 ); |
|
89 c = (p1 >= 2.2); |
|
90 c = (p1 >= 2 ); |
|
91 c = (2.2>= p2 ); |
|
92 c = (2 >= p2 ); |
|
93 |
|
94 c = (e == f ); |
|
95 c = (e == 2.2); |
|
96 c = (e == 2 ); |
|
97 c = (e == p1 ); |
|
98 c = (2.2== f ); |
|
99 c = (2 == f ); |
|
100 c = (p1 == f ); |
|
101 //c = (p1 == p2 ); |
|
102 c = (p1 == 2.2); |
|
103 c = (p1 == 2 ); |
|
104 c = (2.2== p2 ); |
|
105 c = (2 == p2 ); |
|
106 |
|
107 c = (2 <= e <= 3); |
|
108 c = (2 <= p1<= 3); |
|
109 |
|
110 c = (2 >= e >= 3); |
|
111 c = (2 >= p1>= 3); |
|
112 |
|
113 e[x[3]]=2; |
|
114 e[x[3]]=4; |
|
115 e[x[3]]=1; |
|
116 e.constComp()=12; |
|
117 |
|
118 lp.addRow(LP::INF,e,23); |
|
119 lp.addRow(LP::INF,3.0*(p1+p2)-p3,23); |
|
120 lp.addRow(LP::INF,3.0*(x[1]+x[2]/2)-x[3],23); |
|
121 lp.addRow(LP::INF,3.0*(p1+p2*2-5*p3+12-p4/3)+2*p4-4,23); |
|
122 lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23); |
|
123 |
|
124 lp.addRow(x[1]+x[3]<=x[5]-3); |
|
125 lp.addRow(-7<=x[1]+x[3]-12<=3); |
|
126 //lp.addRow(x[1]<=x[5]); |
|
127 |
|
128 } |
|
129 |
|
130 |
|
131 template<class G,class C> |
|
132 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) |
|
133 { |
|
134 LpGlpk lp; |
|
135 |
|
136 typedef G Graph; |
|
137 typedef typename G::Node Node; |
|
138 typedef typename G::NodeIt NodeIt; |
|
139 typedef typename G::Edge Edge; |
|
140 typedef typename G::EdgeIt EdgeIt; |
|
141 typedef typename G::OutEdgeIt OutEdgeIt; |
|
142 typedef typename G::InEdgeIt InEdgeIt; |
|
143 |
|
144 typename G::EdgeMap<LpGlpk::Col> x(g); |
|
145 lp.addColSet(x); |
|
146 //for(EdgeIt e(g);e!=INVALID;++e) x[e]=lp.addCol(); |
|
147 |
|
148 for(EdgeIt e(g);e!=INVALID;++e) { |
|
149 lp.setColUpperBound(x[e],cap[e]); |
|
150 lp.setColLowerBound(x[e],0); |
|
151 } |
|
152 |
|
153 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
|
154 LpGlpk::Expr ex; |
|
155 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
|
156 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
|
157 lp.addRow(0,ex,0); |
|
158 } |
|
159 { |
|
160 LpGlpk::Expr ex; |
|
161 for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e]; |
|
162 for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e]; |
|
163 lp.setObj(ex); |
|
164 } |
|
165 |
|
166 lp.solve(); |
|
167 |
|
168 return 0; |
|
169 } |
|
170 |
|
171 int main() |
|
172 { |
|
173 LpSolverSkeleton lp_skel; |
|
174 LpGlpk lp_glpk; |
|
175 LpCplex lp_cplex; |
|
176 |
|
177 lpTest(lp_skel); |
|
178 lpTest(lp_cplex); |
|
179 |
|
180 ListGraph g; |
|
181 ListGraph::EdgeMap<double> cap(g); |
|
182 |
|
183 maxFlow(g,cap,ListGraph::NodeIt(g),ListGraph::NodeIt(g)); |
|
184 |
|
185 } |
|