Detailed Program

• Wednesday, April 22
• Thursday, April 23
• Friday, April 24

Wednesday, April 22

Session	Time
WA	09:30-10:30
WB	11:00-12:30
WC	13:30-15:00
WD	15:30-17:00

Wednesday 09:30-10:30 - Keynote 1

WA-1

Chair: Bernard Fortz

Room: 0/86

The Traveling Salesman Problem: Package Deliveries, Pub Walks, and Astro Tours

Amazon drivers hit the road every day, each taking a delivery van in a traveling salesman problem (TSP) tour through 150 or more customer stops. Such instances can be readily solved to exact optimality, but the choice of route may be constrained by warehouse sorting operations, van-loading processes, driver preferences, and other considerations. We propose a simple and efficient penalty-based local search algorithm for route optimization in the presence of such constraints. The algorithm was used to win the $100,000 top prize in the Amazon Last Mile Routing Challenge, together with Stephan Held and Keld Helsgaun. We also describe recent progress on exact and approximate solutions to large-scale challenge instances of the TSP, including a shortest-possible walking tour to 81,998 bars in Korea and a 3D tour to 136,606,128 stars, guaranteed to be no more than 1.000144 times longer than a shortest-possible tour.

Wednesday 11:00-12:30

WB-1

Chair: Nicolas Gillis

Room: 0/86

• A Learning Framework for Twin-Width and Related Problems
  Ryan O Connor, Johannes Meintrup, Maximilian Huber, Alexander Leonhardt, Manuel Penschuck, Yosuke Mizutani, Oscar Yeoh, and Deepak Ajwani

• Community detection via matrix factorization under the degree-corrected block model
  Alexandra Dache, Nicolas Gillis, and Arnaud Vandaele

• Soft classification trees: a decomposition algorithm with ILP-based sparsity and pruning
  Edoardo Amaldi, Antonio Consolo, and Filippo Gandini

WB-2

Chair: Marvin Weiler

Room: 0/88

• Towards 1-Resilient Local Fast Failover on Directed Graphs: Flip 1 Bit Once
  Erik van den Akker, Marvin Weiler, and Klaus-Tycho Foerster

• The Power of Symmetric Spanning Graphs in Public Transport
  Philine Schiewe, Irene Heinrich, Olli Herrala, and Piyalee Pattanaik

• Putting Tutte’s counterexample to Tait’s conjecture in perspective to (non-)Hamiltonicity in certain planar cubic graphs
  Enrico Iurlano, Herbert Fleischner, and Günther Raidl

WB-3

Chair: Yasemin Arda

Room: 1/82

• Balancing resource distribution for the healthcare districting problem
  Paulette Castillo, Sourour Elloumi, and Franco Quezada

• Energy-Aware Sequencing and Routing in Green Warehouses by Integrating Energy Management Systems and Renewable Energy
  Giacomo Lanza, Leena Aizdi, Mauro Passacantando, Maria Grazia Scutellà, Silvia Siri, and Stefano Bracco

• Models and Algorithms for the Consistent Travelling Salesman Problem with Vehicle Idling
  Juan José Salazar González and José Daniel Pascual Triana

Wednesday 13:30-15:00

WC-1

Chair: Walid Ben-Ameur

Room: 0/86

• Optimising peak cost over fractional temporally repeated flows
  Marius Schieren, Mariia Anapolska, and Christina Büsing

• Relaxations of the Delay-Constrained Maximum Concurrent Flow Problem
  Guillaume Beraud-Sudreau, Walid Ben-Ameur, and Sébastien Martin

• Supportedness in Multi-Objective Minimum Cost Flow Problem: Representation Quality and Output-Sensitive Complexity
  David Könen and Michael Stiglmayr

WC-2

Chair: Felix Engelhardt

Room: 0/88

• On Robust Min-Cut and Max-Flow under Uncertainty
  Deniz Akkaya and Mustafa Pinar

• Robust optimization on partial network design problem
  Dimitri Hubans, Sonia Cafieri, and Laurent Houssin

• Robust Minimum Weight Perfect Matchings
  Monja Raschke, Felix Engelhardt, and Christina Büsing

WC-3

Chair: Fernando Dias

Room: 1/82

• Solving the Shortest Path Labeling Problem with Reactive GRASP for In-Network Intrusion Detection
  Edoardo Scalzo, Floriano De Rango, Francesca Guerriero, Antonio Iera, Mattia Giovanni Spina, and Giovanni Terremoto

• Minimum flow decompositions from multiassembly problems to line planning
  Philine Schiewe and Fernando Dias

• Characterizing Path-Length Matrices of Unrooted Binary Trees
  Roberto Ronco, Daniele Catanzaro, and Raffaele Pesenti

Wednesday 15:30-17:00

WD-1

Chair: Elisabeth Gaar

Room: 0/86

• Stronger and faster semidefinite programming bounds for the p-median Quadratic Facility Location Problem
  Alexandre Salles da Cunha and Dilson Lucas Pereira

• Mixed-integer programming approaches for the p-α-center Problem
  Sara Joosten, Elisabeth Gaar, and Markus Sinnl

• On mixed-integer programming approaches for the alpha-neighbor p-center problem
  Markus Sinnl and Elisabeth Gaar

WD-2

Chair: Sachin Jayaswal

Room: 0/88

• Exact approach for the 2-Vertex-Connected Star problem
  Louis Kurdyk, André Rossi, and Sonia Toubaline

• Advancing Security and Sustainability in Cost-Effective Multi-Band Flexible-Grid Optical Networks: Optimization Models and Algorithms
  Hadhbi Youssouf, Diarrassouba Ibrahima, and Mahjoub A. Ridha

• A Branch-and-Price Algorithm for Train Stop Scheduling Problem
  Faiz Hamid, Ankit Meshram, and Sachin Jayaswal

WD-3

Chair: Philine Schiewe

Room: 1/82

• k-Truss Minimization by Bilevel Optimization
  Arie Koster, Jonas Kreyer, Ivana Ljubić, and Matthis Penz

• Convex Recoloring through Integer Programming: Formulations, Valid Inequalities, and Computational Experiments
  Boyue Lin, Phablo Moura, and Roel Leus

• Identification and analysis of essential nodes via centrality measure and maximum cliques
  Fernando Dias and Joona Lindell

Thursday, April 23

Session	Time
TA	09:00-10:30
TB	11:00-12:30
TC	13:30-14:30
TD	14:30-15:00

Thursday 09:00-10:30

TA-1

Chair: Markus Sinnl

Room: 0/86

• Automated Benders-like Cut Generation and its Application to the Bilevel Network Design Problem
  Vladimir Stadnichuk and Arie M.C.A. Koster

• Overlapping decompositions of Virtual Network Embedding
  Alexis Schneider, Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart, and Nancy Perrot

• Shortest Path Interdiction and Solution Diversity
  Felix Engelhardt

TA-2

Chair: Cristian Aguayo

Room: 0/88

• Drone-Based Emergency Response Network to Opioid Overdose
  Miguel Lejeune and Wenbo Ma

• Energy Community PV Facility Location Optimisation
  Paula Carroll, Debajyoti Biswas, and Dena Tayebi

• Valid Inequalities for the Vehicle Routing Problem with Drones
  Faiz Hamid and Yogesh Agarwal

TA-3

Chair: Jérôme De Boeck

Room: 1/82

• Accelerating Large-scale Network Capacity Planning via Set-cover-enhanced Benders Decomposition
  Eduardo Moreno, Babak Moazzez, Bruno de Backer, and Hugues Evrard

• Column Generation-Based Heuristic for the Sweep Coverage Problem
  Nicola Ronchini, Fabrizio Marinelli, and Andrea Pizzuti

• Joint Admission Control and Embedding of SFC Requests in a Stochastic Environment for Maximizing Network Revenue
  Daniela Cuesta, Olivier Brun, Matthieu Jonckheere, and Balakrishna Prabhu

Thursday 11:00-12:30

TB-1

Chair: Célia Paquay

Room: 0/86

• A two-stage stochastic programming approach for the optimal sizing of a one-way station-based electric car sharing network
  Céline Gicquel, Christian Clavijo-Lopez, and Mouna Kchaou-Boujelben

• Two-Stage Fixed-Charge Transportation Problem: A Polyhedral Study
  Sachin Jayaswal, Gopal Saha, Guneshwar Anand, and Manu Kumar Gupta

• Arc-flow formulations for a multiple bin size dual bin packing problem for wood reuse
  Pauline Bessemans, Célia Paquay, and Morgane Dumont

TB-2

Chair: Paula Carroll

Room: 0/88

• A Three-Stage Meta-heuristic-Based Framework for Voltage Estimation in Low-Voltage Distribution Grids
  Eghbal Hosseini, Mohsen Banaei, Ahlam Jameel, Fraser O'Brien, and Razgar Ebrahimi

• A consolidation heuristic for a biobjective multimodal transportation planning problem
  Dominik Leib and Neele Leithäuser

• Bi-Objective Approach to Parametric Max-Flow Interdiction
  Simon Wirschem, Alexey Bochkarev, and Stefan Ruzika

TB-3

Chair: Roberto Ronco

Room: 1/82

• Finding a Smallest Discretization in Dynamic Discretization Discovery for Continuous-Time Service Network Design
  Alexander Helber and Tom Wüllner

• Bilevel Facility Location with Endogenous Queueing: An Application to EV Charging Network Design
  Yossiri Adulyasak, Weiquan Wang, Amira Dems, Okan Arslan, and Jean-François Cordeau

• On the complexity of degree-constrained network design problems
  Francesco Pisanu, Daniele Catanzaro, Gwenaël Joret, and Brieuc Pierre

Thursday 13:30-14:30 - Keynote 2

TC-1

Chair: Arie Koster

Room: 0/86

Explainable Optimization: New Perspectives and Challenges

In recent years, there has been a rising demand for transparent and explainable AI models. Although significant progress has been made in providing explanations for machine learning models, this topic has not received the same attention in the Operations Research (OR) community. However, algorithmic decisions in OR are made by complex algorithms which cannot be considered explainable or transparent as we will argue in this talk. We present two promising concepts to provide explanations for (integer) optimization problems. In the first part we introduce the concept of counterfactual explanations which asks the question: “How do the parameters of my problem have to be changed such that a different solution would be optimal”. In the second part we present fast model-agnostic methods which attempt to explain any type of optimization algorithm (exact or heuristic) by calculating contribution scores for each relevant problem parameter.

Thursday 14:30-15:00 - Sponsored Keynote

Hexaly, a new kind of hybrid optimization solver

Hexaly Optimizer is a new kind of hybrid optimization solver. Its modeling interface is nonlinear and set-oriented. In a sense, Hexaly APIs unify and extend modeling concepts from mixed-linear programming, nonlinear programming, and constraint programming. Under the hood, Hexaly combines various exact and heuristic optimization methods, such as branch-and-bound, automatic Dantzig-Wolfe reformulation, column and row generation, propagation methods, local search, direct search, and surrogate modeling techniques.

Regarding performance benchmarks, Hexaly distinguishes itself against the leading solvers in the market, like Gurobi, IBM Cplex, and Google OR Tools, by delivering fast and scalable solutions to Routing, Scheduling, Packing, Clustering, and Location problems.

This talk will introduce our set-based modeling formalism and show its scalability for large instances. We will then explore how the solver can use this formalism to automatically leverage state-of-the-art resolution techniques from both the exact and heuristic fields.

TD-1

Chair: Arie Koster

Room: 0/86

• Hexaly, a new kind of hybrid optimization solver
  Maxime Rougier

Friday, April 24

Session	Time
FA	09:00-10:30
FB	11:00-12:00

Friday 09:00-10:30

FA-1

Chair: Greet Vanden Berghe

Room: 0/86

• A Multi-Period Vehicle Routing Problem with State-Dependent Service Times for Last-Mile Distribution Networks
  Christian Truden, Margaretha Gansterer, Dominic Loske, and Matthias Klumpp

• A Labeling Approach for the Electric Vehicle Routing Problem with Truck Driver Scheduling
  Louis Stubbe, Niels De Walsche, and Greet Vanden Berghe

• Towards Optimizing Fast Rerouting under Multiple Failures
  Stephanie Althoff and Klaus-Tycho Foerster

FA-2

Chair: Nancy Perrot

Room: 0/88

• A Generalized Voting Game for Categorical Network Choices
  Yueh Lin, Stefano Nasini, and Martine Labbé

• Energy-Efficient Function Chaining and Assignment for In-Network Learning
  Garance Gerard, Patient Ntumba Wa Ntumba, Safia Kedad-Sidhoum, Amélie Lambert, and Nancy Perrot

• Optimizing Regional Zero-Emission Bus Operations via Multi-Depot Electric Vehicle Scheduling
  Elisabeth Gaar, Xenia Haslinger, and Sophie N. Parragh

FA-3

Chair: Alexis Schneider

Room: 1/82

• Network Abstraction with Provisioning Guarantees for Multi-Domain Virtual Network Embedding
  Yanis Achaichia, Christelle Caillouet, Nicolas Huin, and Geraldine Texier

• Globally balanced paths for minimizing congestion in HPC networks
  Jan De Neve, Wouter Tavernier, Didier Colle, and Mario Pickavet

• Constrained-Sensors Data Collection with Unmanned Aerial Vehicle
  Luigi De Giovanni, Claudio Enrico Palazzi, and Lorenzo Perinello

FA-4

Chair: Eduardo Amaldi

Room: 0/89

• Optimal boarding and alighting operations in urban mass transit
  Laura Knappik, Lorena Silvana Reyes Rubiano, and Sven Müller

• On The Minimum-Weight Forward (Weakly) Fundamental Cycle Basis Problem in Directed Graphs
  Gabor Riccardi and Niels Lindner

• Thompson Sampling with Cumulative Oversampling for Budgeted Influence Maximization
  Zhen Xu, Xinjie Xing, and Shatian Wang

Friday 11:00-12:00 - Keynote 3

FB-1

Chair: Eduardo Amaldi

Room: 0/86

Semidefinite programming based bounds for the quadratic minimum spanning tree problem

In the quadratic minimum spanning tree problem (QMSTP), the goal is to minimize a quadratic objective over the set of all spanning trees of a graph. In this talk, we show how the QMSTP can be formulated as mixed-integer semidefinite program by exploiting the algebraic connectivity of the underlying graph. Based on these formulations, we derive a doubly nonnegative (DNN) relaxation of the QMSTP and introduce valid inequalities that strengthen this relaxation using the Chvátal–Gomory procedure for mixed-integer conic programming. We also present a variant of the Peaceman–Rachford splitting method that enables us to solve the DNN relaxation efficiently and obtain strong bounds for the QMSTP.

Joint work with Frank de Meijer, Melanie Siebenhofer and Renata Sotirov.