5
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ What's the range for $\alpha$? $\endgroup$
    – Nikos Kazazakis
    Aug 19, 2020 at 14:10
  • $\begingroup$ α is a positive constant smaller than $1$. $\endgroup$
    – Clement
    Aug 19, 2020 at 14:20
  • $\begingroup$ Are the nonlinear function in the objective or among the constraints $\endgroup$
    – Sune
    Aug 19, 2020 at 16:04
  • $\begingroup$ They can be part of the objective and the constraints. Nevertheless, I would be interested in any solution approach. $\endgroup$
    – Clement
    Aug 19, 2020 at 17:24
  • $\begingroup$ Can you show us the whole problem formulation? Then perhaps readers can offer more specific advice. $\endgroup$
    – Mark L. Stone
    Aug 20, 2020 at 8:50

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Aug 20, 2020 at 16:56
  • $\begingroup$ 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. $\endgroup$
    – Clement
    Aug 20, 2020 at 17:36
  • $\begingroup$ 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? $\endgroup$
    – Clement
    Aug 20, 2020 at 17:45
  • $\begingroup$ @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. $\endgroup$
    – Mark L. Stone
    Aug 20, 2020 at 20:43
  • $\begingroup$ @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. $\endgroup$
    – Nikos Kazazakis
    Aug 21, 2020 at 9:50
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Aug 20, 2020 at 16:51
  • $\begingroup$ I am sorry, I hadn't checked the newer comments. Yes, X, Y are variables, α is a constant between 0 and 1.0. $\endgroup$
    – Clement
    Aug 20, 2020 at 17:22
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.