21 /// This demo program shows how to solve a maximum (or maximal) flow |
21 /// This demo program shows how to solve a maximum (or maximal) flow |
22 /// problem using the LEMON LP solver interface. We would like to lay |
22 /// problem using the LEMON LP solver interface. We would like to lay |
23 /// the emphasis on the simplicity of the way one can formulate LP |
23 /// the emphasis on the simplicity of the way one can formulate LP |
24 /// constraints that arise in graph theory in our library LEMON . |
24 /// constraints that arise in graph theory in our library LEMON . |
25 |
25 |
26 #ifdef HAVE_CONFIG_H |
|
27 #include <config.h> |
|
28 #endif |
|
29 |
|
30 #include<lemon/graph_reader.h> |
26 #include<lemon/graph_reader.h> |
31 #include<lemon/list_graph.h> |
27 #include<lemon/list_graph.h> |
|
28 #include <lemon/lp.h> |
32 |
29 |
33 #include <fstream> |
30 #include <fstream> |
34 #include <iostream> |
31 #include <iostream> |
35 |
32 |
36 |
33 |
37 #ifdef HAVE_GLPK |
|
38 #include <lemon/lp_glpk.h> |
|
39 #elif HAVE_CPLEX |
|
40 #include <lemon/lp_cplex.h> |
|
41 #endif |
|
42 |
34 |
43 using namespace lemon; |
35 using namespace lemon; |
44 |
|
45 #ifdef HAVE_GLPK |
|
46 typedef LpGlpk LpDefault; |
|
47 const char default_solver_name[]="GLPK"; |
|
48 #elif HAVE_CPLEX |
|
49 typedef LpCplex LpDefault; |
|
50 const char default_solver_name[]="CPLEX"; |
|
51 #endif |
|
52 |
|
53 |
36 |
54 template<class G,class C> |
37 template<class G,class C> |
55 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) |
38 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t) |
56 { |
39 { |
57 LpDefault lp; |
40 Lp lp; |
58 |
41 |
59 typedef G Graph; |
42 typedef G Graph; |
60 typedef typename G::Node Node; |
43 typedef typename G::Node Node; |
61 typedef typename G::NodeIt NodeIt; |
44 typedef typename G::NodeIt NodeIt; |
62 typedef typename G::Edge Edge; |
45 typedef typename G::Edge Edge; |
63 typedef typename G::EdgeIt EdgeIt; |
46 typedef typename G::EdgeIt EdgeIt; |
64 typedef typename G::OutEdgeIt OutEdgeIt; |
47 typedef typename G::OutEdgeIt OutEdgeIt; |
65 typedef typename G::InEdgeIt InEdgeIt; |
48 typedef typename G::InEdgeIt InEdgeIt; |
66 |
49 |
67 //Define a map on the edges for the variables of the LP problem |
50 //Define a map on the edges for the variables of the LP problem |
68 typename G::template EdgeMap<LpDefault::Col> x(g); |
51 typename G::template EdgeMap<Lp::Col> x(g); |
69 lp.addColSet(x); |
52 lp.addColSet(x); |
70 |
53 |
71 //Nonnegativity and capacity constraints |
54 //Nonnegativity and capacity constraints |
72 for(EdgeIt e(g);e!=INVALID;++e) { |
55 for(EdgeIt e(g);e!=INVALID;++e) { |
73 lp.colUpperBound(x[e],cap[e]); |
56 lp.colUpperBound(x[e],cap[e]); |
75 } |
58 } |
76 |
59 |
77 |
60 |
78 //Flow conservation constraints for the nodes (except for 's' and 't') |
61 //Flow conservation constraints for the nodes (except for 's' and 't') |
79 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
62 for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) { |
80 LpDefault::Expr ex; |
63 Lp::Expr ex; |
81 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
64 for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e]; |
82 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
65 for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e]; |
83 lp.addRow(ex==0); |
66 lp.addRow(ex==0); |
84 } |
67 } |
85 |
68 |
86 //Objective function: the flow value entering 't' |
69 //Objective function: the flow value entering 't' |
87 LpDefault::Expr obj; |
70 Lp::Expr obj; |
88 for(InEdgeIt e(g,t);e!=INVALID;++e) obj+=x[e]; |
71 for(InEdgeIt e(g,t);e!=INVALID;++e) obj+=x[e]; |
89 for(OutEdgeIt e(g,t);e!=INVALID;++e) obj-=x[e]; |
72 for(OutEdgeIt e(g,t);e!=INVALID;++e) obj-=x[e]; |
90 lp.setObj(obj); |
73 lp.setObj(obj); |
91 |
74 |
92 |
75 |
93 //Maximization |
76 //Maximization |
94 lp.max(); |
77 lp.max(); |
95 |
78 |
96 #ifdef HAVE_GLPK |
79 #if DEFAULT_LP==GLPK |
97 lp.presolver(true); |
80 lp.presolver(true); |
98 lp.messageLevel(3); |
81 lp.messageLevel(3); |
99 #endif |
82 #endif |
100 |
83 |
101 std::cout<<"Solver used: "<<default_solver_name<<std::endl; |
84 std::cout<<"Solver used: "<<default_solver_name<<std::endl; |