如何在混合整数规划中关联状态与动作变量推导SUL参数？

我们有一个包含ST、GRC_i、GRC_j三种状态的有向图，边定义如下：

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

已知TDL_i、TDL_j、RVL_i、RVL_j的数值，状态链始终从ST出发，且最终状态已知，需推导SUL_i和SUL_j的值（例如给定特定参数与最终状态时，所有合法路径均指向SUL_i=1、SUL_j=0）。

目前已基于NetworkX与Gurobi构建混合整数规划模型，需解决两个核心问题：

1. 如何添加约束使状态变量与动作变量保持一致（如初始状态为ST时仅能执行TDL_i或TDL_j动作）
2. 如何将图的邻接矩阵融入模型

一、状态与动作变量的一致性约束 #

首先明确两类核心变量的定义：

• 状态变量：设x_{t,s}为0-1变量，表示第t步处于状态s（s可取ST、GRC_i、GRC_j）
• 动作变量：设y_{e}为0-1变量，表示是否执行边e对应的动作（e对应每条边的名称，如TDL_i）

具体约束规则 #

1. 初始状态固定：第一步必须处于ST，即：

   x_{1,ST} = 1
   x_{1,GRC_i} = 0
   x_{1,GRC_j} = 0
   

2. 动作仅能在对应状态执行：对于每条边(src, dst, name)，只有当当前步骤处于src状态时，才能执行该动作：

   y_{name} ≤ x_{t,src}
   

   其中t是执行该动作的步骤。比如初始步骤t=1时，x_{1,GRC_i}=x_{1,GRC_j}=0，所以RVL_i、RVL_j、SUL_i、SUL_j对应的y变量会被约束为0，自然只能执行TDL_i或TDL_j。
3. 动作触发对应的状态转移：执行某动作后，下一个步骤必须进入该边的目标状态：

   x_{t+1,dst} ≥ y_{name}
   

4. 状态完整性约束：
   • 每一步（除最终步骤）必须处于且仅处于一个状态：sum_{s} x_{t,s} = 1
   • 每一步（除最终步骤）必须执行且仅执行一个动作：sum_{e} y_e = 1
   • 处于状态s时，只能执行该状态的出边动作：sum_{e∈out_edges(s)} y_e = x_{t,s}
5. 最终状态约束：设最终步骤为T，已知最终状态为final_s，则：

   x_{T,final_s} = 1
   

二、邻接矩阵融入模型 #

步骤1：构建邻接矩阵 #

先将状态映射为整数索引，方便矩阵操作：

• ST → 0
• GRC_i → 1
• GRC_j → 2

根据给定边生成邻接矩阵A，其中A[src_idx][dst_idx] = 1表示存在从src到dst的边，否则为0：

A = [
    [0, 1, 1],  # ST的出边：GRC_i、GRC_j
    [0, 0, 1],  # GRC_i的出边：GRC_j
    [1, 1, 0]   # GRC_j的出边：ST、GRC_i
]

也可以用NetworkX直接生成：

import networkx as nx

G = nx.DiGraph()
for src, dst, name in EDGES:
    G.add_edge(src, dst, name=name)

# 生成邻接矩阵，转换为稠密矩阵便于操作
adj_matrix = nx.adjacency_matrix(G).todense()
# 状态与索引的映射可通过G.nodes()获取
state_to_idx = {s: i for i, s in enumerate(G.nodes())}

步骤2：用邻接矩阵强化约束 #

1. 合法状态转移约束：对于任意步骤t，下一个状态只能是当前状态邻接的状态，即：

   x_{t+1,dst} ≤ sum_{src} A[src_idx][dst_idx] * x_{t,src}
   

   确保只有邻接矩阵中存在的转移才能发生。
2. 动作合法性绑定：每条动作对应唯一的src和dst，利用邻接矩阵过滤非法动作：如果A[src_idx][dst_idx] = 0，则对应的动作变量y_e直接设为0，或者添加约束y_e = 0。
3. 批量生成约束：通过邻接矩阵的遍历，可以批量生成所有状态-动作关联约束，避免手动逐条添加，提升模型构建效率。例如遍历邻接矩阵的每个元素，若A[i][j] = 1，则找到对应的边动作e，添加y_e ≤ x_{t, state_i}和x_{t+1, state_j} ≥ y_e的约束。

内容的提问来源于stack exchange，提问作者HJA24