In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm which constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard … Read more
We present a number of new algorithmic ideas for solving LP relaxations of extremely large precedence constrained production scheduling problems. These ideas are used to develop an implementation that is tested on a variety of real-life, large scale instances; yielding optimal solutions in very practicable CPU time. Citation Unpublished. Columbia University, BHP Billiton, August 2009. … Read more
The Sherali-Adams lift-and-project hierarchy is a fundamental construct in integer programming, which provides successively tighter linear programming relaxations of the integer hull of a polytope. We initiate a new approach to understanding the Sherali-Adams procedure by relating it to methods from computational algebraic geometry. Our main result is a refinement of the Sherali-Adams procedure that … Read more
Automatic verification of computer code is of paramount importance in embedded systems supplying essential services. One of the most important verification techniques is static code analysis by abstract interpretation: the concrete semantics of a programming language (i.e.the values $\chi$ that variable symbols {\tt x} appearing in a program can take during its execution) are replaced … Read more
In an important paper, Burer recently showed how to reformulate general mixed-binary quadratic optimization problems (QPs) into copositive programs where a linear functional is minimized over a linearly constrained subset of the cone of completely positive matrices. In this note we interpret the implication from a topological point of view, showing that the Minkowski sum … Read more
This paper proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with N nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2, …, … Read more
In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second moment matrix of the nonnegative objective coefficients is assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected value of a … Read more
Mixed Integer Nonlinear Programming (MINLP) problems present two main challenges: the integrality of a subset of variables and nonconvex (nonlinear) objective function and constraints. Many exact solvers for MINLP are branch-and-bound algorithms that compute a lower bound on the optimal solution using a linear programming relaxation of the original problem. In order to solve these … Read more
The classical branch-and-bound algorithm for the integer feasibility problem has exponential worst case complexity. We prove that it is surprisingly efficient on reformulations, in which the columns of the constraint matrix are short, and near orthogonal, i.e. a reduced basis of the generated lattice; when the entries of A (i.e. the dense part of the … Read more
This paper surveys results on the NP-hard mixed-integer quadratically constrained programming problem. The focus is strong convex relaxations and valid inequalities, which can become the basis of efficient global techniques. In particular, we discuss relaxations and inequalities arising from the algebraic description of the problem as well as from dynamic procedures based on disjunctive programming. … Read more