Contributed Session Mon.1.H 2032

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

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

Integer programming algorithms I


Chair: Timm Oertel



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

Chuangyin Dang
A fixed-point iterative approach to integer programming and distributed computation

Coauthor: Yinyu Ye


Integer programming is concerned with the minimization of a linear function over integer or mixed-integer points in a polytope, which is equivalent under binary search to determining whether there is an integer or mixed-integer point in a polytope. Integer programming is an NP-hard problem and has many applications in economics and management. By constructing an increasing mapping satisfying certain
properties, we develop in this paper a fixed-point iterative method for integer programming. The self-dual embedding technique will be applied for a solution to a bounding linear program in the development. Given any polytope, within a finite number of iterations, the method either yields an integer or mixed-integer point in the polytope or proves no such point exists. As a very appealing feature for integer programming, the method can be easily implemented in a distributed way. Furthermore, the method can be applied to compute all integer or mixed-integer points in a polytope. Numerical results show that the method is promising.



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

Thomas Rehn
Exploiting symmetry in integer convex optimization using core points

Coauthors: Katrin Herr, Achill Schürmann


In this talk we consider symmetric convex programming problems with integrality constraints, that is, problems which are invariant under a linear symmetry group. We define a core point of such a symmetry group as an integral point for which the convex hull of its orbit does not contain integral points other than the orbit points themselves. These core points allow us to decompose symmetric integer convex programming problems.
In particular for symmetric integer linear programs we describe two algorithms which make use of this decomposition.
We characterize core points for some frequently occurring symmetry groups, in particular for direct products of symmetric groups. We use these results for prototype implementations, which can compete with state-of-the art commercial solvers on some highly symmetric problems and helped solving an open MIPLIB problem.



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

Timm Oertel
Convex integer minimization in fixed dimension

Coauthors: Christian Wagner, Robert Weismantel


We show that minimizing a convex function over the integer points of a bounded convex set is polynomial in fixed
dimension. For that, we present a geometric cone-shrinking algorithm. That is, we search for improving integer points within cones, reducing their volume step by step.


  payday loans online. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.