Optimization on Friday

Optimization on Friday is a biweekly seminar that focuses on topics related to mathematical optimization. Topics can be theoretic or applied in nature and range anywhere from unpolished ideas and interesting problems to published results.

As of oktober 2016, the seminar is organised by dr. Theresia van Essen.
Visit the new seminar page.

2015 – 2016

10 Jun

Topic: A new look at duality in convex optimization via Fenchel’s duality theorem.
Speaker: Kees Roos

The dual problem of a convex optimization problem can be obtained in a relatively simple and structured way by using a well-known result in convex analysis, namely Fenchel's duality theorem. This alternative way of forming a strong dual problem is the subject in this talk. We recall some standard results from convex analysis and then discuss how the dual problem can be written in terms of the conjugates of the objective function and the constraint functions. We demonstrate the method by deriving dual problems for several classical problems and also for a practical model for radiotherapy treatment planning.

Coordinates: 10 June, 15h00 in Van Katwijkzaal (HB03.240).

6 Jun

Topic: (Citi)bike Sharing
Speaker: Shane Henderson (Cornell University)

Citibike has provided a bike-sharing service in New York City since March of 2013. We have assisted with their logistics since that time. The central decision in New York is one that is common to all bike-sharing programs, namely where bikes and racks should be positioned around the city.

I will discuss a stochastic model of bike flows and an optimization model that uses the results from the stochastic model. This optimization model is a nonlinear integer program in approximately 700 variables. Geometric and coupling arguments reduce the problem to a linear (integer) program, which we can solve to optimality. The resulting plans yield substantial improvements in performance, and Citibike has adopted this work in its planning. I will also describe a simulation-optimization approach that determines a bike allocation assuming a fixed rack allocation, and that differs substantially from the usual simulation-optimization approaches used by the simulation community. Perhaps surprisingly, the simulation optimization yields much more than modest additional improvements over and above those obtained above.

Joint work with Ph.D. students Daniel Freund, Nanjing Jian, Eoin O'Mahony, several undergraduate researchers, and David Shmoys.

Coordinates:Monday 6 June, 13h00 in classroom F (EEMCS building).

3 Jun


27 May

Diamant symposium

20 May

Topic: Two-echelon supply chain coordination under information asymmetry
Speaker: Rutger Kerkkamp (EUR)
Coordinates:20 May, 14h00 in room Vassiliadis (HB10.230).

Topic: Reputation in distributed systems using flow
Speaker: Pim Otte
Coordinates: 20 May, 15h00 in room Vassiliadis (HB10.230).

13 May

Topic: Coding.
Speaker: Jos Weber
Coordinates: 13 May, 15h00 in room Vassiliadis (HB10.230).

22 Apr

Topic: Algorithm for the Vehicule Routing Problem with Time Windows
Speaker: Joris van Tatenhove
Coordinates: 22 April, 15h00 in room Vassiliadis (HB10.230).

15 Apr

Topic: Approximation algorithms for partition functions.
Speaker: Guus Regts (UvA)

Partition functions of edge-coloring models are graph parameters closely related to counting graph homomorphisms. They appear in several academic disciplines; e.g. as Lie algebra weight systems in the theory of Vassiliev knot invariants, as Holant problems in theoretical computer science, as tensor networks in quantum information theory and as partition functions of vertex models in statistical physics.

In this talk I will describe a quasi polynomial time approximation algorithm for partition functions of a certain class of edge-coloring models.

Coordinates: 15 April, 15h00 in room Lipkens (LB 01.050).

12 Apr

Topic: Lazy Max Weight scheduling algorithms for maximum stability in networks with reconfiguration delays.
Speaker: Phil Whiting (Macquarie University, Australia)

We consider the scheduling problem for networks with interference constraints and reconfiguration (switching) delays, which is the duration of time when one (feasible) service schedule is dropped and a distinct service schedule is adopted. Such delays occur in many telecommunication applications e.g. optical transceiver tuning a light-path or mobile servers gathering data from sensors. Under zero reconfiguration delay it is well known that the Max-Weight scheduling algorithm is throughput-optimal without requiring knowledge of arrival rates.

We show that this property of Max-Weight no longer holds when there is a nonzero reconfiguration delay. We then go on to show that a class of algorithms which can be loosely termed Lazy Max-Weight policies in which service configurations are persisted do achieve the full stability region. These include variable frame-based Max-Weight (VFMW) algorithms, as well as Switching Curve Based (SCB) policies. For these latter algorithms the time to the next reconfiguration is not determined in advance.

In the final part of the talk, numerical results are presented for the SCB and VFMW policies and some issues connected with delay performance are discussed.

This is joint work with Sem Borst, Guner Celik and Eytan Modiano.

Coordinates:Tuesday 12 April, 13h00 in room Pi.

8 Apr

Topic: An Optimal Affine-Invariant Smooth Minimization Algorithm.
Speaker: Cristobal Guzman (CWI)

We formulate an affine invariant implementation of the Nesterov Accelerated Method. We show that the complexity bound is then proportional to an affine invariant regularity constant defined with respect to the Minkowski gauge of the feasible set. We also detail matching lower bounds when the feasible set is an lp ball. In this setting, our bounds on iteration complexity for a variant of the Nesterov Accelerated Method (Nesterov & Nemirovski:1985) are thus optimal in terms of target precision, smoothness and problem dimension.

Based on joint work with Alexandre d'Aspremont and Martin Jaggi.

Coordinates: 8 April, 15h00 in room Vassiliadis (HB10.230).

5 Feb

Topic: Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach.
Speaker: Frank Permenter (MIT)

The self-dual embedding method (implemented in solvers such as SeDuMi) is a popular technique for solving conic optimization problems. This method fails when both complementary solutions and improving rays do not exist, which in turn occurs only if Slater's condition does not hold.

We show this method can succeed in all cases if modified in a simple way. Specifically, we identify and exploit a connection with facial reduction, a technique for regularizing problems that fail Slater's condition. This modified method can, in principle, find and certify the optimal value of an arbitrary conic optimization problem, and, for the case of semidefinite programming, is implementable using basic linear algebra and central-path-following techniques.

This is joint work with Henrik A. Friberg and Erling D. Andersen.

Coordinates: 5 February, 15h00 in room Vassiliadis (HB10.230).

2014 – 2015

5 Jun

Topic: Improving the CADANS solver to find a feasible timetable for Dutch Railways.
Speaker: Gert-Jaap Polinder
Coordinates: 5 June, 15h00 in room HB4.140.

1 May

Topic: Approximation of a priori routing problems.
Speaker: Martijn van Ee (VU)
Coordinates: 1 May, 15h00 in room LB 01.050 (Lipkens).

17 Apr

Topic: Shortest vector problem.
Speaker: Daniel Dadush (CWI)

See: arxiv paper.

Coordinates: 17 April, 15h00 in room HB4.140.

10 Apr

Topic: Decision support system for mobile cellular networks
Speaker: Sander Gribling
Coordinates: 10 April, 15h00 in room HB4.140.

20 Mar

Topic: Distributed route discovery in networks using neighbour information
Speaker: Pieter Kleer
Coordinates: 20 March, 15h00 in room HB4.140.

6 Mar

Topic: Reconstructing phylogenetic networks from subnetworks
Speaker: Leo van Iersel
Coordinates: 6 March, 15h00 in room HB9.150 (Dijkstra).

20 Feb

Topic: Efficient Approximation of Quantum Channel Capacities

The capacity of a quantum channel characterizes the ultimate rate at which information can be transmitted reliably over the channel. To compute it, however, turns out to be difficult. In this work, we introduce a framework that bridges recent techniques from convex optimization with quantum information theoretic problems. We propose an iterative algorithm to efficiently approximate the capacity of channels with a classical input and a quantum mechanical output. The method, using the idea of a universal encoder, can be extended to approximate the Holevo capacity for channels with a quantum mechanical input and output. In particular, we show that the problem of computing the Holevo capacity can be reduced to a multidimensional integration problem. For certain families of channels we prove that the complexity to derive an additive $\varepsilon$-close solution to the Holevo capacity is subexponential or even polynomial in the problem size.

Speaker: David Sutter (ETHZ)
Coordinates: 20 Feb, 15h00, location: HB9.150 (Dijkstrazaal)

16 Jan

Topic: How the Experts Algorithm Can Help Solve LPs Online

We consider the problem of solving packing/covering LPs online, when the columns of the constraint matrix are presented in random order. This problem has received much attention: the main open question is to figure out how large the right-hand sides of the LPs have to be (compared to the entries on the left-hand side of the constraint) to get $(1+\e)$-approximations online? It is known that the RHS has to be $\Omega(\e^{-2} \log m)$ times the left-hand sides, where $m$ is the number of constraints.

In this paper we give a primal-dual algorithm to achieve this bound for all packing LPs, and also for a class of mixed packing/covering LPs. Our algorithms construct dual solutions using a regret-minimizing online learning algorithm in a black-box fashion, and use them to construct primal solutions. The adversarial guarantee that holds for the constructed duals help us to take care of most of the correlations that arise in the algorithm; the remaining correlations are handled via martingale concentration and maximal inequalities. These ideas lead to conceptually simple and modular algorithms, which we hope will be useful in other contexts.

(Joint work with Anupam Gupta.)

Speaker: Marco Molinaro
Coordinates: 16 Jan, 15h00 in room HB4.140

19 Dec

Topic: White-box optimization with learned models

One of the main challenges of mathematical optimization is to construct a mathematical model describing the properties of a system. When the structure of the system cannot be fully determined from the knowledge at hand, machine learning and data mining techniques have been used in optimization instead of such models. They have, for example, been used as decision values, fitness functions, or model parameters. These all use the learned models in a black-box manner, e.g., using only the predictions of learned models but not their internal structure. We develop a novel white-box optimization method, that is, we map entire models to a set of integer linear programming constraints such that the internal structure of the models is used during problem solving. We demonstrate experimentally on an auction design problem that this can increase the problem solving capabilities when the learned models are not overly complex.

In this talk, I will describe this method, our results, and highlight the differences with other methods for optimisation under uncertainty. In addition, I will describe new work on the WarmteWeb project where we will apply this method as a surrogate/approximation method for optimisation when the true models/simulators are too complex to optimize.

Speaker: Sicco Verwer
Coordinates: 19 Dec, 15h00 in room HB4.140

12 Dec

Topic: Gonality and chip-firing games on graphs
Speaker: Dion Gijswijt
Coordinates: 12 Dec, 15h00 in room HB4.140

21 Nov

Topic: Optimizing blading in the steppers of lithography machines; a TSP approach
Speaker: Teun Janssen
Coordinates: 21 Nov, 15h00 in room HB4.140

17 Oct

Topic: Chubanov's algorithm for linear optimization
Speaker: Kees Roos
Coordinates: 17 Oct, 15h00 in room HB4.140

26 Sep

Topic: Equivariant semidefinite lifts and sum-of-squares hierarchies
Speaker: David de Laat
Coordinates: 26 Sep, 15h00 in room HB4.140

Working group algebra and combinatorics


This working group was held at CWI and focused on the development of new techniques in combinatorics and optimization.

See this page for the (old) webpage for this seminar.