/** * @file mcfp_cf_itermaxflow_lemon.cc * @author Andrew Powell * @date Oct 9, 2016 * * @brief Solves the Concurrent Flow variant of the Multi- * Commodity Flow Problem. * * In this example, the Concurent Flow variant * of the Multi-Commodity Flow Problem is solved with * an iterative algorithm ( really a method ), where for each commodity, * the Maximum Flow Problem is solved and the capacities * of each arc are then updated accordingly. The method was based on * a similar approach from the following link. * * http://www.es.ele.tue.nl/~kgoossens/Stefan12PHD.pdf * * This problem can be formally formulated as the following. Say the flow network \f$G\f$ * has the following form. * \f{align*}{ G & = \text{Directed Graph} \\ & = (V,E) \\ V & = \text{Node Set} \\ E & = \text{Arc Set} \\ e & = (v_e\in V,w_e\in V,c_e\in \mathbf{R}_{\ge 0}) \\ & \in E \\ v_e & = \text{Source Node of $e\in E$} \\ w_e & = \text{Sink Node of $e\in E$} \\ c_{e} & = \text{Capacity ( Upper Bound ) of Arc $e\in E$} \f} * * Let, the commodities \f$K\f$ have the following definition. * \f{align*}{ K & = \text{Commodity Set} \\ k & = (s_k\in V,t_k\in V,d_k\in \mathbf{R}_{\ge 0}) \\ & \in K \\ s_k & = \text{Source Node of Commodity $k\in K$} \\ t_k & = \text{Sink Node of Commodity $k\in K$} \\ d_k & = \text{Demand of Commodity $k\in K$} \\ \f} * * Given a particular commodity \f$k\in K\f$ and the network \f$G\f$, the \f$\text{Maximum Flow Problem}\f$ * is formalized as the following. * \f{align*}{ \text{Maximize} & : \sum_{v\in V}f_{k,(s_k,v)} : k \in K \\ f_{k,e} & = \text{Flow of Commodity $k\in K$ on Edge $e\in E$} \\ \\ \text{Subject to:} & \\ \Delta_{k,v} & = \text{Net Flow of Arc $e\in E$ of Commodity $k\in K$.} \\ & = \sum_{w \in V} f_{k,(v,w)} - \sum_{w \in V} f_{k,(w,v)} \\ & = 0 : k \in K, \forall v \in \{ w \in V: w \neq s_k,t_k \} \\ & = d_k : k \in K, \forall v \in \{ w \in V: w = s_k \} \text{( Defined by Node Supply)}\\ & = -d_k : k \in K, \forall v \in \{ w \in V: w = t_k \} \text{( Defined by Node Supply)}\\ c_{e} & \ge f_{k,e}\ \ge 0 : k \in K, \forall e \in E \\ \f} * * The \f$\text{Maximum Flow Problem}\f$ is solved with the LEMON's implementation * of an algorithm that solves the network circulation problem. Details on the * LEMON implementation can be found from the following link: * * http://lemon.cs.elte.hu/pub/doc/1.2.3/a00533.html * * The iterative algorithm is finally described below. * \f{algorithm}{ \caption{Calculate $f_{k,e}, \forall k\in K, \forall e\in E$} \label{alg1} \begin{algorithmic} \REQUIRE $c \ge 0, G, K$ \ENSURE $f_{k,e} : \forall k\in K, \forall e\in E$ \STATE $c_{k,e} \Leftarrow c_e : \forall k\in K$ \WHILE{$|K|>0$} \STATE $k^* \Leftarrow \text{argmax}_{k\in K}\{d_k \}$ \STATE $f_{k^*,e} \Leftarrow \text{Solve Maximum Flow Problem for Commodity$k^*$and Graph$G$}$ \STATE $c_{e} \Leftarrow c_{e}-f_{k^*,e} : \forall e\in E$ \IF{$c_e < 0 : \exists e \in E$} \RETURN \FALSE \ENDIF \STATE $K \Leftarrow K - \{k^*\}$ \ENDWHILE \RETURN \TRUE \end{algorithmic} \f} * * The following library is needed to compile and run this application: * * lemon * * Also noted that the -std=c++11 flag is needed, as well. * * In order to generate a tex file of this documented sources, the * following extra packages are necessary: * * amsmath * algorithm * algorithmic * * Cheers! */ #include #include #include #include #include #include #include #include /* Just so this application looks cleaner all the declarations are stored in the following header file. */ #include "mcfp_cf_itermaxflow_lemon.h" /** * @brief Creates directed graph, commodities, and * performs the iterative algorithm. */ int main() try { /* Define the graph. */ Node A = addNode("A"); Node B = addNode("B"); Node C = addNode("C"); addArc(A,B,1.0,"AB"); addArc(B,C,1.0,"BC"); addArc(C,A,1.0,"CA"); /* Define the Commodities. */ addCommodity(A,C,0.5,"k0"); addCommodity(C,B,0.5,"k1"); /* Execute iterative algorithm. Basically, solve the Maximum Flow problem for the remaining commodity whose demand is the highest. Repeat until there are no more remaining commodities. */ Commodities rks( ks ); while ( rks.size() ) { /* Acquire commodity with largest demand. */ Commodities::iterator ldk = rks.begin(); for ( Commodities::iterator k=rks.begin(); k!=rks.end(); ++k ) if ( kds[*k]>kds[*ldk] ) ldk = k; /* Generate the supply map. */ Supplies s(g,0.0); Demand d = kds[*ldk]; s[kss[*ldk]] = d; s[kts[*ldk]] = -d; /* Solve the Maximum Flow Problem for the current commodity. */ FlowMap fm(g); Circ(g,bls,bus,s).flowMap(fm).run(); /* Update the upper bounds and store flows. */ for ( Graph::ArcIt a(g); a!=lemon::INVALID; ++a ) { bus[a] -= fm[a]; if ( bus[a]<0.0 ) throw std::runtime_error( "Algorithm failed." ); kfs[std::make_pair(*ldk,a)] = fm[a]; } /* Remove commodity from the remaining commodities. */ rks.erase(ldk); } /* Display the results. */ displayResults(); return 0; } catch ( std::exception& e ) { std::cerr << e.what() << std::endl; } catch (...) { std::cerr << "A serious error occurred" << std::endl; }