(514f) Feasibility Pump for Solving Convex MINLP Problems with Dicopt

David E. Bernal, S. Vigerske, F. Trespalacios and I.E. Grossmann

DICOPT (short for Discrete Continuous Optimizer) is an MINLP solver based on the outer-approximation method[1,2]. This solver combines the algorithms of outer-approximation, equality relaxation and augmented penalty with other existing NLP and MIP solvers [3]. The outer approximation and equality relaxation algorithm proceeds by alternatingly solving NLP subproblems with fixed discrete variables (in the first iteration is the relaxed MINLP) and an outer-approximation MILP master problem that generates cuts to bound the feasible region. The criteria used by DICOPT for establishing optimality in convex MINLP is a crossover, which is obtained as soon as the bound defined by the objective of the last MIP master problem is worse than the best NLP solution found [3].

For some problems, DICOPT has difficulty in finding a first feasible solution. The main reason for this is that by default, DICOPT does not include constraint linearization in infeasible solutions, only no-good cuts. Furthermore, even if the linearizations are included for infeasible solution the issue persists in some problems. In order to allow DICOPT to find an initial feasible solution of convex MINLP problems, the implementation of a feasibility pump [4] is incorporated into DICOPT.

The feasibility pump is similar to the outer-approximation, but its objective is to find feasible solutions rather than optimal ones. The main idea of this algorithm is to decompose the original mathematical programming problem in two parts: integer feasibility and constraint feasibility. By solving an MIP subproblem its solution is an integer feasible solution, which may violate the constraints; and by solving a continuous relaxation of the original MINLP (NLP subproblem) the solution is constraint feasible but might not be integral. By minimizing in successive iterations the distance between these two types of solutions it is expected to achieve a solution that is both constraint and integral feasible.

The feasibility pump can be used as a standalone solver for convex MINLP problems. This is achieved by iteratively applying the method, while including a bound to the objective function. This bound is obtained by the best known solution and an epsilon improvement. The drawback of this algorithm is that may require many iterations, since each time the objective function is restricted to improve only by epsilon.

In this work, the feasibility pump is applied in DICOPT before the outer-approximation method. In the feasibility pump, large improvements in the objective function are enforced at each iteration. After the method finishes, all the cuts and the best known solution are passed to the outer-approximation method to find and prove optimality. The described algorithm has been implemented in DICOPT and is available in GAMS 24.5. We present computational results of the new method with over 50 instances of convex MINLP problems, and show that it outperforms the previous version of DICOPT.

References

1. Duran, Marco A., and Ignacio E. Grossmann. "An outer-approximation algorithm for a class of mixed-integer nonlinear programs." Mathematical programming 36.3 (1986): 307-339.

2. Fletcher, Roger, and Sven Leyffer. "Solving mixed integer nonlinear programs by outer approximation." Mathematical programming 66.1-3 (1994): 327-349.

3. G. Kocis and I. Grossmann, "Computational experience with DICOPT solving MINLP problems in process systems engineering," Computers and Chemical Engineering 13.3 (1989): 307-315.

4. P. Bonami, G. Cornuéjols, A. Lodi and F. Margot, "A feasibility pump for mixed integer nonlinear programs," Mathematical Programming, vol. 119, pp. 331-352, 2009.