## 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**

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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.