Gurobi providing nonoptimal and worse solution that a simple greedy algorithm for MIQCP problem?
Awaiting user inputHello,
I am writing as I'm trying to solve an MIQCP problem with Gurobi (it has the multiplication of three variables in the objective function, and some quadratic constraints).
The objective function looks like this:
min (x/y)*z
To avoid the division and having the multiplication between the three variables, I added two extra constraints, and two additional decision variables (k and j):
y*k=1 (so that k=1/y)
x*k=j (so that x/y = x*k = j)
and redefined the objective in a form like the following:
min j*z
On a small problem instance Gurobi returns within a few tens of seconds. However, it is providing a solution that is worse than a very simple greedy algorithm I developed.
Could it be that Gurobi is unable to find a solution for my nonlinear problem? Or does it always provides the optimum when it returns if no time limit is specified, and the issue should be searched in an error when I coded my problem?
In the first case, what can I do to try to force Gurobi to compute the optimum?
I tried setting "m.setParam('MIPGap',0)", but I get no difference whether I set or not this parameter.
Thanks a lot in advance!

Hi Francesco,
Perhaps Gurobi is running into numerical or convergence difficulties, it is hard to tell without reproducing it.
Can I suggest the alternative formulation to your problem:
min (x/y)*z
st. (x,y,z) \in DIntroduce a free variable p, and move the objective function into constraints:
min p
p >= (x/y)*z
st. (x,y,z) \in D, p freethen multiply through by y to get the final form:
min p
y*p >= x*z
st. (x,y,z) \in D, p freeThis formulation has less variables, and avoids equality constraints, so it may perform better. Can you give it a try and see if you still encounter an error?
It would also be useful to take your solution from the greedy algorithm, and use it to fix the variables in your problem, via lower and upper bounds, and optimize to see if the solution is accepted by Gurobi.
 Riley
0 
Additionally, have you had a chance to review the Knowledge Base article How do I diagnose a wrong result? There are a number of troubleshooting suggestions there that may help you. G
0
Please sign in to leave a comment.
Comments
2 comments