Implement a custom problem

In this tutorial, you will learn how to use this package to solve your own custom constrained shortest path problem.

First of all, make sure you read the Mathematical background. In order to use the generalized_constrained_shortest_path on your custom problem, you need to define a few different types and methods:

• Types that need to be implemented:
  • Resources types (backward and forward)
  • Expansion functions (backward and forward)
• Methods that need to be implemented:
  • Base.<= between two forward resources
  • Base.minimum of a vector of backward resources
  • Make forward functions callable on forward resources
  • Make backward function callable on backward resources
  • A callable cost function

You can checkout examples already implemented in the src/examples folder of this package.

Example on the unidimensional resource shortest path

We illustrate this on the same problem a in Shortest path with linear resource constraints but simplified with only one constraint.

using ConstrainedShortestPaths
using Graphs, SparseArrays
import Base: <=, minimum

Resources

Forward and backward resources for this example are in the same space:

struct Resource
    c::Float64
    w::Float64
end

Base.<= and Base.minimum

function <=(r1::Resource, r2::Resource)
    return r1.c <= r2.c && r1.w <= r2.w
end

function minimum(R::Vector{Resource})
    return Resource(minimum(r.c for r in R), minimum(r.w for r in R))
end

minimum (generic function with 14 methods)

Expansion functions

Same as the resources, the forward and backward expansion functions coincide in this example.

struct ExpansionFunction
    c::Float64
    w::Float64
end

function (f::ExpansionFunction)(q::Resource)
    return Resource(f.c + q.c, f.w + q.w)
end

Cost function

struct Cost
    W::Float64
end

function (cost::Cost)(fr::Resource, br::Resource)
    return fr.w + br.w <= cost.W ? fr.c + br.c : Inf
end

Test on an instance

nb_vertices = 4
graph = SimpleDiGraph(nb_vertices)
edge_list = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
distance_list = [1, 2, -1, 1, 1]
for (i, j) in edge_list
    add_edge!(graph, i, j)
end
I = [src(e) for e in edges(graph)]
J = [dst(e) for e in edges(graph)]
d = sparse(I, J, distance_list)

W = 1.0

cost_list = [[0.0], [0.0], [10.0], [0.0], [0]]
w = [0.0 for i in 1:nb_vertices, j in 1:nb_vertices, k in 1:1]
for ((i, j), k) in zip(edge_list, cost_list)
    w[i, j, :] = k
end

# origin forward resource and backward forward resource set to 0
resource = Resource(0.0, 0.0)

# forward and backward expansion functions are equal
If = [src(e) for e in edges(graph)]
Jf = [dst(e) for e in edges(graph)]
f = [ExpansionFunction(d[i, j], w[i, j]) for (i, j) in zip(If, Jf)]
F = sparse(If, Jf, f);

instance = CSPInstance(graph, resource, resource, Cost(W), F, F)
(; p_star, c_star) = generalized_constrained_shortest_path(instance)
@info "Result" c_star p_star

This page was generated using Literate.jl.