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


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


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


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.


  There are three major facts that should be watched out for in all payday loans in the United States. In rare cases, the smarting in eyes, the tumefaction of eyelids, nausea and headaches can happen. In case of long term Levitra Soft online administration the side effects become less perceptible or disappear at all.