References of "Weismantel, Robert"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailMixed-integer sets from two rows of two adjacent simplex bases
Andersen, Kent; Louveaux, Quentin ULg; Weismantel, Robert

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 findings 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. Specifically, 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: 102 (18 ULg)
Full Text
Peer Reviewed
See detailAn analysis of mixed integer linear sets based on lattice point free convex sets
Andersen, Kent; Louveaux, Quentin ULg; Weismantel, Robert

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 finite 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 finite 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: 79 (17 ULg)
Full Text
Peer Reviewed
See detailCertificates of linear mixed integer infeasibility
Andersen, Kent; Louveaux, Quentin ULg; Weismantel, Robert

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: 86 (18 ULg)
Full Text
Peer Reviewed
See detailIntermediate integer programming representations using value disjunctions
Köppe, Matthias ULg; Louveaux, Quentin ULg; Weismantel, Robert

in Discrete Optimization (2008), 5(2), 293-313

We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The ... [more ▼]

We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formu- lation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet descrip- tion decomposes into one “linking polyhedron” per block and the “aggre- gated polyhedron”. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coeffi- cients, this theorem provides a complete description in an extended space with a polynomial number of variables. Based on this theory, we propose a new branching scheme that analyzes the problem structure. It is designed to be applied in those subproblems of hard integer programs where LP-based techniques do not provide good branching decisions. Preliminary computational experiments show that it is successful for some benchmark problems of multi-knapsack type. [less ▲]

Detailed reference viewed: 56 (9 ULg)
Full Text
Peer Reviewed
See detailPolyhedral properties for the intersection of two knapsacks
Louveaux, Quentin ULg; Weismantel, Robert

in Mathematical Programming (2008), 113(1), 15-37

We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out ... [more ▼]

We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out that the sign patterns of the weight vectors are responsible for the types of combinatorial valid inequalities appearing in the description of the convex hull of the intersection. In partic- ular, we introduce the notion of an incomplete set inequality which is based on a combinatorial principle for the intersection of two knapsacks. We outline schemes to compute nontrivial bounds for the strength of such inequalities w.r.t. the intersection of the convex hulls of the initial knapsacks. An extension of the inequalities to the mixed case is also given. This opens up the possibility to use the inequalities in an arbitrary simplex tableau. [less ▲]

Detailed reference viewed: 88 (13 ULg)
Full Text
Peer Reviewed
See detailInequalities from two rows of the simplex tableau
Andersen, Kent; Louveaux, Quentin ULg; Weismantel, Robert 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: 130 (14 ULg)
Full Text
See detailCutting planes from two rows of the simplex tableau (extended version)
Andersen, Kent; Louveaux, Quentin ULg; Weismantel, Robert et al

E-print/Working paper (2006)

Detailed reference viewed: 71 (3 ULg)
Full Text
Peer Reviewed
See detailExtended formulations for Gomory Corner polyhedra
Köppe, Matthias ULg; Louveaux, Quentin ULg; Weismantel, Robert et al

in Discrete Optimization (2004), 1(2), 141-165

We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory’s group relaxations. We present algorithmic schemes based on an iterative ... [more ▼]

We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory’s group relaxations. We present algorithmic schemes based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation. [less ▲]

Detailed reference viewed: 65 (4 ULg)