COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/csp.h @ 2376:0ed45a6c74b1

Last change on this file since 2376:0ed45a6c74b1 was 2376:0ed45a6c74b1, checked in by Balazs Dezso, 17 years ago

Reorganization of the modules and groups

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  ///Algorithms for the Resource Constrained Shortest Path Problem
40 
41  ///The Resource Constrained Shortest (Least Cost) Path problem is the
42  ///following. We are given a directed graph with two additive weightings
43  ///on the edges, referred as \e cost and \e delay. In addition,
44  ///a source and a destination node \e s and \e t and a delay
45  ///constraint \e D is given. A path \e p is called \e feasible
46  ///if <em>delay(p)\<=D</em>. Then, the task is to find the least cost
47  ///feasible path.
48  ///
49  template<class Graph,
50           class CM=typename Graph:: template EdgeMap<double>,
51           class DM=CM>
52  class ConstrainedShortestPath
53  {
54  public:
55   
56    GRAPH_TYPEDEFS(typename Graph);
57   
58    typedef SimplePath<Graph> Path;
59   
60    Graph &_g;
61    Tolerance<double> tol;
62
63    CM &_cost;
64    DM &_delay;
65
66    class CoMap
67    {
68      CM &_cost;
69      DM &_delay;
70      double _lambda;
71    public:
72      typedef typename CM::Key Key;
73      typedef double Value;
74      CoMap(CM &c,DM &d) :_cost(c), _delay(d), _lambda(0) {}
75      double lambda() const { return _lambda; }
76      void lambda(double l)  { _lambda=l; }
77      Value operator[](Key &e) const
78      {
79        return _cost[e]+_lambda*_delay[e];
80      }
81    } _co_map;
82   
83   
84    Dijkstra<Graph, CoMap> _dij;
85    ///\e
86   
87    ///\e
88    ///
89    ConstrainedShortestPath(Graph &g, CM &cost, DM &delay)
90      : _g(g), _cost(cost), _delay(delay),
91        _co_map(cost,delay), _dij(_g,_co_map) {}
92   
93
94    ///Compute the cost of a path
95    double cost(const Path &p)
96    {
97      double s=0;
98      //      Path r; 
99      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e];
100      return s;
101    }
102
103    ///Compute the delay of a path
104    double delay(const Path &p)
105    {
106      double s=0;
107      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e];
108      return s;
109    }
110   
111    ///Runs the LARAC algorithm
112   
113    ///This function runs a Lagrange relaxation based heuristic to find
114    ///a delay constrained least cost path.
115    ///\param s source node
116    ///\param t target node
117    ///\retval lo_bo a lower bound on the optimal solution
118    ///\return the found path or an empty
119    Path larac(Node s, Node t, double delta, double &lo_bo)
120    {
121      NoCounter cnt("LARAC iterations: ");
122      double lambda=0;
123      double cp,cq,dp,dq,cr,dr;
124      Path p;
125      Path q;
126      Path r;
127      {
128        Dijkstra<Graph,CM> dij(_g,_cost);
129        dij.run(s,t);
130        cnt++;
131        if(!dij.reached(t)) return Path();
132        p=dij.path(t);
133        cp=cost(p);
134        dp=delay(p);
135      }
136      if(delay(p)<=delta) return p;
137      {
138        Dijkstra<Graph,DM> dij(_g,_delay);
139        dij.run(s,t);
140        cnt++;
141        q=dij.path(t);
142        cq=cost(q);
143        dq=delay(q);
144      }
145      if(delay(q)>delta) return Path();
146      while (true) {
147        lambda=(cp-cq)/(dq-dp);
148        _co_map.lambda(lambda);
149        _dij.run(s,t);
150        cnt++;
151        r=_dij.path(t);
152        cr=cost(r);
153        dr=delay(r);
154        if(!tol.less(cr+lambda*dr,cp+lambda*dp)) {
155          lo_bo=cq+lambda*(dq-delta);
156          return q;
157        }
158        else if(tol.less(dr,delta))
159          {
160            q=r;
161            cq=cr;
162            dq=dr;
163          }
164        else if(tol.less(delta,dr))
165          {
166            p=r;
167            cp=cr;
168            dp=dr;
169          }
170        else return r;
171      }
172    }
173  };
174 
175
176} //END OF NAMESPACE LEMON
177
178#endif
Note: See TracBrowser for help on using the repository browser.