Python LinProg实现不可中断电器调度约束的问题求助

我正在尝试为电器添加不可中断运行约束：启动后必须持续运行。该电器最早启动时间为10:00，最晚启动时间为20:00，运行时长为6小时。但运行现有代码后，得到的运行时段为10、11、13、14、15、16，出现中断，不符合持续运行至15点的预期。我试图添加“StartTime+Duration=Endtime”的约束，以下是待修正的代码：

for idx, appliance in enumerate(appliances):
   if appliance['continuous']:
        for i in range(appliance['time_min'], appliance['time_max'] - appliance['duration_time'] + 2):
        A_eq[idx, i + idx * 24: i + idx * 24 + appliance['duration_time']] = 1
        # Ensure continuity by adding the constraint that start + duration = end
        A_eq[idx, i + idx * 24 + appliance['duration_time'] - 1] = -1
   else:
    for i in range(appliance['time_min'], appliance['time_max'] - appliance['duration_time'] + 1):
        A_eq[idx, i + idx * 24: i + idx * 24 + appliance['duration_time']] = 1

问题核心 #

请问该需求是否可通过LinProg实现，还是属于MILP问题？

回答 #

• 这个需求**必须用MILP（混合整数线性规划）**实现，没法用仅支持连续变量的LinProg完成。
• 原因：不可中断运行的约束本质是要选择一个连续的时间窗口，这类问题得引入0-1整数变量标记电器是否在某个时间点启动，再通过整数变量关联后续时段的运行状态，确保一旦启动就连续跑满指定时长。
• 你现在试的线性约束（StartTime+Duration=Endtime）没法准确描述“连续运行”的逻辑——线性规划的连续变量会允许非整数解或者分段运行的情况，只有整数变量能强制“要么在某时刻启动并连续运行，要么不启动”的二选一规则。
• 给个简单的整数约束思路：
  1. 引入0-1变量x_t，表示电器在t时刻是否启动；
  2. 约束所有x_t的总和≤1，保证最多启动一次；
  3. 若x_t=1，则t到t+5这6个时段的运行变量必须全为1，强制连续运行；
  4. 约束所有时段运行变量的总和=6，保证总运行时长达标。

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