Quadratic objective term in Gurobi Python interface

alex sichwart Source

I am facing problems with quadratic objective terms. I have made up a very simple code in order to illustrate my intention.

Code explanation: we want to give candy to a girl. The girl's joy over receiving 1 candy (joy_per_candy) depends on the total number of candies she receives. The more candies we give her the less is her joy_per_candy. The objective is to maximize her total joy, which is a quadratic term:

total_joy = candies * joy_per_candy

In the case below 1 candy produces a joy_per_candy of 10; 10 candies produce a joy_per_candy of 0. Here is a joy curve. Simple mathematics reveal that the total_joy maximizes for candies = 5.

How can I resolve this?

    joy_curve = [(1,10),(10,0)]
    m = Model('candy')
    candies=m.addVar(ub=joy_curve[1][0])
    joy_per_candy=m.addVar(ub=joy_curve[0][1])
    m.update()
    total_joy=QuadExpr(candies*joy_per_candy)
    m.setObjective(total_joy,GRB.MAXIMIZE)
    m.optimize()

results:

Optimize a model with 0 rows, 2 columns and 0 nonzeros.

Model has 1 quadratic objective term

Matrix range [0e+00, 0e+00]

Objective range [0e+00, 0e+00]

Bounds range [3e+00, 1e+01]

RHS range [0e+00, 0e+00]

Presolve time: 0.00s

GurobiError

mathematical-optimizationgurobi

Answers

answered 3 years ago GrayOnGray #1

The issue is mostly in your specification of the model.

You should start by writing out, on paper, the mathematical expression for your objective. Your joy curve is most naturally interpreted as a specification of coefficients, not a decision variable. You have used it to specify the marginal (i.e. additional) joy per candy. Your objective is the total joy as a function of number of candies. That's a sum or integral over the marginal joy function.

You're trying to write out the expression for total joy as linear in candies for a given joy per candy, i.e. bilinear in joy per candy and number of candies. There is no such expression for the total joy, since the joy per candy is changing as a function of number of candies, and you don't get to choose the joy per candy in your model anyway.

So taking your joy curve at face value and integrating it, your objective should be

(100/9)*(candies - 1) - (5/9)*(candies^2 - 1).

It's a little weird, because the slope of the marginal benefit curve (joy curve) is -10/9. So you would set the objective as:

m.setObjective((100/9)*(candies - 1) - (5/9)*(candies * candies - 1),GRB.MAXIMIZE)

comments powered by Disqus