C++ Reference

C++ Reference: Graph

min_cost_flow.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 // An implementation of a cost-scaling push-relabel algorithm for
15 // the min-cost flow problem.
16 //
17 // In the following, we consider a graph G = (V,E) where V denotes the set
18 // of nodes (vertices) in the graph, E denotes the set of arcs (edges).
19 // n = |V| denotes the number of nodes in the graph, and m = |E| denotes the
20 // number of arcs in the graph.
21 //
22 // With each arc (v,w) is associated a nonnegative capacity u(v,w)
23 // (where 'u' stands for "upper bound") and a unit cost c(v,w). With
24 // each node v is associated a quantity named supply(v), which
25 // represents a supply of fluid (if >0) or a demand (if <0).
26 // Furthermore, no fluid is created in the graph so
27 // sum_{v in V} supply(v) = 0.
28 //
29 // A flow is a function from E to R such that:
30 // a) f(v,w) <= u(v,w) for all (v,w) in E (capacity constraint).
31 // b) f(v,w) = -f(w,v) for all (v,w) in E (flow antisymmetry constraint).
32 // c) sum on v f(v,w) + supply(w) = 0 (flow conservation).
33 //
34 // The cost of a flow is sum on (v,w) in E ( f(v,w) * c(v,w) ) [Note:
35 // It can be confusing to beginners that the cost is actually double
36 // the amount that it might seem at first because of flow
37 // antisymmetry.]
38 //
39 // The problem to solve: find a flow of minimum cost such that all the
40 // fluid flows from the supply nodes to the demand nodes.
41 //
42 // The principles behind this algorithm are the following:
43 // 1/ handle pseudo-flows instead of flows and refine pseudo-flows until an
44 // epsilon-optimal minimum-cost flow is obtained,
45 // 2/ deal with epsilon-optimal pseudo-flows.
46 //
47 // 1/ A pseudo-flow is like a flow, except that a node's outflow minus
48 // its inflow can be different from its supply. If it is the case at a
49 // given node v, it is said that there is an excess (or deficit) at
50 // node v. A deficit is denoted by a negative excess and inflow =
51 // outflow + excess.
52 // (Look at ortools/graph/max_flow.h to see that the definition
53 // of preflow is more restrictive than the one for pseudo-flow in that a preflow
54 // only allows non-negative excesses, i.e., no deficit.)
55 // More formally, a pseudo-flow is a function f such that:
56 // a) f(v,w) <= u(v,w) for all (v,w) in E (capacity constraint).
57 // b) f(v,w) = -f(w,v) for all (v,w) in E (flow antisymmetry constraint).
58 //
59 // For each v in E, we also define the excess at node v, the algebraic sum of
60 // all the incoming preflows at this node, added together with the supply at v.
61 // excess(v) = sum on u f(u,v) + supply(v)
62 //
63 // The goal of the algorithm is to obtain excess(v) = 0 for all v in V, while
64 // consuming capacity on some arcs, at the lowest possible cost.
65 //
66 // 2/ Internally to the algorithm and its analysis (but invisibly to
67 // the client), each node has an associated "price" (or potential), in
68 // addition to its excess. It is formally a function from E to R (the
69 // set of real numbers.). For a given price function p, the reduced
70 // cost of an arc (v,w) is:
71 // c_p(v,w) = c(v,w) + p(v) - p(w)
72 // (c(v,w) is the cost of arc (v,w).) For those familiar with linear
73 // programming, the price function can be viewed as a set of dual
74 // variables.
75 //
76 // For a constant epsilon >= 0, a pseudo-flow f is said to be epsilon-optimal
77 // with respect to a price function p if for every residual arc (v,w) in E,
78 // c_p(v,w) >= -epsilon.
79 //
80 // A flow f is optimal if and only if there exists a price function p such that
81 // no arc is admissible with respect to f and p.
82 //
83 // If the arc costs are integers, and epsilon < 1/n, any epsilon-optimal flow
84 // is optimal. The integer cost case is handled by multiplying all the arc costs
85 // and the initial value of epsilon by (n+1). When epsilon reaches 1, and
86 // the solution is epsilon-optimal, it means: for all residual arc (v,w) in E,
87 // (n+1) * c_p(v,w) >= -1, thus c_p(v,w) >= -1/(n+1) >= 1/n, and the
88 // solution is optimal.
89 //
90 // A node v is said to be *active* if excess(v) > 0.
91 // In this case the following operations can be applied to it:
92 // - if there are *admissible* incident arcs, i.e. arcs which are not saturated,
93 // and whose reduced costs are negative, a PushFlow operation can
94 // be applied. It consists in sending as much flow as both the excess at the
95 // node and the capacity of the arc permit.
96 // - if there are no admissible arcs, the active node considered is relabeled,
97 // This is implemented in Discharge, which itself calls PushFlow and Relabel.
98 //
99 // Discharge itself is called by Refine. Refine first saturates all the
100 // admissible arcs, then builds a stack of active nodes. It then applies
101 // Discharge for each active node, possibly adding new ones in the process,
102 // until no nodes are active. In that case an epsilon-optimal flow is obtained.
103 //
104 // Optimize iteratively calls Refine, while epsilon > 1, and divides epsilon by
105 // alpha (set by default to 5) before each iteration.
106 //
107 // The algorithm starts with epsilon = C, where C is the maximum absolute value
108 // of the arc costs. In the integer case which we are dealing with, since all
109 // costs are multiplied by (n+1), the initial value of epsilon is (n+1)*C.
110 // The algorithm terminates when epsilon = 1, and Refine() has been called.
111 // In this case, a minimum-cost flow is obtained.
112 //
113 // The complexity of the algorithm is O(n^2*m*log(n*C)) where C is the value of
114 // the largest arc cost in the graph.
115 //
116 // IMPORTANT:
117 // The algorithm is not able to detect the infeasibility of a problem (i.e.,
118 // when a bottleneck in the network prohibits sending all the supplies.)
119 // Worse, it could in some cases loop forever. This is why feasibility checking
120 // is enabled by default (FLAGS_min_cost_flow_check_feasibility=true.)
121 // Feasibility checking is implemented using a max-flow, which has a much lower
122 // complexity. The impact on performance is negligible, while the risk of being
123 // caught in an endless loop is removed. Note that using the feasibility checker
124 // roughly doubles the memory consumption.
125 //
126 // The starting reference for this class of algorithms is:
127 // A.V. Goldberg and R.E. Tarjan, "Finding Minimum-Cost Circulations by
128 // Successive Approximation." Mathematics of Operations Research, Vol. 15,
129 // 1990:430-466.
130 // http://portal.acm.org/citation.cfm?id=92225
131 //
132 // Implementation issues are tackled in:
133 // A.V. Goldberg, "An Efficient Implementation of a Scaling Minimum-Cost Flow
134 // Algorithm," Journal of Algorithms, (1997) 22:1-29
135 // http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.258
136 //
137 // A.V. Goldberg and M. Kharitonov, "On Implementing Scaling Push-Relabel
138 // Algorithms for the Minimum-Cost Flow Problem", Network flows and matching:
139 // First DIMACS implementation challenge, DIMACS Series in Discrete Mathematics
140 // and Theoretical Computer Science, (1993) 12:157-198.
141 // ftp://dimacs.rutgers.edu/pub/netflow/submit/papers/Goldberg-mincost/scalmin.ps
142 // and in:
143 // U. Bunnagel, B. Korte, and J. Vygen. “Efficient implementation of the
144 // Goldberg-Tarjan minimum-cost flow algorithm.” Optimization Methods and
145 // Software (1998) vol. 10, no. 2:157-174.
146 // http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.84.9897
147 //
148 // We have tried as much as possible in this implementation to keep the
149 // notations and namings of the papers cited above, except for 'demand' or
150 // 'balance' which have been replaced by 'supply', with the according sign
151 // changes to better accommodate with the API of the rest of our tools. A demand
152 // is denoted by a negative supply.
153 //
154 // TODO(user): See whether the following can bring any improvements on real-life
155 // problems.
156 // R.K. Ahuja, A.V. Goldberg, J.B. Orlin, and R.E. Tarjan, "Finding minimum-cost
157 // flows by double scaling," Mathematical Programming, (1992) 53:243-266.
158 // http://www.springerlink.com/index/gu7404218u6kt166.pdf
159 //
160 // An interesting general reference on network flows is:
161 // R. K. Ahuja, T. L. Magnanti, J. B. Orlin, "Network Flows: Theory, Algorithms,
162 // and Applications," Prentice Hall, 1993, ISBN: 978-0136175490,
163 // http://www.amazon.com/dp/013617549X
164 //
165 // Keywords: Push-relabel, min-cost flow, network, graph, Goldberg, Tarjan,
166 // Dinic, Dinitz.
167 
168 #ifndef OR_TOOLS_GRAPH_MIN_COST_FLOW_H_
169 #define OR_TOOLS_GRAPH_MIN_COST_FLOW_H_
170 
171 #include <algorithm>
172 #include <stack>
173 #include <string>
174 #include <vector>
175 
176 #include "ortools/base/integral_types.h"
177 #include "ortools/base/logging.h"
178 #include "ortools/base/macros.h"
180 #include "ortools/graph/graph.h"
181 #include "ortools/util/stats.h"
182 #include "ortools/util/zvector.h"
183 
184 namespace operations_research {
185 
186 // Forward declaration.
187 template <typename Graph, typename ArcFlowType, typename ArcScaledCostType>
188 class GenericMinCostFlow;
189 
190 // Different statuses for a solved problem.
191 // We use a base class to share it between our different interfaces.
193  public:
194  enum Status {
202  };
203 };
204 
205 // A simple and efficient min-cost flow interface. This is as fast as
206 // GenericMinCostFlow<ReverseArcStaticGraph>, which is the fastest, but is uses
207 // more memory in order to hide the somewhat involved construction of the
208 // static graph.
209 //
210 // TODO(user): If the need arises, extend this interface to support warm start
211 // and incrementality between solves. Note that this is already supported by the
212 // GenericMinCostFlow<> interface.
214  public:
215  // By default, the constructor takes no size. New node indices are created
216  // lazily by AddArcWithCapacityAndUnitCost() or SetNodeSupply() such that the
217  // set of valid nodes will always be [0, NumNodes()).
218  //
219  // You may pre-reserve the internal data structures with a given expected
220  // number of nodes and arcs, to potentially gain performance.
221  explicit SimpleMinCostFlow(NodeIndex reserve_num_nodes = 0,
222  ArcIndex reserve_num_arcs = 0);
223 
224  // Adds a directed arc from tail to head to the underlying graph with
225  // a given capacity and cost per unit of flow.
226  // * Node indices and the capacity must be non-negative (>= 0).
227  // * The unit cost can take any integer value (even negative).
228  // * Self-looping and duplicate arcs are supported.
229  // * After the method finishes, NumArcs() == the returned ArcIndex + 1.
231  FlowQuantity capacity,
232  CostValue unit_cost);
233 
234  // Sets the supply of the given node. The node index must be non-negative (>=
235  // 0). Nodes implicitly created will have a default supply set to 0. A demand
236  // is modeled as a negative supply.
238 
239  // Solves the problem, and returns the problem status. This function
240  // requires that the sum of all node supply minus node demand is zero and
241  // that the graph has enough capacity to send all supplies and serve all
242  // demands. Otherwise, it will return INFEASIBLE.
244  return SolveWithPossibleAdjustment(SupplyAdjustment::DONT_ADJUST);
245  }
246 
247  // Same as Solve(), but does not have the restriction that the supply
248  // must match the demand or that the graph has enough capacity to serve
249  // all the demand or use all the supply. This will compute a maximum-flow
250  // with minimum cost. The value of the maximum-flow will be given by
251  // MaximumFlow().
253  return SolveWithPossibleAdjustment(SupplyAdjustment::ADJUST);
254  }
255 
256  // Returns the cost of the minimum-cost flow found by the algorithm when
257  // the returned Status is OPTIMAL.
259 
260  // Returns the total flow of the minimum-cost flow found by the algorithm
261  // when the returned Status is OPTIMAL.
263 
264  // Returns the flow on arc, this only make sense for a successful Solve().
265  //
266  // Note: It is possible that there is more than one optimal solution. The
267  // algorithm is deterministic so it will always return the same solution for
268  // a given problem. However, there is no guarantee of this from one code
269  // version to the next (but the code does not change often).
271 
272  // Accessors for the user given data. The implementation will crash if "arc"
273  // is not in [0, NumArcs()) or "node" is not in [0, NumNodes()).
275  ArcIndex NumArcs() const;
276  NodeIndex Tail(ArcIndex arc) const;
277  NodeIndex Head(ArcIndex arc) const;
281 
282  private:
283  typedef ::util::ReverseArcStaticGraph<NodeIndex, ArcIndex> Graph;
284  enum SupplyAdjustment { ADJUST, DONT_ADJUST };
285 
286  // Applies the permutation in arc_permutation_ to the given arc index.
287  ArcIndex PermutedArc(ArcIndex arc);
288  // Solves the problem, potentially applying supply and demand adjustment,
289  // and returns the problem status.
290  Status SolveWithPossibleAdjustment(SupplyAdjustment adjustment);
291  void ResizeNodeVectors(NodeIndex node);
292 
293  std::vector<NodeIndex> arc_tail_;
294  std::vector<NodeIndex> arc_head_;
295  std::vector<FlowQuantity> arc_capacity_;
296  std::vector<FlowQuantity> node_supply_;
297  std::vector<CostValue> arc_cost_;
298  std::vector<ArcIndex> arc_permutation_;
299  std::vector<FlowQuantity> arc_flow_;
300  CostValue optimal_cost_;
301  FlowQuantity maximum_flow_;
302 
303  DISALLOW_COPY_AND_ASSIGN(SimpleMinCostFlow);
304 };
305 
306 // Generic MinCostFlow that works with StarGraph and all the graphs handling
307 // reverse arcs from graph.h, see the end of min_cost_flow.cc for the exact
308 // types this class is compiled for.
309 //
310 // One can greatly decrease memory usage by using appropriately small integer
311 // types:
312 // - For the Graph<> types, i.e. NodeIndexType and ArcIndexType, see graph.h.
313 // - ArcFlowType is used for the *per-arc* flow quantity. It must be signed, and
314 // large enough to hold the maximum arc capacity and its negation.
315 // - ArcScaledCostType is used for a per-arc scaled cost. It must be signed
316 // and large enough to hold the maximum unit cost of an arc times
317 // (num_nodes + 1).
318 //
319 // Note that the latter two are different than FlowQuantity and CostValue, which
320 // are used for global, aggregated values and may need to be larger.
321 //
322 // TODO(user): Avoid using the globally defined type CostValue and FlowQuantity.
323 // Also uses the Arc*Type where there is no risk of overflow in more places.
324 template <typename Graph, typename ArcFlowType = FlowQuantity,
325  typename ArcScaledCostType = CostValue>
327  public:
328  typedef typename Graph::NodeIndex NodeIndex;
329  typedef typename Graph::ArcIndex ArcIndex;
330  typedef typename Graph::OutgoingArcIterator OutgoingArcIterator;
331  typedef typename Graph::OutgoingOrOppositeIncomingArcIterator
333  typedef ZVector<ArcIndex> ArcIndexArray;
334 
335  // Initialize a MinCostFlow instance on the given graph. The graph does not
336  // need to be fully built yet, but its capacity reservation is used to
337  // initialize the memory of this class.
338  explicit GenericMinCostFlow(const Graph* graph);
339 
340  // Returns the graph associated to the current object.
341  const Graph* graph() const { return graph_; }
342 
343  // Returns the status of last call to Solve(). NOT_SOLVED is returned if
344  // Solve() has never been called or if the problem has been modified in such a
345  // way that the previous solution becomes invalid.
346  Status status() const { return status_; }
347 
348  // Sets the supply corresponding to node. A demand is modeled as a negative
349  // supply.
351 
352  // Sets the unit cost for the given arc.
353  void SetArcUnitCost(ArcIndex arc, ArcScaledCostType unit_cost);
354 
355  // Sets the capacity for the given arc.
356  void SetArcCapacity(ArcIndex arc, ArcFlowType new_capacity);
357 
358  // Sets the flow for the given arc. Note that new_flow must be smaller than
359  // the capacity of the arc.
360  void SetArcFlow(ArcIndex arc, ArcFlowType new_flow);
361 
362  // Solves the problem, returning true if a min-cost flow could be found.
363  bool Solve();
364 
365  // Checks for feasibility, i.e., that all the supplies and demands can be
366  // matched without exceeding bottlenecks in the network.
367  // If infeasible_supply_node (resp. infeasible_demand_node) are not NULL,
368  // they are populated with the indices of the nodes where the initial supplies
369  // (resp. demands) are too large. Feasible values for the supplies and
370  // demands are accessible through FeasibleSupply.
371  // Note that CheckFeasibility is called by Solve() when the flag
372  // min_cost_flow_check_feasibility is set to true (which is the default.)
373  bool CheckFeasibility(std::vector<NodeIndex>* const infeasible_supply_node,
374  std::vector<NodeIndex>* const infeasible_demand_node);
375 
376  // Makes the min-cost flow problem solvable by truncating supplies and
377  // demands to a level acceptable by the network. There may be several ways to
378  // do it. In our case, the levels are computed from the result of the max-flow
379  // algorithm run in CheckFeasibility().
380  // MakeFeasible returns false if CheckFeasibility() was not called before.
381  bool MakeFeasible();
382 
383  // Returns the cost of the minimum-cost flow found by the algorithm.
384  CostValue GetOptimalCost() const { return total_flow_cost_; }
385 
386  // Returns the flow on the given arc using the equations given in the
387  // comment on residual_arc_capacity_.
389 
390  // Returns the capacity of the given arc.
392 
393  // Returns the unscaled cost for the given arc.
395 
396  // Returns the supply at a given node. Demands are modelled as negative
397  // supplies.
399 
400  // Returns the initial supply at a given node.
402 
403  // Returns the largest supply (if > 0) or largest demand in absolute value
404  // (if < 0) admissible at node. If the problem is not feasible, some of these
405  // values will be smaller (in absolute value) than the initial supplies
406  // and demand given as input.
408 
409  // Whether to use the UpdatePrices() heuristic.
410  void SetUseUpdatePrices(bool value) { use_price_update_ = value; }
411 
412  // Whether to check the feasibility of the problem with a max-flow, prior to
413  // solving it. This uses about twice as much memory, but detects infeasible
414  // problems (where the flow can't be satisfied) and makes Solve() return
415  // INFEASIBLE. If you disable this check, you will spare memory but you must
416  // make sure that your problem is feasible, otherwise the code can loop
417  // forever.
418  void SetCheckFeasibility(bool value) { check_feasibility_ = value; }
419 
420  private:
421  // Returns true if the given arc is admissible i.e. if its residual capacity
422  // is strictly positive, and its reduced cost strictly negative, i.e., pushing
423  // more flow into it will result in a reduction of the total cost.
424  bool IsAdmissible(ArcIndex arc) const;
425  bool FastIsAdmissible(ArcIndex arc, CostValue tail_potential) const;
426 
427  // Returns true if node is active, i.e., if its supply is positive.
428  bool IsActive(NodeIndex node) const;
429 
430  // Returns the reduced cost for a given arc.
431  CostValue ReducedCost(ArcIndex arc) const;
432  CostValue FastReducedCost(ArcIndex arc, CostValue tail_potential) const;
433 
434  // Returns the first incident arc of a given node.
435  ArcIndex GetFirstOutgoingOrOppositeIncomingArc(NodeIndex node) const;
436 
437  // Checks the consistency of the input, i.e., whether the sum of the supplies
438  // for all nodes is equal to zero. To be used in a DCHECK.
439  bool CheckInputConsistency() const;
440 
441  // Checks whether the result is valid, i.e. whether for each arc,
442  // residual_arc_capacity_[arc] == 0 || ReducedCost(arc) >= -epsilon_.
443  // (A solution is epsilon-optimal if ReducedCost(arc) >= -epsilon.)
444  // To be used in a DCHECK.
445  bool CheckResult() const;
446 
447  // Checks that the cost range fits in the range of int64's.
448  // To be used in a DCHECK.
449  bool CheckCostRange() const;
450 
451  // Checks the relabel precondition (to be used in a DCHECK):
452  // - The node must be active, or have a 0 excess (relaxation for the Push
453  // Look-Ahead heuristic).
454  // - The node must have no admissible arcs.
455  bool CheckRelabelPrecondition(NodeIndex node) const;
456 
457  // Returns context concatenated with information about a given arc
458  // in a human-friendly way.
459  std::string DebugString(const std::string& context, ArcIndex arc) const;
460 
461  // Resets the first_admissible_arc_ array to the first incident arc of each
462  // node.
463  void ResetFirstAdmissibleArcs();
464 
465  // Scales the costs, by multiplying them by (graph_->num_nodes() + 1).
466  void ScaleCosts();
467 
468  // Unscales the costs, by dividing them by (graph_->num_nodes() + 1).
469  void UnscaleCosts();
470 
471  // Optimizes the cost by dividing epsilon_ by alpha_ and calling Refine().
472  void Optimize();
473 
474  // Saturates the admissible arcs, i.e., push as much flow as possible.
475  void SaturateAdmissibleArcs();
476 
477  // Pushes flow on a given arc, i.e., consumes flow on
478  // residual_arc_capacity_[arc], and consumes -flow on
479  // residual_arc_capacity_[Opposite(arc)]. Updates node_excess_ at the tail
480  // and head of the arc accordingly.
481  void PushFlow(FlowQuantity flow, ArcIndex arc);
482  void FastPushFlow(FlowQuantity flow, ArcIndex arc, NodeIndex tail);
483 
484  // Initializes the stack active_nodes_.
485  void InitializeActiveNodeStack();
486 
487  // Price update heuristics as described in A.V. Goldberg, "An Efficient
488  // Implementation of a Scaling Minimum-Cost Flow Algorithm," Journal of
489  // Algorithms, (1997) 22:1-29
490  // http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.258
491  void UpdatePrices();
492 
493  // Performs an epsilon-optimization step by saturating admissible arcs
494  // and discharging the active nodes.
495  void Refine();
496 
497  // Discharges an active node by saturating its admissible adjacent arcs,
498  // if any, and by relabelling it when it becomes inactive.
499  void Discharge(NodeIndex node);
500 
501  // Part of the Push LookAhead heuristic. When we are about to push on the
502  // in_arc, we check that the head (i.e node here) can accept the flow and
503  // return true if this is the case:
504  // - Returns true if the node excess is < 0.
505  // - Returns true if node is an admissible arc at its current potential.
506  // - If the two conditions above are false, the node can be relabeled. We
507  // do that and return true if the in_arc is still admissible.
508  bool LookAhead(ArcIndex in_arc, CostValue in_tail_potential, NodeIndex node);
509 
510  // Relabels node, i.e., decreases its potential while keeping the
511  // epsilon-optimality of the pseudo flow. See CheckRelabelPrecondition() for
512  // details on the preconditions.
513  void Relabel(NodeIndex node);
514 
515  // Handy member functions to make the code more compact.
516  NodeIndex Head(ArcIndex arc) const { return graph_->Head(arc); }
517  NodeIndex Tail(ArcIndex arc) const { return graph_->Tail(arc); }
518  ArcIndex Opposite(ArcIndex arc) const;
519  bool IsArcDirect(ArcIndex arc) const;
520  bool IsArcValid(ArcIndex arc) const;
521 
522  // Pointer to the graph passed as argument.
523  const Graph* graph_;
524 
525  // An array representing the supply (if > 0) or the demand (if < 0)
526  // for each node in graph_.
527  QuantityArray node_excess_;
528 
529  // An array representing the potential (or price function) for
530  // each node in graph_.
531  CostArray node_potential_;
532 
533  // An array representing the residual_capacity for each arc in graph_.
534  // Residual capacities enable one to represent the capacity and flow for all
535  // arcs in the graph in the following manner.
536  // For all arcs, residual_arc_capacity_[arc] = capacity[arc] - flow[arc]
537  // Moreover, for reverse arcs, capacity[arc] = 0 by definition.
538  // Also flow[Opposite(arc)] = -flow[arc] by definition.
539  // Therefore:
540  // - for a direct arc:
541  // flow[arc] = 0 - flow[Opposite(arc)]
542  // = capacity[Opposite(arc)] - flow[Opposite(arc)]
543  // = residual_arc_capacity_[Opposite(arc)]
544  // - for a reverse arc:
545  // flow[arc] = -residual_arc_capacity_[arc]
546  // Using these facts enables one to only maintain residual_arc_capacity_,
547  // instead of both capacity and flow, for each direct and indirect arc. This
548  // reduces the amount of memory for this information by a factor 2.
549  // Note that the sum of the largest capacity of an arc in the graph and of
550  // the total flow in the graph mustn't exceed the largest 64 bit integer
551  // to avoid errors. CheckInputConsistency() verifies this constraint.
552  ZVector<ArcFlowType> residual_arc_capacity_;
553 
554  // An array representing the first admissible arc for each node in graph_.
555  ArcIndexArray first_admissible_arc_;
556 
557  // A stack used for managing active nodes in the algorithm.
558  // Note that the papers cited above recommend the use of a queue, but
559  // benchmarking so far has not proved it is better.
560  std::stack<NodeIndex> active_nodes_;
561 
562  // epsilon_ is the tolerance for optimality.
563  CostValue epsilon_;
564 
565  // alpha_ is the factor by which epsilon_ is divided at each iteration of
566  // Refine().
567  const int64 alpha_;
568 
569  // cost_scaling_factor_ is the scaling factor for cost.
570  CostValue cost_scaling_factor_;
571 
572  // An array representing the scaled unit cost for each arc in graph_.
573  ZVector<ArcScaledCostType> scaled_arc_unit_cost_;
574 
575  // The total cost of the flow.
576  CostValue total_flow_cost_;
577 
578  // The status of the problem.
579  Status status_;
580 
581  // An array containing the initial excesses (i.e. the supplies) for each
582  // node. This is used to create the max-flow-based feasibility checker.
583  QuantityArray initial_node_excess_;
584 
585  // An array containing the best acceptable excesses for each of the
586  // nodes. These excesses are imposed by the result of the max-flow-based
587  // feasibility checker for the nodes with an initial supply != 0. For the
588  // other nodes, the excess is simply 0.
589  QuantityArray feasible_node_excess_;
590 
591  // Statistics about this class.
592  StatsGroup stats_;
593 
594  // Number of Relabel() since last UpdatePrices().
595  int num_relabels_since_last_price_update_;
596 
597  // A Boolean which is true when feasibility has been checked.
598  bool feasibility_checked_;
599 
600  // Whether to use the UpdatePrices() heuristic.
601  bool use_price_update_;
602 
603  // Whether to check the problem feasibility with a max-flow.
604  bool check_feasibility_;
605 
606  DISALLOW_COPY_AND_ASSIGN(GenericMinCostFlow);
607 };
608 
609 #if !SWIG
610 
611 // Default MinCostFlow instance that uses StarGraph.
612 // New clients should use SimpleMinCostFlow if they can.
613 class MinCostFlow : public GenericMinCostFlow<StarGraph> {
614  public:
616 };
617 
618 #endif // SWIG
619 
620 } // namespace operations_research
621 #endif // OR_TOOLS_GRAPH_MIN_COST_FLOW_H_
Graph::OutgoingArcIterator OutgoingArcIterator
CostValue UnitCost(ArcIndex arc) const
Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator
FlowQuantity FeasibleSupply(NodeIndex node) const
FlowQuantity Flow(ArcIndex arc) const
void SetNodeSupply(NodeIndex node, FlowQuantity supply)
FlowQuantity InitialSupply(NodeIndex node) const
void SetArcFlow(ArcIndex arc, ArcFlowType new_flow)
bool CheckFeasibility(std::vector< NodeIndex > *const infeasible_supply_node, std::vector< NodeIndex > *const infeasible_demand_node)
FlowQuantity Capacity(ArcIndex arc) const
FlowQuantity Supply(NodeIndex node) const
void SetArcUnitCost(ArcIndex arc, ArcScaledCostType unit_cost)
void SetArcCapacity(ArcIndex arc, ArcFlowType new_capacity)
MinCostFlow(const StarGraph *graph)
CostValue UnitCost(ArcIndex arc) const
ArcIndex AddArcWithCapacityAndUnitCost(NodeIndex tail, NodeIndex head, FlowQuantity capacity, CostValue unit_cost)
FlowQuantity Flow(ArcIndex arc) const
SimpleMinCostFlow(NodeIndex reserve_num_nodes=0, ArcIndex reserve_num_arcs=0)
void SetNodeSupply(NodeIndex node, FlowQuantity supply)
FlowQuantity Capacity(ArcIndex arc) const
NodeIndex Head(ArcIndex arc) const
FlowQuantity Supply(NodeIndex node) const
NodeIndex Tail(ArcIndex arc) const
ZVector< FlowQuantity > QuantityArray
Definition: ebert_graph.h:209
ZVector< CostValue > CostArray
Definition: ebert_graph.h:210
ListGraph Graph
Definition: graph.h:2360