Improving the performance of DICOPT in convex MINLP problems using a feasibility pump

Abstract

The solver DICOPT is based on the outer-approximation algorithm used for solving mixed-integer nonlinear programming (MINLP) problems. This algorithm is very effective for solving some types of convex MINLPs. However, it has been observed that DICOPT has difficulties solving instances in which some of the nonlinear constraints are so restrictive that nonlinear subproblems generated by the algorithm are infeasible. This problem is addressed in this paper with a feasibility pump algorithm, which modifies the objective function in order to efficiently find feasible solutions. It has been implemented as a preprocessing algorithm, which is used to initialize both the incumbent and the mixed-integer linear relaxation of the outer-approximation algorithm. Computational comparisons with previous versions of DICOPT on a set of convex MINLPs demonstrate the effectiveness of the proposed algorithm in terms of solution quality and solution time.