alpar@2360: /* -*- C++ -*- alpar@2360: * alpar@2360: * This file is a part of LEMON, a generic C++ optimization library alpar@2360: * alpar@2553: * Copyright (C) 2003-2008 alpar@2360: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2360: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2360: * alpar@2360: * Permission to use, modify and distribute this software is granted alpar@2360: * provided that this copyright notice appears in all copies. For alpar@2360: * precise terms see the accompanying LICENSE file. alpar@2360: * alpar@2360: * This software is provided "AS IS" with no warranty of any kind, alpar@2360: * express or implied, and with no claim as to its suitability for any alpar@2360: * purpose. alpar@2360: * alpar@2360: */ alpar@2360: alpar@2360: #ifndef LEMON_CSP_H alpar@2360: #define LEMON_CSP_H alpar@2360: deba@2376: ///\ingroup approx alpar@2360: ///\file alpar@2360: ///\brief Algorithm for the Resource Constrained Shortest Path problem. alpar@2360: /// alpar@2360: alpar@2360: #include alpar@2360: #include alpar@2360: #include alpar@2360: #include alpar@2360: #include alpar@2360: #include alpar@2360: #include alpar@2360: #include alpar@2360: namespace lemon { deba@2377: deba@2377: ///\ingroup approx deba@2486: /// deba@2486: ///\brief Algorithms for the Resource Constrained Shortest Path Problem deba@2486: /// alpar@2373: ///The Resource Constrained Shortest (Least Cost) Path problem is the alpar@2373: ///following. We are given a directed graph with two additive weightings alpar@2373: ///on the edges, referred as \e cost and \e delay. In addition, alpar@2373: ///a source and a destination node \e s and \e t and a delay alpar@2373: ///constraint \e D is given. A path \e p is called \e feasible alpar@2373: ///if delay(p)\<=D. Then, the task is to find the least cost alpar@2373: ///feasible path. alpar@2360: /// alpar@2360: template, alpar@2360: class DM=CM> alpar@2360: class ConstrainedShortestPath alpar@2360: { alpar@2360: public: alpar@2360: alpar@2360: GRAPH_TYPEDEFS(typename Graph); alpar@2360: alpar@2360: typedef SimplePath Path; alpar@2360: deba@2401: private: deba@2401: deba@2401: const Graph &_g; alpar@2360: Tolerance tol; alpar@2360: deba@2401: const CM &_cost; deba@2401: const DM &_delay; alpar@2360: alpar@2360: class CoMap alpar@2360: { deba@2401: const CM &_cost; deba@2401: const DM &_delay; alpar@2360: double _lambda; alpar@2360: public: alpar@2360: typedef typename CM::Key Key; alpar@2360: typedef double Value; deba@2401: CoMap(const CM &c, const DM &d) :_cost(c), _delay(d), _lambda(0) {} alpar@2360: double lambda() const { return _lambda; } alpar@2360: void lambda(double l) { _lambda=l; } alpar@2360: Value operator[](Key &e) const alpar@2360: { alpar@2360: return _cost[e]+_lambda*_delay[e]; alpar@2360: } deba@2401: }; deba@2401: deba@2401: CoMap _co_map; alpar@2360: alpar@2360: alpar@2360: Dijkstra _dij; deba@2401: deba@2401: public: deba@2401: deba@2486: /// \brief Constructor alpar@2360: deba@2486: ///Constructor alpar@2360: /// deba@2401: ConstrainedShortestPath(const Graph &g, const CM &ct, const DM &dl) deba@2386: : _g(g), _cost(ct), _delay(dl), deba@2401: _co_map(ct, dl), _dij(_g,_co_map) {} alpar@2360: alpar@2360: alpar@2360: ///Compute the cost of a path deba@2401: double cost(const Path &p) const alpar@2360: { alpar@2360: double s=0; alpar@2360: // Path r; alpar@2360: for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e]; alpar@2360: return s; alpar@2360: } alpar@2360: alpar@2360: ///Compute the delay of a path deba@2401: double delay(const Path &p) const alpar@2360: { alpar@2360: double s=0; alpar@2360: for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e]; alpar@2360: return s; alpar@2360: } alpar@2360: alpar@2360: ///Runs the LARAC algorithm alpar@2360: alpar@2360: ///This function runs a Lagrange relaxation based heuristic to find alpar@2360: ///a delay constrained least cost path. alpar@2360: ///\param s source node alpar@2360: ///\param t target node deba@2486: ///\param delta upper bound on the delta alpar@2360: ///\retval lo_bo a lower bound on the optimal solution alpar@2360: ///\return the found path or an empty alpar@2360: Path larac(Node s, Node t, double delta, double &lo_bo) alpar@2360: { alpar@2360: double lambda=0; alpar@2360: double cp,cq,dp,dq,cr,dr; alpar@2360: Path p; alpar@2360: Path q; alpar@2360: Path r; alpar@2360: { alpar@2360: Dijkstra dij(_g,_cost); alpar@2360: dij.run(s,t); alpar@2360: if(!dij.reached(t)) return Path(); alpar@2360: p=dij.path(t); alpar@2360: cp=cost(p); alpar@2360: dp=delay(p); alpar@2360: } alpar@2360: if(delay(p)<=delta) return p; alpar@2360: { alpar@2360: Dijkstra dij(_g,_delay); alpar@2360: dij.run(s,t); alpar@2360: q=dij.path(t); alpar@2360: cq=cost(q); alpar@2360: dq=delay(q); alpar@2360: } alpar@2360: if(delay(q)>delta) return Path(); alpar@2360: while (true) { alpar@2360: lambda=(cp-cq)/(dq-dp); alpar@2360: _co_map.lambda(lambda); alpar@2360: _dij.run(s,t); alpar@2360: r=_dij.path(t); alpar@2360: cr=cost(r); alpar@2360: dr=delay(r); alpar@2360: if(!tol.less(cr+lambda*dr,cp+lambda*dp)) { alpar@2360: lo_bo=cq+lambda*(dq-delta); alpar@2360: return q; alpar@2360: } alpar@2360: else if(tol.less(dr,delta)) alpar@2360: { alpar@2360: q=r; alpar@2360: cq=cr; alpar@2360: dq=dr; alpar@2360: } alpar@2360: else if(tol.less(delta,dr)) alpar@2360: { alpar@2360: p=r; alpar@2360: cp=cr; alpar@2360: dp=dr; alpar@2360: } alpar@2360: else return r; alpar@2360: } alpar@2360: } alpar@2360: }; alpar@2360: alpar@2360: alpar@2360: } //END OF NAMESPACE LEMON alpar@2360: alpar@2360: #endif