Computing deep facet-defining disjunctive cuts for mixed-integer programming

Cadoux, Florent
April 2010
Mathematical Programming;Apr2010, Vol. 122 Issue 2, p197
Academic Journal
The problem of separation is to find an affine hyperplane, or �cut�, that lies between the origin O and a given closed convex set Q in a Euclidean space. We study cuts which are deep in a well-defined geometrical sense, and facet-defining. The cases when the deepest cut is decomposable as a combination of facet-defining cuts are characterized using the reverse polar set. When Q is a disjunctive polyhedron, a description of the reverse polar, linked to the so-called cut generating linear program of lift-and-project techniques, is given. A successive projections algorithm onto the reverse polar is proposed that computes the decomposition of the deepest cut into facet-defining cuts. Illustrative numerical experiments show how these cuts compare with the deepest cut, and with the most violated cut.


Related Articles

  • Approximation algorithm for a class of global optimization problems. Locatelli, Marco // Journal of Global Optimization;Jan2013, Vol. 55 Issue 1, p13 

    In this paper we develop and derive the computational cost of an $${\varepsilon}$$ -approximation algorithm for a class of global optimization problems, where a suitably defined composition of some ratio functions is minimized over a convex set. The result extends a previous one about a class of...

  • Minimax risk over quadratically convex sets. Reshetov, S. // Journal of Mathematical Sciences;Jun2010, Vol. 167 Issue 4, p537 

    We consider the problem of estimating a vector ? = (?1, ?2,...) ? T ? l2 from observations y i = ? i + s i x i, i = 1, 2,..., where the random values x i are N(0, 1), independent, and identically distributed, the parametric set T is compact, orthosymmetric, convex, and quadratically convex. We...

  • Large transversals to small families of unit disks. Bisztriczky, T.; Fodor, F.; Oliveros, D. // Acta Mathematica Hungarica;2005, Vol. 106 Issue 4, p285 

    It is proved that if the nonempty intersection of bounded closed convex setsAnBis contained in (A+

  • On inclusion and summands of bounded closed convex sets. Grzybowski, J.; Urbański, R. // Acta Mathematica Hungarica;2005, Vol. 106 Issue 4, p293 

    This article introduces coset extensions and group coextensions ofS-sets.

  • On Efficient Sets in R2. Hoang Xuan Phu // Vietnam Journal of Mathematics;Dec2005, Vol. 33 Issue 4, p463 

    Let A ⊂ ℝ² be a nonempty closed convex subset and C ⊂ ℝ² be a nonempty nontrivial convex cone. Due to Luc (1985 and 1989), if A is compact and if the closure C̄ is pointed, then the efficient set E(A\C) of A w,r.t, C is homeomorphic to a nonempty closed interval...

  • Exact Formulae for Coderivatives of Normal Cone Mappings to Perturbed Polyhedral Convex Sets. Huy, N.; Yao, J.-C. // Journal of Optimization Theory & Applications;Apr2013, Vol. 157 Issue 1, p25 

    In this paper, without using any regularity assumptions, we derive a new exact formula for computing the Fréchet coderivative and an exact formula for the Mordukhovich coderivative of normal cone mappings to perturbed polyhedral convex sets. Our development establishes generalizations and...

  • Minimum recession-compatible subsets of closed convex sets. He, Yiran; Sun, Jie // Journal of Global Optimization;Feb2012, Vol. 52 Issue 2, p253 

    A subset B of a closed convex set A is recession-compatible with respect to A if A can be expressed as the Minkowski sum of B and the recession cone of A. We show that if A contains no line, then there exists a recession-compatible subset of A that is minimal with respect to set inclusion. The...

  • d-REPRESENTABILITY OF SIMPLICIAL COMPLEXES OF FIXED DIMENSION. Tancer, Martin // Journal of Computational Geometry;Jun2011, Vol. 2 Issue 1, p183 

    Let K be a simplicial complex with vertex set V = {v1,…, vn}. The complex K is d-representable if there is a collection {C1,…,Cn} of convex sets in ℝd such that any subcollection Due to image rights restrictions.txt has a nonempty intersection if and only if Due to image rights...

  • Functions Like Convex Functions. Pavić, Zlatko // Journal of Function Spaces;4/6/2015, Vol. 2015, p1 

    The paper deals with convex sets, functions satisfying the global convexity property, and positive linear functionals. Jensen's type inequalities can be obtained by using convex combinations with the common center. Following the idea of the common center, the functional forms of Jensen's...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics