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

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 Base.:<=(r1::Resource, r2::Resource)
    return r1.c <= r2.c && r1.w <= r2.w
end

function Base.min(r₁::Resource, r₂::Resource)
    new_c = min(r₁.c, r₂.c)
    new_w = min(r₁.w, r₂.w)
    return Resource(new_c, new_w)
end

Expansion functions

struct ForwardExpansionFunction
    c::Float64
    w::Float64
end

function (f::ForwardExpansionFunction)(q::Resource; W)
    return Resource(f.c + q.c, f.w + q.w), f.w + q.w <= W
end

struct BackwardExpansionFunction
    c::Float64
    w::Float64
end

function (f::BackwardExpansionFunction)(q::Resource; W)
    return Resource(f.c + q.c, f.w + q.w)
end

Cost function

struct Cost end

function (cost::Cost)(fr::Resource, br::Resource)
    return fr.c + br.c
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)]
ff = [ForwardExpansionFunction(d[i, j], w[i, j]) for (i, j) in zip(If, Jf)]
fb = [BackwardExpansionFunction(d[i, j], w[i, j]) for (i, j) in zip(If, Jf)]
FF = sparse(If, Jf, ff);
FB = sparse(If, Jf, fb);

instance = CSPInstance(;
    graph,
    origin_vertex=1,
    destination_vertex=nb_vertices,
    origin_forward_resource=resource,
    destination_backward_resource=resource,
    cost_function=Cost(),
    forward_functions=FF,
    backward_functions=FB,
)
(; p_star, c_star) = generalized_constrained_shortest_path(instance; W=W)
@info "Result" c_star p_star

┌ Info: Result
│   c_star = 2.0
│   p_star =
│    3-element Vector{Int64}:
│     1
│     2
└     4

This page was generated using Literate.jl.