Simple and Efficient Search Procedures for Combinatorial Optimization
- Speaker
Serdar Kadioglu
, Brown University, USA
- Date and Time
Thursday, May 27th, 2010 at 13:30
- Location
Polacksbaken, room 2214
- Abstract
-
Solving combinatorial problems is an interplay between inference and search. In this talk, we focus on the search aspect and present one complete and one incomplete search procedure.
We start with 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.
We then present a local search meta-heuristic inspired by Hegel and Fichte's dialectic. Dialectic is an appealing mental concept for local search as it tightly integrates and yet clearly marks off of one another the two most important aspects of local search algorithms, search space exploration and exploitation. We illustrate dialectic search, its simplicity and great efficiency on problems from highly different problem domains.
Joint work with Meinolf Sellmann