Feasibility in Combinatorial Optimization

Event Details
  • Date/Time:
    • Tuesday May 12, 2009 - Wednesday May 13, 2009
      2:00 pm - 2:59 pm
  • Location: TBA
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Anita Race
H. Milton Stewart School of Industrial and Systems Engineering
Contact Anita Race

Summary Sentence: Feasibility in Combinatorial Optimization

Full Summary: Feasibility in Combinatorial Optimization

TITLE: Feasibility in Combinatorial Optimization

SPEAKER: Dr. Meinholf Sellmann


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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 12, 2009 - 4:35pm
  • Last Updated: Oct 7, 2016 - 9:47pm