COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/csp.h @ 2377:83775fab25dc

Last change on this file since 2377:83775fab25dc was 2377:83775fab25dc, checked in by Balazs Dezso, 13 years ago

Minor changes

File size: 4.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_CSP_H
20#define LEMON_CSP_H
21
22///\ingroup approx
23///\file
24///\brief Algorithm for the Resource Constrained Shortest Path problem.
25///
26///
27///\todo dijkstraZero() solution should be revised.
28
29#include <lemon/list_graph.h>
30#include <lemon/graph_utils.h>
31#include <lemon/error.h>
32#include <lemon/maps.h>
33#include <lemon/tolerance.h>
34#include <lemon/dijkstra.h>
35#include <lemon/path.h>
36#include <lemon/counter.h>
37namespace lemon {
38
39  ///\ingroup approx
40 
41  ///Algorithms for the Resource Constrained Shortest Path Problem
42 
43  ///The Resource Constrained Shortest (Least Cost) Path problem is the
44  ///following. We are given a directed graph with two additive weightings
45  ///on the edges, referred as \e cost and \e delay. In addition,
46  ///a source and a destination node \e s and \e t and a delay
47  ///constraint \e D is given. A path \e p is called \e feasible
48  ///if <em>delay(p)\<=D</em>. Then, the task is to find the least cost
49  ///feasible path.
50  ///
51  template<class Graph,
52           class CM=typename Graph:: template EdgeMap<double>,
53           class DM=CM>
54  class ConstrainedShortestPath
55  {
56  public:
57   
58    GRAPH_TYPEDEFS(typename Graph);
59   
60    typedef SimplePath<Graph> Path;
61   
62    Graph &_g;
63    Tolerance<double> tol;
64
65    CM &_cost;
66    DM &_delay;
67
68    class CoMap
69    {
70      CM &_cost;
71      DM &_delay;
72      double _lambda;
73    public:
74      typedef typename CM::Key Key;
75      typedef double Value;
76      CoMap(CM &c,DM &d) :_cost(c), _delay(d), _lambda(0) {}
77      double lambda() const { return _lambda; }
78      void lambda(double l)  { _lambda=l; }
79      Value operator[](Key &e) const
80      {
81        return _cost[e]+_lambda*_delay[e];
82      }
83    } _co_map;
84   
85   
86    Dijkstra<Graph, CoMap> _dij;
87    ///\e
88   
89    ///\e
90    ///
91    ConstrainedShortestPath(Graph &g, CM &cost, DM &delay)
92      : _g(g), _cost(cost), _delay(delay),
93        _co_map(cost,delay), _dij(_g,_co_map) {}
94   
95
96    ///Compute the cost of a path
97    double cost(const Path &p)
98    {
99      double s=0;
100      //      Path r; 
101      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e];
102      return s;
103    }
104
105    ///Compute the delay of a path
106    double delay(const Path &p)
107    {
108      double s=0;
109      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e];
110      return s;
111    }
112   
113    ///Runs the LARAC algorithm
114   
115    ///This function runs a Lagrange relaxation based heuristic to find
116    ///a delay constrained least cost path.
117    ///\param s source node
118    ///\param t target node
119    ///\retval lo_bo a lower bound on the optimal solution
120    ///\return the found path or an empty
121    Path larac(Node s, Node t, double delta, double &lo_bo)
122    {
123      NoCounter cnt("LARAC iterations: ");
124      double lambda=0;
125      double cp,cq,dp,dq,cr,dr;
126      Path p;
127      Path q;
128      Path r;
129      {
130        Dijkstra<Graph,CM> dij(_g,_cost);
131        dij.run(s,t);
132        cnt++;
133        if(!dij.reached(t)) return Path();
134        p=dij.path(t);
135        cp=cost(p);
136        dp=delay(p);
137      }
138      if(delay(p)<=delta) return p;
139      {
140        Dijkstra<Graph,DM> dij(_g,_delay);
141        dij.run(s,t);
142        cnt++;
143        q=dij.path(t);
144        cq=cost(q);
145        dq=delay(q);
146      }
147      if(delay(q)>delta) return Path();
148      while (true) {
149        lambda=(cp-cq)/(dq-dp);
150        _co_map.lambda(lambda);
151        _dij.run(s,t);
152        cnt++;
153        r=_dij.path(t);
154        cr=cost(r);
155        dr=delay(r);
156        if(!tol.less(cr+lambda*dr,cp+lambda*dp)) {
157          lo_bo=cq+lambda*(dq-delta);
158          return q;
159        }
160        else if(tol.less(dr,delta))
161          {
162            q=r;
163            cq=cr;
164            dq=dr;
165          }
166        else if(tol.less(delta,dr))
167          {
168            p=r;
169            cp=cr;
170            dp=dr;
171          }
172        else return r;
173      }
174    }
175  };
176 
177
178} //END OF NAMESPACE LEMON
179
180#endif
Note: See TracBrowser for help on using the repository browser.