COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_test.cc @ 1273:2b2ffa625775

Last change on this file since 1273:2b2ffa625775 was 1273:2b2ffa625775, checked in by Alpar Juttner, 19 years ago
  • Better (but still incomplete) doc
  • lp_test runs correctly
File size: 3.2 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*(x[1]+x[2]/2)-x[3],23);
120  lp.addRow(LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
121
122  lp.addRow(x[1]+x[3]<=x[5]-3);
123  lp.addRow(-7<=x[1]+x[3]-12<=3);
124  lp.addRow(x[1]<=x[5]);
125
126}
127
128
129template<class G,class C>
130double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
131{
132  LpGlpk lp;
133 
134  typedef G Graph;
135  typedef typename G::Node Node;
136  typedef typename G::NodeIt NodeIt;
137  typedef typename G::Edge Edge;
138  typedef typename G::EdgeIt EdgeIt;
139  typedef typename G::OutEdgeIt OutEdgeIt;
140  typedef typename G::InEdgeIt InEdgeIt;
141 
142  typename G::EdgeMap<LpGlpk::Col> x(g);
143  lp.addColSet(x);
144 
145  for(EdgeIt e(g);e!=INVALID;++e) {
146    lp.setColUpperBound(x[e],cap[e]);
147    lp.setColLowerBound(x[e],0);
148  }
149
150  for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
151    LpGlpk::Expr ex;
152    for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
153    for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
154    lp.addRow(ex==0);
155  }
156  {
157    LpGlpk::Expr ex;
158    for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
159    for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
160    lp.setObj(ex);
161  }
162
163  lp.solve();
164
165  return 0;
166}
167
168int main()
169{
170  LpSolverSkeleton lp_skel;
171  LpGlpk lp_glpk;
172
173  lpTest(lp_skel);
174  lpTest(lp_glpk);
175
176  ListGraph g;
177  ListGraph::Node s=g.addNode();
178  ListGraph::Node t=g.addNode();
179
180  ListGraph::EdgeMap<double> cap(g);
181 
182  maxFlow(g,cap,s,t);
183
184}
Note: See TracBrowser for help on using the repository browser.