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
184namespace operations_research {
185
186// Forward declaration.
187template <typename Graph, typename ArcFlowType, typename ArcScaledCostType>
188class 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()).
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.
324template <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.
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.
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.
613class 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