|
Limbo
|
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
|
Limbo
|
LP solved with min-cost flow. A better implementation of limbo::solvers::lpmcf::LpDualMcf. More...
#include <DualMinCostFlow.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 < 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 | |||
| DualMinCostFlow (model_type *model) | |||
| constructor More... | |||
| ~DualMinCostFlow () | |||
| destructor | |||
| SolverProperty | operator() (solver_type *solver=NULL) | ||
| API to run the algorithm. More... | |||
| value_type | diffBigM () const | ||
| void | setDiffBigM (value_type v) | ||
| set big M as a large number for differential constraints More... | |||
| value_type | boundBigM () const | ||
| void | setBoundBigM (value_type v) | ||
| set big M as a large number for bound constraints More... | |||
| graph_type const & | graph () 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 | |
| DualMinCostFlow (DualMinCostFlow const &rhs) | |
| copy constructor, forbidden More... | |
| DualMinCostFlow & | operator= (DualMinCostFlow const &rhs) |
| assignment, forbidden More... | |
| SolverProperty | solve (solver_type *solver) |
| kernel function to solve the problem More... | |
| void | prepare () |
| prepare data like big M | |
| void | buildGraph () |
| build dual min-cost flow graph | |
| void | mapObjective2Graph () |
| map variables and the objective to graph nodes | |
| unsigned int | mapDiffConstraint2Graph (bool countArcs) |
| map differential constraints to graph arcs More... | |
| unsigned int | mapBoundConstraint2Graph (bool countArcs) |
| map bound constraints to graph arcs More... | |
| void | addArcForDiffConstraint (node_type xi, node_type xj, value_type cij, value_type bigM) |
| generalized method to add an arc for differential constraint \( x_i - x_j \ge c_{ij} \), resolve negative arc costs by arc reversal More... | |
| 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_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 | |
| value_type | m_diffBigM |
| a big number for infinity for differential constraints | |
| value_type | m_boundBigM |
| a big number for infinity for bound constraints | |
| value_type | m_reversedArcFlowCost |
| normalized flow cost of overall reversed arcs to resolve negative arc cost, to get total flow cost of reversed arcs, it needs to times with big M | |
| arc_flow_map_type | m_mFlow |
| solution of min-cost flow, which is the dual solution of LP | |
| node_pot_map_type | m_mPotential |
| dual solution of min-cost flow, which is the solution of LP | |
LP solved with min-cost flow. A better implementation of limbo::solvers::lpmcf::LpDualMcf.
The dual problem of this LP is a min-cost flow problem, so we can solve the graph problem and then call shortest path algrithm to calculate optimum of primal problem.
\begin{eqnarray*} & min. & \sum_{i=1}^{n} c_i \cdot x_i - \sum_{i,j} u_{ij} \alpha_{ij}, \\ & s.t. & x_i - x_j - \alpha_{ij} \ge b_{ij}, \forall (i, j) \in E, \\ & & d_i \le x_i \le u_i, \forall i \in [1, n], \\ & & \alpha_{ij} \ge 0, \forall (i, j) \in A. \end{eqnarray*}
\begin{eqnarray*} & min. & \sum_{i=1}^{n} c_i \cdot (y_i-y_0) - \sum_{i,j} u_{ij} \alpha_{ij}, \\ & s.t. & y_i - y_j -\alpha_{ij} \ge b_{ij}, \forall (i, j) \in E \\ & & d_i \le y_i - y_0 - \alpha_{ij} \le u_i, \forall i \in [1, n], \\ & & y_i \textrm{ is unbounded integer}, \forall i \in [0, n], \\ & & \alpha_{ij} \ge 0, \forall (i, j) \in A. \end{eqnarray*}
\begin{eqnarray*} & min. & \sum_{i=0}^{n} c_i \cdot y_i - \sum_{i,j} u_{ij} \alpha_{ij}, \textrm{ where } \ c_i = \left\{\begin{array}{lr} c_i, & \forall i \in [1, n], \\ - \sum_{j=1}^{n} c_i, & i = 0, \end{array}\right. \\ & s.t. & y_i - y_j \ge \ \left\{\begin{array}{lr} b_{ij}, & \forall (i, j) \in E, \\ d_i, & \forall j = 0, i \in [1, n], \\ -u_i, & \forall i = 0, j \in [1, n], \end{array}\right. \\ & & y_i \textrm{ is unbounded integer}, \forall i \in [0, n], \\ & & \alpha_{ij} \ge 0, \forall (i, j) \in A. \end{eqnarray*}
Map to dual min-cost flow problem.
Let's use \(c'_i\) for generalized \(c_i\) and \(b'_{ij}\) for generalized \(b_{ij}\).
Then \(c'_i\) is node supply. For each \((i, j) \in E'\), an arc from i to j with cost \(-b'_{ij}\) and flow range \([0, u_{ij}]\). The variable \(\alpha_{ij}\) denotes the slackness in the primal problem, but the capacity constraint in the dual problem. We can set the edge capacity as \(u_{ij}\). We can also leave the edge uncapacited ( \(\infty\)) if there are no such variables.
Some concolusions from [1] where \(f_{ij}^*\) denotes the optimal flow on edge \((i, j)\) and \(c_{ij}^\pi\) denotes the reduced cost in the residual network.
These conclusions might be useful to check optimality for the primal problem.
Caution: this mapping of LP to dual min-cost flow results may result in negative arc cost which is not supported by all the algorithms (only capacity scaling algorithm supports). Therefore, graph transformation is introduced to convert arcs with negative costs to positive costs with arc inversal.
| T | coefficient type |
| V | variable type |
Definition at line 102 of file DualMinCostFlow.h.
|
inline |
constructor
| model | pointer to the model of problem |
Definition at line 132 of file DualMinCostFlow.h.
|
protected |
copy constructor, forbidden
| rhs | right hand side |
|
protected |
generalized method to add an arc for differential constraint \( x_i - x_j \ge c_{ij} \), resolve negative arc costs by arc reversal
| xi | node corresponding to variable \( x_i \) |
| xj | node corresponding to variable \( x_j \) |
| cij | constant at right hand side |
| bigM | large number for upper bound of capacity |
Definition at line 508 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::value_type limbo::solvers::DualMinCostFlow< T, V >::boundBigM | ( | ) | const |
Definition at line 257 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::arc_cost_map_type const & limbo::solvers::DualMinCostFlow< T, V >::costMap | ( | ) | const |
Definition at line 282 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::value_type limbo::solvers::DualMinCostFlow< T, V >::diffBigM | ( | ) | const |
Definition at line 247 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::arc_flow_map_type & limbo::solvers::DualMinCostFlow< T, V >::flowMap | ( | ) |
Definition at line 292 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::graph_type const & limbo::solvers::DualMinCostFlow< T, V >::graph | ( | ) | const |
Definition at line 267 of file DualMinCostFlow.h.
|
protected |
map bound constraints to graph arcs
| countArcs | flag for counting arcs mode, if true, only count arcs and no actual arcs are added; otherwise, add arcs |
Definition at line 463 of file DualMinCostFlow.h.
|
protected |
map differential constraints to graph arcs
| countArcs | flag for counting arcs mode, if true, only count arcs and no actual arcs are added; otherwise, add arcs |
Definition at line 434 of file DualMinCostFlow.h.
|
inline |
API to run the algorithm.
| solver | an object to solve min cost flow, use default updater if NULL |
Definition at line 153 of file DualMinCostFlow.h.
|
protected |
assignment, forbidden
| rhs | right hand side |
| DualMinCostFlow< T, V >::node_pot_map_type & limbo::solvers::DualMinCostFlow< T, V >::potentialMap | ( | ) |
Definition at line 297 of file DualMinCostFlow.h.
| void limbo::solvers::DualMinCostFlow< T, V >::setBoundBigM | ( | value_type | v | ) |
set big M as a large number for bound constraints
| v | value |
Definition at line 262 of file DualMinCostFlow.h.
| void limbo::solvers::DualMinCostFlow< T, V >::setDiffBigM | ( | value_type | v | ) |
set big M as a large number for differential constraints
| v | value |
Definition at line 252 of file DualMinCostFlow.h.
| void limbo::solvers::DualMinCostFlow< T, V >::setTotalFlowCost | ( | value_type | cost | ) |
| cost | total cost of min-cost flow graph |
Definition at line 307 of file DualMinCostFlow.h.
|
protected |
kernel function to solve the problem
| solver | an object to solve min cost flow, use default updater if NULL |
Definition at line 342 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::node_value_map_type const & limbo::solvers::DualMinCostFlow< T, V >::supplyMap | ( | ) | const |
Definition at line 287 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::value_type limbo::solvers::DualMinCostFlow< T, V >::totalCost | ( | ) | const |
Definition at line 312 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::value_type limbo::solvers::DualMinCostFlow< T, V >::totalFlowCost | ( | ) | const |
Definition at line 302 of file DualMinCostFlow.h.
| DualMinCostFlow< T, V >::arc_value_map_type const & limbo::solvers::DualMinCostFlow< T, V >::upperMap | ( | ) | const |
Definition at line 277 of file DualMinCostFlow.h.
1.8.8