5

I wonder if there are methods to determine the global optimum of MINLP problems, when the nonlinear functions involved are only of the form $Z = Y e^{- \alpha X}$, where $Y \ge 0$ and $X \ge 0$.

Are there any papers describing such an approach? Do these functions bear any characteristics that may be exploited?

Using logarithms I can rewrite the functions as $\log(Z) = \log(Y) - \alpha X$, but I don't think I am winning anything.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Clement
  • 2,252
  • 7
  • 13

3 Answers3

4

Assuming the continuous relaxation is convex you can most likely use conic optimization with the exponential cone. The Mosek modelling cookbook has the details.

Unsurprisingly Mosek can solve the mixed integer version of such problems.

ErlingMOSEK
  • 3,166
  • 10
  • 21
  • Presuming $X$ and $Y$ are both optimization variables (I submitted a comment requesting confirmation of that), then unless $\alpha = 0$, the function $Y\text{exp}(-\alpha X)$ is neither convex nor concave; therefore the resulting constraint would be non-convex, and Mosek would not be applicable. – Mark L. Stone Aug 20 '20 at 16:51
  • I am sorry, I hadn't checked the newer comments. Yes, X, Y are variables, α is a constant between 0 and 1.0. – Clement Aug 20 '20 at 17:22
4

This is a non-convex global optimisation problem. The state-of-the-art way to solve this is to use a factorable relaxation.

A key insight here is that $e^{-\alpha X}$ is convex (since your $\alpha$ is positive).

The methodology would be as follows:

  • Introduce a new auxiliary variable $w=e^{-\alpha X}$
  • You now have $Z=Yw$, and $w=e^{-\alpha X}$
  • Because both constraints are non-convex, you split each to two inequalities:

$Z\leq Yw, -Z\leq -Yw$

$ w\leq e^{-\alpha X}, -w\leq -e^{-\alpha X}$

The first set of inequalities can be convexified using a McCormick relaxation.

The second set of inequalities are convex and concave respectively. The convex inequality can be relaxed using an outer approximation, and the concave inequality using a secant.

You then plug your relaxed problem into a branch-and-bound algorithm and it will converge quadratically.

Note that this methodology is independent of the signs of $Z,Y,X$.

Alternatively, you can plug this into a global solver which will do all of this for you automatically. Couenne is an open-source choice, and if you are an academic/student you can also use SCIP or our own Octeract Engine for free.

Nikos Kazazakis
  • 12,121
  • 17
  • 59
  • BARON can also be used. If the problem has no more than 10 variables, 10 constraints, and 50 nonlinear operations, the free demo version of BARON can be used regardless of the status of the user. – Mark L. Stone Aug 20 '20 at 16:56
  • Nikos, yes the problem is a MINLP and I am aiming at getting the global optimum. I had a look at the manuals of different solvers. As far as I can tell, all of them can cope with exp(), log() terms. I hoped that they expoit something special about these function types when it comes to the solution of problems containing such terms. I tried BARON & COUENNE with small instances of the problem and both find the optimal solution. On larger instances they get lost in the B&B tree. I don't know how other solvers may behave, but I think, our problems should not be reduced to choose the right solver. – Clement Aug 20 '20 at 17:36
  • Nikos, you are writing: "You then plug your relaxed problem into a branch-and-bound algorithm ...". What do you mean by "plug into"? Is there an implementation of a B&B algorithm, which I can feed with my model? – Clement Aug 20 '20 at 17:45
  • @Clement One other B&B global solver you can try is YALMIP's BMIBNB. How well it works may depend on which local nonlinear solver you supply as its upper solver, as well as lower solver and LP solver. it's free, other than having to supply the local nonlinear solver and a MILP solver for it to call. If BARON and COUENNE don't do well, odds aren't good for BMIBNB, but you don';t know until you try. BTW, did you provide the maximum help to BARON by telling it what's convex convex - it might not figure it all out itself,- but if you claim a constraint convex and it''s not, solution may be wrong. – Mark L. Stone Aug 20 '20 at 20:43
  • @Clement Ok, a few different points here: (i) for BnB it depends on how much manual work you want to put into it. MINOTAUR is a great open source MINLP toolbox you could use for BnB, but you'll have to spend quite a bit of time to figure everything out. (ii) BARON and LINDO also work great for many problems, and (iii) Octeract Engine uses parallel BnB which is very helpful for larger problems, especially if you have decent computing power. It is also free for academics/students for problems of unlimited size, which is why I'm mentioning it as a viable alternative among the other free options. – Nikos Kazazakis Aug 21 '20 at 09:50
  • @Clement On a more philosophical note, you are right - our problems should not be reduced to choose the right solver. In practice however, solving these problems is immensely complicated. We are now I think well over 500,000 hours of development for our solver, with much more left to do - this is well beyond the scope of what a single person can do. More importantly, global optimisation is usually just too hard to be tackled at the formulation level. In practice we need algorithms that interact in very complicated ways at the solver level to make this stuff work. – Nikos Kazazakis Aug 21 '20 at 09:54
  • @Clement You may be interested to try LocalSolver (for free). Surprisingly, this is a global optimization solver ;-) The modeling will be easy for you thanks to the broad range of math functions supported, especially "exp". For very large-scale problems, it has shown to deliver high-quality solutions in short running times, thanks to unique heuristics. – Hexaly Aug 25 '20 at 10:24
2

You may find a partial answer to your question in the following article (forthcoming in OR) by JP Vielma and J Huchette https://arxiv.org/abs/1708.00050

In that paper, the authors consider the problem of approximating non-linear functions of one or two variables in the objective via the disjunction of multiple hyperplanes. You can then pass the resulting MIP to a general-purpose mixed-integer solver.

That article contains citations to other sources that may also be of help.

Claudio Contardo
  • 1,574
  • 6
  • 13