Home

Aims & Objectives

Important Dates

Committees

Plenary Speakers

Registration

Abstract Submission

Conference Venue

Scientific Program

Social Program

Accommodation & Travel

Contact

Plenary Speakers

Confirmed Speakers

Yves Crama
HEC Liège

Reformulations of nonlinear binary optimization problems

A pseudo-Boolean function is a real-valued function f(x)=f(x1,x2,...,xn) of n binary variables. It is well-known that every pseudo-Boolean function can be uniquely represented as a multilinear polynomial in its variables. Nonlinear binary optimization problems, or pseudo-Boolean optimization (PBO) problems, of the form min{ f(x) : x ∈ {0,1}n } where f(x) is a pseudo-Boolean 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 Rodriguez-Heck) regarding reformulations of nonlinear PBO problems either as linear integer programming problems or as quadratic PBO problems.

John B. Gauci
University of Malta
Christos H. Papadimitriou
University of California at Berkeley
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 high-dimensional 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 decision-making will be highlighted.