Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Types | List of all members
operations_research::MinCostFlowBase Class Reference

#include <min_cost_flow.h>

Inheritance diagram for operations_research::MinCostFlowBase:
operations_research::GenericMinCostFlow< StarGraph > operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType > operations_research::SimpleMinCostFlow operations_research::MinCostFlow

Public Types

enum  Status {
  NOT_SOLVED , OPTIMAL , FEASIBLE , INFEASIBLE ,
  UNBALANCED , BAD_RESULT , BAD_COST_RANGE
}
 

Detailed Description

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.

Member Enumeration Documentation

◆ Status

enum operations_research::MinCostFlowBase::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:

  • The sum of all incoming/outgoing capacity at each node should not overflow.
    Todo
    (user): this is not always properly checked and probably deserve a different return status.

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.

Definition at line 192 of file min_cost_flow.h.

The documentation for this class was generated from the following file: