9
$\begingroup$

INTRODUCTION

My research often involves solving MINLP problems with few constraints (usually two) and not many variables (say between one and three integer ones, and between one and five real-valued ones).

The bottlenecks of these problems are the calculation of the objective function and the constraints: they are smooth functions but are quite complex, usually including integrals and cumulative distribution functions (CDF) of continuous random variables (NB: I am not saying that I deal with stochastic problems, but just with problems that involve probability calculations). Occasionally, I have to deal also with calculations involving sparse matrices.

Sometimes, explicit expressions for the gradient of the objective function can be obtained, but not always. Most of the times, the functions in the problem are not convex, strictly speaking, but they happen to be monotonous or convex or unimodal for some of the continuous variables involved (assuming that the rest of variables are fixed).

My typical approach here is performing a sort of enumerative search on the integer variables, and, for each combination of the integer variables, solving the (resulting NLP) problem to optimality for the real-valued variables.

I do this because I found that, sometimes, MINLP solvers get stuck in local optima or even have problems to find a feasible solution. That is why I prefer to handle the integer part of the problem myself by fixing the integer variables and then using NLP solvers for the continuous part.

Besides, sometimes, as a result of the mathematical study of the behaviour of the specific functions of my problems, I am able to deduce an ad-hoc solving strategy for the NLP part (I mean, once the integer variables are fixed).

An additional, general problem is that, sometimes, the calculation of the functions involved is heavily time-consuming.

MY QUESTION

In short, my problem is that I still have not found the right software environment or setting to solve my optimisation problems. The best software to deal with integrals, CDFs or sparse matrices (for instance: Mathematica, Matlab, Scilab...) is not the software providing the best MINLP/NLP algorithms (for instance: GAMS...).

I was recently using Matlab for some problems, and it is really great, but the functions I was dealing with were really time-consuming, and therefore every optimisation strategy took too long.

I am tempted to go back to C++, since it is faster, and it can handle complex calculations via the GNU Scientific Library (GSL), for instance. But I do not know whether there are good implementations of MINLP/NLP solvers in C++.

I could also consider the possibility of using heuristic algorithms, but I actually think that my problems are not purely combinatorial ones (since they do not have hundreds of (integer) variables and constraints), and that it is worth trying to solve them to optimality in an exact way.

I have not studied other possibilities, such as calling precompiled C++ routines from another solving software.

So, what software setting would you suggest for dealing with this kind of problems?

$\endgroup$
1
  • $\begingroup$ If the problem is non-convex and you don't provide the explicit formulation to the solver, then you can't solve it exactly. Or is the NLP that you get after fixing the integer variables convex? $\endgroup$
    – fontanf
    Aug 20 at 16:45
5
$\begingroup$

I suggest you have a look at LocalSolver to solve your problem. It is free for basic research and teaching.

Contrarily to its name suggests, LocalSolver is a global optimization solver. It handles MINLPs. LocaLSolver uses diversification techniques to avoid getting stuck into local optima. Moreover, it allows plugging to your optimization model some external functions. These functions, for example, simulators, can be used in constraints and/or objectives. At last, LocalSolver automatically handles a time-consuming objective function by using surrogate modeling techniques.

In your case, since the complexity is in the definition of the objective function, I suggest you write a function in C++ (it seems that you prefer developing in C++) that evaluates the objective given in input the values of the few decisions you have to take. Then, you model the problem analytically, defining decision variables and the two constraints. You use your C++ function as the objective function by calling it as an external function in your LocalSolver model.

If the evaluation of the C++ function takes too much time (typically, several minutes per call), maybe using surrogate modeling can be beneficial. For this, you will have to change the call to an external function into the call to a so-called black-box function. Having transformed it into a black-box function, you can define a budget of calls to the time-consuming objective function. For example, you can ask to LocalSolver to call the function at most 100 times. If each call lasts 1 minute, then the overall running time will be 100 minutes approximately. Since your model involves less than 10 variables, it should work very well. Some ready-to-use C++ code examples are given in our Example Tour.

If you encounter any trouble, please feel free to ask support to contact@localsolver.com. The team will be glad to help you. Your problem is very interesting.

Disclaimer: LocalSolver is a commercial optimization solver; nevertheless, it can be used for free for basic research and teaching.

$\endgroup$
4
$\begingroup$

So it seems your strategy (enumerative search on the integer variables) works well, and the issue is solving pure NLP problems. The choice of programming/modeling language you use is dependent on what type of NLPs you solve and that whether you rely on the existing solvers or would be willing to implement your own algorithms.

In any case, it is likely that you find Python a good choice, if not the best, for various reasons. There are many libraries/solver APIs available that make your life easier. Some of these solvers have been mentioned here. Even if you are going to develop your own algorithm, you could use packages such as Numpy for the heavy numerical parts. Note that some solvers already exist in Scipy. You may also use the well-known solvers CPLEX and GUROBI if they can handle the type of NLP you have. Even if not, you may still successfully employ them as part of your algorithms.

In the worst case, you have the option to write your algorithms in C/C++ and call them from within Python. Python also gives you access to rich statistical, machine learning and visualization libraries that you might find useful in developing and/or analyzing your algorithms. Another important advantage of Python is that it is free (unlike, say, MATLAB).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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