Cutting planes and infeasibility certificates from lattice-point-free polyhedra

Conference (2007, July)

A central result in the theory of integer optimization states that a system of linear diophantine equations Ax = b has no integral solution if and only if there exists a vector in the dual lattice, yT A ... [more ▼]

A central result in the theory of integer optimization states that a system of linear diophantine equations Ax = b has no integral solution if and only if there exists a vector in the dual lattice, yT A integral such that yT b is fractional. We extend this result to systems that both have equations and inequalities {Ax = b, C x ≤ d}. We show that a certificate of integral infeasibility is a linear system with rank(C) variables containing no integral point. The result also extends to the mixed integer setting. [less ▲]

Cutting planes from lattice-point-free polyhedra

Conference (2007, January)

In this talk, we generalize the concept of a split (that leads to split cuts) to any lattice-point-free polyhedron. We show how we can generate cutting planes for a polyhedron from these objects ... [more ▼]

In this talk, we generalize the concept of a split (that leads to split cuts) to any lattice-point-free polyhedron. We show how we can generate cutting planes for a polyhedron from these objects. Associated to any lattice-point-free polyhedron, we define a "split-dimension" (which is equal to 1 in the case of a split in the usual sense). We then consider the operation of adding to a polyhedron all cutting planes that we can obtain from considering all the lattice-point-free polyhedra with a split-dimension lower or equal to d. We call the obtained object the "d-dimensional split closure" of the initial polyhedron. We discuss whether this object is again a polyhedron or not. As an important illustration, we focus on objects of split-dimension equal to 1 or 2. [less ▲]

Cutting planes from two rows of the simplex tableau (extended version)

E-print/Working paper (2006)

Discrete optimization

Poster (2005, September)

Have you ever wondered what is the shortest route to join the office? What is the best way to plan a trip through several cities? You have maybe already played with magical squares? Then you have met one ... [more ▼]

Have you ever wondered what is the shortest route to join the office? What is the best way to plan a trip through several cities? You have maybe already played with magical squares? Then you have met one of the nu- merous instances of discrete optimization. Discrete optimization is a field of mathematics which deals with any problem where parts of the solutions cannot be divided or fractional. And as one may guess, this is the case in many real-life problems. This poster is divided in three main topics. The first part focuses on formulating those problems. We will start from one of the industrial appli- cations and show how we can model it as a mathematical problem. In the second part we sketch the main tools and algorithms used to tackle those problems. In particular we point out the fact that requiring integrality leads to extremely hard problems to solve. We show that despite this fact, we are able to solve problems of substantial size. However there remain some problems that are hard to solve using the state-of-the-art techniques. In the third part we indicate what are the chal- lenges of the field. In particular we will give an overview of the research car- ried out in the universities supported by the Marie-Curie network ADONET. [less ▲]

Exploring Structure and Reformulations in Different Integer Programming Algorithms

Doctoral thesis (2004)

In this thesis we consider four topics all related to using problem reformulations in order to solve integer programs, i.e. optimization problems in which the decision variables must be integer. We first ... [more ▼]

In this thesis we consider four topics all related to using problem reformulations in order to solve integer programs, i.e. optimization problems in which the decision variables must be integer. We first consider the polyhedral approach. We start by addressing the ques- tion of lifting valid inequalities, i.e. finding a valid inequality for a set Y from the knowledge of a valid inequality for a lower-dimensional restriction X of Y . We simplify and clarify the presentation of the procedure. This allows us to derive conditions under which the computation of the lifting is tractable. The second topic is the study of valid inequalities for the single node flow set. The single node flow set is the problem obtained by considering one node of a fixed charge network flow problem. We derive valid inequalities for this set and various generalizations. Our approach is a systematic procedure using only basic tools of integer programming: fixing and complementing variables, mixed- integer rounding and lifting. The method allows us to explain and generate a large range of inequalities describing the convex hull of such sets. The last two topics are based on non-standard approaches for integer pro- gramming. We first show how the group relaxation approach can be used to provide reformulations for the integral basis method. This is based on a study of extended formulations for the group problem. We present four extended for- mulations and show that the projections of three of these formulations provide the convex hull of the original group problem. Initial computational tests of the approach are also reported. Finally we consider a 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 re- duced basis is O(n4) and 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. Computa- tional results show the gain from such an approach. [less ▲]

Extended formulations for Gomory Corner polyhedra

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 ▲]

Lifting, Superadditivity, Mixed Integer Rounding and Single Node Flow Sets Revisited

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 ▲]