The Speaker

Meinolf Sellmann serves as Assistant Professor at Brown University since 2004. He received his Diploma of Computer Science in 1997 from Paderborn
University (Germany). After a year at Lucent Technology Bell Labs (Murray Hill, NJ) he returned to his alma mater in Paderborn in 1998 from where he
received his PhD in 2002. Before coming to Brown, he spent sixteen months as Postdoctoral Associate at Cornell University.

Professor Sellmann's research is driven by our society's need to increase its operational efficiency so that we can face the challenges that global
competition for limited natural resources poses to our aging and shrinking workforce. By integrating methods from artificial intelligence, algorithm
theory, and operations research, Sellmann's group focusses on providing efficient optimization technology which is easily accessible to general computer scientists. Main contributions of his research are the development of efficient filtering algorithms for Knapsack, Shortest Path, and Grammar Constraints, Symmetry Breaking by Dominance Detection, Structural Symmetry Breaking, Streamlined Constraint Reasoning, CP-based Column Generation, CP-based Lagrangian Relaxation, and the introduction of associated theoretical notions like Relaxed Consistency and Approximated Consistency.

AG 1, AG 3, AG 5, SWS, AG 2, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

Feasibility in Combinatorial Optimization

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

Kurt Mehlhorn

--email hidden

passcode not visible

logged in users only