On the Separation of Split Inequalities for Non-Convex Quadratic Integer Programming

We investigate the computational potential of split inequalities for non-convex quadratic integer programming, first introduced by Letchford and further examined by Burer and Letchford. These inequalities can be separated by solving convex quadratic integer minimization problems. For small instances with box-constraints, we show that the resulting dual bounds are very tight; they can close a … Read more

A branch and cut algorithm for minimum spanning trees under conflict constraints

We study approaches for the exact solution of the \NP–hard minimum spanning tree problem under conflict constraints. Given a graph $G(V,E)$ and a set $C \subset E \times E$ of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the … Read more

Cutting-planes for optimization of convex functions over nonconvex sets

Motivated by mixed-integer, nonlinear optimization problems, we derive linear inequality characterizations for sets of the form conv{(x, q ) \in R^d × R : q \in Q(x), x \in R^d – int(P )} where Q is convex and differentiable and P \subset R^d . We show that in several cases our characterization leads to polynomial-time … Read more

A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines

Research on due date oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine environment. In this study, we leverage on our previous work … Read more

On the Rank of Cutting-Plane Proof Systems

We introduce a natural abstraction of propositional proof systems that are based on cut- ting planes. This leads to a new class of proof systems that includes many well-known meth- ods, such as Gomory-Chvátal cuts, lift-and-project cuts, Sherali-Adams cuts, or split cuts. The rank of a proof system corresponds to the number of rounds that … Read more

Implementing cutting plane management and selection techniques

One main objective of research in the area of mixed-integer programming is developing cutting plane techniques to improve the solvability of mixed-integer programs (MIPs). Various cutting plane separators are typically available in MIP solvers. The large number of cutting planes generated by these separators, however, can pose a computational problem. Therefore, a sophisticated cut management … Read more

Convex hulls of superincreasing knapsacks and lexicographic orderings

We consider bounded integer knapsacks where the weights and variable upper bounds together form a superincreasing sequence. The elements of this superincreasing knapsack are exactly those vectors that are lexicographically smaller than the greedy solution to optimizing over this knapsack. We describe the convex hull of this n-dimensional set with O(n) facets. We also establish … Read more

On the Relative Strength of Different Generalizations of Split Cuts

Split cuts are among the most important and well-understood cuts for general mixed-integer programs. In this paper we consider some recent generalizations of split cuts and compare their relative strength. More precisely, we compare the elementary closures of {split}, {cross}, {crooked cross} and general {multi-branch split cuts} as well as cuts obtained from multi-row and … Read more

Polyhedral Aspects of Self-Avoiding Walks

In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this … Read more