Open for all UnRAVeL Members: 2nd Gerhard Woeginger Research Colloquium of the Center of Algorithmics and Optimization

Thursday, July 6, 2023, 2:30pm

Location: SeMath, Pontdriesch 14-16

Schedule:
2:30 -- 2:40 pm: Welcome and news from the center
2:40 -- 3:45 pm: Dan Dadush (Networks & Optimization Group, CWI Amsterdam): Interior point methods are not worse than Simplex
3:45 -- 4:15 pm: Coffee Break in Math Lounge (3rd floor)
4:15 --5:15 pm: Contributed talks by  Murwan Siddig, Katharina Eickhoff, and Henri Lotze (all RWTH Aachen)

 

Abstracts:

 

Dan Dadush (Networks & Optimization group, CWI Amsterdam): 
Interior point methods are not worse than Simplex

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the classical simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighbourhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of n shadow vertex simplex paths. This is joint work with Xavier Allamigeon (INRIA / Ecole Polytechnique), Georg Loho (U. Twente), Bento Natura (LSE), Laszlo Vegh (LSE).



Murwan Siddig (Chair of Optimization of Distribution Networks, RWTH): 
Multistage Stochastic Programming with a Random Number of Stages: Applications in Hurricane Disaster Relief Logistics Planning

We present a logistics planning problem for prepositioning relief commodities in preparation for an impending hurricane landfall. We assume that the hurricane’s intensity, landfall time, and location evolve according to a Markov chain and model the problem as a multistage stochastic programming (MSP) problem with random number of stages. Our work is the first to introduce an MSP model with a random number of stages for the case where the stochastic process is stage-wise dependent. We benchmark the performance of the MSP model with several alternative decision policies, based on two-stage stochastic programming models, including a static policy, a rolling-horizon policy, and a decision tree-based policy. Our numerical results provide key insights into the value of MSP models in hurricane disaster relief logistics planning.



Katharina Eickhoff (Chair of Management Science, RWTH): 
Computation of Walrasian prices with an ascending auction based on matroid partition

Determining prices on a market where a seller aims to sell a finite set of indivisible distinguishable goods to a finite set of buyers is a well-studied problem with countless applications. Prices on the items are called Walrasian (equilibrium) prices if they admit an envy-free allocation of items to the buyers such that all items with positive prices are sold. Such Walrasian prices are guaranteed to exist if the buyers’ valuations are gross substitute, a concept introduced by Kelso and Crawford.
A very natural process to determine prices of the goods is an ascending auction, where prices are raised step by step on overdemanded sets. Provided that all buyers have gross substitute valuations, Gul and Stacchetti have shown that an ascending auction which iteratively raises prices on inclusion-wise minimal maximal overdemanded sets terminates with the (unique) componentwise minimal Walrasian price vector. It is by now known that an inclusion-wise minimal maximal overdemanded set can be computed in polynomial time with tools from discrete convexity. We present a simple and purely combinatorial polynomial time algorithm for their computation: we show that the desired overdemanded sets can be computed using the exchange graph of the classical matroid partitioning algorithm.
Moreover, we show that for gross substitute valuations the component-wise minimal prices that admit an envy-free allocation are the same as the minimal Walrasian prices. This enables us to show a very natural monotonicity of minimal Walrasian prices with respect to changes in supply and demand.
This is joint work with Britta Peis, Niklas Rieken, Laura Vargas Koch and Lázló A. Végh.


Henri Lotze (Chair of Theoretical Computer Science, RWTH): 
New Approaches to Relaxing Online Optimization

An online algorithm is a special kind of optimization algorithm that is required to take immediate and irrevocable decisions given only a prefix of an instance. In the design of such algorithms, one usually interested in bounding the worst-case ratio of the algorithm's solution in relation to the optimal solution on the same instance, which is commonly called the competitive ratio of an algorithm. In this talk, we explore two novel approaches of modifying the classical online model to better model real-life optimization. The first is that of so-called reservations, in which elements of the instance may be "made offline" for a price. The second model is that of predictions, in which the algorithm is given information about the upcoming instance. This information may however be flawed, up to a constant or multiplicative error. We discuss both models using the Online Simple Knapsack Problem as an example. This is joint work with Hans-Joachim Böckenhauer, Elisabet Burjons, Felix Frei, Matthias Gehnen, Juraj Hromkovič and Peter Rossmanith