How to test if a feasible solution is optimal

Answered

Jack Keefer

• September 08, 2023 22:18

I wanted to know if it was possible to use Gurobi to test if a feasible solution is the optimal solution to a nonlinear binary programming problem. Is it possible to have Gurobi use the solution I provide as the starting point, then search for a better solution and end/inform me if any better solution is found?

 

In my setting, fully optimizing the problem each time would be far too computationally intensive and unnecessary, so simply receiving an answer if any better solution exists would be enough for me. Is there a way I can set up Gurobi to do this? Any resources on this topic (for Gurobi or theoretical) would be appreciated! 

 

The following is not necessary for answering my question but is additional context: I am trying to find parameter values such that the observed solution in my data solves a cooperative game, given those parameter values (i.e. inverse optimization). Specifically, individuals get a value from participating. Then if they participate, they can make a choice and receive value that depends on the choices of other individuals participating (and the individual's choice similarly affects those other players too). I can observe everything except the fixed value they receive from participating that is not affected by other players. I believe I can make an educated guess of these values and then check if they are correct, hence my request on Gurobi. 

 

Thanks for any help!

Related to

• Solutions
• Nonlinear

0

• 

  Riley Clement

  Gurobi Staff

  • September 11, 2023 07:26

  Hi Jack,
  
  You can certainly provide Gurobi with a feasible solution (aka MIP start), although there is no guarantee that Gurobi will use it.  In determining whether your feasible solution is an optimal solution there are two possible answers: "yes" and "no".  

  An answer of "no" is given whenever a better solution is found.  An answer of "yes" can only be given when the gap between the dual bound and the objective of your feasible solution is reduced to zero - and this is "fully optimizing" as you put it, and may be time consuming depending on the strength of your model.

  One approach you could use to reduce time for a "no" answer is to manually calculate the objective of your feasible solution then use the BestObjStop parameter, with a value a tiny bit better than your feasible solution objective, to terminate the solve as soon as a better solution is found.

  - Riley

  0

Please sign in to leave a comment.