如何在or-tools中定义复杂的objective函数？

Question

我想知道如何使用 or-tools（如果可能的话）定义一个复杂的 objective 函数。

下面的基本示例展示了如何在 python:

中使用 Or-tools 解决基本线性问题

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

在这个非常基本的示例中，objective 函数是 Minimize(0.5*x + 2*y)。例如，获取最小二乘 Minimize(x^2 + y^2) 或变量的绝对值 Minimize(abs(x) + y) 的语法是什么？

是否可以定义一个子函数并将其调用到objective函数中？还是我应该换个方式？

非常感谢，

罗曼

Answer 1

你已经用 linear-programming 标记了这个问题，所以你已经具备了在这里找出答案的要素。

如果您查看 this page，您会发现 OR-Tools 解决了线性程序，以及少数其他优化问题系列。

所以你提到的第一个 objective 函数，Minimize(0.5*x + 2*y) 是可解的，因为它是线性的。

您提到的第二个 objective---Minimize(x^2 + y^2)---无法用 OR-Tools 求解，因为它是非线性的：那些平方项使它成为二次项。为了解决这个问题，你需要一些可以做 quadratic programming, second-order cone programming, or quadratically constrained quadratic programming. All of these methods include linear programming as a subset. The tool I recommend for solving these sorts of problems is cvxpy 的东西，它提供了一个强大而优雅的界面。（或者，您可以将二次近似为线性分段，但您将招致更多约束。）

你提到的最后一个 objective，Minimize(c*abs(x) + y) 可以作为线性程序求解，即使 abs(x) 本身是非线性的。为此，我们将 objective 重写为 min( c*(t1-t2) +y) 并添加约束 t1,t2>=0。只要 c 为正并且您正在最小化（或者 c 为负并且您正在最大化），这就有效。更长的解释是 here.

您可以执行许多这样的变换，而数学 programmer/operations 研究人员的技能之一就是记住其中的许多变换。

如何在or-tools中定义复杂的objective函数？

How to define complex objective functions in or-tools?

python

linear-programming

least-squares

or-tools

objective-function