We show that there are 0-1 and unbounded knapsack polytopes with super-polynomial extension complexity. More specifically, for each n in N we exhibit 0-1 and unbounded knapsack polyhedra in dimension n with extension complexity \Omega(2^\sqrt{n}). ArticleDownload View PDF
Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a … Read more
Let B be the set of n-dimensional binary vectors and let V be a subset of m of its elements. We give an extended formulation of the convex hull of B\V which is polynomial in n and m. In developing this result, we give a two-sided extension of a result in Laurent and Sassano (1992) … Read more
We introduce a natural strengthening of Gomory-Chvátal cutting planes for the important class of 0/1-integer programming problems and study the properties of the elementary closure that arises from the new class of cuts. Most notably, we prove that the new closure is polyhedral, we characterize the family of all facet-defining inequalities, and we compare it … Read more
We are interested in methods to solve mixed-integer nonlinear optimal control problems (MIOCPs) constrained by ordinary di erential equations and combinatorial constraints on some of the control functions. To solve these problems we use a rst discretize, then opti- mize approach to get a specially structured mixed-integer nonlinear program (MINLP). We decompose this MINLP into an … Read more
This paper introduces novel formulations for optimally responding to epidemics and cyber attacks in networks. In our models, at a given time period, network nodes (e.g., users or computing resources) are associated with probabilities of being infected, and each network edge is associated with some probability of propagating the infection. A decision maker would like … Read more
In this paper we examine the impact of using the Sherali-Adams procedure on highly symmetric integer programming problems. Linear relaxations of the extended formulations generated by Sherali-Adams can be very large, containing on the order of n choose d many variables for the level-d closure. When large amounts of symmetry are present in the problem … Read more
The quadratic traveling salesman problem asks for a tour of minimal costs where the costs are associated with each two arcs that are traversed in succession. This structure arises, e. g., if the succession of two arcs represents the costs of loading processes in transport networks or a switch between different technologies in communication networks. … Read more
We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with diff erent basis vector sets. We discuss how several well-known TSP lower bounds correspond to intuitive basis vector choices and give an economic interpretation wherein the salesman must pay tolls as he travels between … Read more
This paper introduces interdiction branching, a new branching method for binary integer programs that is designed to overcome the difficulties encountered in solving problems for which branching on variables is inherently weak. Unlike traditional methods, selection of the disjunction in interdiction branching takes into account the best feasible solution found so far. In particular, the … Read more