Google OR-Tools：求解包含多个变量的 max 函数的 objective 函数

Question

我的目标是优化一个包含多个变量的 max 函数的 objective 函数。鉴于 OR-Tools 似乎只有线性求解器并且 max 函数是非线性的，这是否可能？我从 this and this 中看到可以线性化约束或 objective 函数，但仅限于两个变量的情况。

# Build data model
data = {}
data['constraint_coeffs'] = [
    [1 for x in range(10)],
]
data['bounds'] = [100]
data['max_power'] = 500
data['demand_coeffs'] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
data['energy_coeffs'] = [1, 1, 1, 1, 2, 2, 2, 6, 6, 6]
data['num_vars'] = 10
data['num_constraints'] = len(data['constraint_coeffs'])

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')

# Set variables
x = {}
for j in range(data['num_vars']):
    x[j] = solver.NumVar(0, solver.infinity(), 'x[%i]' % j)

# Set energy constraint
for i in range(data['num_constraints']):
    constraint_expr = [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])]
    solver.Add(sum(constraint_expr) == data['bounds'][i])

# Set max power constraints
for j in range(data['num_vars']):
    solver.Add(x[j] <= data['max_power'])

这里是问题发生的地方：

obj_expr = [data['energy_coeffs'][j] * x[j] / 60 for j in range(data['num_vars']) + max(data['demand_coeffs'][j] * x[j] for j in range(data['num_vars']))]
solver.Minimize(solver.Sum(obj_expr))

status = solver.Solve()

这是错误消息：

ValueError                    Traceback (most recent call last)
<ipython-input-10-03aba3620a74> in <module>
----> 1 obj_expr = [data['energy_coeffs'][j] * x[j] / 60 for j in range(data['num_vars']) + max(data['demand_coeffs'][j] * x[j] for j in range(data['num_vars']))]

~/anaconda3/envs/.../lib/python3.7/site-packages/ortools/linear_solver/linear_solver_natural_api.py in __gt__(self, arg)
    152   def __gt__(self, arg):
    153     raise ValueError(
--> 154         'Operators "<" and ">" not supported with the linear solver')
    155 
    156   def __ne__(self, arg):

ValueError: Operators "<" and ">" not supported with the linear solver

Answer 1

是的，这在任何求解器中都是可能的。如果你想最小化一组值的最大值，你可以简单地引入一个新的虚拟变量并将它限制为大于集合中的每个值，然后在你的 objective 中使用该虚拟变量。所以在伪代码中：

Let:
c[i] = some indexed set of coefficients
x[i] = some indexed variable

Desire:
minimax (c[i]*x[i])

Introduce:
my_max = real valued variable, non-indexed

Make constraint
for i in I:
  my_max >= c[i]*x[i]

然后你可以在你的objective（最小化）函数中使用my_max（或者你怎么称呼它）而不是max()

Google OR-Tools：求解包含多个变量的 max 函数的 objective 函数

Google OR-Tools: Solving an objective function containing max function of multiple variables

python

linear-programming

nonlinear-optimization

or-tools