A deterministic-stochastic method for nonconvex MINLP problems

Abstract

A mixed-integer programming problem is one where some of the variables must have only integer values. Although some real practical problems can be solved with mixed-integer linear methods, there are problems occurring in the engineering area that are modelled as mixed-integer nonlinear programming (MINLP) problems. When they contain nonconvex functions then they are the most difficult of all since they combine all the difficulties arising from the two sub-classes: mixed-integer linear programming and nonconvex nonlinear programming (NLP). Efficient deterministic methods for solving MINLP are clever combinations of Branch-and-Bound (B&B) and Outer-Approximations classes. When solving nonconvex NLP relaxation problems that arise in the nodes of a tree in a B&B algorithm, using local search methods, only convergence to local optimal solutions is guaranteed. Pruning criteria cannot be used to avoid an exhaustive search in the solution space. To address this issue, we propose the use of a simulated annealing algorithm to guarantee convergence, at least with probability one, to a global optimum of the nonconvex NLP relaxation problem. We present some preliminary tests with our algorithm.