Generieren Sie alle Pfade, die aus der festgelegten Anzahl von Besuchen von Knoten / Kanten bestehen ⇐ Python

[Anonymous]

In einer Grafik/Kette gibt es 3 verschiedene Zustände: ST , grc_i und grc_j .
Die folgenden Kanten zwischen den Zuständen existieren:

Code: Select all

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'),

]

Die Werte für tdl_i , tdl_i , rvl_i und rvl_j sind bekannt.
startet immer in ST und der endgültige Status ist immer Bekannt. Beispiel Wenn wir folgende Informationen haben: < /p>

Code: Select all

RVL_i = 2
RVL_j = 1
TDL_i = 0
TDL_j = 2
< /code>
und die endgültige Position ist grc_i < /code> Es gibt zwei Pfade, die diese Kriterien erfüllen: < /p>

[list]
[*] st -> tdl_j -> grc_j -> rvl_i -> grc_i -> rvl_j -> grc_j -> sul_i
-> st -> tdl_j -> grc_j -> rvl_i -> grc_i < /li < /li>
 st -> tdl_j -> grc_j -> sul_i -> st -> tdl_j -> grc_j -> rvl_i -> grc_i -> rvl_j -> grc_j ->
rvl_i -> grc_i < / li>
[/list]

Da beide Pfade implizieren, dass sul_i = 1 

und sul_j = 0 wir schließen, dass dies ist Der Fall. zu sul_i + sul_j + 1
[*] Die Anzahl der Besuche zu ggrc_i ist gleich TDL_I + RVL_I
< LI> Die Anzahl der Besuche in GRC_J entspricht TDL_J + RVL_J
[*] Die obere Bohrung von Sul_i ist die Anzahl der Besuche bei GRC_J
[*] Die obere Bound von sul_j ist die Anzahl der Besuche in GRC_I
[*] Die maximale Gesamtsumme Anzahl der Schritte ist 2 * (tdl_i + tdl_j + rvl_i + rvl_i)

Ich habe gedacht, dies als Mixed-In -teger-Programm zu lösen . < /p>

Code: Select all

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
< /code>
Wie kann ich auferlegen, dass die Aktions- und Zuständevariablen miteinander übereinstimmen? Beispielsweise kann die erste Aktion nur TDL_I 

oder tdl_j , da wir in ST . Aber wie soll ich das in das Modell einbeziehen?