*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
