COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/csp.h @ 2360:72c7075ad5ba

Last change on this file since 2360:72c7075ad5ba was 2360:72c7075ad5ba, checked in by Alpar Juttner, 13 years ago

Lagrange relaxation based algorithm for the delay constrained least cost
path problem.

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