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
The Time Dependent Traveling Salesman Problem (TDTSP) is a generalization of the classical Traveling Salesman Problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. … Read more
We show that half-integral polytopes obtained as the convex hull of a random set of half-integral points of the 0/1 cube have rank as high as Ω(logn/loglogn) with positive probability — even if the size of the set relative to the total number of half-integral points of the cube tends to 0. The high rank … Read more
To improve the efficiency in power generation and to reduce the greenhouse gas emission, both Demand Response (DR) strategy and intermittent renewable energy have been proposed or applied in electric power systems. However, the uncertainty and the generation pattern in wind farms and the complexity of demand side management pose huge challenges in power system … Read more
In this paper we consider a relaxation of the corner polyhedron introduced by Andersen et al., which we denote by RCP. We study the relative strength of the split and triangle cuts of RCP’s. Basu et al. showed examples where the split closure can be arbitrarily worse than the triangle closure under a `worst-cost’ type … Read more
We will analyze mixed 0/1 second order cone programs where the fractional and binary variables are solely coupled via the conic constraints. For this special type of mixed-integer second order cone programs we devise a cutting-plane framework based on the generalized Benders cut and an implicit Sherali-Adams reformulation. We show that the resulting cuts are … Read more
Let S be a subset of integer points that satisfy the property that $conv(S) \cap Z^n = S$. Then a convex set K is called an S-free convex set if $int(K) \cap S = \emptyset$. A maximal S-free convex set is an S-free convex set that is not properly contained in any S-free convex set. … Read more
In optimization-based classification model selection, for example when using linear programming formulations, a standard approach is to penalize the L1 norm of some linear functional in order to select sparse models. Instead, we propose a novel integer linear program for sparse classifier selection, generalizing the minimum disagreement hyperplane problem whose complexity has been investigated in … Read more
We propose a unifying framework for polyhedral approximation in convex optimization. It subsumes classical methods, such as cutting plane and simplicial decomposition, but also includes new methods, and new versions/extensions of old methods, such as a simplicial decomposition method for nondifferentiable optimization, and a new piecewise linear approximation method for convex single commodity network flow … 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