Metaheuristics are normally working good but I am looking for some deterministic algorithms.
Despide being meta-heuristic, i can suggest Differential evalution .Because it has gradient procedure and may be you can obtain deterministic answer. By the way, Optimality Critera is also good method for the deterministic answer.
It depends a lot on different factors - for example whether the nonlinear part is convex or not. If that is the case, then a nonlinear form of Benders decomposition (called, I think, generalized Benders decomposition) is convergent - at least in theory! :-)
I think any mixed-integer programming problem is a nononvex as we cannot define its gradient.
For solving the MINLP problems, the branch and cut algorithm is the best one. However, the deterministic algorithms result in sub-optimal solutions.
If you do not want to implement the algorithm yourself, there are some freely available on http://www.coin-or.org/projects/ -> Optimization deterministic nonlinear discrete & Optimization deterministic nonlinear nonconvex mixed-integer. Another one is Minotaur (available from https://wiki.mcs.anl.gov/minotaur/index.php/Minotaur_Download) Good luck!
Dear Jan Schwientek, thanks a lot for you response.
Actually, I am already using coin-or (AMPL). Here, I am interested to know some efficient deterministic optimization algorithm for solving MINPL problems. Presently, I am using BONMIN (branch and bound method) which is a very time consuming algorithm. Total numbers of variables in my problem are 372 in which there are 72 discrete variables. Also, there are 1184 nonlinear constraints. I need some efficient algorithm for solving the problem with such complexity.
There are two further solvers LaGO and Couenne with AMPL-interfaces. But I cannot suggest you one of them or another one, because I have no experience with them in mixed-integer nonlinear optimization.
BONMIN in AMPL is supported by various algorithms for solving MINLP which are:
B-BB (simple branch-and-bound algorithm,)
B-OA (OA Decomposition algorithm,)
B-QG (Quesada and Grossmann branch-and-cut algorithm,)
B-Hyb (hybrid outer approximation based branch-and-cut
B-Ecp (ecp cuts based branch-and-cut a la FilMINT.)
B-iFP (Iterated Feasibility Pump for MINLP.)
Out of these, B-BB is given good results but taking extremely large time. B-OA is relatively much faster than B-BB but not able to achieve the results obtained by B-BB. That is way, I am looking for some better algorithm.
To solve mixed-integer programming problem, you may use any of recent developed heuristic-based methods like cuckoo search, Differential evolution, grey wolf optimiser and many more. It also depends on the size of your problems,
There are many exact algorithms available for the convex case, e.g., generalized Benders decomposition, outer approximation, branch-and-cut, LP/NLP-based branch-and-bound. I recommend reading these surveys:
P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke & A. Mahajan (2013) Mixed-integer nonlinear optimization. Acta Numerica, 22, 1-131.
C. D'Ambrosio & A. Lodi (2013) Mixed integer nonlinear programming tools: An updated practical overview. Annals of Operations Research, 204, 301-320.
I.E. Grossmann (2002) Review of nonlinear mixed-integer and disjunctive programming techniques. Optimization and Engineering, 3, 227-252.
If some or all of your objective and constraints functions are non-convex, things get more tricky, since you are then in the world of global optimization. For this case, you could take a look at the following survey, which I co-authored with Sam Burer:
S. Burer & A. Letchford (2009) Non-convex mixed-integer nonlinear programming: a survey. Surveys in OR / MS, 17, 97-106.
Considering software already available, you might use IPOPT if the problem is convex (BONMIN if you also have integer variables). If non convex, those solvers give you just local optima. In that case, you may employ other solvers as Couenne/BARON/Scip.
Regards,
Alberto
Thank you very much Prof. Adam N. Letchford.
It seems that the references suggested by you are very useful to me. I wish to seek your advice in future regarding the optimization.
Thank you very much Dr. Alberto Costa for you answer. I would like to use BARON solver suggested by you.
Dear Dr. Alberto Costa,
I want your opinion about convexity test of MILP/MINLP problems. The actual question is available at the link given below:
https://www.researchgate.net/post/Is_it_necessary_to_test_CONVEXITY_of_an_MILP_MINLP_problem
Dear Mahamad Nabab Alam,
I replied directly to the other post.
Regards,
Alberto
Thank you very much Dr. Alberto Costa for your very informative reply.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms