Computational Optimisation Group

Seminar: Generalized maximum entropy estimation
2019-02-26 14:00 - 15:00 UTC
Title: Generalized maximum entropy estimation
Speaker: Dr David Sutter
Affiliation: Institute for Theoretical Physics, ETH Zurich
Location: 217 Huxley Building
Time: 14:00 – 15:00
Abstract. We consider the problem of estimating a probability distribution that maximizes the entropy while satisfying a finite number of moment constraints, possibly corrupted by noise. Based on duality of convex programming, we present a novel approximation scheme using a smoothed fast gradient method that is equipped with explicit bounds on the approximation error.
This is joint work with T. Sutter, P. Esfahani, and J. Lygeros (arXiv:1708.07311).
Biography. Dr David Sutter is a postdoctoral researcher at ETH Zurich, working on mathematical aspects of quantum information theory. He obtained his PhD degree from the Institute for Theoretical Physics at ETH Zurich under the supervision of Prof. Renato Renner. Dr Sutter’s interests lie in the intersection of quantum mechanics, information theory, and mathematical physics. To understand the fundamental limits of information processing and communications, he utilizes tools from matrix analysis, optimization theory and probability theory.

Seminar: Data-Driven Methods for Integrated Production Scheduling and Process Control
2019-04-25 11:00 - 12:00 (Europe/London)
Title: Data-Driven Methods for Integrated Production Scheduling and Process Control
Speaker: Calvin Tsay
Affiliation: McKetta Dept of Chemical Engineering, University of Texas at Austin
Location: 218 Huxley Building
Time: 11:00 – 12:00
Abstract. Due to the fast-changing market conditions enabled by globalization and modern infrastructures, industrial production scheduling is often performed over relatively short time intervals to maximize profits. For chemical processes, plant dynamics and control become highly relevant at these shortened time intervals, and careful attention is required to ensure computed schedules are feasible when implemented in the physical process. With this motivation, many recent works focused on integrating dynamic information from the process control layer into production scheduling. Unfortunately, the resulting optimization problems are high-dimensional and often intractable because of the broad range of time scales involved.
In this presentation, we describe data-driven techniques for learning low-order dynamic models of the behavior of a process and its controller (i.e., “closed-loop” behavior). Then, we formulate an optimal scheduling problem involving the learned, reduced-order representation of the relevant dynamics. Furthermore, we present a data-mining approach that exploits historical process data to reduce the dimensionality of the aforementioned dynamic models. Throughout the presentation, we will focus on applications to the scheduling of industrial air separation units, which consume immense amounts of electricity, in response to time-varying electricity prices (an operational strategy termed “demand response”). Several case studies will be presented, ranging from model-based analyses to a real-world application on an industrial air separation unit.

Seminar: Exact and heuristic MIP methods for the solution of MINLP - Examples from gas transport optimization problems
2019-05-02 13:30 - 14:30 (Europe/London)
Title: Exact and heuristic MIP methods for the solution of MINLP – Examples from gas transport optimization problems
Speaker: Dr Lars Schewe
Affiliation: Dept of Mathematics, FAU Erlangen-Nürnberg
Location: 217 Huxley Building
Time: 13:30 – 14:30
Abstract. In this talk, we present exact and heuristic methods for MINLP, the development of which was motivated by applications in gas transport optimization. In this talk, we present a sample of our approaches and focus on provable results for both the exact and the heuristic methods. The methods have been applied on both academic and real-world instances. We first discuss how to solve MINLPs using a hierarchy of piece-wise linear relaxations and discuss a convergence result for such an algorithm. We show how this algorithm performs on problems in instationary gas transport. We then show how we can use a combination of penalty and alternating-direction methods to solve difficult instances of gas transport optimization problems and on instances from the MINLPLib. For these methods, we can also give convergence results and discuss their relation to feasibility pump methods.

Seminar: Robust Discrete Optimization: Globalized Gamma Robustness and Radius of Robust Feasibility
2019-05-02 15:00 - 16:00 (Europe/London)
Title: Robust Discrete Optimization: Globalized Gamma Robustness and Radius of Robust Feasibility
Speaker: Prof. Dr Frauke Liers
Affiliation: Dept of Mathematics, FAU Erlangen-Nürnberg
Location: 217 Huxley Building
Time: 15:00 – 16:00
Abstract. In this talk, we extend the notion of two robust optimization methodologies that were originally introduced for continuous problems towards robust discrete tasks. On the one hand, we look at globalized robust optimization that has been proposed as a generalization of the standard robust optimization framework in order to allow for a controlled decrease in protection. It depends on the distance of the realized from the predefined uncertainty set. In this talk, we specialize the notion of globalized robustness to Gamma-uncertainty in order to extend its usability for discrete optimization. We show that the generalized robust counterpart possesses algorithmically tractable reformulations for mixed-integer linear nominal problems that use only slightly more variables and constraints than the standard robust counterpart under Gamma-uncertainty. For combinatorial problems, our globalized robust counterpart remains fixed-parameter tractable, although with a runtime exponential in Gamma. In computational studies, it turns out that our algorithmically tractable reformulations are not more difficult to solve than the respective standard robust counterparts, while globalized robustness is guaranteed. Secondly, we extend the notion of determining the radius of robust feasibility for a mixed integer linear problem (MIP) with uncertain constraints. The radius of robust feasibility (RRF) determines a value for the maximal size of the uncertainty set such that robust feasibility of the MIP can be guaranteed. We will analyze relations between the RRF of a MIP and its continuous relaxation. In contrast to the general setting of the literature, we extend the concept to computing the RRF to MIPs that might include safe constraints. Finally, we apply our methods to the standard benchmark set of the MIPLIB in order to test their performance and analyze the price of robustness with respect to the RRF.The work about Globalized Gamma Robustness is joint with Andreas Bärmann (FAU Erlangen-Nürnberg, Germany) and Christina Büsing (RWTH Aachen, Germany). The work about the radius of robust feasibility is joint with Lars Schewe and Johannes Thürauf (both FAU Erlangen-Nürnberg, Germany)

Seminar: Extremal Cuts and Isoperimetry in Random Cubic Graphs
2019-06-28 14:00 - 15:00 (Europe/London)
Title: Extremal Cuts and Isoperimetry in Random Cubic Graphs
Speaker: Prof. Gregory B. Sorkin
Affiliation: Dept of Mathematics, The London School of Economics and Political Science (LSE)
Location: LT139 Huxley Building
Time: 14:00 – 15:00
Abstract. The minimum bisection width of random cubic graphs is of interest because it is one of the simplest questions imaginable in extremal combinatorics, and also because the minimum bisection of (general) cubic graphs plays a role in the construction of efficient exponential-time algorithms, and it seems likely that random cubic graphs are extremal.
It is known that a random cubic graph has a minimum bisection of size at most 1/6 times its order (indeed this is known for all cubic graphs), and we reduce this upper bound to below 1/7 (to 0.13993) by analyzing an algorithm with a couple of surprising features. We increase the corresponding lower bound on minimum bisection using the Hamilton cycle model of a random cubic graph. We use the same Hamilton cycle approach to decrease the upper bound on maximum cut. We will discuss some related conjectures.

Seminar: Chordal Completions - Semidefinite Programming and Minimum Completions
2019-07-02 14:00 - 15:00 (Europe/London)
Title: Chordal Completions – Semidefinite Programming and Minimum Completions
Speaker: Dr Arvind Raghunathan
Affiliation: Mitsubishi Electric Research Laboratories (MERL)
Location: 217 Huxley Building
Time: 14:00 – 15:00
Abstract. A graph is chordal if every cycle of length at least four contains a chord, that is, an edge connecting two nonconsecutive vertices of the cycle. Chordal completion of a given undirected graph G is a chordal graph, on the same vertex set, that has G as a subgraph. Several classical applications in sparse linear systems, database management, computer vision, and SemiDefinite Programming (SDP) utilize chordal completions. The computation workload that results can be related to the number of edges that are added. Hence, finding the minimum number of edges that makes a graph chordal is important. We refer to this as the Minimum Chordal Completion Problem (MCCP). In this talk, we will present results on an application of completions in SDPs and the solution of MCCP.
Conversion approach, a decomposition based on chordal completions, is routinely used for solving large-scale SDPs. We show that the SDP resulting from the conversion approach is numerically degenerate under very mild assumptions. Numerical experiments on SDPLIB are provided to demonstrate the impact on solvers such as SDPT3 and SeDuMi.
We propose a new formulation for the MCCP which does not rely on finding perfect elimination orderings of the graph, as has been considered in previous work. We introduce several families of facet-defining inequalities for cycle subgraphs. Numerical studies combining heuristic separation methods based on a threshold rounding and lazy-constraint generation indicate that our approach substantially outperforms existing methods for the MCCP, solving many benchmark graphs to optimality for the first time.
Biography. Arvind Raghunathan is a Senior Principal Scientist at Mitsubishi Electric Research Laboratories (MERL). His research interests are in the development of algorithms for the solution of nonlinear and mixed integer programming problems with applications in electric grid operations, model predictive control, and transportation. Arvind’s research has found business impact in Mitsubishi’s products and has won top technical honors within MERL and Mitsubishi Electric Corporation. Arvind currently serves as an associate editor for Optimization & Engineering journal and as an expert of ANSI on the ISO Working Group on Smart Transportation. He obtained a Ph.D. from Carnegie Mellon University and a B.Tech from Indian Institute of Technology (Madras) both in Chemical Engineering. He worked for United Technologies Research Center for 7 years prior to joining MERL.

Seminar: Largest Small n-Polygons: Numerical Results and Conjectured Optima
2019-07-22 14:00 - 15:00 UTC
Title: Largest Small n-Polygons: Numerical Results and Conjectured Optima
Speaker: János D. Pintér
Affiliation: Department of Industrial and Systems Engineering, Lehigh University
Location: 218 Huxley Building
Time: 14:00 – 15:00

Abstract. LSP(n), the largest small polygon with n vertices, is defined as the polygon of unit diameter that
has maximal area A(n). Finding the configuration LSP(n) and the corresponding A(n) for even
values n >= 6 is a long-standing challenge that can be also perceived as class of hard global
optimization problems. We present numerical solution estimates for all even values 6 <= n <= 80,
using the AMPL model development environment with the LGO global-local solver engine option.
Our results are in close agreement with the results obtained by other researchers who tackled the
problem using exact approaches (for 6 <= n <= 20), and with the best results obtained using general
purpose numerical optimization software (for selected values from the range 6 <= n <= 100). Based
on our numerical results, we also present a regression model based estimate of {A(n)} for all even
values n >= 6.

Bio. János D. Pintér is a researcher and practitioner with over four decades of experience. His
general professional interests are related to Computational Optimization, Data Analytics, and
Operations Research (O.R.). His more specific primary area of expertise is nonlinear optimization,
including model, algorithm and software development, with a range of applications.
He received his M.Sc. in the area of Applied Mathematics / Operations Research from
Eötvös Loránd University, Hungary; Ph.D. in Probability Theory / Stochastic Optimization from
Moscow State University; and D.Sc. in Mathematics / Global Optimization from the Hungarian
Academy of Sciences.
As of 2019, Dr. Pintér wrote and edited ten books. He is also the author/co-author of more
than 200 journal articles, book chapters, proceedings contributions, book reviews, and research
reports. His monograph titled Global Optimization in Action received the 2000 INFORMS
Computing Society Prize for Research Excellence.
Among other professional affiliations, he serves on the editorial board of the Journal of
Global Optimization, and he is an editor of the book series SpringerBriefs in Optimization. He also
served as Global Optimization vice-chair of the INFORMS Optimization Society, and as a member
(later chair) of the Managing Board of EUROPT. Currently, he is a member of the Canadian and
the Hungarian Operations Research Societies, INFORMS, and EUROPT.
He has worked and presented lectures in about 40 countries of the Americas, Europe, the
Middle East, and the Pacific Region. His LGO software – with links to modeling languages and
scientific-technical computing systems – has been in use at hundreds of academic, business,
government, and research organizations.
In 2016, Dr. Pintér joined the Department of Industrial and Systems Engineering at Lehigh
University as a Professor of Practice. Since that time, he has been teaching a range of O.R. related
courses for undergraduate and graduate students, as well as ISE in-class and online (distance)
courses for healthcare engineering professionals.

Seminar with Prof. Greg Sorkin: Extremal Cuts and Isoperimetry in Random Cubic Graphs
2019-11-28 14:00 - 15:30 UTC | Huxley 217
The minimum bisection width of random cubic graphs is of interest because it is one of the simplest questions imaginable in extremal combinatorics, and also because the minimum bisection of (general) cubic graphs plays a role in the construction of efficient exponential-time algorithms, and it seems likely that random cubic graphs are extremal.
It is known that a random cubic graph has a minimum bisection of size at most 1/6 times its order (indeed this is known for all cubic graphs), and we reduce this upper bound to below 1/7 (to 0.13993) by analyzing an algorithm with a couple of surprising features. We increase the corresponding lower bound on minimum bisection using the Hamilton cycle model of a random cubic graph. We use the same Hamilton cycle approach to decrease the upper bound on maximum cut. We will discuss some related conjectures.

Seminar by prof. Miguel Anjos
2019-12-02 10:30 - 23:30 UTC | Huxley 217
Professor Miguel Anjos from the University of Edinburgh is giving a seminar on: Tight-and-Cheap Conic Relaxations for AC Optimal Power Flow and Optimal Reactive Power Dispatch

Abstract: The classical alternating current optimal power flow problem is nonconvex and generally hard to solve. We propose a new conic relaxation obtained by combining semidefinite optimization with RLT. The proposed relaxation is stronger than the second-order cone relaxation, competitive with the recently proposed QC relaxation, and up to one order of magnitude faster than for the semidefinite chordal approach on benchmarks with up to 6515 nodes, with comparable global bounds. We extend the approach to optimal reactive power dispatch, which requires the introduction of binary and integer variables, and obtain with similar results and performance.

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 UTC | 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 UTC
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
