We present a new tree-search algorithm for solving mixed-integer nonlinear programs (MINLPs). Rather than relying on computationally expensive nonlinear solves at every node of the branch-and-bound tree, our algorithm solves a quadratic approximation at every node. We show that the resulting algorithm retains global convergence properties for convex MINLPs, and we present numerical results on … Read more
A wide range of problems arising in practical applications can be formulated as Mixed-Integer Nonlinear Programs (MINLPs). For the case in which the objective and constraint functions are convex, some quite effective exact and heuristic algorithms are available. When non-convexities are present, however, things become much more difficult, since then even the continuous relaxation is … Read more
Mathematical programming problems involving nonconvexities are usually solved to optimality using a (spatial) Branch-and-Bound algorithm. Algorithmic efficiency depends on many factors, among which the widths of the bounding box for the problem variables at each Branch-and-Bound node naturally plays a critical role. The practically fastest box-tightening algorithm is known as FBBT (Feasibility-Based Bounds Tightening): an … Read more
We consider the problem of minimizing a continuously di erentiable function of several variables subject to simple bound and general nonlinear inequality constraints, where some of the variables are restricted to take integer values. We assume that the rst order derivatives of the objective and constraint functions can be neither calculated nor approximated explicitly. This class … Read more
Mathematical programs whose formulation is symmetric often take a long time to solve using Branch-and-Bound type algorithms, because of the several symmetric optima. One of the techniques used to decrease the adverse effects of symmetry is adjoining symmetry breaking constraints to the formulation before solving the problem. These constraints aim to make some of the … Read more
A common structure in convex mixed-integer nonlinear programs is additively separable nonlinear functions consisting of a sum of univariate functions. In the presence of such structures, we propose three improvements to the classical Outer Approximation algorithms that exploit separability. The first improvement is a simple extended formulation. The second a refined outer approximation. Finally, the … Read more
In the context of convex mixed-integer nonlinear programming (MINLP), we investigate how the outer approximation method and the generalized Benders decomposition method are affected when the respective NLP subproblems are solved inexactly. We show that the cuts in the corresponding master problems can be changed to incorporate the inexact residuals, still rendering equivalence and finiteness … Read more
In the context of convex mixed-integer nonlinear programming (MINLP), we investigate how the outer approximation method and the generalized Benders decomposition method are affected when the respective NLP subproblems are solved inexactly. We show that the cuts in the corresponding master problems can be changed to incorporate the inexact residuals, still rendering equivalence and finiteness … Read more
In this paper, we study 0-1 mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have polyhedral structures that are similar to those of certain fixed-charge single-node flow sets. As a result, we obtain new facet-defining inequalities for these sets that generalize well-known … Read more
We describe a procedure to reduce variable bounds in Mixed Integer Nonlinear Programming (MINLP) as well as Mixed Integer Linear Programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction technique extends the implied bounds procedure used in MINLP and MILP and … Read more