Limbo
|
LP solved with min-cost flow. More...
#include <MinCostFlow.h>
Public Types | |
typedef LinearModel< T, V > | model_type |
linear model type for the problem | |
typedef model_type::coefficient_value_type | coefficient_value_type |
typedef model_type::variable_value_type | variable_value_type |
typedef variable_value_type | value_type |
typedef model_type::variable_type | variable_type |
typedef model_type::constraint_type | constraint_type |
typedef model_type::expression_type | expression_type |
typedef model_type::term_type | term_type |
typedef model_type::property_type | property_type |
typedef lemon::SmartDigraph | graph_type |
typedef graph_type::Node | node_type |
typedef graph_type::Arc | arc_type |
typedef graph_type::NodeMap < value_type > | node_value_map_type |
typedef graph_type::NodeMap < std::string > | node_name_map_type |
typedef graph_type::ArcMap < std::string > | arc_name_map_type |
typedef graph_type::ArcMap < value_type > | arc_value_map_type |
typedef graph_type::ArcMap < value_type > | arc_cost_map_type |
typedef graph_type::ArcMap < value_type > | arc_flow_map_type |
typedef graph_type::NodeMap < value_type > | node_pot_map_type |
typedef MinCostFlowSolver < coefficient_value_type, variable_value_type > | solver_type |
Public Member Functions | |||
MinCostFlow (model_type *model) | |||
constructor More... | |||
~MinCostFlow () | |||
destructor | |||
SolverProperty | operator() (solver_type *solver=NULL) | ||
API to run the algorithm. More... | |||
graph_type const & | graph () const | ||
arc_value_map_type const & | lowerMap () const | ||
arc_value_map_type const & | upperMap () const | ||
arc_cost_map_type const & | costMap () const | ||
node_value_map_type const & | supplyMap () const | ||
arc_flow_map_type & | flowMap () | ||
node_pot_map_type & | potentialMap () | ||
value_type | totalFlowCost () const | ||
void | setTotalFlowCost (value_type cost) | ||
value_type | totalCost () const | ||
print functions to debug.lgf | |||
print graph
| |||
void | printGraph (bool writeSol) const | ||
Protected Member Functions | |
MinCostFlow (MinCostFlow const &rhs) | |
copy constructor, forbidden More... | |
MinCostFlow & | operator= (MinCostFlow const &rhs) |
assignment, forbidden More... | |
SolverProperty | solve (solver_type *solver) |
kernel function to solve the problem More... | |
void | buildGraph () |
build min-cost flow graph | |
void | setObjective (expression_type const &obj) |
set objective, support incremental set | |
void | applySolution () |
apply solutions to model | |
Protected Attributes | |
model_type * | m_model |
model for the problem | |
graph_type | m_graph |
input graph | |
arc_value_map_type | m_mLower |
lower bound of flow, usually zero | |
arc_value_map_type | m_mUpper |
upper bound of flow, arc capacity in min-cost flow | |
arc_cost_map_type | m_mCost |
arc cost in min-cost flow | |
node_value_map_type | m_mSupply |
node supply in min-cost flow | |
value_type | m_totalFlowCost |
total cost after solving | |
arc_flow_map_type | m_mFlow |
solution of min-cost flow, which is the solution of LP | |
node_pot_map_type | m_mPotential |
solution of min-cost flow, which is the dual solution of LP | |
LP solved with min-cost flow.
The primal problem of this LP is a min-cost flow problem, so we can solve the graph problem.
\begin{eqnarray*} & min. & \sum_{i, j \in E} c_{ij} \cdot x_{ij}, \\ & s.t. & l_{ij} \le x_{ij} \le u_{ij}, \forall (i, j) \in E, \\ & & \sum_{j \in V} x_{ij} = s_i, \forall i \ne t, \in V, \\ & & x_{ij} = -x_{ji}, \forall (i, j) \in E. (implicit) \end{eqnarray*}
T | coefficient type |
V | variable type |
Definition at line 60 of file MinCostFlow.h.
|
inline |
constructor
model | pointer to the model of problem |
Definition at line 91 of file MinCostFlow.h.
|
protected |
copy constructor, forbidden
rhs | right hand side |
MinCostFlow< T, V >::arc_cost_map_type const & limbo::solvers::MinCostFlow< T, V >::costMap | ( | ) | const |
Definition at line 189 of file MinCostFlow.h.
MinCostFlow< T, V >::arc_flow_map_type & limbo::solvers::MinCostFlow< T, V >::flowMap | ( | ) |
Definition at line 199 of file MinCostFlow.h.
MinCostFlow< T, V >::graph_type const & limbo::solvers::MinCostFlow< T, V >::graph | ( | ) | const |
Definition at line 174 of file MinCostFlow.h.
MinCostFlow< T, V >::arc_value_map_type const & limbo::solvers::MinCostFlow< T, V >::lowerMap | ( | ) | const |
Definition at line 179 of file MinCostFlow.h.
|
inline |
API to run the algorithm.
solver | an object to solve min cost flow, use default updater if NULL |
Definition at line 110 of file MinCostFlow.h.
|
protected |
assignment, forbidden
rhs | right hand side |
MinCostFlow< T, V >::node_pot_map_type & limbo::solvers::MinCostFlow< T, V >::potentialMap | ( | ) |
Definition at line 204 of file MinCostFlow.h.
void limbo::solvers::MinCostFlow< T, V >::setTotalFlowCost | ( | value_type | cost | ) |
cost | total cost of min-cost flow graph |
Definition at line 214 of file MinCostFlow.h.
|
protected |
kernel function to solve the problem
solver | an object to solve min cost flow, use default updater if NULL |
Definition at line 252 of file MinCostFlow.h.
MinCostFlow< T, V >::node_value_map_type const & limbo::solvers::MinCostFlow< T, V >::supplyMap | ( | ) | const |
Definition at line 194 of file MinCostFlow.h.
MinCostFlow< T, V >::value_type limbo::solvers::MinCostFlow< T, V >::totalCost | ( | ) | const |
Definition at line 219 of file MinCostFlow.h.
MinCostFlow< T, V >::value_type limbo::solvers::MinCostFlow< T, V >::totalFlowCost | ( | ) | const |
Definition at line 209 of file MinCostFlow.h.
MinCostFlow< T, V >::arc_value_map_type const & limbo::solvers::MinCostFlow< T, V >::upperMap | ( | ) | const |
Definition at line 184 of file MinCostFlow.h.