Disjunctive cutting planes and algorithms for convex Mixed Integer Nonlinear Programming

Mixed Integer Nonlinear Programming (MINLP) problems are optimization problems whose objective is to minimize a nonlinear function subject to nonlinear constraints and integrality requirements on some of the decision variables. The thesis focuses on convex MINLP, wherein the objective function and nonlinear constraints are convex. A primary aim of the thesis is to develop effective techniques to strengthen the continuous relaxation of MINLP problems, a fundamental missing ingredient in most available methods for MINLP. All the proposed methods are tested and implemented in the FilMINT, a linearization-based MINLP solver.;We introduce strong-branching inequalities that are generated as by-product of a nonlinear programming based strong-branching scheme and demonstrate the relation of strong-branching inequalities to the standard disjunctive inequalities. We also introduce ways to strengthen strong- branching inequalities using optimality conditions and the integrality of decision variables. We use linearizations from strong branching in the generation of standard disjunctive inequalities. Implementation of each method yields significant improvement in the performance of our solver FilMINT.;We introduce a new computationally effective mechanism for generating disjunctive inequalities for convex MINLP. The methodology solely depends on solving a sequence of cut-generating linear programming problems. At each iteration of our method, we strategically improve the cut by adding more nonlinear structure via linearizations. We perform a computational experiment aimed at measuring the strength of disjunctive inequalities for convex MINLP. On a large test suite, our disjunctive cut generation method closes on average 69% of the integrality gap. Integrating this method into FilMINT allowed us to solve many instances that could not be solved in a time limit of three hours.;We explore ways to exploit the separability of nonlinear functions in MINLP problems. We empirically demonstrate how the performance of the state-of-the-art software that implements linearization-based methods can be improved. Exploiting separability also significantly improves the performance of our disjunctive cut-generation procedure.;The end result of the work is dramatic improvements in the solver FilMINT, improving its performance on some instances by several orders of magnitude.