INFEASIBILITY CERTIFICATION

回答済み

María Ciudad Alañón

• 2022年03月29日 14:56

Hi!

I have a bilinear problem with bilinear constraints, i.e. a non convex problem. I solved it with Gurobi but for my results I need to know something: when Gurobi outputs that the problem is infeasible, is there any way to certify that a small ball around an infeasible point is also infeasible?

Thank you!

0

• 

  Jaromił Najman

  Gurobi Staff

  • 2022年03月30日 08:10

  Hi María,

  Could you elaborate a bit more on what exactly you need?

  When you try to solve an infeasible nonconvex problem with a spatial branch-and-bound algorithm, the algorithm at some point proves that there is no point in the defined variable bounds, which fulfills all given constraints. You will not get any infeasible point back from Gurobi, because all points in the given variable bounds are infeasible. Thus, there is always a small ball around an infeasible point that is also infeasible. If this would not be the case, then there would be a feasible point in the defined domain contradicting the infeasibility proof.

  Note that there are numerically troublesome corner cases where a model can be declared infeasible despite being feasible and vice versa. This is most often the result of computational tolerances and a badly scaled model. See Guidelines for Numerical Issues for more insights.

  Best regards, 
  Jaromił

  0

サインインしてコメントを残してください。