关于从pulp到gurobipy的线性规划问题的错误结果
问题描述 投票：0回答：1
这是我第一次在 Stack Overflow 上提问。 最近我尝试将 gurobipy 代码转换为纸浆并遇到一些问题。 数据资源：
- 员工列表及其可用工作时间和每小时工资：
- 规定在给定时间工作的最低员工数量（夜间需要较少的员工，高峰时段需要更多的员工）
（参考：https://blogs.mathworks.com/loren/2016/01/06/generate-an-optimal-employee-work-schedule-using-integer-线性-programming/）
目标：
- 尽量减少雇主必须支付的日工资总额。
限制：
- 在任何给定时间，您都必须满足最低人员配备要求。
- 一名员工每天只能工作一个班次。
- 员工必须在其可用时间内工作。
- 如果员工被要求值班，他们必须至少工作指定的最短时数，且不得超过指定的最长时数
原始gurobipy代码：
import gurobipy
# Create Data
EMPLOYEE, MIN, MAX, COST, START, END = gurobipy.multidict({
"SMITH" : [6, 8, 30, 6, 20], "JOHNSON": [6, 8, 50, 0, 24], 'WILLIAMS': [6, 8, 30, 0, 24],
'JONES' : [6, 8, 30, 0, 24], 'BROWN': [6, 8, 40, 0, 24], 'DAVIS': [6, 8, 50, 0, 24],
'MILLER' : [6, 8, 45, 6, 18], 'WILSON': [6, 8, 30, 0, 24], 'MOORE': [6, 8, 35, 0, 24],
'TAYLOR' : [6, 8, 40, 0, 24], 'ANDERSON': [2, 3, 60, 0, 6], 'THOMAS': [2, 4, 40, 0, 24],
'JACKSON' : [2, 4, 60, 8, 16], 'WHITE': [2, 6, 55, 0, 24], 'HARRIS': [2, 6, 45, 0, 24],
'MARTIN' : [2, 3, 40, 0, 24], 'THOMPSON': [2, 5, 50, 12, 24], 'GARCIA': [2, 4, 50, 0, 24],
'MARTINEZ': [2, 4, 40, 0, 24], 'ROBINSON': [2, 5, 50, 0, 24]})
REQUIRED = [1, 1, 2, 3, 6, 6, 7, 8, 9, 8, 8, 8, 7, 6, 6, 5, 5, 4, 4, 3, 2, 2, 2, 2]
MODEL = gurobipy.Model("Work Schedule")
# Create variable
x = MODEL.addVars(EMPLOYEE, range(24), range(1, 25), vtype=gurobipy.GRB.BINARY)
MODEL.update()
# Obj
MODEL.setObjective(gurobipy.quicksum((j - i) * x[d, i, j] * COST[d] for d in EMPLOYEE for i in range(24) for j in range(i + 1, 25)), sense=gurobipy.GRB.MINIMIZE)
# Constraints
MODEL.addConstrs(x.sum(d) <= (gurobipy.quicksum(x[d, i, j] for i in range(START[d], END[d] + 1) for j in range(i + 1, END[d] + 1) if MIN[d] <= j - i <= MAX[d])) for d in EMPLOYEE)
MODEL.addConstrs(gurobipy.quicksum(x[d, i, j] for i in range(START[d], END[d] + 1) for j in range(i + 1,END[d] + 1) if MIN[d] <= j - i <= MAX[d]) <= 1 for d in EMPLOYEE)
MODEL.addConstrs(gurobipy.quicksum(x[d, i, j] for d in EMPLOYEE for i in range(24) for j in range(i + 1, 25) if i <= c < j) >= REQUIRED[c] for c in range(24))
# Excute
MODEL.optimize()
我的纸浆代码：
# Create Data
# EMPLOYEE: 0)MIN, 1)MAX, 2)COST, 3)START, 4)END
md = {'SMITH':[6,8,30,6,20],'JOHNSON':[6,8,50,0,24],'WILLIAMS':[6,8,30,0,24],
'JONES':[6,8,30,0,24],'BROWN':[6,8,40,0,24],'DAVIS':[6,8,50,0,24],
'MILLER':[6,8,45,6,18],'WILSON':[6,8,30,0,24],'MOORE':[6,8,35,0,24],
'TAYLOR':[6,8,40,0,24],'ANDERSON':[2,3,60,0,6],'THOMAS':[2,4,40,0,24],
'JACKSON':[2,4,60,8,16],'WHITE':[2,6,55,0,24],'HARRIS':[2,6,45,0,24],
'MARTIN':[2,3,40,0,24],'THOMPSON':[2,5,50,12,24],'GARCIA':[2,4,50,0,24],
'MARTINEZ':[2,4,40,0,24],'ROBINSON':[2,5,50,0,24]}
REQUIRED = [1, 1, 2, 3, 6, 6, 7, 8, 9, 8, 8, 8, 7, 6, 6, 5, 5, 4, 4, 3, 2, 2, 2, 2]
MIN, MAX, COST, START, END = 0, 1, 2, 3, 4
t = 24
# Create Op
MODEL = pulp.LpProblem("Work Schedule", pulp.LpMinimize)
# Create variable
x = pulp.LpVariable.dicts("x", [(d, i, j) for d in md.keys() for i in range(t) for j in range(1, t+1)], cat=pulp.LpBinary)
# Create Obj
MODEL += pulp.lpSum((j - i) * x[d, i, j] * md[d][COST] for i in range(t) for j in range(i+1, t+1) for d in md.keys())
# Constraints
for c in range(len(REQUIRED)):
MODEL += pulp.lpSum(x[d, i, j] for d in md.keys() for i in range(t) for j in range(i+1, t+1) if i <= c < j) >= REQUIRED[c]
for k, v in md.items():
#print(k, v)
MODEL += pulp.lpSum(x[k, i, j] for i in range(v[START], v[END] + 1) for j in range(i + 1, v[END] + 1) if v[MIN] <= (j - i) <= v[MAX]) <= 1
MODEL += pulp.lpSum(x[k, i, j] for i in range(v[START], v[END] + 1) for j in range(i + 1, t + 1)) <= pulp.lpSum(x[k, i, j] for i in range(v[START], v[END] + 1) for j in range(i + 1, v[END] + 1) if v[MIN] <= (j - i) <= v[MAX])
MODEL.solve()
gurobipy代码结果为：
我的纸浆代码结果是：
显然，我的结果是不正确的，但是当我单独检查每个条件时，我找不到任何差异。有谁知道如何解决这一问题？非常感谢大家。
1个回答
0
投票
投票
我不相信这两种方法的结果，因为你忽略了
ANDERSONGALLERY我仍然不认为你应该拥有 O(n^2) 个变量。在没有额外维度的情况下，很容易将员工工时选择变量限制为连续的。
import pulp
import pandas as pd
md = pd.DataFrame(
columns=('EmployeeName', 'MinHours', 'MaxHours', 'HourlyWage', 'Start', 'End'),
data=[
( 'SMITH', 6, 8, 30, 6, 20),
( 'JOHNSON', 6, 8, 50, 0, 24),
('WILLIAMS', 6, 8, 30, 0, 24),
( 'JONES', 6, 8, 30, 0, 24),
( 'BROWN', 6, 8, 40, 0, 24),
( 'DAVIS', 6, 8, 50, 0, 24),
( 'MILLER', 6, 8, 45, 6, 18),
( 'WILSON', 6, 8, 30, 0, 24),
( 'MOORE', 6, 8, 35, 0, 24),
( 'TAYLOR', 6, 8, 40, 0, 24),
('ANDERSON', 2, 3, 60, 18, 24 + 6),
( 'THOMAS', 2, 4, 40, 0, 24),
( 'JACKSON', 2, 4, 60, 8, 16),
( 'WHITE', 2, 6, 55, 0, 24),
( 'HARRIS', 2, 6, 45, 0, 24),
( 'MARTIN', 2, 3, 40, 0, 24),
('THOMPSON', 2, 5, 50, 12, 24),
( 'GARCIA', 2, 4, 50, 0, 24),
('MARTINEZ', 2, 4, 40, 0, 24),
('ROBINSON', 2, 5, 50, 0, 24),
],
).set_index(keys='EmployeeName', drop=True).sort_index()
# Hourly staffing requirements, over 24 hours only
hour48 = pd.RangeIndex(name='Hour', start=0, stop=48)
required = pd.Series(
name='Required', index=hour48[:24],
data=(1, 1, 2, 3, 6, 6, 7, 8, 9, 8, 8, 8, 7, 6, 6, 5, 5, 4, 4, 3, 2, 2, 2, 2),
)
# Long-style employee-hour selection variables, multi-indexed by employee and hour
flat = pd.DataFrame(
data=pulp.LpVariable.matrix(name='sel', indices=(md.index, hour48), cat=pulp.LpBinary),
index=md.index, columns=hour48,
).stack()
flat.name = 'Select'
# For each employee and available hour, each selection variable beside the employee data
lp_vars = pd.merge(
left=md, right=flat, on='EmployeeName',
).set_index(flat.index)
hour_idx = lp_vars.index.get_level_values('Hour')
lp_vars = lp_vars[
(hour_idx >= lp_vars['Start']) &
(hour_idx < lp_vars['End'])
]
# The expense for each employee, as affine expressions
md['Duration'] = lp_vars['Select'].groupby('EmployeeName').agg(pulp.lpSum)
md['Expense'] = md['HourlyWage'] * md['Duration']
model = pulp.LpProblem(name='Work_Schedule', sense=pulp.LpMinimize)
model.setObjective(pulp.lpSum(md['Expense']))
for name, row in md.iterrows():
model.addConstraint(
name=f'hours_min_{name}',
constraint=row['Duration'] >= row['MinHours'],
)
model.addConstraint(
name=f'hours_max_{name}',
constraint=row['Duration'] <= row['MaxHours'],
)
hour_idx = lp_vars.index.get_level_values('Hour')
for hour, min_staff in required.items():
hour_vars = lp_vars[hour_idx % 24 == hour]
# For each hour (or the same hour in the next day), enforce minimum staff
model.addConstraint(
name=f'min_staff_{hour}',
constraint=pulp.lpSum(hour_vars['Select']) >= min_staff,
)
for name, selects in lp_vars['Select'].groupby('EmployeeName'):
selects = selects.droplevel('EmployeeName')
# At the beginning and end of the day, within the minimum number of working hours, the
# selector values are simply monotonic
employee = md.loc[name]
nmin = employee['MinHours']
for s0, s1 in zip(selects[:nmin-1], selects[1: nmin]):
model.addConstraint(s0 <= s1)
for s0, s1 in zip(selects[-nmin: -1], selects[1-nmin:]):
model.addConstraint(s0 >= s1)
# In the middle of the day, conditionally enforce monotonicity based on selection
M = 48
for i in range(nmin-1, selects.size-nmin):
model.addConstraint(
name=f'm_{name}_{selects.index[i]}',
constraint=M*selects.iloc[i] <=
M*(selects.iloc[i+1] + 1) -
pulp.lpSum(selects.iloc[i+2: 1-nmin]),
)
print(model)
model.solve()
if model.status != pulp.LpStatusOptimal:
raise ValueError(model.status)
md[['Duration', 'Expense']] = md[['Duration', 'Expense']].map(pulp.LpAffineExpression.value)
lp_vars['Select'] = lp_vars['Select'].map(pulp.LpVariable.value)
pd.options.display.width = 200
pd.options.display.max_columns = 99
print(md)
hours_total = lp_vars['Select'].groupby('Hour').sum()
next_day = hours_total[required.size:]
hours_total[:next_day.size] += next_day.values
print(pd.DataFrame({
'required': required,
'allocated': hours_total[:required.size],
}))
print(
lp_vars['Select']
.astype(int)
.unstack('Hour', fill_value=0)
.sort_index(axis=1)
)
Work_Schedule:
MINIMIZE
60*sel_ANDERSON_18 + 60*sel_ANDERSON_19 + ...
SUBJECT TO
hours_min_ANDERSON: sel_ANDERSON_18 + sel_ANDERSON_19 + sel_ANDERSON_20
+ sel_ANDERSON_21 + sel_ANDERSON_22 + sel_ANDERSON_23 + sel_ANDERSON_24
+ sel_ANDERSON_25 + sel_ANDERSON_26 + sel_ANDERSON_27 + sel_ANDERSON_28
+ sel_ANDERSON_29 >= 2
...
VARIABLES
0 <= sel_ANDERSON_18 <= 1 Integer
0 <= sel_ANDERSON_19 <= 1 Integer
0 <= sel_ANDERSON_20 <= 1 Integer
...
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
At line 2 NAME MODEL
At line 3 ROWS
At line 467 COLUMNS
At line 5951 RHS
At line 6414 BOUNDS
At line 6833 ENDATA
Problem MODEL has 462 rows, 418 columns and 4229 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Continuous objective value is 4700 - 0.01 seconds
...
Result - Optimal solution found
Objective value: 4700.00000000
...
MinHours MaxHours HourlyWage Start End Duration Expense
EmployeeName
ANDERSON 2 3 60 18 30 2.0 120.0
BROWN 6 8 40 0 24 8.0 320.0
DAVIS 6 8 50 0 24 8.0 400.0
GARCIA 2 4 50 0 24 4.0 200.0
HARRIS 2 6 45 0 24 6.0 270.0
JACKSON 2 4 60 8 16 2.0 120.0
JOHNSON 6 8 50 0 24 8.0 400.0
JONES 6 8 30 0 24 8.0 240.0
MARTIN 2 3 40 0 24 3.0 120.0
MARTINEZ 2 4 40 0 24 4.0 160.0
MILLER 6 8 45 6 18 8.0 360.0
MOORE 6 8 35 0 24 8.0 280.0
ROBINSON 2 5 50 0 24 3.0 150.0
SMITH 6 8 30 6 20 8.0 240.0
TAYLOR 6 8 40 0 24 8.0 320.0
THOMAS 2 4 40 0 24 4.0 160.0
THOMPSON 2 5 50 12 24 5.0 250.0
WHITE 2 6 55 0 24 2.0 110.0
WILLIAMS 6 8 30 0 24 8.0 240.0
WILSON 6 8 30 0 24 8.0 240.0
required allocated
Hour
0 1 1.0
1 1 1.0
2 2 2.0
3 3 3.0
4 6 6.0
5 6 6.0
6 7 7.0
7 8 8.0
8 9 9.0
9 8 8.0
10 8 8.0
11 8 8.0
12 7 7.0
13 6 6.0
14 6 6.0
15 5 5.0
16 5 5.0
17 4 4.0
18 4 4.0
19 3 3.0
20 2 2.0
21 2 2.0
22 2 2.0
23 2 2.0
Hour 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
EmployeeName
ANDERSON 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
BROWN 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0
DAVIS 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
GARCIA 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
HARRIS 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
JACKSON 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
JOHNSON 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
JONES 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
MARTIN 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
MARTINEZ 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
MILLER 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
MOORE 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
ROBINSON 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
SMITH 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
TAYLOR 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
THOMAS 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
THOMPSON 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
WHITE 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
WILLIAMS 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
WILSON 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
最新问题
- Java Path2D.Double 在 JPanel 上画有“尾巴”
- 子目录上的 Apache2 基本身份验证不提示身份验证
- 为什么在 Jupyter Notebook 中导入 pandas、numpy 和 seaborn 时出现 NameError: name "type_check" is not Defined？
- 如何在自动热键中暂停循环
- 从 URL 读取远程 txt 文件并将其按原样存储到 const char* [] 数组的 C++ 代码
- 如何在pixi js中显示精灵
- 修改反向代理的 apache 配置后不会强制使用 https
- getUid 只能从同一个库组内调用（groupId=com.google.firebase）[关闭]
- 使用拖动手势进行 SwiftUI 旋转
- 是否可以用if语句写单行return语句？
- 有参数时可能排名错误
- 如何获取 PydanticBaseSettingsSource 中的模型类型？
- 确定哪些页面文本框在多页上有文本
- 在 Android 应用程序中加载 Google 地图太慢
- 您的 WordPress 服务器似乎超载。 [盖茨比]
- 将 for 生成的序列结果插入到 clojurescript 中的FlexibleXYPlot中
- 通过 Powershell ReGex 从文本中提取字符串
- SQL 从备份数据库恢复单个表。列有时间戳，我必须使用 IDENTITY_INSERT
- Shiny 混合 R 和 Python 中的 Yolov8 CNN 模型
- Azure 函数 - .NET 剧作家
© www.soinside.com 2019 - 2024. All rights reserved.