Invited Session Mon.1.MA 004

Monday, 10:30 - 12:00 h, Room: MA 004

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

Advances in integer programming


Chair: Shmuel Onn



Monday, 10:30 - 10:55 h, Room: MA 004, Talk 1

Antoine Deza
Combinatorial, computational, and geometric approaches to the colourful simplicial depth

Coauthors: Frédéric Meunier, Tamon Stephen, Feng Xie


In statistics, there are several measures of the depth of a point p relative to a fixed set S of sample points in dimension d. One of the most intuitive is the simplicial depth of p introduced by Liu (1990), which is the number of simplices generated by points in S that contain p. Obtaining a lower bound for the simplicial depth is a challenging problem. Carathéodory's Theorem can be restated as: The simplicial depth is at least 1 if p belongs to the convex hull of S. Bárány (1982) showed that the simplicial depth is a least a fraction of all possible simplices generated from S. Gromov (2010) improved the fraction via a topological approach. Bárány's result uses a colourful version of the Carathéodory's theorem leading to the associated colourful simplicial depth. We present recent generalizations of the Colourful Carathéodory's theorem due to Arocha et al. and Homlsen et al. and our strengthening of these. We provide a new lower bound for the colourful simplicial depth improving the earlier bounds of Bárány & Matoušek and of Stephen & Thomas. Computational approaches for small dimension and the colourful linear programming feasibility problem introduced by Bárány & Onn are discussed.



Monday, 11:00 - 11:25 h, Room: MA 004, Talk 2

Justo Puerto
Ordered weighted average optimization of combinatorial problems


This talk addresses a class of combinatorial optimization models that include among others, bottleneck, k-centrum, general balanced, lexicographic, ordered median and universal optimization. These problems have been analyzed under different names for different authors in the last years (Calvete and Mateos (1998), De la Croce et al. (1999), Lee (1992), Nickel and Puerto (2005), Puerto and Tamir (2005), Punnen and Aneja (1996, 2004), Turner and Hamacher (2011), Turner et al. (2011)). We study the common framework that underlines those models, present different formulations as integer programs and study their relationships and reinforcements. This approach leads to a branch and cut algorithm applicable to he general problem which is effective up to median size instances. For some specific cases we also analyze specific properties leading to polynomial time combinatorial algorithms.



Monday, 11:30 - 11:55 h, Room: MA 004, Talk 3

Matthias Köppe
A discretization-free FPTAS for polynomial optimization over the mixed-integer points in a class of polytopes of varying dimension

Coauthors: Nicole Berline, Michèle Vergne


We present a new fully polynomial-time approximation scheme for the
problem of optimizing non-convex polynomial functions over the
mixed-integer points of a polytope of fixed dimension. This improves
upon earlier work that was based on discretization [De Loera,
Hemmecke, Köppe, Weismantel, FPTAS for optimizing polynomials~ … ,
Math. Prog. Ser. A 118 (2008), 273-290]. The algorithm also extends
to a class of problems in varying dimension.
The algorithm is based on the study of intermediate sums,
interpolating between integrals and discrete sums, initiated by
A. Barvinok [2006] and continued by Baldoni, Berline, De Loera, Köppe,
Vergne [Computation of the highest coefficients~ … ,
Found. Comput. Math. 2012] and Baldoni, Berline, Köppe, Vergne
[Intermediate sums on polyhedra~ … , Mathematika 2012]. For a given
polytope P with facets parallel to rational hyperplanes and a rational
subspace L, we integrate a given polynomial function h over all
lattice slices of the polytope P parallel to the subspace L and sum up
the integrals.
This is the culmination of an effort to extend the efficient
theory of discrete generating functions to the mixed-integer case.


  payday loan . In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.