COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_test.cc @ 1272:17be4c5bc6c6

Last change on this file since 1272:17be4c5bc6c6 was 1272:17be4c5bc6c6, checked in by Alpar Juttner, 19 years ago
  • Non-template expressions and constraints (lin_expr.h isn't used)
File size: 3.3 KB
Line 
1#include"lp_solver_skeleton.h"
2#include"lp_glpk.h"
3#include<lemon/list_graph.h>
4
5using namespace lemon;
6
7void 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
131template<class G,class C>
132double 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
171int main()
172{
173  LpSolverSkeleton lp_skel;
174  LpGlpk lp_glpk;
175
176  lpTest(lp_skel);
177  lpTest(lp_glpk);
178
179  ListGraph g;
180  ListGraph::EdgeMap<double> cap(g);
181 
182  maxFlow(g,cap,ListGraph::NodeIt(g),ListGraph::NodeIt(g));
183
184}
Note: See TracBrowser for help on using the repository browser.