Gurobi providing non-optimal and worse solution that a simple greedy algorithm for MIQCP problem?

Awaiting user input

Francesco Raviglione

• January 25, 2024 18:35

Hello,
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 non-linear 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!

Related to

• MIQCP
• Wrong Result

0

• 

  Riley Clement

  Gurobi Staff

  • January 26, 2024 04:07

  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 D

  Introduce a free variable p, and move the objective function into constraints:

  min p
  p >= (x/y)*z
  st. (x,y,z) \in D, p free

  then multiply through by y to get the final form:

  min p
  y*p >= x*z
  st. (x,y,z) \in D, p free

  This 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
• 

  Gwyneth Butera

  Gurobi Staff

  • January 29, 2024 11:23

  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.