Блог

Главная - Вопросы по программированию - Google ИЛИ-Инструменты: Решение целевой функции, содержащей максимальную функцию нескольких переменных

Google ИЛИ-Инструменты: Решение целевой функции, содержащей максимальную функцию нескольких переменных

#python #linear-programming #nonlinear-optimization #or-tools

Вопрос:

Я стремлюсь оптимизировать целевую функцию, которая включает в себя max функцию нескольких переменных. Возможно ли это с помощью инструментов ИЛИ, учитывая, что, по-видимому, у него есть только линейные решатели, а max функция нелинейна? Я видел из этого и этого, что можно линеаризовать ограничения или целевые функции, но только в случае двух переменных.

 # 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

Ответ №1:

Да, это возможно в любом решателе. Если вы хотите минимизировать максимум набора значений, вы можете просто ввести новую фиктивную переменную и ограничить ее величиной, превышающей каждое из значений в наборе, а затем использовать эту фиктивную переменную в своей цели. Итак, в псевдокоде:

 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]

Затем вы можете использовать my_max (или как вы это называете) в своей целевой функции (минимизации) вместо max()

Комментарии:

1. Спасибо! Звучит очевидно теперь, когда вы упомянули об этом. Один из вариантов этого — возможно ли, чтобы решатель нашел максимальное значение x[i] для всех i, тогда целевая функция должна быть c[i] * x[i] для этого индекса i?

2. Это значительно сложнее, поскольку предлагаемая конструкция слепа к индексу i max.

Метки: ,