Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Mixed-integer sets from two rows of two adjacent simplex bases ; Louveaux, Quentin ; in Mathematical Programming (2010), 124(1-2), 455-480 In 2007 we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with ... [more ▼] In 2007 we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with either three or four variables. In this paper we generalize our ﬁndings and show that, when upper bounds on the non-basic variables are also considered, further classes of facets arise that cannot be obtained from triangles and quadrilaterals. Speciﬁcally, when exactly one upper bound on a non-basic variable is intro- duced, stronger inequalities that can be derived from pentagons involving up to six variables also appear. [less ▲] Detailed reference viewed: 120 (18 ULg)An analysis of mixed integer linear sets based on lattice point free convex sets ; Louveaux, Quentin ; in Mathematics of Operations Research (2010), 35(1), 233-256 The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the w th split closure. We show the w th split closure is a ... [more ▼] The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the w th split closure. We show the w th split closure is a polyhedron. This generalizes a previous result showing this to be true when w = 1. We also consider the design of ﬁnite cutting plane proofs for the validity of an inequality. Given a measure of “size” of a maximal lattice free polyhedron, a natural question is how large a size s of a maximal lattice free polyhedron is required to design a ﬁnite cutting plane proof for the validity of an inequality. We characterize s based on the faces of the linear relaxation of the mixed integer linear set. [less ▲] Detailed reference viewed: 88 (17 ULg)Certificates of linear mixed integer infeasibility ; Louveaux, Quentin ; in Operations Research Letters (2008), 36(6), 734-738 We derive a certificate of integral infeasibility for linear systems with equations and inequalities by generating algebraically an outer description of a lattice point free polyhedron that contains the ... [more ▼] We derive a certificate of integral infeasibility for linear systems with equations and inequalities by generating algebraically an outer description of a lattice point free polyhedron that contains the given integer infeasible system. The extension to the mixed integer setting is also derived. [less ▲] Detailed reference viewed: 96 (18 ULg)Inequalities from two rows of the simplex tableau ; Louveaux, Quentin ; et al in Fischetti, Matteo; David P., Williamson (Eds.) Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings. (2007, June) In this paper we explore the geometry of the integer points in a cone rooted at a rational point. This basic geometric object allows us to establish some links between lattice point free bodies and the ... [more ▼] In this paper we explore the geometry of the integer points in a cone rooted at a rational point. This basic geometric object allows us to establish some links between lattice point free bodies and the derivation of inequalities for mixed integer linear programs by considering two rows of a simplex tableau simultaneously. [less ▲] Detailed reference viewed: 144 (14 ULg)Cutting planes from two rows of the simplex tableau (extended version) ; Louveaux, Quentin ; et al E-print/Working paper (2006) Detailed reference viewed: 85 (3 ULg) |
||