
Yves Crama
HEC Liège
Reformulations of nonlinear binary optimization problems
A pseudoBoolean function is a realvalued function
f(x)=f(x_{1},x_{2},...,x_{n}) of n binary
variables. It is wellknown that every pseudoBoolean function can be uniquely
represented as a multilinear polynomial in its variables. Nonlinear binary
optimization problems, or pseudoBoolean optimization (PBO) problems, of the
form min{ f(x) : x ∈ {0,1}^{n} } where f(x) is a
pseudoBoolean polynomial, have attracted the attention of numerous researchers
for more than 50 years. These problems are notoriously difficult, as they
naturally encompass a broad variety of models such as maximum satisfiability,
max cut, graph coloring, or image restoration. In this talk, I present recent
results (obtained in collaboration with Martin Anthony, Endre Boros, Christoph
Buchheim, Aritanan Gruber, and Elisabeth RodriguezHeck) regarding
reformulations of nonlinear PBO problems either as linear integer programming
problems or as quadratic PBO problems.


Daniel Kuhn
École polytechnique fédérale de Lausanne
From Data to Less Data to Decisions
The proliferation of “big data" created by mobile devices, social media,
sensor networks, satellites etc. offers the potential to make more informed
decisions, but it also poses a significant challenge to the scalability of the
current optimization methods and decision support tools. This raises a number
of fundamental questions: How should uncertain parameters in the big data
regime be represented so that they lend themselves to integration into
optimization problems? Which observations and features of a highdimensional
parameter set are most relevant for a particular optimization problem? How can
these relevant observations and features be identified efficiently? How can one
maintain the computational tractability of the emerging optimization problems?
In the first part of the talk I will introduce tractable approaches for
reducing large datasets to smaller ones at minimal loss of information. In the
second part I will describe tractable methods for recognizing balanced clusters
of similar datapoints in large unstructured datasets. Both methods come with
rigorous performance guarantees. Implications for practical decisionmaking
will be highlighted.
