How to define complex objective functions in or-tools?

Question

I would like to know how to define a complex objective function using or-tools (if it is possible).

The basic example below shows how to have basic linear problem with Or-tools in 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 

In this very basic example the objective function is Minimize(0.5*x + 2*y). What would be the syntax to obtain, for example, the least squares Minimize(x^2 + y^2) or the absolute value of a variable Minimize(abs(x) + y)?

Is it possible to define a sub-function and call it into the objective function? Or should I proceed another way?

Many thanks in advance,

Romain

Pit

Answer 1

You've tagged this question with linear-programming, so you already have the ingredients to figure out the answer here.

If you check out this page, you'll see that OR-Tools solves linear programs, as well as few other families of optimization problems.

So the first objective function you mention, Minimize(0.5*x + 2*y) is solvable because it is linear.

The second objective you mention---Minimize(x^2 + y^2)---cannot be solved with OR-Tools because it is nonlinear: those squared terms make it quadratic. To solve this problem you need something that can do 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, which offers a powerful and elegant interface. (Alternatively, you can approximate the quadratic as linear-piecewise, but you will incur many more constraints.)

The last objective you mention, Minimize(c*abs(x) + y) can be solved as a linear program even though abs(x) itself is nonlinear. To do so, we rewrite the objective as min( c*(t1-t2) +y) and add the constraints t1,t2>=0. This works as long as c is positive and you are minimizing (or c is negative and you are maximizing). A longer explanation is here.

There are many such transformations you can perform and one of the skills of a mathematical programmer/operations researcher is to have many of them memorized.

Edo

I thought that OR-tools could be used with Gurobi that supports quadratic problems. Is it a limitation of the API of OR-tools? – Pit

@Stradivari: Good find! – Edo

Thanks a lot @Stradivari! I will check how to switch to Gurobi in the coming weeks. We were already thinking about using it. Now, it becomes mandatory. – Pit

@Romain: I'd still suggest looking at cvxpy. It can also offload to Gurobi and solve a wide range of problems. – Edo