How was upper bound generated for non-linear, non-convex maximization optimization model?

Answered

Yifei Sun

• April 26, 2022 16:20
• Edited

I am currently running a maximization optimization model which is non-linear and non-convex. It has bilinear constraints and exponential constraints. I wonder how Gurobi generates the upper bound. I would really appreciate it if you can point me to some papers or documentation. Thanks!

0

• 

  Jaromił Najman

  Gurobi Staff

  • April 29, 2022 13:32
  • Edited

  Gurobi uses an interior point solver to search for feasible solutions of nonlinear nonconvex problems. One book about primal-dual interior methods can be found here. Interior point methods have are of big interest in the nonlinear nonconvex optimization community. One of the most popular nonlinear interior point solvers is the open-source solver IPOPT (not used by Gurobi).

  Once a solution is available, neighborhood search methods such as RINS are applied to try to improve the given solution point.

  Another way of finding feasible solutions for nonlinear nonconvex problems is through branching on continuous variables and checking the branching point or the LP relaxation solution point. This can sometimes be the best way of finding feasible solutions.

   

  0
• 

  Yifei Sun

  • May 01, 2022 14:38

  

  

  

  Hi Jaromil, 

  Thanks for your quick answer. This is very helpful! I also wonder how Gurobi calculates the provable upper bound (not the feasible solution) for the non-linear maximization problem. 

  Thanks,
  Yifei

  0
• 

  Jaromił Najman

  Gurobi Staff

  • May 02, 2022 07:49

  Hi Yifei,

  Gurobi uses a spatial branch-and-bound algorithm with an outer approximation approach. You can find more details in our webinar on non-convex features and tech talk through non-convex optimization.

  A good starting literature for nonlinear global optimization is Global Optimization by Horst & Tuy.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.