Algorithms and solution methods to verify the solution from gurobi

Answered

Jose peeterson

• February 19, 2022 09:44
• Edited

I have the following objective function:

where is the only positive decision variable. is a function of . is equivalent to given in the equality constraint below. Other variables are positive constants except  a = -4.092*(10^-4), b = -2.167. c = 1.408*(10^-5), d = 6.130.

The plot of the objective function is shown below: y is and x is . The objective function value, is z.

We are minimizing a concave objective (continuous surface).

The constraints are given below:

We are minimizing this concave objective so it is a non-convex optimization problem.

What are the algorithms used in gurobi that will search for a solution with an objective of this form with sum of exponentials that are functions of a first order term (and with first order term multiplying one exponential term) then all of that multiplying a first order term? 

Are the solutions optimal or sub-optimal? I want to verify gurobi solution by implementing this algorithm. 

I have tried 2 pieces of 2nd order polynomials to estimate this surface in Gurobi but even then what algorithms or analytical techniques are used to find the minimum? But what if I want to keep it as accurate as possible by using this exact objective function? What are the analytical techniques then? When I use the exact objective function some solutions take longer to solve than others. 

Basically, I want to have a algorithm/technique so that I know what is happening when the solution is found. Then I will be able to compare this theoretical solution and Gurobi output. 

Please also refer me to any papers if possible.

Thanks.

0

• 

  Jaromił Najman

  Gurobi Staff

  • February 21, 2022 09:53
  • Edited

  For completeness, this post is connected to Different objective functions on different domains.

  What are the algorithms used in gurobi that will search for a solution with an objective of this form with sum of exponentials that are functions of a first order term (and with first order term multiplying one exponential term) then all of that multiplying a first order term?

  Gurobi does not work with nonlinear terms with the exception of square and bilinear terms. This means that each exponential term in your function has to be approximated via piecewise-linear functions and is then solved as a regular MIP. You can find great books and blogs on solving MIPs in Gurobi's Resources library. I guess that for you, the book Integer Programming by L. A. Wolsey should be a perfect fit.

  Are the solutions optimal or sub-optimal? I want to verify gurobi solution by implementing this algorithm. 

  All solutions found by Gurobi are globally optimal up to some specified optimality tolerance (MIPGap). Additionally, you have to consider the approximation error that comes into play when you approximate an exponential function by, e.g., a piecewise-linear function.

  I have tried 2 pieces of 2nd order polynomials to estimate this surface in Gurobi but even then what algorithms or analytical techniques are used to find the minimum?

  For nonconvex quadratic programs, Gurobi uses a so-called spatial Branch-and-Bound (B&B) algorithm. You can find a great description of the algorithm in the Global Optimization book by Horst & Tuy.

  But what if I want to keep it as accurate as possible by using this exact objective function? What are the analytical techniques then? When I use the exact objective function some solutions take longer to solve than others. 

  Gurobi currently does not support these nonlinear functions except for piecewise-linear approximations and appropriate reformulations.  If by exact objective function, you mean to actually directly work with the nonlinear functions such as \(\exp\) and \(\frac{x}{y}\), then you have to try a different solver, which supports nonlinear terms.
  In general, solvers which directly work with these nonlinear functions also use a spatial B&B algorithm of some sort. In addition to the Global Optimization book by Horst & Tuy, the book on Global Optimization by Locatelli & Schoen, Convexification by Tawarmalani & Sahinidis, and the Encyclopedia of Optimization by Floudas & Pardalos all give a great overview of the algorithms used for nonconvex optimization problems.
  It is expected that some techniques take longer than others because the problems solved are different ones, e.g., piecewise-linear approximation is a MIP, quadratic approximation is a nonconvex MIQCP, using \(\exp\) directly is a nonconvex (MI)NLP. One cannot state a priori which problem and which technique will perform best.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.