如何在开源求解器中表达分段线性函数

问题描述 投票：0回答：3

在我的优化问题中，单位成本随距离（而不是距离桶）而变化。举个例子：

from to unit_cost total_cost_from total_cost_to
[[0, 174, 25, 0, 4350],
 [174, 281, 27, 4350, 7239],
 [281, 398, 29, 7239, 10632],
 [398, 533, 31, 10632, 14817],
 [533, 636, 32, 14817, 18113]]

因此，对于 174 到 281 单位距离，单位成本 = 27

因此，如果在最优解中，距离取值为 180，则 

total cost =  174*25 + (180-174)*27 = 4512

我知道许多商业求解器已将分段功能合并到其 API 中，但我如何通过开源求解器实现相同的功能

python linear-programming mixed-integer-programming
3个回答
1
投票

是的，我们可以在开源求解器中制定分段线性函数。我们将引入额外的变量，一个变量对应函数中的每个断点。假设我们有 

n
括号，从概念上讲，我们将这些变量视为括号边界上的权重，告诉我们在括号中的位置。我们希望最多有两个连续变量非零，且它们的总和为一。

这将告诉我们 x 位于何处，从而告诉我们目标函数值是多少。

以下是 Google-ortool 线性求解器中的公式。

from ortools.linear_solver import pywraplp

data = [
    [0, 174, 25, 0, 4350],
    [174, 281, 27, 4350, 7239],
    [281, 398, 29, 7239, 10632],
    [398, 533, 31, 10632, 14817],
    [533, 636, 32, 14817, 18113],
]

s = pywraplp.Solver("", pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
n = len(data)

# this is the final quantity selected
x = s.NumVar(data[0][0], data[n - 1][0], "x")

# introduce additional variables, one for each break-point in the function
# weights on the bracket boundaries, telling us where we are in the bracket
w = [s.NumVar(0, 1, "w[%i]" % (i,)) for i in range(n)]

# z is the set of binary variables whose only purpose is to
# enforce the SOS2 conditions over w's
z = [s.BoolVar("") for i in range(n)]

# We want the sum of the w's to be one
s.Add(1 == sum(w[i] for i in range(n)))

# calculation of x weighted sum of across brackets
# if say, w2 = 0.25 and w3 = 0.75, then we know that we are in the third bracket,
# x = w2 * point2 + w3 * point3
s.Add(x == sum(w[i] * data[i][0] for i in range(n)))

# put a constraint to determine the value of x
# since we will minimise cost (later) x will be forced to 180
# in optimal solution
# challenge is to identify the correct pair of brackets where 145 will lie
s.Add(x >= 180)

# Below constraints enforce SOS2 condition
# SOS2 : at most two consecutive variables to be non-zero

# There exists an order, in other words the variables can be sorted along one of their attributes
# They are all positive and continuous
# At most 2 of them are non-zero
# The two variables have to be adjacent

# above conditions are translated into code below
for i in range(n):
    s.Add(w[i] <= z[i])

s.Add(sum(z[i] for i in range(n)) <= 2)

# only adjacent z's can attain a value of 1
z_sum = {}
for i in range(n - 2):
    z_sum[i] = s.IntVar(0, 2, "")
    s.Add(z_sum[i] == z[i] + z[i + 1])

z_sum_bool = {i: s.BoolVar("") for i in range(n - 2)}

for i in range(n - 2):
    s.Add(z_sum[i] >= -2 * (1 - z_sum_bool[i]) + 2)

s.Add(sum(z_sum_bool[i] for i in range(n - 2)) == 1)

# minimize cost
cost = s.Sum(w[i] * data[i][3] for i in range(n))
s.Minimize(cost)
s.Solve()
R = [w[i].SolutionValue() for i in range(n)]


w[I]
结果为 
[0.0, 0.94392523364486, 0.05607476635514003, 0.0, 0.0]

这意味着 180 距离位于 

second to third
括号内或 
174 - 281
之间。

s.Objective().Value()
= 
4512
只不过是
174*25 + (180-174)*27

0
投票

在 

PuLP
中，我们可以为每个间隔创建一个变量并相应地设置它们的界限： 数据：


breakpoints = [0, 174, 281, 398, 533, 636]
slopes = [25, 27, 29, 31, 32]

interval_lengths = [breakpoints[i+1] - breakpoints[i] for i in range(len(breakpoints)-1)]

型号：

from pulp import *

prob = LpProblem("PiecewiseLinearVariables", LpMinimize)
x=LpVariable('x', lowBound=180,upBound=180, cat='Continuous')
variables = {}

# Create a variable for each interval, set its bounds to the respective interval length
for i in range(0,len(interval_lengths)):
    segment = f"Segment_{i+1}"
    variables[segment] = LpVariable(segment, lowBound=0,upBound=interval_lengths[i], cat='Continuous')
#Force the segments to take on values
prob += x==lpSum(var for var in variables.values())
#Add the weighted cost to the objective
prob + = lpSum(slope * var for var, slope in zip(variables.values(), slopes))

prob.solve()

解决方案：

for var in variables.values():
    print(f"{var.name}: {var.varValue}")
print(f"x: {value(x)}")

输出：

Optimal - objective value 4512 # From model.solve() output
Segment_1: 174.0
Segment_2: 6.0
Segment_3: 0.0
Segment_4: 0.0
Segment_5: 0.0
x: 180.0

不需要 SOS 或二进制变量，这通常会产生更简单的模型。

0
投票

对于许多类别的问题（您尚未指定），不需要二进制赋值变量 - @SebastianWozny 已经认识到这一点，但理解为什么很重要。

您的增量成本单调增加。对于成本最小化问题，本质上它总是先填充下层桶，然后再填充上层桶。如果您的增量成本发生变化，使其不再单调，那么这将不起作用。同样，如果出于某种原因您想要最大化预算支出，这也是行不通的。

简化列的总成本和列的总成本。另外，还不清楚为什么应该有一个最终的最大距离：最后一行的增量价格不应该适用于它上面的所有距离吗？

import numpy as np
import pandas as pd
import pulp

df = pd.DataFrame(
    [
        [  0, 25],
        [174, 27],
        [281, 29],
        [398, 31],
        [533, 32],
    ],
    columns=['from', 'unit_cost'],
)


def make_distance(row: pd.Series) -> pulp.LpVariable:
    return pulp.LpVariable(
        name=f'distance_{row.name}',
        lowBound=0,
        upBound=row.dist_range if np.isfinite(row.dist_range) else None,
    )

df['dist_range'] = df['from'].diff().shift(-1, fill_value=np.inf)
df['distance'] = df.apply(make_distance, axis=1)

distance = df.distance.sum()
cost = df.distance.dot(df.unit_cost)
prob = pulp.LpProblem(name='fixed_budget_max_distance', sense=pulp.LpMaximize)
prob.objective = distance + 0
prob.addConstraint(name='cost', constraint=cost <= 10e3)

print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
print('Can travel up to', distance.value(), 'at cost', cost.value())
print('Distance buckets:')
print(df.distance.apply(pulp.LpVariable.value))

fixed_budget_max_distance:
MAXIMIZE
1*distance_0 + 1*distance_1 + 1*distance_2 + 1*distance_3 + 1*distance_4 + 0
SUBJECT TO
cost: 25 distance_0 + 27 distance_1 + 29 distance_2 + 31 distance_3
 + 32 distance_4 <= 10000

VARIABLES
distance_0 <= 174 Continuous
distance_1 <= 107 Continuous
distance_2 <= 117 Continuous
distance_3 <= 135 Continuous
distance_4 Continuous

Optimal - objective value 376.2069
Optimal objective 376.2068966 - 3 iterations time 0.002
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

Can travel up to 376.206897 at cost 10000.000013
Distance buckets:
0    174.000000
1    107.000000
2     95.206897
3      0.000000
4      0.000000
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.