Invited Session Wed.1.H 2032

Wednesday, 10:30 - 12:00 h, Room: H 2032

Cluster 11: Integer & mixed-integer programming [...]

Trends in mixed integer programming IV


Chair: Robert Weismantel and Andrea Lodi



Wednesday, 10:30 - 10:55 h, Room: H 2032, Talk 1

François Soumis
Integral simplex using decomposition

Coauthors: Issmail Elhallaoui, Abdelouahab Zaghrouti


Since the early '70s, several authors proposed, without much success, adaptations of the simplex algorithm to reach an optimal integer solution to the set-partitioning problem, with a sequence of basic integer solutions. We present an algorithm that iteratively finds improving integer solutions up to optimality. The algorithm identifies the negative reduce cost columns producing integer pivots. If it has no more of these columns the algorithm solves a subproblem identifying a small group of columns to pivot in the base to reach a better integer solution. These two procedures permit to reach an optimal solution. Theoretical background and experimental results on problems up to 1600 constraints and 500,000 variables are presented. The larger problems are solved in time between 10 and 20 minutes.



Wednesday, 11:00 - 11:25 h, Room: H 2032, Talk 2

Enrico Malaguti
Algorithms for 2-dimensional 2-staged guillotine cutting stock problems

Coauthor: Fabio Furini


Given a set of rectangular items classes with an associated positive demand and infinitely many identical rectangular bins, the 2-dimensional cutting stock problem requires cutting all the items by using the minimum number of bins or, equivalently, by minimizing the global area of the used bins. We consider the 2-dimensional 2-staged guillotine cutting stock problem, where items must be obtained through at most two stages of guillotine cuts (we allow trimming, i.e., a third stage cut can be used to separate a rectangle from a waste area). The problem is a generalization of the corresponding 2-dimensional bin packing problem, where the demand is equal to 1 for all the item classes.
In this talk we describe a branch-and-price algorithm for the problem, and discuss the adaptation of generic branching rules to the specific case. In addition, we extend a compact integer linear programming model from the literature, proposed for the bin packing case, to the more general cutting stock problem.
The performance of the proposed models and solution algorithms is evaluated through computational experiments on a set of benchmark instances from the literature.



Wednesday, 11:30 - 11:55 h, Room: H 2032, Talk 3

Friedrich Eisenbrand
On bin packing, the MIRUP conjecture and discrepancy theory

Coauthors: Dömötör Pálvölgyi, Thomas Rothvoß


Bin packing a classical combinatorial optimization problems for which the development of approximation algorithms and integer programming methods is an impressive success story. Yet, a prominent problem related to bin-packing is still open: Is there an OPT+1 approximation algorithm and does the column-generation ILP of Gilmore and Gomory have a constant additive integrality gap?
In this talk, I survey some recent results around this open problem that deal with a relationship of approximation algorithms for bin packing and discrepancy theory. In particular, I describe the limits of LP-rounding for bin packing that are implied by a recent lower bound on the discrepancy of three permutations by Newman and Nikolov.


  pay day loans . On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.