We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained by … Read more
We propose a new method for separating valid inequalities for the epigraph of a function of binary variables. The proposed inequalities are disjunctive cuts defined by disjunctive terms obtained by enumerating a subset $I$ of the binary variables. We show that by restricting the support of the cut to the same set of variables $I$, … Read more
Generating polyhedral outer approximations and solving mixed-integer linear relaxations remains one of the main approaches for solving convex mixed-integer nonlinear programming (MINLP) problems. There are several algorithms based on this concept, and the efficiency is greatly affected by the tightness of the outer approximation. In this paper, we present a new framework for strengthening cutting … Read more
In the early 1980s, Balas and Jeroslow presented monoidal disjunctive cuts exploiting the integrality of variables. This article investigates the relation of monoidal cut strengthening to other classes of cutting planes for general two-term disjunctions. We introduce a generalization of mixed-integer rounding cuts and show equivalence to monoidal disjunctive cuts. Moreover, we demonstrate the effectiveness … Read more
In this paper we provide a unified treatment of general two-term disjunctions on cross-sections of the second-order cone. We derive a closed-form expression for a convex inequality that is valid for such a disjunctive set and show that this inequality is sufficient to characterize the closed convex hull of all two-term disjunctions on ellipsoids and … Read more
Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone, and develop a methodology to derive closed-form expressions for convex inequalities … Read more
In this paper branching for attacking MILP is investigated. Under certain circumstances branches can be done concurrently. By introducing a new calculus it is shown there are restrictions for dual values. As a second result of this study a new class of cuts for MILP is found, which are defined by those values. This class … Read more
We describe a computationally effective method for generating disjunctive inequalities for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs, and in the limit will generate an inequality as strong as can be produced by the cut-generating nonlinear program suggested by Stubbs and Mehrotra. Using this procedure, we … Read more
We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined recently in another paper). We then extend this observation to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables provided that … Read more
In this paper, we study the relationship between {\em 2D lattice-free cuts}, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in $\R^2$, and various types of disjunctions. Recently, Li and Richard (2007) studied disjunctive cuts obtained from $t$-branch split disjunctions … Read more