Computational Optimisation Group

Seminar by Associate Professor Jakob Nordström
2019-12-06 14:00 - 15:30 UTC | Huxley 217
TITLE:
Learn to Relax: Integrating Integer Linear Programming with Conflict-Driven Search

ABSTRACT:
Pseudo-Boolean (PB) solvers optimize 0-1 integer linear programs by
extending the conflict-driven learning paradigm from SAT solving.
Though PB solvers should be exponentially more efficient than SAT
solvers in theory, in practice they can sometimes get hopelessly stuck
even when the relaxed linear program (LP) is infeasible over the
reals. Inspired by mixed integer programming (MIP), we address this
problem by interleaving incremental LP solving with cut generation
within the conflict-driven PB search. This hybrid approach, which for
the first time combines MIP techniques with full-blown conflict
analysis over linear inequalities using the cutting planes method,
significantly improves performance on a wide range of benchmarks,
approaching a “best of two worlds” scenario between SAT-style
conflict-driven search and MIP-style branch-and-cut.

Seminar by Prof. Oliver Stein (Cancelled due to the Covid-19 situation)
2020-03-23 14:00 - 15:00 | CPSE lecture theatre
Title: Pessimistic Bilevel Optimization
Pessimistic bilevel optimization problems, as optimistic ones, possess a structure involving
three interrelated optimization problems. Moreover, their finite infima are only
attained under strong conditions. We address these difficulties within a framework of moderate
assumptions and a perturbation approach which allow us to approximate such finite
infima arbitrarily well by minimal values of a sequence of solvable single-level problems.
To this end, as already done for optimistic problems, we introduce the standard version of
the pessimistic bilevel problem. For its algorithmic treatment, we reformulate it as a standard
optimistic bilevel program with a two follower Nash game in the lower level. The latter lower level
game, in turn, is replaced by its Karush-Kuhn-Tucker conditions, resulting in a single-level
mathematical program with complementarity constraints.
We show that the perturbed pessimistic bilevel problem, its standard version, the
two follower game as well as the mathematical program with complementarity constraints
are equivalent with respect to their global minimal points. We also highlight the more intricate
connections between their local minimal points. As an illustration, we consider a regulator problem
from economics.

Bio:
Oliver Stein is full professor at the Institute of Operations Research (IOR) at the Karlsruhe Institute of Technology (KIT).
He received his doctoral degree from the University of Trier in 1997, and his venia legendi from RWTH Aachen University in 2002.
His research covers algorithms and their theoretical foundation for continuous and mixed-integer nonlinear optimization problems,
parametric optimization, multi-leader-multi-follower games, and multi-objective optimization. Oliver was fellow of the Friedrich-Ebert
Foundation, the Alexander-von-Humboldt Foundation, and the German Research Foundation (Heisenberg followship), and received various
teaching awards. Oliver is member of MOS, SIAM, GAMM, GOR, and DMV. Since 2015 he acts as Editor-in-Chief of MMOR.

Seminar: Bayesian Optimization in Molecule Space: Challenges and Opportunities
2024-01-19 14:00 - 15:00
Title: Bayesian Optimization in Molecule Space: Challenges and Opportunities
Speaker: Austin Tripp
Affiliation: University of Cambridge
Location: Huxley 315
Abstract. Rational design of experiments in chemistry is one of the most commonly mentioned applications of Bayesian optimization (BO). Therefore you might presume that existing BO algorithms for chemistry are well-developed. In this talk I explain how performing BO on the discrete, structured space of molecules introduces extra complexity to BO which standard methods do not handle well. I will outline specific problems and potential avenues for solving them, in addition to covering some recent work in this area. All are welcome, but the target audience for this talk is optimization researchers interested in the fundamental algorithmic problems which chemistry applications present.
Biography. Austin Tripp is a final-year PhD student at Cambridge researching ML methods for molecules. More info on his website austintripp.ca
