Optimization seminar

Modal title

Modal content

Date / Time

Speaker

Title

Location

26 March 2018
16:30-17:30

Dr. Matthias Walter
RWTH Aachen, Aachen, Germany

Event Details

Title	Extended Formulations for Radial Cones
Speaker, Affiliation	Dr. Matthias Walter, RWTH Aachen, Aachen, Germany
Date, Time	26 March 2018, 16:30-17:30
Location	HG G 19.1
Abstract	In this talk we discuss extended formulations for radial cones of vertices of polyhedra, where the radial cone of a polyhedron P and a vertex v is the polyhedron defined by the constraints of P that are active at v. Given an extended formulation for P, it is easy to obtain an extended formulation of comparable size for each its radial cones. On the contrary, it is possible that radial cones of P admit much smaller extended formulations than P itself. A prominent example of this type is the perfect-matching polytope, which cannot be described by subexponential-size extended formulations (Rothvoss 2014). However, Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. Moreover, they generalized their construction to V-join polyhedra.In the same paper, the authors asked whether the same holds for the odd-cut polyhedron, the blocker of the V-join polyhedron. We answer this question negatively. Precisely, we show that radial cones of odd-cut polyhedra cannot be described by subexponential-size extended formulations. To obtain our result, for a polyhedron P of blocking type, we establish a general relationship between its radial cones and certain faces of the blocker of P. This is joint work with Stefan Weltge.

Extended Formulations for Radial Conesread_more

28 May 2018
16:30-17:30

Prof. Dr. Amitabh Basu
Johns Hopkins University, Baltimore, USA
Dr. Timm Oertel
Cardiff University, Cardiff, UK

Event Details

Title	Optimality of Gomory Mixed-Integer Cuts //// Distances to Lattice Points in Knapsack Polyhedra
Speaker, Affiliation	Prof. Dr. Amitabh Basu, Johns Hopkins University, Baltimore, USA Dr. Timm Oertel, Cardiff University, Cardiff, UK
Date, Time	28 May 2018, 16:30-17:30
Location	HG G 19.1
Abstract	We investigate natural measures of the quality of cutting planes such as depth of cut and volume cut off. We find the optimal cutting planes according to these measures for the infinite and finite group relaxations introduced by Gomory-Johnson. Interestingly, when the volume cut off is used as the measure, the optimal cuts turn out to be automorphisms of the well-known Gomory mixed-integer cut. The proofs uncover interesting connections with rearrangement inequalities in functional analysis and generalizations of the Brunn-Minkowski theorem to topological groups. /////////// We give an optimal upper bound for the distance from a vertex of a knapsack polyhedron to its nearest feasible lattice point. In a randomised setting, we show that the upper bound can be significantly improved on average. As a corollary, we obtain an optimal upper bound for the additive integrality gap of integer knapsack problems and show that the integrality gap of a “typical” knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.

Optimality of Gomory Mixed-Integer Cuts //// Distances to Lattice Points in Knapsack Polyhedraread_more

Note: if you want you can subscribe to the iCal/ics Calender.

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 AS 17 SS 17 AS 16 SS 16 AS 15 SS 15 AS 14 SS 14 AS 13 SS 13 AS 12 SS 12 AS 11 SS 11 AS 10 SS 10 AS 09