4 |
4 |
5 #include <lemon/smart_graph.h> |
5 #include <lemon/smart_graph.h> |
6 #include <lemon/list_graph.h> |
6 #include <lemon/list_graph.h> |
7 #include <lemon/dimacs.h> |
7 #include <lemon/dimacs.h> |
8 #include <lemon/time_measure.h> |
8 #include <lemon/time_measure.h> |
9 #include <lp_solver_wrapper_3.h> |
9 #include <lp_solver_base.h> |
10 |
10 |
11 using std::cout; |
11 using std::cout; |
12 using std::endl; |
12 using std::endl; |
13 using namespace lemon; |
13 using namespace lemon; |
14 |
14 |
49 typedef LPSolver::RowIt RowIt; |
49 typedef LPSolver::RowIt RowIt; |
50 typedef Graph::EdgeMap<ColIt> EdgeIndexMap; |
50 typedef Graph::EdgeMap<ColIt> EdgeIndexMap; |
51 EdgeIndexMap edge_index_map(g); |
51 EdgeIndexMap edge_index_map(g); |
52 PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map); |
52 PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map); |
53 |
53 |
54 // capacity function |
54 // nonnegativity of flow and capacity function |
55 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { |
55 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { |
56 ColIt col_it=lp.addCol(); |
56 ColIt col_it=lp.addCol(); |
57 edge_index_map.set(e, col_it); |
57 edge_index_map.set(e, col_it); |
58 // interesting property in GLPK: |
58 // interesting property in GLPK: |
59 // if you change the order of the following two lines, the |
59 // if you change the order of the following two lines, the |
60 // two runs of GLPK are extremely different |
60 // two runs of GLPK are extremely different |
|
61 lp.setColLowerBound(col_it, 0); |
61 lp.setColUpperBound(col_it, cap[e]); |
62 lp.setColUpperBound(col_it, cap[e]); |
62 lp.setColLowerBound(col_it, 0); |
|
63 } |
63 } |
64 |
64 |
65 for (Graph::NodeIt n(g); n!=INVALID; ++n) { |
65 for (Graph::NodeIt n(g); n!=INVALID; ++n) { |
66 LPSolver::Expression expr; |
66 LPSolver::Expression expr; |
67 for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
67 for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
70 expr-=edge_index_map[e]; |
70 expr-=edge_index_map[e]; |
71 // cost function |
71 // cost function |
72 if (n==s) { |
72 if (n==s) { |
73 lp.setObjCoeffs(expr); |
73 lp.setObjCoeffs(expr); |
74 } |
74 } |
75 // flow conservation |
75 // flow conservation constraints |
76 if ((n!=s) && (n!=t)) { |
76 if ((n!=s) && (n!=t)) { |
77 RowIt row_it=lp.addRow(); |
77 RowIt row_it=lp.addRow(); |
78 lp.setRowCoeffs(row_it, expr); |
78 lp.setRowCoeffs(row_it, expr); |
79 lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0); |
79 lp.setRowLowerBound(row_it, 0.0); |
|
80 lp.setRowUpperBound(row_it, 0.0); |
80 } |
81 } |
81 } |
82 } |
82 lp.solveSimplex(); |
83 lp.solveSimplex(); |
83 cout << "elapsed time: " << ts << endl; |
84 cout << "elapsed time: " << ts << endl; |
84 } |
85 } |