#include <min_cost_flow.h>
Different statuses for a solved problem. We use a base class to share it between our different interfaces.
Definition at line 190 of file min_cost_flow.h.
◆ Status
| Enumerator |
|---|
| NOT_SOLVED | |
| OPTIMAL | |
| FEASIBLE | |
| INFEASIBLE | |
| UNBALANCED | |
| BAD_RESULT | |
| BAD_COST_RANGE | This is returned when an integer overflow occurred during the algorithm execution.
Some details on how to deal with this:
- Since we scale cost, each arc unit cost times (num_nodes + 1) should not overflow. We detect that at the beginning of the Solve().
- This is however not sufficient as the node potential depends on the minimum cost of sending 1 unit of flow through the residual graph. If the maximum arc unit cost is smaller than kint64max / (2 * n ^ 2) then one shouldn't run into any overflow. But in pratice this bound is quite loose. So it is possible to try with higher cost, and the algorithm will detect if an overflow actually happen and return BAD_COST_RANGE, so we can retry with smaller cost.
And two remarks:
- Note that the complexity of the algorithm depends on the maximum cost, so it is usually a good idea to use unit cost that are as small as possible.
- Even if there is no overflow, note that the total cost can easily not fit on an int64_t since it is the product of the unit cost times the actual amount of flow sent. This is easy to detect since the final optimal cost will be set to kint64max. It is also relatively easy to deal with since we will still have the proper flow on each arc. It is thus possible to recompute the total cost in double or using absl::int128 if the need arise.
|
| BAD_CAPACITY_RANGE | This is returned in our initial check if the arc capacity are too large. For each node these quantity should not overflow the FlowQuantity type which is int64_t by default.
- Its initial excess (+supply or -demand) + sum incoming arc capacity
- Its initial excess (+supply or -demand) - sum outgoing arc capacity.
- Note
- these are upper bounds that guarantee that no overflow will take place during the algorithm execution. It is possible to go over that and still encounter no overflow, but since we cannot guarantee this, we rather check early and return a proper status.
-
we might cap the capacity of the arcs if we can detect it is too large in order to avoid returning this status for simple case, like if a client used int64_t max for all arcs out of the source.
- Todo
- (user): Not sure this is a good idea, probably better to make sure client use reasonable capacities. Also we should template by FlowQuantity and allow use of absl::int128 so we never have issue if the input is int64_t.
|
Definition at line 192 of file min_cost_flow.h.
The documentation for this class was generated from the following file:
1.13.2