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:

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 write the following function:

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 be TDL_i or TDL_j because we start in ST. Similar, if the chain ends in ST, the last action must be either SUL_i or SUL_j.

Your help is much appreciated

Ronald van der Velden

Gurobi Staff

February 12, 2025 06:43

Hi Huib,

You could add two sets of constraints for each (node, i) combination:

Incoming: The sum of all actions[edge, i] that point towards node should equal states[node, i]
Outgoing: The sum of all actions[edge, i+1] that leave from node should equal states[node, i]

Kind regards,
Ronald

February 12, 2025 07:09

Just a few additional thoughts:

You can calculate SUL_i and SUL_j without generating paths. Their values only depend on the values of GRC_i, GRB_j, RVL_i, RVL_j and the desired end state.
Once you know these, your model knows the exact number of states, removing the need for min_N and max_N.
Generating all possible path can lead to an exponentially large number of solutions. You can try our solution pool feature. Are you really looking for all of them?

Huib Meulenbelt

February 14, 2025 18:00 Edited

Hi Ronald, thank you for your insights. I am mainly interested in finding the value of `SUL_i` and `SUL_j`.

You stated that its possible to retrieve these values without the paths. Is the following function correct

from typing import Literal, Tuple


def get_SUL(TDL_i: int, TDL_j: int, RVL_i: int, RVL_j: int, final_state: Literal['ST', 'GRC_i', 'GRC_j']) -> Tuple[int, int]:
    SUL_i = TDL_j + RVL_j - RVL_i
    SUL_j = TDL_i + RVL_i - RVL_j
    
    if final_state == 'GRC_i':
        SUL_j -= 1
    elif final_state == 'GRC_j':
        SUL_i -= 1
    else:
        pass
    
    return SUL_i, SUL_j

February 19, 2025 06:42

The approach is roughly what I had in mind. The best way to verify if it's 100% correct, would be by testing it on several datasets.

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

Comments

Didn't find what you were looking for?