How bad are quadratic constraints?

Answered

Florian Speicher

• September 25, 2024 10:35
• Edited

Hallo,

I was studying mathematics in OR some time ago. When I was doing so, I learned a "hierachy" of complexity for problems, meaning that the running time for solving those problems increase.

In particular I learned that 

min c^t*x where Ax =b and x may contain integer constraints is much "easier" as

min x^tQx where Ax=b and x may contain integer constraints.

Or in other words optimizing a linear function with linear and integer constraints is way easier than minimizing a quadratic (convex) function with linear integer constraints.

Now I use gurobi for some time and follow your documentation. I am not sure anymore if my "information" is still valid. So my question is now, 

Has gurobi a harder time to optimize a quadratic (convex) function with linear and integer constraints  than minimizing a linear function with linear integer constraints? Or is my knowledge outdated?

Background is that I have a large MILP  (~1e6-1e7 constraints/variables) which does what it should but could be more "precise" if I allow some quadratic terms in the objective. Not in the constraints though.

Also the problem size would decrease if I allow quadratic expressions. It would be some work however to rewrite it accordingly. So before doing so I would ask for some experience if can be worthwile doing so or if it is a waste of time as quadratic objectives lead to significantly longer computing time.

A last comment. My problems are generally hard. Meaning that gurobi mostly finds new solutions via the heuristics.

Thanks,

Florian

Related to

• MIQP

0

• 

  Maliheh Aramon

  Gurobi Staff

  • September 25, 2024 19:36

  Hi Florian, 

  Whether an MILP instance is easier to solve than an MIQP instance (quadratic objective with linear constraints) depends on several factors that are difficult to predict in advance. The best way to determine which formulation works better is to experiment with both. The consensus in the optimization community is that MILP instances are typically easier to solve than MIQP instances but there might be exceptions.

  Gurobi is highly capable of solving convex MIQP instances. If reformulating your problem as an MIQP reduces its size, this could result in a smaller and stronger presolved model. Therefore, if you are unsatisfied with the performance of your MILP formulation, we suggest considering a reformulation as an MIQP and testing it for comparison.

  Best regards,

  Maliheh

  0

Please sign in to leave a comment.