Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_MIN_COST_MAX_FLOW_H
20 #define LEMON_MIN_COST_MAX_FLOW_H
22 /// \ingroup min_cost_flow
25 /// \brief An efficient algorithm for finding a minimum cost maximum
28 #include <lemon/preflow.h>
29 #include <lemon/network_simplex.h>
30 #include <lemon/maps.h>
34 /// \addtogroup min_cost_flow
37 /// \brief An efficient algorithm for finding a minimum cost maximum
40 /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient
41 /// algorithm for finding a maximum flow having minimal total cost
42 /// from a given source node to a given target node in a directed
45 /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses
46 /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum
47 /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex"
48 /// algorithm for finding a minimum cost flow of that value.
50 /// \param Graph The directed graph type the algorithm runs on.
51 /// \param CapacityMap The type of the capacity (upper bound) map.
52 /// \param CostMap The type of the cost (length) map.
55 /// - Edge capacities and costs should be nonnegative integers.
56 /// However \c CostMap::Value should be signed type.
58 /// \author Peter Kovacs
60 template < typename Graph,
61 typename CapacityMap = typename Graph::template EdgeMap<int>,
62 typename CostMap = typename Graph::template EdgeMap<int> >
65 typedef typename Graph::Node Node;
66 typedef typename Graph::Edge Edge;
68 typedef typename CapacityMap::Value Capacity;
69 typedef typename Graph::template NodeMap<Capacity> SupplyMap;
70 typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
76 /// \brief The type of the flow map.
77 typedef typename Graph::template EdgeMap<Capacity> FlowMap;
81 /// \brief The directed graph the algorithm runs on.
83 /// \brief The modified capacity map.
84 const CapacityMap &capacity;
85 /// \brief The cost map.
87 /// \brief The source node.
89 /// \brief The target node.
91 /// \brief The edge map of the found flow.
94 typedef Preflow<Graph, Capacity, CapacityMap, FlowMap> PreflowImpl;
95 /// \brief \ref lemon::Preflow "Preflow" class for finding the
96 /// maximum flow value.
101 /// \brief The constructor of the class.
103 /// The constructor of the class.
105 /// \param _graph The directed graph the algorithm runs on.
106 /// \param _capacity The capacities (upper bounds) of the edges.
107 /// \param _cost The cost (length) values of the edges.
108 /// \param _s The source node.
109 /// \param _t The target node.
110 MinCostMaxFlow( const Graph &_graph,
111 const CapacityMap &_capacity,
112 const CostMap &_cost,
114 graph(_graph), capacity(_capacity), cost(_cost),
115 source(_s), target(_t), flow(_graph),
116 preflow(_graph, _s, _t, _capacity, flow)
119 /// \brief Returns a const reference to the flow map.
121 /// Returns a const reference to the flow map.
123 /// \pre \ref run() must be called before using this function.
124 const FlowMap& flowMap() const {
128 /// \brief Returns the total cost of the found flow.
130 /// Returns the total cost of the found flow. The complexity of the
131 /// function is \f$ O(e) \f$.
133 /// \pre \ref run() must be called before using this function.
134 Cost totalCost() const {
136 for (EdgeIt e(graph); e != INVALID; ++e)
137 c += flow[e] * cost[e];
141 /// \brief Runs the algorithm.
144 MinCostFlowImpl mcf_impl( graph, capacity, cost,
145 source, target, preflow.flowValue() );
147 flow = mcf_impl.flowMap();
150 }; //class MinCostMaxFlow
156 #endif //LEMON_MIN_COST_MAX_FLOW_H