如何在pyomo中添加分段线性约束
How to add piece-wise linear constraint in pyomo
在任务分配问题中，我们假设：
我们需要分配4个任务到4天。
只有一名工人，每天最多工作8小时
我们想尽量减少总工作时间。
我们可以打包任务并在一天内节省时间。需要的小时数是
0 task --> 0 hours
1 task --> 6 hours
2 task --> 8 hours
# 任务 V.S 的插图。 # of Hours needed:
蓝色虚线：y = 6*n
黑线：实际时间=min(6*n, 6 + 2 * (n - 1))
红线：涨停板
这个计算函数（对于黑线）可以在Python中定义为
def compute_hours(n):
return min(6*n, 6 + 2 * (n - 1))
在约束设置中使用上面定义的函数，pyomo在我将其放入约束列表时出现错误。
> File "<ipython-input-69-57dbda13a71f>", line 23, in compute_hours
> return min(6*n, 6 + 2 * (n - 1)) File "pyomo\core\expr\logical_expr.pyx", line 183, in
> pyomo.core.expr.logical_expr.InequalityExpression.__bool__
> pyomo.common.errors.PyomoException: Cannot convert non-constant
> expression to bool. This error is usually caused by using an
> expression in a boolean context such as an if statement. For example,
> m.x = Var()
> if m.x <= 0:
> ... would cause this exception.
使用以下示例代码也很容易重现该错误：
# Allocating tasks to days
from pyomo.environ import *
import pandas as pd
m = ConcreteModel()
# We have 4 tasks in total. Each cost 6 hours
m.TASKS = ('task1', 'task2', 'task3', 'task4')
# There are 4 days to allocate to
m.DAYS = (1, 2, 3, 4)
# Hours per task
HOURS_PER_TASK = 6
def compute_hours(n):
return min(6*n, 6 + 2 * (n - 1))
# for x in range(0, 4):
# print(x, compute_hours(x))
# Create a decision array for the allocation
m.ALLOCATION = Var(m.TASKS, m.DAYS, domain=Binary)
# Create an array for total hours computation
m.TOTAL_HOURS = Var(m.DAYS, domain=Integers)
# minimize the number of days that are allocated tasks
m.OBJ = Objective(expr=sum([m.TOTAL_HOURS[day] for day in m.DAYS]), sense=minimize)
m.c = ConstraintList()
# One task is done once only in all days
for task in m.TASKS:
m.c.add(sum([m.ALLOCATION[task, day] for day in m.DAYS]) == 1)
# Compute Total hours a day
for day in m.DAYS:
m.c.add(sum([m.ALLOCATION[task, day] for task in m.TASKS])*HOURS_PER_TASK == m.TOTAL_HOURS[day])
# The following computation does not work
#m.c.add(compute_hours(sum([m.ALLOCATION[task, day] for task in m.TASKS])*HOURS_PER_TASK) == m.TOTAL_HOURS[day])
# Add max working hours per day
for day in m.DAYS:
m.c.add(m.TOTAL_HOURS[day] <= 8)
SolverFactory('glpk').solve(m).write()
# Show the results
SCHEDULE_df = pd.DataFrame(index = m.TASKS, columns= m.DAYS)
SCHEDULE_HOURS_df = pd.DataFrame(index = m.TASKS, columns= m.DAYS)
for i in m.TASKS:
for j in m.DAYS:
SCHEDULE_df.loc[i,j] = m.ALLOCATION[i,j]()
print('------------------------------------------')
print('ALLOCATION:')
print(SCHEDULE_df)
print('------------------------------------------')
print('Total hours per day:')
print(m.TOTAL_HOURS.get_values())
print('Total hours:')
print(value(m.OBJ))
如果我们假设每个任务总是需要 6 个小时，这个例子仍然可以给出结果。
------------------------------------------
ALLOCATION:
1 2 3 4
task1 1 0 0 0
task2 0 1 0 0
task3 0 0 1 0
task4 0 0 0 1
------------------------------------------
Total hours per day:
{1: 6.0, 2: 6.0, 3: 6.0, 4: 6.0}
Total hours:
24.0
如果我们能实现捆绑，那么这个工人只需要工作两天，工作量为 8hours/day（而不是工作量为 6hours/day 4 天）。
约翰.
Pyomo 得到了 Piecewise Linear Expression for these cases. (kernel layer also got the Piecewise Function Library)
在您的情况下，实际上很容易在 Pyomo 中使用 Piecewise。
您需要创建一个与 m.TOTAL_HOURS 具有相同索引的辅助变量（由 pyomo 请求），我们称它为 m.TASK_PER_DAY ，它将说明分配给的任务数每天。这个 TASK_PER_DAY var 然后将使用 m.ALLOCATION 每天使用任务总和来计算（约束）（类似于您尝试约束）。然后，您可以使用 pyomo Piecewise 根据 TASK_PER_DAY
计算 TOTAL_HOURS
编辑： 关于 pw_pts 和 f_rule 的进一步解释，它们是 Piecewise 中建模错误的来源。
pw_pts 是 Piecewise 中的断点（独立值，定义域）。 f_rule 是给定点 pw_pts 处的已知值。这可能是一个函数或几个点。如果你想线性插值点（如你的图像），你只需要定义这样的点 pw_pts=[0,1,2,3,...] 和 f_rule=[0,6,8,10,...]，但是对于 constant piecewise functions 你需要指定相同的点两次，以便确保对于域点，分段 returns 与阶跃函数中的值相同。在你的建模中，由于变量是integers，所以没有问题，但最好把问题弄清楚。
m.TASK_PER_DAY = Var(m.DAYS, domain=Integers)
m.PIECEWISE_DAILY_HOURS = Piecewise(
m.DAYS,
m.TOTAL_HOURS,
m.TASK_PER_DAY,
pw_pts=[0,1,2,3],
f_rule=[0,6,8,10],
pw_repn='SOS2',
pw_constr_type='EQ',
unbounded_domain_var=True
)
#Constraining TASK_PER_DAY
def Assign_Task(model, day):
return model.TASK_PER_DAY[day] == sum(model.ALLOCATION[task,day] for task in model.TASKS)
m.assign_task = Constraint(m.DAYS, rule=Assign_Task)
在这种方法中，您没有限制执行任务的日期，因此，分配的日期可以是任意一天，但每天肯定有 2 个任务。如果你想限制模型尽快（早期）执行任务，你需要添加新的约束。
以下代码可以重现所需的输出：
import pyomo.environ as pyo
m = pyo.ConcreteModel()
#Sets
# We have 4 tasks in total. Each cost 6 hours
m.TASKS = ('task1', 'task2', 'task3', 'task4')
# There are 4 days to allocate to
m.DAYS = (1, 2, 3, 4)
# Hours per task
HOURS_PER_TASK = 6
#Variables
# Create a decision array for the allocation
m.ALLOCATION = pyo.Var(m.TASKS, m.DAYS, domain=Binary)
m.TOTAL_HOURS = pyo.Var(m.DAYS, domain=Integers)
m.TASK_PER_DAY = pyo.Var(m.DAYS, domain=Integers)
#Piecewise
m.PIECEWISE_DAILY_HOURS = pyo.Piecewise(
m.DAYS,
m.TOTAL_HOURS,
m.TASK_PER_DAY,
pw_pts=[0,0,1,1,2,2,3,3],
f_rule=[0,0,6,6,8,8,10,10],
pw_repn='SOS2',
pw_constr_type='EQ',
unbounded_domain_var=True
)
#Objective
# minimize the number of days that are allocated tasks
m.OBJ = pyo.Objective(expr=sum([m.TOTAL_HOURS[day] for day in m.DAYS]), sense=minimize)
m.c = pyo.ConstraintList()
# One task is done once only in all days
for task in m.TASKS:
m.c.add(sum([m.ALLOCATION[task, day] for day in m.DAYS]) == 1)
#Compute the number of tasks per day
def Assign_Task(model, day):
return model.TASK_PER_DAY[day] == sum(model.ALLOCATION[task,day] for task in model.TASKS)
m.assign_task = pyo.Constraint(m.DAYS, rule=Assign_Task)
# Add max working hours per day
for day in m.DAYS:
m.c.add(m.TOTAL_HOURS[day] <= 8)
pyo.SolverFactory('gurobi').solve(m, tee=True)
然后解决方案减少到 16 小时。
>>>m.OBJ()
16.0
>>>m.TOTAL_HOURS.display()
TOTAL_HOURS : Size=4, Index=TOTAL_HOURS_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
1 : None : -0.0 : None : False : False : Integers
2 : None : 8.0 : None : False : False : Integers
3 : None : -0.0 : None : False : False : Integers
4 : None : 8.0 : None : False : False : Integers
>>>m.TASK_PER_DAY.display()
TASK_PER_DAY : Size=4, Index=TASK_PER_DAY_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
1 : None : 0.0 : None : False : False : Integers
2 : None : 2.0 : None : False : False : Integers
3 : None : 0.0 : None : False : False : Integers
4 : None : 2.0 : None : False : False : Integers
>>>m.ALLOCATION.display()
ALLOCATION : Size=16, Index=ALLOCATION_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
('task1', 1) : 0 : -0.0 : 1 : False : False : Binary
('task1', 2) : 0 : 1.0 : 1 : False : False : Binary
('task1', 3) : 0 : -0.0 : 1 : False : False : Binary
('task1', 4) : 0 : -0.0 : 1 : False : False : Binary
('task2', 1) : 0 : -0.0 : 1 : False : False : Binary
('task2', 2) : 0 : -0.0 : 1 : False : False : Binary
('task2', 3) : 0 : -0.0 : 1 : False : False : Binary
('task2', 4) : 0 : 1.0 : 1 : False : False : Binary
('task3', 1) : 0 : -0.0 : 1 : False : False : Binary
('task3', 2) : 0 : 1.0 : 1 : False : False : Binary
('task3', 3) : 0 : -0.0 : 1 : False : False : Binary
('task3', 4) : 0 : -0.0 : 1 : False : False : Binary
('task4', 1) : 0 : -0.0 : 1 : False : False : Binary
('task4', 2) : 0 : -0.0 : 1 : False : False : Binary
('task4', 3) : 0 : -0.0 : 1 : False : False : Binary
('task4', 4) : 0 : 1.0 : 1 : False : False : Binary
在任务分配问题中，我们假设：
我们需要分配4个任务到4天。
只有一名工人，每天最多工作8小时
我们想尽量减少总工作时间。
我们可以打包任务并在一天内节省时间。需要的小时数是
0 task --> 0 hours
1 task --> 6 hours
2 task --> 8 hours
# 任务 V.S 的插图。 # of Hours needed:
蓝色虚线：y = 6*n
黑线：实际时间=min(6*n, 6 + 2 * (n - 1))
红线：涨停板
这个计算函数（对于黑线）可以在Python中定义为
def compute_hours(n):
return min(6*n, 6 + 2 * (n - 1))
在约束设置中使用上面定义的函数，pyomo在我将其放入约束列表时出现错误。
> File "<ipython-input-69-57dbda13a71f>", line 23, in compute_hours
> return min(6*n, 6 + 2 * (n - 1)) File "pyomo\core\expr\logical_expr.pyx", line 183, in
> pyomo.core.expr.logical_expr.InequalityExpression.__bool__
> pyomo.common.errors.PyomoException: Cannot convert non-constant
> expression to bool. This error is usually caused by using an
> expression in a boolean context such as an if statement. For example,
> m.x = Var()
> if m.x <= 0:
> ... would cause this exception.
使用以下示例代码也很容易重现该错误：
# Allocating tasks to days
from pyomo.environ import *
import pandas as pd
m = ConcreteModel()
# We have 4 tasks in total. Each cost 6 hours
m.TASKS = ('task1', 'task2', 'task3', 'task4')
# There are 4 days to allocate to
m.DAYS = (1, 2, 3, 4)
# Hours per task
HOURS_PER_TASK = 6
def compute_hours(n):
return min(6*n, 6 + 2 * (n - 1))
# for x in range(0, 4):
# print(x, compute_hours(x))
# Create a decision array for the allocation
m.ALLOCATION = Var(m.TASKS, m.DAYS, domain=Binary)
# Create an array for total hours computation
m.TOTAL_HOURS = Var(m.DAYS, domain=Integers)
# minimize the number of days that are allocated tasks
m.OBJ = Objective(expr=sum([m.TOTAL_HOURS[day] for day in m.DAYS]), sense=minimize)
m.c = ConstraintList()
# One task is done once only in all days
for task in m.TASKS:
m.c.add(sum([m.ALLOCATION[task, day] for day in m.DAYS]) == 1)
# Compute Total hours a day
for day in m.DAYS:
m.c.add(sum([m.ALLOCATION[task, day] for task in m.TASKS])*HOURS_PER_TASK == m.TOTAL_HOURS[day])
# The following computation does not work
#m.c.add(compute_hours(sum([m.ALLOCATION[task, day] for task in m.TASKS])*HOURS_PER_TASK) == m.TOTAL_HOURS[day])
# Add max working hours per day
for day in m.DAYS:
m.c.add(m.TOTAL_HOURS[day] <= 8)
SolverFactory('glpk').solve(m).write()
# Show the results
SCHEDULE_df = pd.DataFrame(index = m.TASKS, columns= m.DAYS)
SCHEDULE_HOURS_df = pd.DataFrame(index = m.TASKS, columns= m.DAYS)
for i in m.TASKS:
for j in m.DAYS:
SCHEDULE_df.loc[i,j] = m.ALLOCATION[i,j]()
print('------------------------------------------')
print('ALLOCATION:')
print(SCHEDULE_df)
print('------------------------------------------')
print('Total hours per day:')
print(m.TOTAL_HOURS.get_values())
print('Total hours:')
print(value(m.OBJ))
如果我们假设每个任务总是需要 6 个小时，这个例子仍然可以给出结果。
------------------------------------------
ALLOCATION:
1 2 3 4
task1 1 0 0 0
task2 0 1 0 0
task3 0 0 1 0
task4 0 0 0 1
------------------------------------------
Total hours per day:
{1: 6.0, 2: 6.0, 3: 6.0, 4: 6.0}
Total hours:
24.0
如果我们能实现捆绑，那么这个工人只需要工作两天，工作量为 8hours/day（而不是工作量为 6hours/day 4 天）。
约翰.
Pyomo 得到了 Piecewise Linear Expression for these cases. (kernel layer also got the Piecewise Function Library)
在您的情况下，实际上很容易在 Pyomo 中使用 Piecewise。
您需要创建一个与 m.TOTAL_HOURS 具有相同索引的辅助变量（由 pyomo 请求），我们称它为 m.TASK_PER_DAY ，它将说明分配给的任务数每天。这个 TASK_PER_DAY var 然后将使用 m.ALLOCATION 每天使用任务总和来计算（约束）（类似于您尝试约束）。然后，您可以使用 pyomo Piecewise 根据 TASK_PER_DAY
TOTAL_HOURS
编辑： 关于 pw_pts 和 f_rule 的进一步解释，它们是 Piecewise 中建模错误的来源。
pw_pts 是 Piecewise 中的断点（独立值，定义域）。 f_rule 是给定点 pw_pts 处的已知值。这可能是一个函数或几个点。如果你想线性插值点（如你的图像），你只需要定义这样的点 pw_pts=[0,1,2,3,...] 和 f_rule=[0,6,8,10,...]，但是对于 constant piecewise functions 你需要指定相同的点两次，以便确保对于域点，分段 returns 与阶跃函数中的值相同。在你的建模中，由于变量是integers，所以没有问题，但最好把问题弄清楚。
m.TASK_PER_DAY = Var(m.DAYS, domain=Integers)
m.PIECEWISE_DAILY_HOURS = Piecewise(
m.DAYS,
m.TOTAL_HOURS,
m.TASK_PER_DAY,
pw_pts=[0,1,2,3],
f_rule=[0,6,8,10],
pw_repn='SOS2',
pw_constr_type='EQ',
unbounded_domain_var=True
)
#Constraining TASK_PER_DAY
def Assign_Task(model, day):
return model.TASK_PER_DAY[day] == sum(model.ALLOCATION[task,day] for task in model.TASKS)
m.assign_task = Constraint(m.DAYS, rule=Assign_Task)
在这种方法中，您没有限制执行任务的日期，因此，分配的日期可以是任意一天，但每天肯定有 2 个任务。如果你想限制模型尽快（早期）执行任务，你需要添加新的约束。
以下代码可以重现所需的输出：
import pyomo.environ as pyo
m = pyo.ConcreteModel()
#Sets
# We have 4 tasks in total. Each cost 6 hours
m.TASKS = ('task1', 'task2', 'task3', 'task4')
# There are 4 days to allocate to
m.DAYS = (1, 2, 3, 4)
# Hours per task
HOURS_PER_TASK = 6
#Variables
# Create a decision array for the allocation
m.ALLOCATION = pyo.Var(m.TASKS, m.DAYS, domain=Binary)
m.TOTAL_HOURS = pyo.Var(m.DAYS, domain=Integers)
m.TASK_PER_DAY = pyo.Var(m.DAYS, domain=Integers)
#Piecewise
m.PIECEWISE_DAILY_HOURS = pyo.Piecewise(
m.DAYS,
m.TOTAL_HOURS,
m.TASK_PER_DAY,
pw_pts=[0,0,1,1,2,2,3,3],
f_rule=[0,0,6,6,8,8,10,10],
pw_repn='SOS2',
pw_constr_type='EQ',
unbounded_domain_var=True
)
#Objective
# minimize the number of days that are allocated tasks
m.OBJ = pyo.Objective(expr=sum([m.TOTAL_HOURS[day] for day in m.DAYS]), sense=minimize)
m.c = pyo.ConstraintList()
# One task is done once only in all days
for task in m.TASKS:
m.c.add(sum([m.ALLOCATION[task, day] for day in m.DAYS]) == 1)
#Compute the number of tasks per day
def Assign_Task(model, day):
return model.TASK_PER_DAY[day] == sum(model.ALLOCATION[task,day] for task in model.TASKS)
m.assign_task = pyo.Constraint(m.DAYS, rule=Assign_Task)
# Add max working hours per day
for day in m.DAYS:
m.c.add(m.TOTAL_HOURS[day] <= 8)
pyo.SolverFactory('gurobi').solve(m, tee=True)
然后解决方案减少到 16 小时。
>>>m.OBJ()
16.0
>>>m.TOTAL_HOURS.display()
TOTAL_HOURS : Size=4, Index=TOTAL_HOURS_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
1 : None : -0.0 : None : False : False : Integers
2 : None : 8.0 : None : False : False : Integers
3 : None : -0.0 : None : False : False : Integers
4 : None : 8.0 : None : False : False : Integers
>>>m.TASK_PER_DAY.display()
TASK_PER_DAY : Size=4, Index=TASK_PER_DAY_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
1 : None : 0.0 : None : False : False : Integers
2 : None : 2.0 : None : False : False : Integers
3 : None : 0.0 : None : False : False : Integers
4 : None : 2.0 : None : False : False : Integers
>>>m.ALLOCATION.display()
ALLOCATION : Size=16, Index=ALLOCATION_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
('task1', 1) : 0 : -0.0 : 1 : False : False : Binary
('task1', 2) : 0 : 1.0 : 1 : False : False : Binary
('task1', 3) : 0 : -0.0 : 1 : False : False : Binary
('task1', 4) : 0 : -0.0 : 1 : False : False : Binary
('task2', 1) : 0 : -0.0 : 1 : False : False : Binary
('task2', 2) : 0 : -0.0 : 1 : False : False : Binary
('task2', 3) : 0 : -0.0 : 1 : False : False : Binary
('task2', 4) : 0 : 1.0 : 1 : False : False : Binary
('task3', 1) : 0 : -0.0 : 1 : False : False : Binary
('task3', 2) : 0 : 1.0 : 1 : False : False : Binary
('task3', 3) : 0 : -0.0 : 1 : False : False : Binary
('task3', 4) : 0 : -0.0 : 1 : False : False : Binary
('task4', 1) : 0 : -0.0 : 1 : False : False : Binary
('task4', 2) : 0 : -0.0 : 1 : False : False : Binary
('task4', 3) : 0 : -0.0 : 1 : False : False : Binary
('task4', 4) : 0 : 1.0 : 1 : False : False : Binary