确保二进制向量中的所有正值在 PulP 优化期间彼此相邻

Question

我有一个调度优化问题，我需要根据优先级优化在给定时间范围内执行的活动。在下面的问题中，有足够的时间来执行所有活动，因此应该执行所有活动。

问题在于，优化是分解活动，而不是建议活动的整个持续时间一次性发生的时间表。

import pulp

# Define activities with durations, resource requirements, priorities, and parallel constraints
# Resources are per timeframe (ie, if every hour you need 1 machine, the value is 1 not 1*hours)
# priority is total
activities = {
    "Activity A": {
        "duration": 2,
        "resources": {"resource1": 1, "resource2": 1},
        "priority": 3,
    },
    "Activity B": {
        "duration": 3,
        "resources": {"resource1": 2, "resource2": 1},
        "priority": 2,
    },
    "Activity C": {
        "duration": 1,
        "resources": {"resource1": 1, "resource2": 2},
        "priority": 1,
    },
    "Activity D": {
        "duration": 2,
        "resources": {"resource1": 1, "resource2": 1},
        "priority": 4,
    },
}

for name, value in activities.items():
    activities[name]["priority"] = (
        activities[name]["priority"] / activities[name]["duration"]
    )

# Define the time horizon
time_horizon = 10

# Create a LP problem
problem = pulp.LpProblem("ScheduleOptimization", pulp.LpMaximize)

# Create binary variables for each activity and time slot
activity_vars = {}
for activity in activities:
    for t in range(time_horizon):
        activity_vars[(activity, t)] = pulp.LpVariable(
            f"{activity}_{t}", 0, 1, pulp.LpInteger
        )

# Create a variable to represent the total priority
total_priority = pulp.LpVariable("TotalPriority", cat=pulp.LpContinuous)

# Objective: Maximize the total priority
problem += total_priority

# Constraints
## Activities can run a maximum of their duration
for activity_name, activity in activities.items():
    problem += (
        pulp.lpSum(activity_vars[(activity_name, tt)] for tt in range(0, time_horizon))
        <= activity["duration"]
    )

# Update total_priority variable to reflect the actual total priority
problem += total_priority == pulp.lpSum(
    activity["priority"] * activity_vars[(activity_name, t)]
    for activity_name, activity in activities.items()
    for t in range(time_horizon)
)

# Solve the problem
problem.solve(pulp.PULP_CBC_CMD(msg=1))

# Print the schedule
schedule = {}
for activity_name in activities:
    for t in range(time_horizon):
        print(
            activity_vars[(activity_name, t)],
            "___",
            pulp.value(activity_vars[(activity_name, t)]),
        )
        if (
            pulp.value(activity_vars[(activity_name, t)]) == 1
            and schedule.get(activity_name) is None
        ):
            schedule[activity_name] = t

print("Optimal Schedule:")
for activity, start_time in schedule.items():
    print(f"{activity} starts at time {start_time}")
print(f"Total Priority: {pulp.value(total_priority)}")

我希望所有活动都像活动 B 一样，在其持续时间内开始和结束（即向量 [Activity_B_0 到 Activity_B_9] 中的所有 1 都在一起 -> [0,0,0,0,0,1,1, 1,0,0]

另一方面，如果活动 A 一次性发生，则尽管没有打破任何约束，但活动 A 仍会被分解。 [1,0,1, ...] 应该是 [1,1,0, ...]

下面是一个示例解决方案，其中变量 Activity_A_0 指的是活动 A 在时间 0 处处于活动状态。如果活动的持续时间为 2，则 Activit_A_x 的总和应 == 2。

Activity_A_0 ___ 1.0 #Not continuous
Activity_A_1 ___ 0.0 #Not continuous
Activity_A_2 ___ 1.0 #Not continuous
Activity_A_3 ___ 0.0
Activity_A_4 ___ 0.0
Activity_A_5 ___ 0.0
Activity_A_6 ___ 0.0
Activity_A_7 ___ 0.0
Activity_A_8 ___ 0.0
Activity_A_9 ___ 0.0
Activity_B_0 ___ 0.0
Activity_B_1 ___ 0.0
Activity_B_2 ___ 0.0
Activity_B_3 ___ 0.0
Activity_B_4 ___ 0.0
Activity_B_5 ___ 1.0 #Continuous
Activity_B_6 ___ 1.0 #Continuous
Activity_B_7 ___ 1.0 #Continuous
Activity_B_8 ___ 0.0
Activity_B_9 ___ 0.0
Activity_C_0 ___ 0.0
Activity_C_1 ___ 0.0
Activity_C_2 ___ 0.0
Activity_C_3 ___ 0.0
Activity_C_4 ___ 0.0
Activity_C_5 ___ 0.0
Activity_C_6 ___ 0.0
Activity_C_7 ___ 0.0
Activity_C_8 ___ 1.0
Activity_C_9 ___ 0.0
Activity_D_0 ___ 0.0
Activity_D_1 ___ 1.0 # Not Continuous
Activity_D_2 ___ 0.0 # Not Continuous
Activity_D_3 ___ 1.0 # Not Continuous
Activity_D_4 ___ 0.0
Activity_D_5 ___ 0.0
Activity_D_6 ___ 0.0
Activity_D_7 ___ 0.0
Activity_D_8 ___ 0.0
Activity_D_9 ___ 0.0

Answer 1

将所有因素放在一起的一个非常标准且经常使用的方法是限制模式

0 1

（初创企业）出现的次数。这可以用

建模

 s[t] >= x[t] - x[t-1] 
 sum(s[t]) <= 1
 x[t],s[t] binary