Как определить сложные целевые функции в or-tools?

Я хотел бы знать, как определить сложную целевую функцию с помощью или-инструментов (если это возможно).

В базовом примере ниже показано, как решить базовую линейную проблему с Or-tools в Python:

solver = pywraplp.Solver('lp_pricing_problem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

# Define variables with a range from 0 to 1000.
x = solver.NumVar(0, 1000, 'Variable_x')
y = solver.NumVar(0, 1000, 'Variable_y')

# Define some constraints.
solver.Add(x >= 17)
solver.Add(x <= 147)
solver.Add(y >= 61)
solver.Add(y <= 93)

# Minimize 0.5*x + 2*y
objective = solver.Objective()
objective.SetCoefficient(x, 0.5)
objective.SetCoefficient(y, 2)
objective.SetMinimization()

status = solver.Solve()

# Print the solution
if status == solver.OPTIMAL:
    print("x: {}, y: {}".format(x.solution_value(), y.solution_value())) # x: 17.0, y: 61.0

В этом очень простом примере целевая функция Minimize(0.5*x + 2*y). Каким будет синтаксис для получения, например, наименьших квадратов Minimize(x^2 + y^2) или абсолютного значения переменной Minimize(abs(x) + y)?

Можно ли определить подфункцию и вызвать ее в целевую функцию? Или мне пойти другим путем?

Спасибо заранее,

Ромен


python least-squares or-tools linear-programming objective-function
person Romain Capron    schedule 16.12.2019    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Вы пометили этот вопрос с помощью linear-programming, так что у вас уже есть ингредиенты, чтобы найти здесь ответ.

Если вы посетите эту страницу, то увидите, что OR-Tools решает <сильный > линейные программы, а также несколько других семейств задач оптимизации.

Итак, первая целевая функция, которую вы упомянули, Minimize(0.5*x + 2*y), разрешима, потому что она линейна.

Вторая цель, которую вы упомянули ---_ 3 _--- не может быть решена с помощью OR-Tools, потому что она нелинейна: эти квадратичные члены делают ее квадратичной. Чтобы решить эту проблему, вам нужно что-то, что умеет выполнять квадратичное программирование, программирование конуса второго порядка или квадратичное программирование с ограничениями. Все эти методы включают линейное программирование как подмножество. Для решения подобных проблем я рекомендую инструмент cvxpy, который предлагает мощный и элегантный интерфейс. (В качестве альтернативы вы можете аппроксимировать квадратичную как линейно-кусочную, но вы столкнетесь с гораздо большим количеством ограничений.)

Последняя цель, которую вы упомянули, Minimize(c*abs(x) + y) может быть решена как линейная программа, даже если сама abs(x) нелинейна. Для этого мы переписываем цель как min( c*(t1-t2) +y) и добавляем ограничения t1,t2>=0. Это работает, пока c положительно и вы минимизируете (или c отрицательно и вы максимизируете). Более подробное объяснение можно найти здесь.

Вы можете выполнить множество таких преобразований, и один из навыков математического программиста / исследователя операций - запомнить многие из них.

person Richard    schedule 16.12.2019
comment
Я думал, что инструменты OR можно использовать с Gurobi, который поддерживает квадратичные задачи. Это ограничение API OR-инструментов? - person Romain Capron; 16.12.2019
comment
@Stradivari: Хорошая находка! - person Richard; 16.12.2019
comment
Большое спасибо @Stradivari! Я проверю, как перейти на Гуроби в ближайшие недели. Мы уже думали об этом. Теперь это становится обязательным. - person Romain Capron; 17.12.2019
comment
@Romain: Я все равно предлагаю посмотреть cvxpy. Также он может разгрузиться в Гуроби и решить широкий круг задач. - person Richard; 17.12.2019