[Python] Generate all paths that consists of specified number of visits of nodes / edges

In a graph/chain there are 3 different states: ST, GRC_i and GRC_j. The following edges between the states exists:

EDGES = [
# source, target, name
('ST', 'GRC_i', 'TDL_i'),
('ST', 'GRC_j', 'TDL_j'),
('GRC_i', 'GRC_j', 'RVL_j'),
('GRC_j', 'GRC_i', 'RVL_i'),
('GRC_j', 'ST', 'SUL_i'),
('GRC_i', 'ST', 'SUL_j'),

]




The values for TDL_i, TDL_i, RVL_i and RVL_j are known. The chain always starts in ST and the final state is always known.

I want to infer SUL_i and SUL_j based on possible paths that satisfy the known information.

For example if we have the following information:

RVL_i = 2
RVL_j = 1
TDL_i = 0
TDL_j = 2


and the final position is GRC_i there are two paths that satisfy this criteria:

1. ST -> TDL_j -> GRC_j -> RVL_i -> GRC_i -> RVL_j -> GRC_j -> SUL_i -> ST -> TDL_j -> GRC_j -> RVL_i -> GRC_i
2. ST -> TDL_j -> GRC_j -> SUL_i -> ST -> TDL_j -> GRC_j -> RVL_i -> GRC_i -> RVL_j -> GRC_j -> RVL_i -> GRC_i

​

Because both paths imply that SUL_i = 1 and SUL_j = 0 we conclude that this is the case.

The following relationships are evident:

• The number of visits to ST is equal to SUL_i + SUL_j + 1
• The number of visits to GRC_i is equal to TDL_i + RVL_i
• The number of visits to GRC_j is equal to TDL_j + RVL_j
• The upper-bound of SUL_i is the number of visits to GRC_j
• The upper-bound of SUL_j is the number of visits to GRC_i
• The maximum total number of steps is 2 * (TDL_i + TDL_j + RVL_i + RVL_i)

I was thinking to solve this as a mixed-integer program.

import networkx as nx
import gurobipy as grb
from gurobipy import GRB
from typing import Literal


def get_SUL(TDL_i: int, TDL_j: int, RVL_i: int, RVL_j: int, final_state: Literal['ST', 'GRC_i', 'GRC_j']):
G = nx.DiGraph()

G.add_edges_from([
('ST', 'GRC_i'),
('ST', 'GRC_j'),
('GRC_i', 'GRC_j'),
('GRC_j', 'GRC_i'),
('GRC_j', 'ST'),
('GRC_i', 'ST')
])

n_actions = len(list(G.edges()))
n_states = len(list(G.nodes()))

min_N = TDL_i + TDL_j + RVL_i + RVL_i
max_N = 2 * (TDL_i + TDL_j + RVL_i + RVL_i)

for N in range(min_N, max_N + 1):
m = grb.Model()

SUL_i = m.addVar(lb=0, ub=TDL_j + RVL_j)
SUL_j = m.addVar(lb=0, ub=TDL_i + RVL_i)

# actions
actions = m.addMVar((n_actions, N), vtype=GRB.BINARY)

m.addConstr(actions[0,:].sum() == TDL_i)
m.addConstr(actions[1,:].sum() == TDL_j)
m.addConstr(actions[2,:].sum() == RVL_i)
m.addConstr(actions[3,:].sum() == RVL_j)
m.addConstr(actions[4,:].sum() == SUL_i)
m.addConstr(actions[5,:].sum() == SUL_j)

m.addConstrs(actions[:,n].sum() == 1 for n in range(N))

# states
states = m.addMVar((n_states, N), vtype=GRB.BINARY)

m.addConstr(states[0,:].sum() == SUL_i + SUL_j + 1)
m.addConstr(states[0,:].sum() == TDL_i + RVL_i)
m.addConstr(states[0,:].sum() == TDL_j + RVL_j)

m.addConstr(states[0,0] == 1)

if final_state == 'ST':
m.addConstr(states[0,-1] == 1)
m.addConstr(states[1,-1] == 0)
m.addConstr(states[2,-1] == 0)
elif final_state == 'GRC_i':
m.addConstr(states[0,-1] == 0)
m.addConstr(states[1,-1] == 1)
m.addConstr(states[2,-1] == 0)
else:
m.addConstr(states[0,-1] == 0)
m.addConstr(states[1,-1] == 0)
m.addConstr(states[2,-1] == 1)

m.addConstrs(actions[:,n].sum() == 1 for n in range(N))

# additional constraints


How do I impose that the action- and states variables are in agreement with each other? For example, the first action can only TDL_i or TDL_j because we start in ST. I can obtain the adjacency matrix using nx.to_numpy_array(G) but how should I incorporate this into the model?

Continue reading...