Browse ORBi by ORBi project

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

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)Lifting, Superadditivity, Mixed Integer Rounding and Single Node Flow Sets Revisited Louveaux, Quentin ; in Annals of Operations Research (2007), 153(1), 47-77 In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure com- bining mixed integer rounding with lifting for ... [more ▼] In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure com- bining mixed integer rounding with lifting for the development of strong valid inequalities for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for mixed integer programs. The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive lifting which allows one to lift simultane- ously different sets of variables. In the second, our procedure for generating strong valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer rounding inequality, and superaddilifting. It is applied to several generalizations of the 0-1 single node flow set. [less ▲] Detailed reference viewed: 51 (10 ULg)Extended formulations for Gomory Corner polyhedra Köppe, Matthias ; Louveaux, Quentin ; 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: 72 (4 ULg)Lifting, Superadditivity, Mixed Integer Rounding and Single Node Flow Sets Revisited Louveaux, Quentin ; in 4OR : Quarterly Journal of the Belgian, French and Italian Operations Research Societies (2003), 1 In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure combining mixed integer rounding with lifting for the ... [more ▼] In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for mixed integer programs. The survey contains essentially two parts. In the first we present lifting in a very general way, empha- sizing superadditive lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong valid inequalities consists of reduction to a knapsack set with a single continuous variable, construc- tion of a mixed integer rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0-1 single node flow set. [less ▲] Detailed reference viewed: 110 (18 ULg)Combining problem structure and basis reduction to solve a class of hard integer programs Louveaux, Quentin ; in Mathematics of Operations Research (2002), 27(3), 470-484 We consider a hard integer programming problem that is difficult for the standard branch-and-bound approach even for small instances. A reformulation based on lattice basis reduction is known to be more ... [more ▼] We consider a hard integer programming problem that is difficult for the standard branch-and-bound approach even for small instances. A reformulation based on lattice basis reduction is known to be more effective. However the step to compute the reduced basis, even if it is found in polynomial time, becomes a bottleneck for small to medium instances. By using the structure of the problem, we show that we can decompose the problem and obtain the basis by taking the kronecker product of two smaller bases easier to compute. Furthermore, if the two small bases are reduced, the kronecker product is also reduced up to a reordering of the vectors. Computational results show the gain from such an approach. [less ▲] Detailed reference viewed: 66 (15 ULg) |
||