CSPInstance{G,FR,BR,C,FF,BF}

Attributes

• graph
• origin_forward_resource
• destination_backward_resource
• cost_function
• forward_functions
• backward_functions

PiecewiseLinear

Type used to represent increasing piecewise linear functions, with starting slope 0.

Attributes

• final_slope::Float64: (positive) slope of the last linear piece.
• break_x::Vector{Float64}: (ordered) list of all break points x-coordinates.
• break_y::Vector{Float64}: (non decreasing) list of all break points y-coordinates corresponding to break_x elementwise.

(f)(x)

Returns f(x).

+(f1, f2)

Return a PiecewiseLinear corresponding to f1 + f2.

basic_shortest_path(graph, distmx=weights(graph), s, t)

Compute shortest path between vertices s and t of graph graph.

Arguments

• graph::AbstractGraph: acyclic directed graph.
• distmx::AbstractMatrix: distmx[i, j] corresponds to the distance between vertices i and j along edge (i, j) of graph.

Returns

• p_star::Vector{Int}: optimal path found.
• c_star::Float64: length of path p_star.

closest_break_point(break_x, x)

Find the index of the closest break point from x. (at its right i fright=true else at its left)

compose(f1, f2)

Return a PiecewiseLinear corresponding to f1 ∘ f2 ! only support functions with only one break point and final slope 1

compute_bounds(instance)

Compute backward bounds of instance (see Computing bounds).

generalized_a_star(instance, s, t, bounds)

Perform generalized A star algorithm on instnace using bounds (see Generalized A^\star).

generalized_a_star_with_threshold(instance, bounds, threshold)

Compute all paths below threshold.

generalized_constrained_shortest_path(instance, s, t)

Compute the shortest path of instance.

generalized_constrained_shortest_path(instance)

Compute shortest path between first and last nodes of instance

get_points(f1, f2, i1, i2)

Return break point i1 of f1 and break point i2 of f2. If i1 or i2 are out of range, return a border (x, f(x)).

get_x(f, i; x_max=1000)

Return x coordinate of breakpoint i. If i is out of range, return xmax

intersection(f1, f2, i1, i2)

Return -1 if there is no intersection else the x coordinate of the intersection.

meet(f1, f2)

Compute the minimum of two PiecewiseLinear functions Return a PiecewiseLinear f, such that ∀x, f(x) = min(f1(x), f2(x)).

resource_shortest_path(g, s, t, distmx, costmx)

Compute resource contrained shortest path between vertices s and t of graph g.

Arguments

• g::AbstractGraph: acyclic directed graph.
• max_costs::AbstractVector: list of upper bounds for each resource constraint.
• distmx::AbstractMatrix: distmx[i, j] corresponds to the distance between vertices i and j along edge (i, j) of g.
• costmx::Array{Float64, 3}: cost_mx[i, j, k] corresponds to the resource cost of edge (i, j) for the kth resource constraint.

Returns

• p_star::Vector{Int}: optimal path found.
• c_star::Float64: length of path p_star.

stochastic_routing_shortest_path(graph, slacks, delays)

Compute stochastic routing shortest path between first and last vertices of graph graph.

Arguments

• graph::AbstractGraph: acyclic directed graph.
• slacks: slacks[i, j] corresponds to the time slack between i and j.
• delays: delays[i, ω] corresponds to delay of i for scenario ω.

Returns

• p_star::Vector{Int}: optimal path found.
• c_star::Float64: length of path p_star.