1 // -*- c++ -*- |
|
2 #include <iostream> |
|
3 #include <fstream> |
|
4 |
|
5 #include <lemon/graph_utils.h> |
|
6 #include <lemon/smart_graph.h> |
|
7 #include <lemon/list_graph.h> |
|
8 #include <lemon/dimacs.h> |
|
9 #include <lemon/time_measure.h> |
|
10 #include <lp_solver_glpk.h> |
|
11 |
|
12 using std::cout; |
|
13 using std::endl; |
|
14 using namespace lemon; |
|
15 |
|
16 template<typename Edge, typename EdgeIndexMap> |
|
17 class PrimalMap { |
|
18 protected: |
|
19 LpGlpk* lp; |
|
20 EdgeIndexMap* edge_index_map; |
|
21 public: |
|
22 PrimalMap(LpGlpk& _lp, EdgeIndexMap& _edge_index_map) : |
|
23 lp(&_lp), edge_index_map(&_edge_index_map) { } |
|
24 double operator[](Edge e) const { |
|
25 return lp->getPrimal((*edge_index_map)[e]); |
|
26 } |
|
27 }; |
|
28 |
|
29 // Use a DIMACS max flow file as stdin. |
|
30 // max_flow_expresion < dimacs_max_flow_file |
|
31 |
|
32 int main(int, char **) { |
|
33 |
|
34 typedef ListGraph Graph; |
|
35 typedef Graph::Node Node; |
|
36 typedef Graph::Edge Edge; |
|
37 typedef Graph::EdgeIt EdgeIt; |
|
38 |
|
39 Graph g; |
|
40 |
|
41 Node s, t; |
|
42 Graph::EdgeMap<int> cap(g); |
|
43 readDimacs(std::cin, g, cap, s, t); |
|
44 Timer ts; |
|
45 |
|
46 typedef LpGlpk LPSolver; |
|
47 LPSolver lp; |
|
48 lp.setMaximize(); |
|
49 typedef LPSolver::Col Col; |
|
50 typedef LPSolver::Row Row; |
|
51 typedef Graph::EdgeMap<Col> EdgeIndexMap; |
|
52 typedef Graph::NodeMap<Row> NodeIndexMap; |
|
53 EdgeIndexMap edge_index_map(g); |
|
54 NodeIndexMap node_index_map(g); |
|
55 PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map); |
|
56 |
|
57 // nonnegativity of flow and capacity function |
|
58 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { |
|
59 Col col=lp.addCol(); |
|
60 edge_index_map.set(e, col); |
|
61 // interesting property in GLPK: |
|
62 // if you change the order of the following two lines, the |
|
63 // two runs of GLPK are extremely different |
|
64 lp.setColLowerBound(col, 0); |
|
65 lp.setColUpperBound(col, cap[e]); |
|
66 } |
|
67 |
|
68 for (Graph::NodeIt n(g); n!=INVALID; ++n) { |
|
69 LPSolver::Expression expr; |
|
70 for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
|
71 expr+=edge_index_map[e]; |
|
72 for (Graph::InEdgeIt e(g, n); e!=INVALID; ++e) |
|
73 expr-=edge_index_map[e]; |
|
74 // cost function |
|
75 if (n==s) { |
|
76 lp.setObjCoeffs(expr); |
|
77 } |
|
78 // flow conservation constraints |
|
79 if ((n!=s) && (n!=t)) { |
|
80 node_index_map.set(n, lp.addRow(expr == 0.0)); |
|
81 } |
|
82 } |
|
83 lp.solveSimplex(); |
|
84 cout << "elapsed time: " << ts << endl; |
|
85 // cout << "rows:" << endl; |
|
86 // for ( |
|
87 // LPSolver::Rows::ClassIt i(lp.row_iter_map, 0); |
|
88 // i!=INVALID; |
|
89 // ++i) { |
|
90 // cout << i << " "; |
|
91 // } |
|
92 // cout << endl; |
|
93 // cout << "cols:" << endl; |
|
94 // for ( |
|
95 // LPSolver::Cols::ClassIt i(lp.col_iter_map, 0); |
|
96 // i!=INVALID; |
|
97 // ++i) { |
|
98 // cout << i << " "; |
|
99 // } |
|
100 // cout << endl; |
|
101 lp.setMIP(); |
|
102 cout << "elapsed time: " << ts << endl; |
|
103 for (LPSolver::Cols::ClassIt it(lp.col_iter_map ,1); it!=INVALID; ++it) { |
|
104 lp.setColInt(it); |
|
105 } |
|
106 cout << "elapsed time: " << ts << endl; |
|
107 lp.solveBandB(); |
|
108 cout << "elapsed time: " << ts << endl; |
|
109 } |
|