| A Mixed Integer Nonlinear Program (MINLP) is the problem of minimizing a nonlinear function subject to nonlinear constraints and integrality restrictions on some or all of the decision variables. MINLP is one of the most fundamentally challenging problems in optimization, its difficulty arising from the combination of functional nonlinearities and nonconvexity induced by integrality restrictions. Nevertheless, MINLP is a tremendously important problem, with many important engineering and operations applications being formulated as MINLP models. The main focus of this thesis is on convex MINLPs, where the objective function is convex, and the points that satisfy the nonlinear constraints form a convex set. We aim to develop an efficient framework and set of methods for solving convex MINLPs, as well as to demonstrate the advantages of modeling applications as MINLPs.;The framework provides us with the means to investigate different heuristic schemes and solution techniques for solving MINLPs. The area of primal heuristics for MINLPs deserves special attention because of the dramatic impact it can have in reducing the tree search. We investigate three heuristics for getting feasible solutions, based on the principle of the feasibility pump. The first scheme is based on solving a nonlinear program and rounding its solution iteratively. The second scheme is an extension of a known heuristic for MINLPs and is based on iteratively solving a nonlinear program and an MILP. We suggest ways to improve the linear model, reduce the time spent in enumeration, and improve an incumbent within this scheme. The third scheme integrates the solution of an NLP with the tree search, similar to the way in which the LP/NLP algorithm avoids the re-solution of the MILP iteratively. The last two approaches are exact solution schemes for convex MINLPs, since they do not cycle. Our computational experience validates the effectiveness of our approach for use in a branch-and-cut framework.;Finally, we illustrate the advantages of using MINLP modeling and solution techniques for an important class of programs, called Mixed Variable Programs (MVP), that are used to model some important applications. A typical MVP model contains categorical variables that do not allow continuous relaxations, and requires heuristics for its solution. We use integer and nonlinear modeling techniques to formulate such problems and illustrate our approach on a thermal insulation system. We come up with three different MINLP models, with varying degree of smoothness. This allows us to solve such problems using more sophisticated techniques. We highlight the pros and cons of our approach and present numerical results for the model using both FilMINT and a branch-and-bound solver based on nonlinear programming relaxations. Our approach provides a blueprint for modeling such design problems containing categorical variables.;To achieve this goal, we introduce an algorithmic framework that aims to solve MINLPs at a cost which is a small multiple of the cost of solving comparable mixed integer linear programs. First, we discuss how to implement a (known) linearization-based algorithm (known as LP/NLP branch-and-bound) using existing software components for mixed integer linear programming (MILP) branch-and-cut and (continuous) nonlinear programming. Implementing the algorithm in an existing MILP branch-and-cut framework provides a convenient mechanism for exploring the impact of various advanced MILP features, such as cutting planes, branching rules, heuristics, and node selection strategies. Further, we discuss new ideas for effectively developing and managing the linear model. We exploit the convexity property of the model to generate linearizations, treating them in a manner similar to the way cutting planes are treated in a branch-and-cut framework for MILPs. Our implementation, called FilMINT, is a powerful and flexible software package for MINLP---competitive with all other known software available for this problem class. |
