## Invited Session Fri.2.H 2013

#### Friday, 13:15 - 14:45 h, Room: H 2013

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

### Trends in integer programming

**Chair: Jon Lee**

**Friday, 13:15 - 13:40 h, Room: H 2013, Talk 1**

**Amitabh Basu**

A *(k+1)*-slope theorem for the *k*-dimensional infinite group relaxation

**Coauthors: Robert Hildebrand, Matthias Koeppe, Marco Molinaro**

**Abstract:**

We prove that any minimal valid function for the *k*-dimensional infinite group relaxation that is piecewise linear with at most *k+1* slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for *k=1*, and CornuĂ©jols and Molinaro for *k=2*.

**Friday, 13:45 - 14:10 h, Room: H 2013, Talk 2**

**Siqian Shen**

Bilevel interdiction and risk-and-return tradeoffs in probabilistic programs with single or multiple chance constraints

**Abstract:**

Chance-constrained programs (CCP) measure value-at-risk of uncertain events, and impose a pre-given tolerance as an upper bound for such a risk. This paper focuses on problems with discretely distributed right-hand-sides in the chance constraints, and trades off risk and cost by also treating risk tolerances as decision variables. We first consider a problem with a single chance constraint in a bilevel interdiction setting, in which a leader decides a risk tolerance, to maximize a follower's objective of a minimization CCP. We show that only a finite number of possible tolerance thresholds matter to the follower's CCP, and interpret the risk tolerance variable as SOS1 binary variables. The bilevel program is then transformed into a deterministic IP. Similar results are used for solving a minimization problem with multiple chance constraints, where each has a risk tolerance variable and the summation of all tolerances is no more than a fixed budget. We develop an IP reformulation with multiple SOS1 binary variables, and solve it via decomposition and modified Benders cuts.

**Friday, 14:15 - 14:40 h, Room: H 2013, Talk 3**

**Christopher Thomas Ryan**

Computing pure Nash equilibria in symmetric games

**Coauthors: Albert Xin Jiang, Kevin Leyton-Brown**

**Abstract:**

We analyze the complexity of computing pure strategy Nash equilibria (PSNE) in symmetric games with a fixed number of actions. We restrict ourselves to "compact'' representations, meaning that the number of players can be exponential in the representation size. We give polynomial-time algorithms for finding a sample PSNE and counting the number of PSNEs.