Conference 2023
Top image

 
Home
Program
Invited Speakers
PhD student presentations
Registration
Registration for seminar only
Participants
Location
Previous conferences
 
Return to LNMB Site
 

48th CONFERENCE
Tuesday | Abstracts of presentations by PhD students II

 

Session A

 

Integrality Gaps for Random Integer Programs via Discrepancy

 

Session A: St. Jan-zaal

Sander Borst - sander.borst@cwi.nl

Tuesday, 11.00 - 11.25

Supervisor: Daniel Dadush

 

 

The Branch-and-Bound algorithm is a well-known method for solving integer linear programs. In the worst case this algorithm achieves an exponential running time, but until recently very little about was known about its behaviour on random instances. We show that for certain classes of random ILP's, the running time is only polynomial. To prove this result we solve a discrepancy problem for random matrices using Fourier analysis.

 

 

Operational Railway Crew Planning with Individual Sharing-Sweet-and-Sour Rules

 

Session A: St. Jan-zaal

Bart van Rossum - vanrossum@ese.eur.nl

Tuesday, 11.25 - 11.50

Supervisors: Dennis Huisman, Twan Dollevoet

 

 

Railway operators typically employ large numbers of drivers and guards, and are interested in providing them with fair and attractive working conditions. At Netherlands Railways (NS), the largest passenger railway operator in the Netherlands, this challenge is addressed through the use of Sharing-Sweet-and-Sour rules, which specify a fair allocation of sweet (attractive) and sour (unattractive) work over the different crew bases. While these rules are currently implemented at the crew base level and in the tactical planning phase, NS is considering formulating these rules at the individual level and in the operational planning phase. This gives rise to a new problem, which we call the operational railway crew planning problem with individual Sharing-Sweet-and-Sour rules. We propose a rolling horizon approach based on a column generation heuristic to solve this problem, which is able to achieve high satisfaction levels of the individual rules on several large real-life instances from NS. Our approach is not only relevant to railway operators, but can be applied in any setting where work must be fairly allocated to individuals in a dynamic fashion.

 

Dealing with Uncertainty in Energy Planning Optimization Problems

 

Session A: St. Jan-zaal

Justin Starreveld - j.s.starreveld@uva.nl

Tuesday, 11.50 - 12.15

Supervisors: Dick den Hertog, Zofia Lukszo

 

 

Strategic long term energy planning requires a large scope and long time horizon. The parameters of such models are often subject to much uncertainty and ignoring this uncertainty may lead to faulty or even disastrous decision making. In this talk I will explain the concept of robustness analysis, and argue for its practical usefulness over the more conventional sensitivity analysis. We extend the methodology to a multistage adaptive setting and apply the methodology to a hydrogen supply chain network design problem.

 

 

 

Sum of squares approximations for the cone of copositive matrices and associated bounds for the stability number of a graph

 

Session A: St. Jan-zaal

Luis Felipe Vargas - luis.vargas@cwi.nl

Tuesday, 12.15 - 12.40

Supervisor: Monique Laurent

 

 

The cone of copositive matrices COP_n is the set of nxn real symmetric matrices M for which the quadratic form x^TMx is nonnegative over the nonnegative orthant. Optimizing a linear function over the copositive cone is a hard problem in general since it permits to capture many hard combinatorial problems, including the maximum stable set problem. In this talk we first consider several hierarchies of approximations for COP_n that are based on sums of squares of polynomials and we present some links among them. Based on this we revisit the copositive formulation for the stability number of a graph and show new results on a conjecture proposed by de Klerk and Pasechnik in 2002. We finish with some open questions and new advances about the exactness of the sums of squares approximations for COP_n.

 

 

 

Session B

 

Trust and Fairness: Contracting on a Shared-based Platform

 

Session B: Congo-zaal

Ying Yin - y.yin@eur.nl

Tuesday, 11.00 - 11.25

Supervisors: Rob Zuidwijk, Simcha Jong Kon Chin

 

 

Trust and fairness regarding information and revenue sharing are key factors in the development of the sharing economy. We study a contracting problem between a platform and its content supplier, in which the platform can either offer to manage the content on behalf of the supplier and share revenue afterwards (contract A), or let the supplier manage his own content and report trade, while charging him a commission fee per reported trade (contract B). At the contracting stage, the platform decides how much revenue to share in contract A and the commission fee in contract B. In addition, the platform offers a revenue forecast in contract A to help the supplier better predict the revenue when his content is managed by someone else (i.e., the platform). The supplier decides which contract to accept based on utility maximization, considering his trust in the platform's disclosed revenue forecast in contract A and his fairness concern over the revenue-sharing ratios in both contracts. By developing a browser contracting game and getting 71 management-major students to play as the platform, we first demonstrate that our model has practical potentials. Using game-theoretical models, we then derive the optimal contracting mechanism in different scenarios. We show that the optimal contracts diverge into two categories: (1) a fair contract where the platform shares more of the content revenue with the supplier who has a higher fairness sensitivity; and (2) a trustworthy contract where the platform does not inflate or deflate its revenue forecast during the contracting process, considering its deception cost. We also find that the supplier with a higher fairness sensitivity will under-report the content revenue in the contract where he manages his own content. When facing the supplier who has a smaller deception cost, and is thus prone to cheat when reporting revenue, the platform will charge a larger commission fee. However, the larger the commission fee, the more the supplier will cheat.

 

 

 

Minimizing the Carry-Over Effect

 

Session B: Congo-zaal

Roel Lambers - r.lambers@tue.nl

Tuesday, 11.25 - 11.50

Supervisor: Frits Spieksma

 

 

The Carry-Over Effect in scheduling measures how many different pairs of consecutive opponents occur among all players in a competition. If this number is low, the Carry-Over Effect is said to be high, which is considered undesirable. A balanced Round Robin competition has every pair of consecutive opponents appear exactly once, but not for every number of players N, such a schedule exists. In fact, only when N is 20, 22, or a power of 2, such balanced schedules have been constructed. The limiting factor in finding new balanced schedules is among others the sheer number of possible Round Robin schedules. By restricting focus to specific types of promising schedules, we go on the hunt for these balanced schedules for large N.

 

 

An Improved Smoothed Analysis of 2-Opt for the Euclidean TSP

 

Session B: Congo-zaal

Jesse van Rhijn - j.vanrhijn@utwente.nl

Tuesday, 11.50 - 12.15

Supervisors: Bodo Manthey, Tjark Vredeveld

 

 

The 2-opt heuristic is a simple local search heuristic for the Travelling Salesperson Problem (TSP). Although it usually performs well in practice, its worst-case running time is poor. Attempts to reconcile this difference have used smoothed analysis, in which adversarial instances are perturbed probabilistically. We are interested in the classical model of smoothed analysis for the Euclidean TSP, in which the perturbations are Gaussian. This model was previously used by Manthey \& Veenstra, who obtained smoothed complexity bounds polynomial in $n$, the dimension $d$, and the perturbation strength $\sigma^{-1}$. However, their analysis only works for $d \geq 4$. The only previous analysis for $d \leq 3$ was performed by Englert, Roglin & Vocking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in $n$ and $\sigma^{−d}$, and super-exponential in $d$. As no direct analysis existed for Gaussian perturbations that yields polynomial bounds for all $d$, we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt.

 

 

Enhancing digital road networks for better operations in developing countries

 

Session B: Congo-zaal

Valentijn Stienen - v.f.stienen@tilburguniversity.edu

Tuesday, 12.15 - 12.40

Supervisors: Dick den Hertog, Joris Wagenaar, Hein Fleuren

 

 

Data scarcity in developing countries often significantly complicates the use of analytics to address development challenges. One of the most fundamental data structures needed in operations management is digitized road data; a poorly digitized road network significantly reduces our ability to optimize, for instance, trade of micro-enterprises (SDG 8) and placement of hospitals (SDG 3). Here, we introduce a method that accurately extends and combines large, existing road network representations, for regions with sparse geospatial data. Our method significantly improved the digital road network for smallholder farmers in Indonesia, and, in a case study of optimized geospatial accessibility to healthcare in Timor-Leste, it improved the detection of people located in the vicinity of a hospital.