TITLE: Feasibility in Combinatorial Optimization

SPEAKER: Dr. Meinholf Sellmann

ABSTRACT:

It is well-known that constrained optimization and constraint satisfaction problems are closely related in that being able to solve one allows solving the other. For example, the classic two-phase simplex algorithm reduces the problem of finding a feasible solution to a linear optimization problem for which achieving feasibility is trivial. Conversely, the ellipsoid algorithm reduces the linear optimization problem to a linear feasibility problem.

We study two problems on the intersection of constrained optimization and constraint satisfaction. The first regards the idea to simplify optimization problems based on feasibility and optimality considerations. We devise an expected amortized sub-linear time algorithm for the simplification of Knapsack problems and present numerical results which show speed-ups of two orders of magnitude compared to the former state-of-the-art.

The second problem regards binary search which is frequently used to augment a feasibility solver to handle optimization problems. In this setting, we often observe that negative trials (i.e. showing that a certain solution quality cannot be achieved) is significantly harder than positive trials. We consider a simple cost-model where negative trials cost a constant factor more than positive trials and show how, in this setting, binary search can be biased optimally to achieve optimal worst-case and average-case performance.

Joint work with Serdar Kadioglu, Irit Katriel, Eli Upfal, and Pascal Van Hentenryck.