In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (2008). By analyzing $n$-dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the … Read more
We study a mixed integer linear program with $m$ integer variables and $k$ non-negative continuous variables in the form of the relaxation of the corner polyhedron that was introduced by Andersen, Louveaux, Weismantel and Wolsey [\emph{Inequalities from two rows of a simplex tableau}, Proc.\ IPCO 2007, LNCS, vol.~4513, Springer, pp.~1–15]. We describe the facets of … Read more
In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and … Read more
In a recent paper, Dash, Dey and Gunluk (2010) showed that many families of inequalities for the two-row continuous group relaxation and variants of this relaxation are cross cuts or crooked cross cuts, both of which generalize split cuts. Li and Richard (2008) recently studied t-branch split cuts for mixed-integer programs for integers t >= … Read more
We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem arises in a number of other contexts, e.g. it is a relaxation of general mixed-integer programming. We show how … Read more
Optimum Experimental Design (OED) problems are optimization problems in which an experimental setting and decisions on when to measure – the so-called sampling design – are to be determined such that a follow-up parameter estimation yields accurate results for model parameters. In this paper we use the interpretation of OED as optimal control problems with … Read more
We give new facets and valid inequalities for the separable piecewise linear optimization knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. In a companion paper (de Farias, Gupta, Kozyreff, Zhao, 2011) we demonstrate the efficiency of the inequalities when used as cuts in a branch-and-cut … Read more
We report and analyze the results of our extensive computational testing of branch-and-cut for piecewise linear optimization using the cutting planes given recently by Zhao and de Farias. Besides analysis of the performance of the cuts, we also analyze the effect of formulation on the performance of branch-and-cut. Finally, we report and analyze initial results … Read more
We consider the question of finding deep cuts from a model constructed with two rows of a simplex tableau. To do that, we show how to reduce the complexity of setting up the polar of such model from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore we … Read more
In this work, we propose a global optimization approach for mixed-integer programming problems. To this aim, we preliminarily de ne an exact penalty algorithm model for globally solving general problems and we show its convergence properties. Then, we describe a particular version of the algorithm that solves mixed integer problems. CitationDIS Technical Report n. 17, 2010.ArticleDownload … Read more