# Changes in doc/min_cost_flow.dox[710:8b0df68370a4:956:141f9c0db4a3] in lemon

Ignore:
File:
1 edited

Unmodified
Removed
• ## doc/min_cost_flow.dox

 r710 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). minimum total cost from a set of supply nodes to a set of demand nodes in a network with capacity constraints (lower and upper bounds) and arc costs. and arc costs \ref amo93networkflows. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. - For all \f$u\in V\f$ nodes: - \f$\pi(u)<=0\f$; - \f$\pi(u)\leq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$. Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] It means that the total demand must be less or equal to the It means that the total demand must be less or equal to the total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or positive) and all the demands have to be satisfied, but there - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. - For all \f$u\in V\f$ nodes: - \f$\pi(u)>=0\f$; - \f$\pi(u)\geq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$.
Note: See TracChangeset for help on using the changeset viewer.