Multi-sample shortest paths#
Here we will see how the multi-sample capabilities of CORNETO allow to exactly solve more complex problems on networks.
Imagine you have a directed graph G with a defined set of vertices and edges. Each edge in this graph has two different costs associated with it, one for each sample (let’s call these Sample 1 and Sample 2). These costs represent two possible scenarios or configurations. For each sample, we want to find the shortest path using the costs defined for that sample. We could run a standard shortest path method per sample. However, given that there can be multiple shortest paths with the same total cost, following that strategy, we cannot identify interesting solutions, for example, if there is a path that is the shortest for both samples. Without a multi-sample method, we need to enumerate all shortest paths per sample, and then compare them to find the answer. This is not only computationally expensive but also not feasible for large networks.
Using CORNETO, it is possible to create a multi shortest path problem to identify a pair of shortest paths—one for each sample—that minimize the number of “non-selected” edges across both samples. This objective can be interpreted in two ways:
If there are multiple shortest paths with the same total cost for a given sample, prefer the one with the fewest edges (i.e., the most direct route).
If the shortest paths differ between the two samples, prioritize the selection of paths that share the greatest number of common edges. This ensures that, despite different costs, the paths are as similar as possible.
We will see how to solve this problem using CORNETO’s multi-sample capabilities.
import corneto as cn
cn.info()
|
|
G = cn.Graph()
G.add_edge("A", "B")
G.add_edge("A", "C")
G.add_edge("A", "F")
G.add_edge("B", "D")
G.add_edge("B", "E")
G.add_edge("C", "F")
G.add_edge("D", "A")
G.add_edge("D", "C")
G.add_edge("D", "G")
G.add_edge("E", "D")
G.add_edge("E", "H")
G.add_edge("F", "G")
G.add_edge("G", "E")
G.add_edge("G", "H")
G.add_edge("H", "F")
G.plot()
for i, e in enumerate(G.E):
print(i, e)
0 (frozenset({'A'}), frozenset({'B'}))
1 (frozenset({'A'}), frozenset({'C'}))
2 (frozenset({'A'}), frozenset({'F'}))
3 (frozenset({'B'}), frozenset({'D'}))
4 (frozenset({'B'}), frozenset({'E'}))
5 (frozenset({'C'}), frozenset({'F'}))
6 (frozenset({'D'}), frozenset({'A'}))
7 (frozenset({'D'}), frozenset({'C'}))
8 (frozenset({'D'}), frozenset({'G'}))
9 (frozenset({'E'}), frozenset({'D'}))
10 (frozenset({'E'}), frozenset({'H'}))
11 (frozenset({'F'}), frozenset({'G'}))
12 (frozenset({'G'}), frozenset({'E'}))
13 (frozenset({'G'}), frozenset({'H'}))
14 (frozenset({'H'}), frozenset({'F'}))
# Weights for the 14 edges for the two samples
c1_weights = [3, 6, 7, 1, 7, 1, 1, 2, 6, 2, 5, 2, 1, 6, 1]
c2_weights = [5, 15, 17, 6, 14, 1, 2, 3, 6, 1, 3, 2, 2, 5, 2]
from corneto.methods import solve_shortest_path
# We solve independently each shortest path problem
edges, P, Gc = solve_shortest_path(G, "A", "H", edge_weights=c1_weights, solver="SCIPY")
Gc.edge_subgraph(edges).plot(orphan_edges=False)
P.objectives[0].value
np.float64(15.0)
edges, P, Gc = solve_shortest_path(G, "A", "H", edge_weights=c2_weights, solver="SCIPY")
Gc.edge_subgraph(edges).plot(orphan_edges=False)
P.objectives[0].value
np.float64(22.0)
from corneto.methods.shortest_path import create_multisample_shortest_path
samples = [("A", "H"), ("A", "H")]
edge_weights = [c1_weights, c2_weights]
P, Gc = create_multisample_shortest_path(
G, samples, edge_weights=edge_weights, lam=0.01
)
Gc.plot()
P.solve(solver="scipy", verbosity=1)
===============================================================================
CVXPY
v1.6.5
===============================================================================
(CVXPY) May 07 02:05:23 PM: Your problem has 51 variables, 126 constraints, and 0 parameters.
(CVXPY) May 07 02:05:23 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) May 07 02:05:23 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) May 07 02:05:23 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
(CVXPY) May 07 02:05:23 PM: Your problem is compiled with the CPP canonicalization backend.
-------------------------------------------------------------------------------
Compilation
-------------------------------------------------------------------------------
(CVXPY) May 07 02:05:23 PM: Compiling problem (target solver=SCIPY).
(CVXPY) May 07 02:05:23 PM: Reduction chain: Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> SCIPY
(CVXPY) May 07 02:05:23 PM: Applying reduction Dcp2Cone
(CVXPY) May 07 02:05:23 PM: Applying reduction CvxAttr2Constr
(CVXPY) May 07 02:05:23 PM: Applying reduction ConeMatrixStuffing
(CVXPY) May 07 02:05:23 PM: Applying reduction SCIPY
(CVXPY) May 07 02:05:23 PM: Finished problem compilation (took 1.130e-02 seconds).
-------------------------------------------------------------------------------
Numerical solver
-------------------------------------------------------------------------------
(CVXPY) May 07 02:05:23 PM: Invoking solver SCIPY to obtain a solution.
Solver terminated with message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
-------------------------------------------------------------------------------
Summary
-------------------------------------------------------------------------------
(CVXPY) May 07 02:05:23 PM: Problem status: optimal
(CVXPY) May 07 02:05:23 PM: Optimal value: 3.705e+01
(CVXPY) May 07 02:05:23 PM: Compilation took 1.130e-02 seconds
(CVXPY) May 07 02:05:23 PM: Solver (including time spent in interface) took 4.096e-03 seconds
Problem(Minimize(Expression(AFFINE, UNKNOWN, ())), [Inequality(Constant(CONSTANT, ZERO, (17, 2))), Inequality(Variable((17, 2), _flow)), Equality(Expression(AFFINE, UNKNOWN, (8, 2)), Constant(CONSTANT, ZERO, ())), Equality(Expression(AFFINE, UNKNOWN, (2,)), Constant(CONSTANT, NONNEGATIVE, ())), Equality(Expression(AFFINE, UNKNOWN, (2,)), Constant(CONSTANT, NONNEGATIVE, ())), Equality(Expression(AFFINE, UNKNOWN, (2,)), Constant(CONSTANT, NONNEGATIVE, ())), Equality(Expression(AFFINE, UNKNOWN, (2,)), Constant(CONSTANT, NONNEGATIVE, ())), Inequality(Expression(AFFINE, UNKNOWN, (17,))), Inequality(Variable((17,), active_edge, boolean=True))])
# We obtain the same optimal cost for each shortest path, but now we identified a shortest path that is common to both samples
P.objectives[0].value, P.objectives[1].value, P.objectives[2].value
(np.float64(15.0), np.float64(22.0), np.float64(5.0))
# Even though flow is continuous, we have discrete values which indicate the shortest paths.
P.expr.flow.value
array([[ 1., 1.],
[-0., -0.],
[-0., -0.],
[-0., -0.],
[ 1., 1.],
[ 0., 0.],
[-0., -0.],
[-0., -0.],
[-0., -0.],
[-0., -0.],
[ 1., 1.],
[-0., 0.],
[-0., -0.],
[-0., -0.],
[-0., -0.],
[ 1., 1.],
[ 1., 1.]])
import numpy as np
sum(np.sum(P.expr.flow.value, axis=1) > 0)
np.int64(5)
Gc.edge_subgraph(np.flatnonzero(P.expr.flow.value[:, 0] > 0)).plot()
Gc.edge_subgraph(np.flatnonzero(P.expr.flow.value[:, 1] > 0)).plot()