WE 16:00 PM1 Auditorium A

Jacob Trepat Borecka jacob.trepat@ivt.baug.ethz.ch

ETH Zurich

Leutwiler, Florin, ETH Zurich; Corman, Francesco, ETH Zurich

*Computational Evaluation of Logic-based Benders Cuts for Railway Scheduling*

Responsive and effective railway operations can be based on a flexible timetable concept with daily adjustments, based on the varying needs of the network such that it satisfies a set of business objectives. This motivates the industrial need to develop solution algorithms to solve large-scale scheduling problems fast and efficiently in terms of solving speed and solution quality. Therefore we implement, on an existing logic-based Benders decomposition framework, different automatic decomposition architectures, including geographic-based, time-based and train-based. In particular, we explore a process based on dynamic aggregation of atomic subproblems into larger subproblems during the solution process, for each architecture. We evaluate how these specific choices balance to a different extent the computation effort to solve decomposed subproblems, versus coordinating them towards a global solution.

OPTSM, Optimization in Public Transport and Shared Mobility;
Invited Session
WE 16:20 PM1 Auditorium A

Benedetta Pratelli benedetta.pratelli@maior.it

M.A.I.O.R. SRL

Carosi, Samuela, M.A.I.O.R. SRL; Geraci, Francesco, M.A.I.O.R.

SRL; Tresoldi, Emanuele, M.A.I.O.R. SRL

*A sequential approach for large scale electric vehicle scheduling problems*

In the last few years, to reduce air and noise pollution due to a growing mobility demand and to a greater traffic congestion, the large majority of local transportation companies are migrating their fleet from diesel-powered to electric buses (EV). The introduction of this type of vehicles means considering the specific characteristics the new technology is bringing along, such as managing the constraints that it requires to operate. One of the critical aspects to carefully consider is the re-design of the algorithms employed by decision support tools to provide efficient solutions for Time-Tabling, Vehicle Scheduling (VS) and Crew Scheduling planning phases. In particular, the VS phase is the most affected since the new requirements and constraints associated with EVs can modify the structure of the underlying mathematical problem. In this work we present a math-heuristic procedure for the solution of the Electric Vehicle Scheduling problem (EVS) requiring minimal modifications in the creation of vehicle blocks with respects to standard diesel-powered vehicles. Our approach acts on already constructed vehicle blocks and transform them in electric-complying vehicle blocks respecting all energy constraints and charging requirements. The core of the procedure is a flow-based Mixed Integer Linear Programming (MILP) model with additional constraints. The model is solved with a generic MILP solver (COIN-OR CBC); additional steps are taken whether potential infeasibility is detected. The approach has been tested on large-scale real-world instances, with several hundreds of electric vehicle blocks. The procedure showed to be time-comparable with similar VS instances using diesel-powered vehicles, and was always able to find feasible solutions.

OPTSM, Optimization in Public Transport and Shared Mobility;
Invited Session
WE 16:40 PM1 Auditorium A

Valentina Cacchiani valentina.cacchiani@unibo.it

Department of Electrical, Electronic and Information Engineering
Guglielmo Marconi, University of Bologna, Italy
Tresoldi, Emanuele, Department of Computer Science Giovanni degli
Antoni, University of Milan, Italy

*Integrated timetabling and electric vehicle scheduling in public transport*

Timetabling and vehicle scheduling are often solved in sequence due to their complexity. In this work, instead, we tackle the two problems in an integrated way for a bus company operating in a transport network, and consider a mixed-fleet of vehicles that include electric buses. The problem was introduced for the MINOA Research Challenge. In this problem, timetabling aims at determining the best service frequency: in particular, for each line and direction, the frequency is measured at a main station of the line as the headway between two consecutive trips of the line. The goal is to select a subset of trips out of a large set in order to minimize the headway deviation from a given ideal headway. Vehicle scheduling calls for finding the sequence of trips (vehicle-block) to be assigned to each vehicle with the goal of minimizing the company costs, while ensuring that each trip selected in the timetabling is executed by one vehicle. Several additional constraints, such as service regularity, deadhead trips, available parking slots are taken into account. In addition, constraints related to charging requirements are included to handle electric buses. We propose a heuristic algorithm based on an Integer Linear Programming (ILP) model with arc-variables representing which consecutive trips are selected for the timetabling problem, and exponentially many variables corresponding to vehicle-blocks for the vehicle scheduling problem. Column generation is applied to solve the continuous relaxation of the model, and variable fixing is employed to obtain feasible solutions. Computational results are reported on instances of the MINOA Research Challenge.

OPTSM, Optimization in Public Transport and Shared Mobility;
Invited Session
# Industrial & Startup Session

WE 15:40 PM1 Auditorium B

Francesco Sambo francesco.sambo@verizonconnect.com

Verizon Connect Italy

Verizon Connect Italy - Industrial presentation

** NO ABSTRACT PROVIDED **

Industrial & Startup Session
WE 16:00 PM1 Audtorium B

Federica Picca Nicolino federica.picca@intuendi.com

Intuendi

*Intuendi - Industrial presentation*

** NO ABSTRACT PROVIDED **

Industrial & Startup Session
WE 16:20 PM1 Audtorium B

Jacopo Corno jacopo.corno@deiksrl.com

Deix

Deix - Industrial presentation

** NO ABSTRACT PROVIDED **

Industrial & Startup Session
WE 16:40 PM1 Audtorium B

Veronica Asta veronica.asta@optimeasyway.com

OPTIM easy

*OPTIM easy - Industrial presentation*

** NO ABSTRACT PROVIDED **

Industrial & Startup Session
Applications of OR; Contributed Session

WE 17:30 PM2 001

Jelena J. Stankovi jelena.stankovic@eknfak.ni.ac.rs

University of Ni, Faculty of Economics, Serbia

Hedwig Yamu, Claudia, Oslo Metropolitan University, Department
of Civil Engineering and Energy Technology, Norway; Marjanovi,
Ivana, University of Ni, Faculty of Economics, Serbia; Stanojevi,
Marina, University of Ni, Faculty of Economics, Serbia

*Urban Poverty and Material Deprivation: A Spatial Efficiency Assessment*

Urban poverty and inequality are one of the leading challenges fac-
ing modern society, with the main goal in most agendas being the need
to eradicate urban poverty in all its forms and dimensions. Urban areas
are, on the one hand, the bearers of economic growth and development
and the cultural uplift of the population, while on the other hand, ur-
ban regions face complex and growing challenges related to population
inequality. Reaching inclusive growth at the country level is based on
achieving inclusive growth in urban areas, primarily bearing in mind that
the majority of the world's population lives in urban areas. The tra-
ditional practice of measuring the well-being of the population based on
monitoring mainly economic performance has provided an inadequate pre-
sentation of the quality of socio-economic growth and development. Mod-
ern concepts of measuring well-being include both economic and social
performance, with special attention to indicators related to material de-
privation, poverty and social inclusion. However, the level of poverty and
material deprivation of a population is traditionally defined on the basis
of data on income or wealth. Yet, modern research indicates that poverty
is a multidimensional concept and that the concept of inclusive growth
is becoming dominant in today's conditions. Achieving inclusive growth
involves a complex process faced with numerous challenges. Achieving
social inclusion, nurturing a sense of belonging, eradicating poverty and
reducing social vulnerability stand out as important components of inclu-
sive growth and development. Nevertheless, socioeconomic deprivation of
the population in developing countries is usually quantified and monitored
through census data, without taking into account the multidimensionality
of this problem. Namely, the census data generally provide information
on a particular aspect of socioeconomic deprivation, with the main focus
on the percentage of the population at risk of poverty or social exclusion.
Although the percentage of the population at risk of poverty or social
exclusion is an important indicator of living conditions, its disadvantage
is that it alone does not cover all dimensions of vulnerability, and in order
to quantify the vulnerability of the population, it is necessary to create
a multidimensional, comprehensive measure that encompasses various as-

Applications of OR; Contributed Session
pects of poverty, social exclusion and material deprivation. With that in mind, the main goal of this paper is to contribute to the development of a methodological approach that can be applied to assess urban poverty and material deprivation using data of urban areas of the Republic of Serbia. The model developed in the paper includes primary, unprocessed data collected by the Statistical Office of the Republic of Serbia in the Survey on Income and Living Conditions (SILC), as a part of EU Statistics on Income and Living Conditions (EU-SILC) covering the period from 2015 to 2020 and the analysis, i.e. grouping individual data according to the spatial area where they were collected. The assessment of urban poverty and material deprivation will be performed by creating a composite index using the Benefit of Doubt approach. The Benefit of Doubt approach is the variant of the Data Envelopment Analysis approach which is modified in the way that it contains only outputs, and can provide information on the reasons for the inefficiency of certain urban areas. Given that policymakers have limited budgets when making strategic decisions aimed at eradicating poverty and material deprivation, the results of the analysis can provide guidance on the needs of the most vulnerable regions, and prioritise the urban areas according to the identified shortcomings.

Applications of OR; Contributed Session
WE 17:50 PM2 001

Gabi Hanukov gabih@ariel.ac.il

Ariel University

*Postponing Complementary Services*

Studies on service systems and queueing theory classically assume that a customer who obtains service must be present in the system during the whole time the service is provided. However, as time passed, many service systems realized that part of the service can be performed while the customer is absent. The customer can use this time efficiently outside the system. Adopting this potentially favorable approach, we study a Markovian service system in which the service can be split into two phases: an opening service (OS), which can be provided only when the customer is present, and a complementary service (CS), which can be carried out in the absence of the customer. To improve the systems overall performance, after providing the OS, the server can postpone executing the CS to time intervals in which the system is empty of customers. The prepared OSs are stored in a designated storage facility. Once the system becomes empty, the server executes the CS for the stored OSs, one at a time. We consider two unbounded dimensions system involving a multivariate probability generating function and derive closed-form expressions for the systems steady-state probabilities and its various performance measures. An economic analysis compares the described model with a corresponding limited OS capacity model.

Applications of OR; Contributed Session
WE 18:10 PM2 001

Joep Freixas josep.freixas@upc.edu

Universitat Politècnica de Catalunya

*On the search of an optimal tie-breaking system for sport competi-
tions with a large number of participants*

We propose a simple method of undoing tiebreaks in sport competi-
tions with a large number of competitors and relatively small number of
rounds of competition. Such methods are common in many games includ-
ing Chess, Go, Bridge or Scrabble, among others.

Strength of schedule is the idea behind the methods based on the
games already played: that the player that played the harder competition
to achieve the same number of points should be ranked higher.

Tie-breaking methods decide in strict order the prizes to be received. One of the most commonly used methods is the well-known Buchholz method, based on the arithmetic mean of the scores obtained by the opponents. The alternative method that we propose in this paper, which is quite close (in statistical terms) to the median of the scores obtained by the opponents, is also a weighted average of the opponents' scores, whose weights are based on the binomial distribution. The main objective of the article is to compare the proposed method with that of Buchholz, highlighting the many advantages over it.

Unfortunately, even today Buchholz's method and its variants are rou-
tinely used as the first and second tiebreaker criteria. It is used as a
first and second criteria in the rapid and blitz chess world championships
that took place in December 2021. We believe that Buchholz's method
should be replaced by the one proposed here as soon as possible.
WE 17:30 PM2 002

Fausto Errico fausto.errico@etsmtl.ca

École de technologie supérieure, Université du Québec
Clément Altman, Guy Desaulniers

*The fragility-constrained vehicle routing problem with time windows*

We study a new variant of the well-studied Vehicle Routing Problem with Time Windows (VRPTW), called the fragility-constrained VRPTW, which assumes that 1) the capacity of a vehicle is organized in multiple identical stacks; 2) all items picked up at a customer are either fragile or not; 3) no non-fragile items can be put on top of a fragile item (the fragility constraint); and 4) no en-route load rearrangement is possible. We first characterize the feasibility of a route with respect to this fragility constraint. Then, to solve this new problem, we develop an exact branch-price-and-cut (BPC) algorithm that includes a labeling algorithm exploiting this feasibility characterization to efficiently generate feasible routes. This algorithm is benchmarked against another BPC algorithm that deals with the fragility constraint in the column generation master problem through infeasible path cuts. Our computational results show that the former BPC algorithm clearly outperforms the latter in terms of computational time and that the fragility constraint has a greater impact on the optimal solution cost (compared to that of the VRPTW) when vehicle capacity decreases, stack height increases and for a more balanced mix of customers with fragile and non-fragile items.

Applications of OR; Contributed Session
WE 17:50 PM2 002

Veronica Asta veronica.asta@optimeasyway.com

OPTIM easy - University of Genoa Spin off
Ambrosino, Daniela, University of Genoa; Siri, Silvia, University of
Genoa

*Last mile and first mile trucks optimization*

With the growth of international trade, the importance of an efficient
management of intermodal freight transport is not negligible; moreover,
the improvement of intermodal transport is considered one strategy for
reducing negative externalities of transportation activities. For these rea-
sons, each activity connected with the intermodal transport must be care-
fully analysed and optimized. In this work, we focus on the last and first
mile trucks optimization, two activities usually managed by Multimodal
Transport Operators (MTOs) in door-to-door services. The first mile
consists in bringing an empty container to a customer that has to load
some goods into the container to be transferred to the final destination.
Generally, the full container is transferred from the customer depot to an
intermodal terminal, from which it will continue its trip by rail. The last
mile consists in the last part of a trip, i.e. a full container picked up at an
intermodal terminal, loaded on a truck, is delivered to a customer; the cus-
tomer unloads goods from the container and the empty container is moved
back to an intermodal depot. In this work, an optimization approach is
proposed to organize the first mile and the last mile trips of an intermodal
terminal, in such a way to reduce as much as possible the trips of empty
containers. The combination of two trips is possible if and only if some
time constraints and some restrictions related to the type of containers
(size, hight, etc), type of goods and type of vehicle are respected. Some
preliminary results based on random instances are presented. In particu-
lar, a comparison of solutions with and without the trip combination, in
terms of kilometres travelled and service time, is reported.

Applications of OR; Contributed Session
WE 18:10 PM2 002

Nicolas Zufferey n.zufferey@unige.ch

GSEM, University of Geneva

Marie-Sklaerder, Vié, Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport, CIRRELT, Québec, Canada; Leandro, Coelho, Canada Research Chair in Integrated Logistics, Université Laval, Canada

*Reducing the supply-chain nervosity thanks to flexible planning*

This study is motivated by a major fast-moving consumer goods com-
pany. It considers a 3-echelon supply chain made of one plant, one distri-
bution center and several shops. A flexible planning (FLEXP) approach
is proposed to reduce the supply chain nervosity (e.g., bullwhip effect,
peaks of production, peaks of inventories, shortages). FLEXP tries to
take the best out of both the well-known PULL and PUSH approaches.
Indeed, PULL is characterized by low shortages but high production vari-
ations, whereas PUSH is characterized by low production variations but
high shortages. FLEXP relies on assigning penalties only if the daily
production and the daily inventories are out of predetermined ideal inter-
vals. More precisely, the following objective functions are minimized in
a lexicographic fashion: the shortage at the shop level, the out-of-range
production, the out-of-range inventories (in the distribution center and
the shops). As the demand is non-deterministic, a simulationoptimiza-
tion algorithm is designed. The experiments performed on 20 instances
demonstrate the benefit of FLEXP when compared to both PULL and
PUSH.
# NOML, Nonlinear Optimization and Machine Learning; Invited Session

WE 17:30 PM2 003

Holger Rauhut rauhut@mathc.rwth-aachen.de

RWTH Aachen University, Chair for Mathematics of Information Processing

*Implicit bias of gradient descent for learning linear neural networks*

Deep neural networks are usually trained by minimizing a non-convex loss functional via (stochastic) gradient descent methods. A puzzling empirical observation is that learning neural networks with a number of parameters exceeding the number of training examples often leads to zero loss, i.e., the network exactly interpolates the data. Nevertheless, it generalizes very well to unseen data, which is in stark contrast to intuition from classical statistics which would predict a scenario of overfitting. A current working hypothesis is that the chosen optimization algorithm has a significant influence on the selection of the learned network. In fact, in this overparameterized context there are many global minimizers so that the optimization method induces an implicit bias on the computed solution. It seems that gradient descent methods and their stochastic variants favor networks of low complexity (in a suitable sense to be understood), and, hence, appear to be very well suited for large classes of real data. Initial attempts in understanding the implicit bias phenomenon considers the simplified setting of linear networks, i.e., (deep) factorizations of matrices. This has revealed a surprising relation to the field of low rank matrix recovery (a variant of compressive sensing) in the sense that gradient descent favors low rank matrices in certain situations. Moreover, restricting further to diagonal matrices, or equivalently factorizing the entries of a vector to be recovered, shows connection to compressive sensing and 11-minimization.

After giving a general introduction to these topics, the talk will concentrate on results by the speaker on the convergence of gradient flows and gradient descent for learning linear neural networks and on the implicit bias towards low rank and sparse solutions.
WE 17:50 PM2 003

Tommaso Aldinucci tommaso.aldinucci@unifi.it

Dipartimento di Ingegneria dell'Informazione, Università degli Studi
di Firenze

Enrico Civitelli, Leonardo Di Gangi, Alessandro Sestini (DINFO /
Univ Firenze)

Contextual Decision Trees

Focusing on Random Forests, we propose a multi-armed contextual bandit recommendation framework for feature-based selection of a single shallow tree of the learned ensemble. The trained system, which works on top of the Random Forest, dynamically identifies a base predictor that is responsible for providing the final output. In this way, we obtain local interpretations by observing the rules of the recommended tree. The carried out experiments reveal that our dynamic method is superior to an independent fitted CART decision tree and comparable to the whole black-box Random Forest in terms of predictive performances.
WE 18:10 PM2 003

Behzad Pirouz behzad.pirouz@dimes.unical.it

Dimes, Universita della Calabria

Gaudioso, Manlio, Dimes Universita della Calabria

*A Multi-Objective Programming Problem for Sparse Optimization with Application in SVM Feature Selection*

We propose a novel Multi-Objective Optimization (MO) model for sparse optimization based on the polyhedral k-norm. We put particular emphasis on the application of sparse optimization in Feature Selection for Support Vector Machine (SVM) classification. In our MO model, the first objective is the classic SVM classification error, while the second one is the number of significant features, that is, the number of nonzero components of the normal vector to the separating hyperplane. The model we consider is the continuous relaxation of an MINLP model. The objective is to calculate the Pareto optimal solutions, leaving it to the decision-maker to evaluate the tradeoff and the best compromise between the two objectives. We present some numerical results obtained using MO algorithms for our model. They are compared with those of several existing models based on the *l*\_1 and *l*\_2 norm in single and multi-objective format.
# Optimization on Graphs; Contributed Session

WE 17:30 PM2 Auditorium A

Carmine Cerrone carmine.cerrone@unige.it

University of Genoa

Anna, Sciomachen, University of Genoa; Daniela, Ambrosino, University of Genoa

*A multi period VRP for evaluating distribution strategies*

In this work, a Rich Vehicle Routing Problem (RVRP) is faced for solving city logistic problems. In particular, we deal with the problem of a logistic company that has to define the best distribution strategy for obtaining an efficient usage of vehicles and for reducing transportation costs while serving customers with different priority demands during a given planning horizon [1]. Each customer's demand is partitioned into three sets in accordance with different priorities. It is possible to split the customer demand. In this case, the split delivery consists in postponing the customer's demand according to its priority. This problem can be defined as a multi-period vehicle routing problem with a heterogeneous fleet of vehicles, with customers requirements and company restrictions to satisfy, in which the fleet composition has to be daily defined. Actually, the company has a fleet of owned vehicles and the possibility to select, day by day, a certain number of vehicles from the fleet of a third-party company. Routing costs must be minimized together with the number of used vehicles. Only small instances can be solved up to optimality (i.e., instances with 20 customers). Thus, a heuristic approach based on a local search combined with a heuristic split of the input instance is proposed to solve this problem. A complete experimental campaign is presented for validating the proposed approach. Tests have been used for evaluating the quality of the obtained solutions. Moreover, the benefits that can be obtained by postponing deliveries are evaluated. Results are discussed, and some conclusions are highlighted. [1] Ambrosino, D., Cerrone, C. *A Rich Vehicle Routing Problem for a City Logistics Problem*, (2022) Mathematics, 10 (2), art. no. 191.
Applications of OR; Contributed Session

WE 17:50 PM2 Auditorium A

Maria Truvolo 5388109@studenti.unige.it

Università di Genova

Anna Sciomachen, Università di Genova

*Selection of pickup-delivery points in urban areas to reduce emission costs*

The problem of defining pickup-delivery points plays a crucial role in contemporary business development. Finding the optimal position to locate different assets of a company guarantees the reduction of the costs and emissions due to the logistical advantages that arise from the transport, storage and delivery of the goods. It also allows the expansion of the areas covered by the provided services by removing redundancies and narrowing the logistic gap between producers and consumers.[1] This work faces a variant of the classic multi-facility location problem represented by a graph, in which the set of nodes is partitioned into a set P of pickup-delivery points and a set C of customers. Customers must go to a node $p \in P$ to pick up the required items. The number and the subset of the selected nodes of P are chosen with the goal of minimizing the total emission cost [2,3]. In this perspective, both travelling distance and means of transport (i.e., walking, bike, car, electrical vehicle, etc.) are considered. The fixed cost associated with the nodes in P is given. A customer C is assigned to a given node P if it can reach P at its minimum sustainable cost while not exceeding a predefined maximum distance between them. We present the model of the problem and develop a heuristic algorithm to produce effective solutions. The heuristic algorithm is based on a clustering of the nodes. In order to perform extensively computational tests on realistic scenarios, we design an algorithm able to extract topological data from QGIS databases. The computational results are analyzed to certify the effectiveness of the produced approach in terms of quality of the solution and computational times.

[1] E. Ben Alaïa, I. H. Dridi, H. Bouchriha, and P. Borne, Insertion of new depot locations for the optimization of multi-vehicles multi-depots pickup and Delivery Problems using Genetic Algorithm, Proc. 2015 Int. Conf. Ind. Eng. Syst. Manag. IEEE IESM 2015, pp. 695701, Jan. 2016.

[2] D. Ambrosino, A. Sciomachen, and M. G. Scutellà, A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem, Comput. Oper. Res., vol. 36, no. 2, pp. 442460, Feb. 2009.

[3] E. Nathanail, M. Gogas, and G. Adamos, Smart Interconnections of Interurban and Urban Freight Transport towards Achieving Sustainable City Logistics, Transp. Res. Procedia, vol. 14, pp. 983992, 2016.

Applications of OR; Contributed Session
# Optimization on Graphs; Contributed Session

WE 18:10 PM2 Auditorium A

Cristina Ondei cristina.ondei@unimi.it

Dipartimento di Informatica, Università degli Studi di Milano
Ceselli, Alberto, Dipartimento di Informatica Università degli Studi
di Milano; Righini, Giovanni, Dipartimento di Informatica Univer-
sità degli Studi di Milano; Tresoldi, Emanuele, M.A.I.O.R.

*Exact algorithms for the electric travelling salesman problem*

Electric vehicles play an increasingly important role in transportation, making the design of adequate algorithms necessary. In the Electric TSP, a vehicle with a limited battery needs to visit a given set of clients. A set of recharge stations is also given, so that the vehicle can stop and recharge when necessary during the route. While clients must be visited only once, recharge stations can be visited multiple times. We consider a specific variant of this problem where multiple technologies (characterized by different costs and times per unit of recharge) are available at the single station. To solve it we consider two different exact techniques. The first approach is a branch-and-price algorithm, where every variable in the master problem represents a path (i.e. a sequence of clients) between two stations. The second method consists in a branch-and-cut algorithm. We experiment both algorithms on a set of instances from the literature, having different size, battery and time limits. This computational evaluation allows us to highlight the relative strengths and weaknesses of the two approaches.
# Industrial & Startup Session

WE 17:30 PM2 Auditorium B

Duccio Grandi duccio.grandi@maior.it

M.A.I.O.R.

M.A.I.O.R. and elite-level sporting events

Presentazione per la giornata aziendale
M.A.I.O.R. and elite-level sporting events

MAIOR, Management Artificial Intelligence Operations Research, is an Italian software house with a core business in planning, scheduling, managing public transport. We provided our software and our expertise in 3 different worldwide sporting events: Olympic Winter Games in Turin 2006, Olympic Games in Beijing 2008, FIFA World Cup in Qatar 2022. Three important similar events, with 16 years between them, in different countries with different cultures, different economic resources, different human workforce, different laws. And the same goal of providing a world-class public transport service for spectators. Public transport for events cant be planned as a standard mass transit service because every single day is different from the others due to single events occurring at specific hours in different places and involving various amounts of spectators. In events lasting 20 days, 20 different service days must be planned and managed. In Turin 2006, main goal was to transport spectators and athletes from Turin and Olympic Village to the mountains where the majority of events took place. Bus drivers came from the whole Italy with their own buses. Turin transport committee rented buses with driver from many big and small Transit Operators all over Italy. So transport planning dealt with many different labor rules and bus typologies in order to provide an optimized scheduling. With a final need of generalizations, simplifications and models to computerize the risk of a chaos. In Beijing 2008, main goal was to transport spectators all over an enormous city already congested. Workforce wasnt an issue: simple labor rules and as many drivers as you need. Buses were the most important constraint in order to optimize transit scheduling. Finally a lesson on algorithms and heuristics. In Doha Qatar 2022, main goal is to transport spectators between hotels, stadiums, metro stations and city points of interest. All of that in a city that is constantly growing and building new roads almost daily. Workforce ist an issue, again simple labor rules and many drivers. But after 14 years since Beijing 2008, public transport expectations have changed completely. Increased dimensions: now thousands of buses and drivers are planned. Information network: data is shared between various systems, all of them must be in sync: driver apps, passenger apps, bus on-board systems, real-time control rooms, human resource offices. However, from an Operations Research standpoint the most interesting problem is the

## Industrial & Startup Session
usage of a huge number of electric vehicles. Brand new and state of the art electric vehicles but with a range that is still not sufficient to cover all assigned trips of the day. MAIOR presents lessons learned from these 3 events that are distant geographically and culturally spanning 16 years.
WE 17:50 PM2 Auditorium B

Matteo Pozzi matteo.pozzi@optit.net

OPTIT

OPTIT - *Industrial presentation*

** NO ABSTRACT PROVIDED **

Industrial & Startup Session
WE 18:10 PM2 Auditorium B

Stefano Cappugi s.cappugi@firlab.com

Firlab

FirLab - Industrial presentation

** NO ABSTRACT PROVIDED **

Industrial & Startup Session
# Stochastic Optimization; Contributed Session

TH 10:00 AM1 001

Stefano Smriglio stefano.smriglio@univaq.it

DISIM - Università degli Studi dell'Aquila
Mattia, Sara, IASI - CNR; Rossi, Fabrizio, DISIM - Università degli
Studi dell'Aquila

*Robust optimization models in call centers workforce management*

Workforce management (WFM) is a complex process and represents a prominent issue in call centers optimization. Its general goal is to find a satisfactory trade-off between the Level of Service (LoS) provided to customers and personnel costs. LoS is mostly based on waiting times and quality of the response, while personnel costs constitute one major expense for call center companies. WFM is traditionally split into a sequence of almost separate steps: forecasting call volumes (forecasting); determining the staffing levels, defined as the number of agents required at each time period to guarantee the desired LoS (staffing); translating them into agents work shifts (shift scheduling); assigning agents to such shifts (rotating) and, finally, monitoring out-of-adherence situations at operational level and reacting accordingly. This process offers several significant challenges for stochastic modelling and has been deeply investagated by the scientific literature. In particular, such a decomposition is well-known to be highly suboptimal for several practical reasons. For instance, the staffing levels are hard to cover with shifts, leading to considerable over-staffing. Moreover, work shifts include rest breaks which may impact significantly on the LoS.

We present two robust optimization models where agents flexibility is exploited so as to handle such drawbacks. In one case, we propose a two-stage robust model aimed at integrating staffing with shift scheduling with the goal of preserving LoS from unpredicted demand fluctuations. As for workbreak scheduling, we introduce an element which is relevant in practice but hardly studied scientifically: the agents satisfaction. Again, We illustrate a two-stage robust optimization model for shift scheduling, where agents are free to decide when to have breaks within the regulatory restrictions. Practical cases are discussed, showing the trade off between industrial costs and agents autonomy.
TH 10:20 AM1 001

Claudia Archetti archetti@essec.edu

ESSEC Business School
Li, Yuanyuan, ESSEC Business School; Ljubic, Ivana, ESSEC Busi-
ness School

*Reinforcement Learning Approaches for the Orienteering Problem*
*with Stochastic and Dynamic Release Dates*

E-commerce markets are booming at remarkable rates. Due to an un-
precedented series of lockdowns, billions of people stay at home to prevent
the spread of the virus. It is reported that the e-commerce revenue saw
a 10% increase in Europe in 2020 due to the pandemic. At the same
time, the expectations of customers in terms of service quality are also in-
creasing. When it comes to the specific challenges to improve customers'
satisfactions on delivery, one of the crucial features is related to the start-
ing point of the last-mile delivery leg. An important feature of last-mile
distribution is that its operations start as soon as parcels are delivered to
the final logistic center, typically a city distribution center (CDC). Given
the short delivery times requested by the customers, delivery operations
typically need to start before all parcels expected to arrive that day are
available at the CDC. This raises a question: whether to wait for more
or all parcels to be delivered at the CDC or to start the delivery as soon
as there is any available parcel and vehicle? In this paper, we focus on
the sequential decision making problem related to when to deliver parcels
and which parcels to deliver under the assumption that the time at which
parcels become available at the CDC (called release dates) is stochastic
and dynamic. We introduce a new problem called the Orienteering Prob-
lem with Stochastic and Dynamic Release Dates (DOP-rd) where a single
and uncapacitated vehicle is serving customer requests with no time win-
dow, and the service has to finish within a deadline. The release dates are
considered to be uncertain, stochastically and dynamically updated dur-
ing the sequential decision making process. The objective is to maximize
the number of requests served within the deadline. We model the problem
as a Markov decision process and present two approximation approaches
for its solutions. Both are based on scenario generations representing re-
alizations of RDs and make use of a batch approach to approximate the
value of future information, and specifically to approximate the number
of requests served in future routes, i.e., routes that leave the depot in a
future time instant. The two approximation approaches we propose are:
Policy Function Approximation (PFA) through a consensus function in
which a ILP determines, for each scenario, the requests to serve immedi-
ately, i.e., in a route leaving the depot immediately, and those included in
future routes, and a consensus function over all scenarios determines the
final solution; one-step look-ahead policy with Value Function Approxi-
mation (VFA) where a two-stage stochastic model is solved in which the

Stochastic Optimization; Contributed Session
first stage is to determine the route leaving immediately, while the second stage concerns future routes. We perform computational tests on a set of benchmark instances. We compare the two approaches described above with myopic approaches mimicking common practice and upper bounds related to perfect information. The results show that both PFA and VFA largely outperform myopic approaches and provide reasonable gaps with respect to the solution with perfect information.
TH 09:00 AM1 001

Javier Faulin javier.faulin@unavarra.es

Public University of Navarre
Serrano-Hernandez, Adrian, Public University of Navarre; Cadarso, Luis, Rey Juan Carlos University of Madrid; Ballano, Aitor, Public University of Navarre; Sawik, Bartosz, Public University of Navarre and AGH University Krakow

*Multi-Stage Stochastic Optimization for a Biorefinery Supply Chain in Spain*

Nowadays, biofuels are evolving as renewable and sustainable energy sources, especially on developed countries, due to the neutral CO2 emissions within their complete cycle. Regarding this topic, a biorefinery is considered to be set in Northern Spain. The problem considers uncertainty in biomass prices and availability, therefore, a stochastic optimization approach is needed to reduce the risks of the project. The optimization is represented as a three-stage scenario tree, composed of strategic and tactical nodes. The former refers to location of the biorefinery, while the latter refers to the rent of different warehouses. Additionally, operational nodes are rooted to the strategic and tactical nodes forming two-stage operational scenario trees. In these operational nodes, decisions related to the biomass acquisition are made. Meaningful insights are obtained from the application of stochastic optimization at all levels: strategic (the facility location problem), tactical (warehouses strategy) and operational (biomass purchases), highlighting a superior performance than the deterministic equivalent model.
TH 09:20 AM1 001

Antonio Frangioni frangio@di.unipi.it

Dipartimento di Informatica, Università di Pisa
van Ackooij, Wim, EDF R&D; Lobato, Rafael D., Dipartimento di
Informatica, Università di Pisa

*Stochastic Dual Dynamic Programming and Lagrangian decomposition for seasonal storage valuation in SMS++*

The increase in the share of renewable energy sources in the power system, especially intermittent ones like solar and wind, brings several challenges. As both energy production and demand vary throughout the year (in winter, for example, there is a reduction in the supply of solar energy while the demand for energy for heating increases), energy storage becomes a relevant factor to take advantage of excess energy produced in certain seasons of the year and respond to increased energy demand in others. An important system for seasonal storage is that formed by cascading hydroelectric reservoirs. The management of such systems is a challenging task which hinges on a good assessment of the future value of stored energy (water) in these systems. In order to assess the value of water, and thus be able to properly manage these reservoir systems, a large-scale multi-stage stochastic problem spanning a year must be solved, where each stage is a weekly unit-commitment problems. Since the unit-commitment problems are non-convex in nature, they make the seasonal storage valuation problem unsuitable for what would otherwise be the most natural approach to solve it, i.e., Stochastic Dual Dynamic Programming. In this work we exploit the natural convexification capabilities of Lagrangian relaxation to devise a Stochastic Dual Dynamic Programming approach to the seasonal storage valuation problem where the Lagrangian Dual of the single-stage subproblems is solved (using a Bundle-type approach), which corresponds to solving the convexified relaxation of the original problem. This is known to be at least as tight as, and typically strictly tighter than, the standard way to convexify a stochastic MINLP amenable to the Stochastic Dual Dynamic Programming approach, i.e., the continuous relaxation. We report on extensive experiments which show that these huge-scale stochastic problems can indeed be solved on HPC architectures. This is made possible by the use of the SMS++ software framework (https://smspp.gitlab.io/) for large-scale problems with multiple nested forms of structure, and in particular by its native parallel capabilities that allow to exploit two different forms of parallelization (between scenarios in the SDDP approach and within subproblems in the Lagrangian one) at the same time.
TH 09:40 AM1 001

Maxime Grangereau maxime.grangereau@edf.fr

EDF Lab Paris Saclay,
Laurent, El Ghaoui, University of California at Berkeley; Fangda,
Gu, University of California at Berkeley (USA); Riadh, Zorgati, EDF
R&D

Robust Optimization for Smart Charging of Electrical Vehicles

We present a robust optimization approach accounting for various uncertainties affecting Electrical Vehicles (EV) charging stations operations, such as electricity prices, vehicle arrival and departure times, and state of charge at arrival. We develop the robust counterparts for two smart charging models. The first model, based on aggregated demand, optimizes the charging profile over a time span when the aspect of the allocation of vehicles to the different charging outlets is ignored. When considering the problem of minimizing the charging price using a linear pricing model, charging occurs only at times with lower electricity prices and with high EV availability, whereas if we consider a quadratic cost functional, consumption is smoothed over the time horizon and can be obtained by the classical water-filling approach. We consider in this first model three sources of uncertainty: electricity prices, initial states of charge of vehicles when they arrive at the charging station and arrival/departure times of vehicles. We propose several robust counterparts of the optimal charging model with linear price accounting for these three sources of uncertainties.

The robust counterpart of the model accounting for price uncertainty is cast as a Second-Order Cone problem, for which numerical results show that its solution achieves a balance between the deterministic linear pricing model, where charging at low prices moments, and the water-filling solution, which dispatches consumption uniformly over time. While the robust counterpart of the model accounting for uncertainties in the initial states of charge of vehicles may lead to overly conservative results, an affinely adjustable robust counterpart can be cast as a linear programming problem and strikes a good balance between conservativeness, computation time and performance. We use scenario uncertainty to account for the random arrival/departure times. Naïve use of this approach may lead to overly conservative results as one needs to provision for every possible scenario. An approach called interval uncertainty, which assumes independence of the uncertainty impacting different vehicles allows to reduce the number of scenarios to consider. An affinely adjustable robust counterpart model allows to reach good performance and can be cast as a linear programming problem of moderate size if one considers interval uncertainty and a finite number of scenarios. The second model, involving the allocation of EVs to the different charging station's sockets, trades-off profit versus a measure of customer satisfaction. We develop a scenario-based robust counterpart of this model where each arrival and departure
times corresponds to a scenario, assuming that the initial state of charge
of each EV is fully known. We also suggest another formulation of this
problem, based on the cardinality function, which may be more conve-
nient when dealing with uncertainties. In this model, physical limits on
charging and load constraints are convex while vehicle and socket assign-
ments constraints, re-formulated by using the cardinality (total number
of non-zero components), require some vector to be of cardinality one,
which lead to nonconvex constraints. Assuming a linear objective, our
problem can be expressed as a linear programming problem with cardi-
nality constraints. We review the use of some efficient heuristics to deal
with cardinality constraints, such as L1-norm approximations or an en-
tropy function approach.
# Discrete Optimization; Contributed Session

TH 10:00 AM1 002

Lorenzo Moreschini lorenzo.moreschini@unibs.it

Università degli Studi di Brescia

Mansini, Renata, Università degli Studi di Brescia; Zanotti, Roberto,

Università degli Studi di Brescia

*A New Kernel Search approach for the Knapsack Problem with Forfeits*

In scientific literature, knapsack problems are among the most widely used problems to test meta- and math- heuristics. In recent years, several knapsack variants have been introduced by adding specific features to the problem. In this work, we focus on the Knapsack Problem with Forfeits (see [1] and [2]), a recently introduced generalization of the Knapsack Problem in which pairs of items are mutually exclusive and cannot be selected simultaneously, unless a forfeit is paid in the objective function. We propose a matheuristic algorithm based on the Kernel Search (KS) framework to solve the problem. KS is a well-known general-purpose framework for the solution of Mixed Integer Linear Programming (MILP) problems (interested readers are referred to [3] and to the recent work [4]). Initially proposed more than ten years ago, the method is based on the identification of a subset of promising variables (the kernel set) and the partition of the remaining variables into buckets. More precisely, KS builds and solves a sequence of small MILP subproblems, each one taking into account the kernel set plus the additional variables belonging to a bucket. To keep the framework as streamlined as possible, the solution of subproblems is usually done through a commercial MILP solver, like Gurobi or Cplex.

We propose a new KS variant that exploits parallelism. In particular, rather than solving subproblems sequentially, we tackle several subproblems at the same time, and share relevant information (new best lower bound, promising variables, etc.) among subproblems while the solution process is underway. Using the Knapsack Problem with Forfeits as test problem, we address several challenges that arise when trying to develop a parallel algorithm that uses a solver with built-in parallelism. Computational results, obtained on benchmark instances from the literature, seem to be promising. We have been able to evaluate several aspects of the new solution approach, with a particular focus on the trade-off in terms of efficiency and effectiveness between our custom parallel strategy and the solver's built-in one.

[1] Raffaele Cerulli, Ciriaco D'Ambrosio, Andrea Raiconi, Gaetano Vitale, 2020. The Knapsack Problem with Forfeits, Combinatorial Optimization: 6th International Symposium, ISCO 2020, Montreal, QC, Canada, May 4-6, Pages 263-272. [2] Giovanni Capobianco, Ciriaco D'Am-

## Discrete Optimization; Contributed Session
brosio, Luigi Pavone, Andrea Raiconi, Gaetano Vitale, Fabio Sebastiano, 2022. A hybrid metaheuristic for the Knapsack Problem with Forfeits, Soft Computing, Volume 26, Pages 749-762. [3] Enrico Angelelli, Renata Mansini, M. Grazia Speranza, 2010. Kernel search: A general heuristic for the multi-dimensional knapsack problem, Computers & Operations Research, Volume 37, Issue 11, Pages 2017-2026. [4] Leonardo Lamanna, Renata Mansini, Roberto Zanotti, 2022. A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem. European Journal of Operational Research, Volume 297, Issue 1, Pages 53-65.
TH 10:20 AM1 002

Alessandro Agnetis agnetis@diism.unisi.it

Università di Siena
Pranzo, Marco, Università di Siena

*New results for sequencing two classes of jobs on a two-machine flow shop with a no-idle constraint*

We consider a scheduling problem with two classes of jobs having distinct features and impact on the objective function. A set of *n* jobs has to be performed on a two-machine flow shop. Jobs are partitioned into two classes, denoted as A and B. The jobs of class A (called A-jobs) must be processed by *M*₁ only, while the jobs of class B (called B-jobs) must be processed by *M*₁ and then by *M*₂ (the processing time on *M*₂ being larger than that on *M*₁). The problem is to sequence the jobs so that the total completion time of the A-jobs is minimum, subject to the constraint that both machines must be always busy until the end of the schedule (no-idle constraint). The decision maker has therefore to balance two conflicting needs, namely to schedule the A-jobs early in the sequence (so that their contribution to the objective function is minimized) but at the same time to schedule B-jobs so that the second machine is kept busy. The motivation for this problem comes from the testing department of an electronic firm, here corresponding to machine *M*₁. The A-jobs correspond to orders which, after processing on *M*₁, are directly sold to the market, and the firm is therefore interested in minimizing the average time-to-market of these jobs. An external manufacturer also outsources testing services to the firm, and will use the tested components to produce its own electronic devices. These testing jobs correspond to B-jobs, and the manufacturers facility corresponds to machine *M*₂ of the flow shop. For this NP-hard problem we present a set of results, namely: (i) We show that the special case in which all B-jobs have the same length can be solved in polynomial time. (ii) We introduce a new ILP formulation of a relaxed version of the problem, which exploits some properties of the optimal solution. The formulation avoids the use of big M constants. The solution to this relaxed problem is used both by an exact algorithm, based on lazy constraint generation, and by a heuristic approach which recovers a feasible solution. (iii) We report on extensive computational results on small-size (*n* = 20) and medium-size (*n* = 50) instances. In particular, a large sample of instances has been generated for various values of the ratio *μ* > 1 between total processing time on *M*₂ and total processing time on *M*₁. Computation time of the exact approach strongly depends on the value of *μ*. It turns out that the most critical instances are those for which *μ* is relatively small, i.e., *μ* = 1.1, 1.6, which are also the instances for which the no-idle constraint on *M*₂ is more binding. For these instances, when *n* = 50 the exact approach reaches a gap between 3 and 4% after 1 hour of computation, while the recovery heuristic (which requires few seconds)
displays slightly larger gaps. For larger values of $\mu$, the problem is solved
to optimality within few seconds, even when $n = 50$.
TH 09:00 AM1 002

Jocelin Cailloux jo-celin.cailloux@unige.ch

Université de Genève, Managements, Genève, Switzerland
Nicolas, Zufferey, GSEM - University of Geneva, Uni-Mail, 1211
Geneva 4, Switzerland; Olivier, Gallay, Department of Operations,
Faculty of Business and Economics (HEC Lausanne), University of
Lausanne, CH-1015, Lausanne, Switzerland

Tabu search for industrial job clustering and scheduling problem

We address a clustering and scheduling problem on a single-machine
production line. In this problem proposed by a micro-machining com-
pany, the goal is to partition a set of jobs (some of them being urgent)
into a minimum number of clusters such that the cyclic scheduling of the
clusters is robust (using min-max criterion) with respects to the setup
times. Each cluster must satisfy two constraints: only jobs with small
setup times among them are allowed in the cluster and the setup and
processing times in the cluster cannot exceed a shift duration of 8 hours.
We divide our problem in three subproblems solved sequentially to min-
imize three objective functions in a lexicographic order: (A) the number
of clusters containing an urgent job; (B) the total number of clusters;
(C) the worst-case scenario for the scheduling. For each subproblem,
graph-coloring models and methods are designed, and traveling-salesman
approaches are furthermore introduced for (C). A strict computing-time
(30 minutes) is imposed by industrial needs. We present a metaheuristic
relying on various tabu-search procedures compared with a linear model
(solved with CPLEX) and a constructive heuristic representing a current-
practice rule. Extensive computational experiments were performed to
assess the performance of the proposed metaheuristic.
TH 09:20 AM1 002

Simona Mancini simona.mancini@aau.at

University of Klagenfurt

Gansterer, Margaretha, University of Klagenfurt

*Combined fleet sizing, facility location, and vehicle scheduling for electric public transport*

In this work we analyze the integrated problem of locating and sizing
charging infrastructures, sizing a fleet of traditional and electric buses to
cover a set of scheduled trips, and determine the sequence of trips to be
executed by each vehicle, including stops for recharging when needed. The
resulting integrated decision problem which, to the best of our knowledge,
has never been addressed in the literature, can be described as follows. A
set of trips to be performed is given as input. For each trip, the starting
location, the arrival location, the starting time, the duration, and the en-
ergy required to cover it with an electric vehicle are known. The set of
available buses is composed of three different typologies: traditional diesel
vehicles (TV), standard electric vehicles (EV), electric vehicles equipped
with ultra-fast recharging technology (UV). The last category includes
new models equipped with a pantograph on the top, which allows to fully
recharge the battery in less than 10 minutes if connected to a compatible
charging device. Such vehicles exploit the latest available technology and
therefore their purchasing cost as well as the cost for the compatible charg-
ing infrastructures is very high. However, the recharging time, 12 times
faster than standard electric vehicles, make them very useful when dealing
with tight scheduling plans. Some prototypes of these vehicles are already
in use in the city of Milan since 2021, and many other municipalities are
planning to integrate them in their fleet. We assume that TV are available
for free (since the public transport companies already own them), while
a purchasing cost must be paid for each selected EV or UV. The cost
of UVs is much higher than that of EVs. A set of potential locations for
charging stations are assumed to be known. Each of them is characterized
by a maximum number of charging slots for standard and for ultra-fast
recharging technologies together with a maximum total number of slots.
EVs are compatible only with EV chargers while UVs only with UV ones.
An installation cost, lower for EV chargers than for UV chargers, must be
paid for each charger installed. These costs also include embedded costs
for electricity, therefore the only costs paid for trips covered by EVs or UVs
are those related to vehicles purchases and for installation. No additional
traveling costs are considered. Differently, for each trip covered by TV a
fixed travel cost is paid in addition to variable travel costs. This incurs for
each vehicle traveling from (i) the depot to starting location of the first
trip and (ii) to reach the depot from the arrival location of the last trip.
Additionally, the percentage of battery to recharge, i.e. the duration of
the recharging stop, is a decision variable itself. The goal of the problem
is to decide how many EVs and UVs to purchase, how many chargers of each type to install in which recharging station, and to provide a feasible schedule for each vehicle. The latter has to cover eventual stops for recharging, in order to minimize the overall costs. To solve the problem, we propose an innovative integer programming formulation, in which we model multiple visits to recharging stations without dummy clones and we present an exact method based on Combinatorial Benders Cuts, in which the master problem is modeled as a temporal bin packing problem with side constraints.
TH 09:40 AM1 002

Adriano Masone adriano.masone@unina.it

Department of Electrical Engineering and Information Technology,
University of Naples Federico II

Boccia, Maurizio, Department of Electrical Engineering and Infor-
mation Technology, University of Naples Federico II; Mancuso, An-
drea, Department of Electrical Engineering and Information Tech-
nology, University of Naples Federico II; Sterle, Claudio, Depart-
ment of Electrical Engineering and Information Technology, Uni-
versity of Naples Federico II

*Exact and heuristic approaches for a parallel machine scheduling problem with maintenance activities*

The majority of contributions in machine scheduling literature assumes that machines are always available for processing jobs over the working time horizon. However, this assumption is not always realistic. Indeed, machines can require a maintenance activity pe-riodically to prevent mal-functions in many manufacturing situations. A maintenance activity can include several operations including inspection, changing tools, installing equipment or some physical resources that allow effective work. Dur-ing these operations, machines are not available for processing jobs. In this context, a maintenance operation is an activity that a priori can avoid potential faults resulting in malfunctions and also prevents criti-cal non-availability of the system. However, there is a cost arising from each maintenance operation and the sum of these costs can cover a big percentage of the total operating cost. On this basis, including mainte-nance activities in the working schedule is essential to overcome delays in production and to reduce system failure and costs. In this context, scheduling problems with maintenance activities received great attention in literature where they are classified into fixed and coordinated problems. In the first class of problems, jobs have to be scheduled coherently with planned maintenance activities, whose starting and completion times are known in advance. Instead, in the second class of problems, both jobs and maintenance activities with related starting times have to be sched-uled. In this work, we study a coordinated parallel machine scheduling problem with maintenance activities arising from a real problem of a man-ufacturing company implementing the Industry 4.0 paradigm for internal logistics. We propose an original integer linear programming (ILP) formu-lation to optimally solve the addressed problem and a matheuristic based on a decomposition of the problem in two phases. The results show the ef-fectiveness of the proposed approaches and the impact of the maintenance time on the production process completion time.
# NOML, Nonlinear Optimization and Machine Learning; Invited Session

TH 10:00 AM1 003

Matteo Lapucci matteo.lapucci@unifi.it

Università degli Studi di Firenze

Kanzow, Christian, Universität Würzburg; Sciandrone, Marco, Sapienza

Università di Roma

*Inexact Penalty Decomposition in General Settings*

The Penalty Decomposition (PD) approach is an algorithmic framework proposed to tackle optimization problems with peculiar constraints structure, such as cardinality constrained problems [1] or low rank approximation problems [2]. First, the problems are equivalently reformulated by the variable splitting technique, which introduces a new vector of variables to decouple the complicated constraint and the rest of the problem elements. This reformulation is then solved by a sequential penalty method, where the approximate solution to penalty subproblems is found by using a two-block alternate minimization (AM) scheme. Recently, an inexact version of the approach has been proposed [3] for the case of sparsity constrained problems with no additional constraints; in this case, one of the two steps of AM is carried out by a single descent step along the gradients direction. In this talk, we will review various settings where the PD approach could be successfully employed and we will discuss the theoretical convergence properties of the inexact scheme in general cases. The framework is also seen in relation to a recently proposed augmented Lagrangian method [4].

[1] Z. Lu and Y. Zhang. Sparse approximation via penalty decomposition methods. SIAM Journal on Optimization, 23(4):24482478, 2013. [2] Y. Zhang and Z. Lu. Penalty decomposition methods for rank minimization. Advances in neural information processing systems, 24, 2011. [3] M. Lapucci, T. Levato, and M. Sciandrone. Convergent inexact penalty decomposition methods for cardinality-constrained problems. Journal of Optimization Theory and Applications, 188(2):473496, 2021. [4] X. Jia, C. Kanzow, P. Mehlitz, and G. Wachsmuth. An augmented lagrangian method for optimization problems with structured geometric constraints. arXiv preprint arXiv:2105.08317, 2021.
TH 09:00 AM1 003

Antonio M. Sudoso sudoso@diag.uniroma1.it

Sapienza University of Rome

Piccialli, Veronica, Sapienza University of Rome

*Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming*

The minimum sum-of-squares clustering problem (MSSC), or *k*-means type clustering, aims to partition *n* data points into *k* clusters so that the total sum of squared Euclidean distances between the data points and the cluster centers is minimized. The MSSC problem is traditionally considered an unsupervised learning task. In recent years, using background knowledge to improve the cluster quality and promote interpretability of the clustering process has become a hot topic at the intersection of mathematical optimization and machine learning research. Taking advantage of background information in data clustering leads to the so-called semi-supervised or constrained clustering. In this talk, we present a branch-and-cut algorithm for MSSC where the background knowledge is incorporated in the form of strict cardinality constraints. For the lower bound procedure, we derive a new semidefinite programming relaxation and we use a cutting-plane procedure for strengthening the bound. For the upper bound, instead, by using integer programming tools, we propose an adaptation of the *k*-means algorithm to the constrained case. Numerical results show that our method outperforms state-of-the-art algorithms, significantly increasing the size of the instances either solved to global optimality or with an optimality gap of less than 1%.

NOML, Nonlinear Optimization and Machine Learning; Invited Session
TH 09:20 AM1 003

Federica Porta federica.porta@unimore.it

Università di Modena e Reggio Emilia
Franchini, Giorgia, Università di Modena e Reggio Emilia; Ruggiero, Valeria, Università di Ferrara; Trombini, Ilaria, Università di Ferrara

*Proximal stochastic gradient methods with variable learning rate and dynamical variance reduction*

Proximal first order stochastic optimization methods are effective tools for the minimization of problems arising in machine learning applications. Since they only require the computation of the gradient corresponding to either a single or a small number of training examples, their overall cost per iteration is low and they can be exploited with very large datasets. However, two drawbacks can be identified when using proximal first order stochastic optimization algorithms: a strong dependency of the practical performance on the choice of the learning rate and, even for very regular objective functions, a poor convergence rate due to the large variance introduced by random sampling. We develop a proximal first order stochastic method which mitigates these two aspects. We indeed combine a proper technique to dynamically reduce the variance of the stochastic gradients along the iterative process with a descent condition in expectation for the objective function, aimed to automatically fix the value for the learning rate parameter at each iteration and to give a local estimate of the inverse of the local Lipschitz constant of the objective function gradient. For general objective functionals, the stationarity of the limit points of the sequence generated by the proposed scheme can be proved, almost surely. For convex objective functionals, both the almost sure convergence of the whole sequence of the iterates to a minimum point and an O(1/k) convergence rate for the objective function values have been shown. This contribution has been submitted for the invited session Nonlinear Optimization and Machine Learning.

NOML, Nonlinear Optimization and Machine Learning; Invited Session
TH 09:40 AM1 003

Manlio Gaudioso manlio.gaudioso@unical.it

DIMES, Università della Calabria and ICAR-CNR
Miglionico, Giovanna, DIMES- Università della Calabria

On the stepsize choice in subgradient methods.

The subgradient method is the classic tool for dealing with minimiza-
tion of convex nonsmooth functions. It is an easily implementable non-
monotone algorithm. The displacement from the current approximation
of a solution is exclusively based on the knowledge of one subgradient at
such a point and on fixing an appropriate value of the stepsize along the
anti-subgradient. Starting from an analysis of the two-point approach of
Barzilai and Borwein for smooth functions, we focus on designing some
stepsize rules able to retain memory of the previous step in the subgradient
method framework. We present the results of our numerical experiments
on several benchmark test problems.

NOML, Nonlinear Optimization and Machine Learning; Invited
Session
# Optimization on Graphs; Contributed Session

TH 10:00 AM1 Auditorium A

Davide Donato Russo d.russo7@studenti.unimol.it

Università degli Stude del Molise

Cerrone, Carmine, Università di Genova; Perea Rojas-Marcos, Federico, Universidad de Sevilla

*Path planning for autonomous vehicles in smart wherehouses*

Autonomous vehicles are becoming a reality in controlled scenarios thanks to the fast growth of technologies. They are largely used, for example, in autonomous warehouses or automated city transport systems. In this work, we present the Concurrent Shortest Path Problem. It is a variant of the Shortest Path Problem in which, given a discretized time horizon, is possible to handle multiple shortest paths, while avoiding collisions between vehicles. The aim of the problem is to minimize the total path length while avoiding collisions on nodes. We present two formulations for the problem. The first, consider a multilayer temporal graph, and the second is inspired by the bin packing problem. A deep comparison of these two formulations is performed, to analyze which one works better under which conditions. Finally, several tests were performed to assess the effectiveness of the proposed approaches.
TH 10:20 AM1 Audtorium A

Victor Hugo Vidigal Corrêa victor.vidigal@ufv.br

Federal University of Viçosa

Dong, Hang, Nagoya University; Iori, Manuel, University of Modena
and Reggio Emilia; Gustavo dos Santos, André, Federal University
of Viçosa; Yagiura, Mutsunori, Nagoya University; Zucchi, Giorgio,
University of Modena and Reggio Emilia

*An Iterated Local Search Algorithm for a Multi-period Orienteering Problem Arising in Car Patrolling*

In this work, we address a real-life multi-period orienteering problem
arising in a large Italian company that needs to patrol a vast area in order
to provide security services. The area is divided into clusters, and each
cluster is assigned to a patrol. A cluster comprises a set of customers,
each requiring different services on a weekly basis. Some services are
mandatory, while others are optional. It might be impossible to perform
all optional services, and each of them is assigned a score when performed.
The problem is to determine a set of routes, one for each patrol and each
day, that maximizes the total collected score, while meeting a number of
operational constraints, including hard time windows, maximum riding
time, and minimum time between two consecutive visits for the same
service at the same customer.

To solve the problem, we propose a mixed integer linear programming
(MILP) model and an iterated local search (ILS) algorithm. The ILS
invokes at each iteration an inner variable neighborhood descent (VND)
procedure. While the ILS uses large neighborhood structures to shake the
solution, the VND uses a set of more specialized neighborhood structures
in order to lead the solution to an improved locally optimal solution.

The performance of a commercial solver on the MILP model and of
the ILS heuristic was assessed by testing them on a large set of real-life
instances, from several provinces in Italy, provided by the company. The
MILP model was solved by using Gurobi 9.5 and was able to find optimal
solutions for small-size instances in a two-hour time limit. For larger-size
instances, the ILS heuristic yielded better solutions than Gurobi. The
solutions produced by the ILS were also better than those practically in
use at the company for all instances that were addressed.
TH 09:00 AM1 Auditorium A

Diego Maria Pinto diegomaria.pinto@iasi.cnr.it

IASI-CNR

Marco, Boresta, IASI-CNR; Annalivia, Croella, DIAG-SAPIENZA, Claudio, Gentile, IASI-CNR; Laura, Palagi, DIAG-SAPIENZA; Giuseppe, Stecca, IASI-CNR; Paolo, Ventura, IASI-CNR

*Optimal Network Design for Waste Management in Regional Districts: the PIPER Project*

Waste management (WM) optimization is one of the key tasks to realize circular economy and achieve sustainability in large metropolitan areas. In this regard, location models are one of the main quantitative tools for spatial planning of service networks and, in combination with other methods such as data analytics and simulation, they can be effectively used in order to support network reengineering processes. Considering the WM setting, these models are able to support the reality of decision making whenever they also take into account the underlying network changes such as demand evolution, cost patterns modifications, transport and facility technology progresses.

This work proposes a network design model for a large metropolitan area, as a part of regional research project named PIPER - Intelligent Platform for the Optimization of Recycling Operations (grant n. A0375-2020-36611). The project aims at exploiting advanced applied research in the fields of optimization and artificial intelligence, and to apply them to the problems related to the sustainability of recycling processes, in terms of environmental, social, end economic targets.

The reengineering of the waste management network allows the optimization of specific objectives, such as network crossing times, costs and waitings, while satisfying a variety of constraints both of recycling performance and of financial balance. Costs evaluation will take into account both facilities construction and maintenance costs and the transportation costs through the network. In the reengineered network a key role is played by the so called transshipment locations, facilities used to lower the time spent by collection vehicles travelling the network instead of collecting waste bins. The models take into consideration the regional allocation of waste storage, treatment and selection plants, the distribution and concentration of urban agglomerations and industrial districts. Regarding the type of facilities, we distinguish waste sorting plants, waste-to-energy plants, composting plants, incineration plants and landfills. These models can indeed suggest the location of a new facility based on the demand, the variability and the type of urban and industrial waste produced in the area.

Thus, applying the principles of self-sufficiency and proximity to disposal, we proceeded to the definition of mathematical models useful for recommending the type of strategic and operational interventions required

**Optimization on Graphs; Contributed Session**
to improve a regional waste management network.

Some of the environmental indicators and data used are the same monitored by the regional agency for environment protection ARPA, by the Italian agency ISPRA and by AMA Spa, the main logistic player in the region in question and one of the the biggest WM companies in Europe.

Optimization on Graphs; Contributed Session
TH 09:20 AM1 Auditorium A

Cristina Requejo crequejo@ua.pt

University of Aveiro

Pereira, António, University of Aveiro

*A preliminary approach to the short-length time-slotted routing topologies problem*

The data transmission process is of the utmost importance nowadays and consists of transferring data between digital devices. The process enables devices or components within devices to communicate between them and occurs via point-to-point data streams or channels. These channels may previously have been in the form of copper wires but are now much more likely to be part of a wireless network.

The way data is transmitted by these channels is regulated through protocols such as the Time Slotted Channel Hopping (TSCH). This is one of the medium access control modes that is defined in IEEE 802.15.4e standard, a protocol designed for the Industrial Internet of Things (IIoT) applications such as smart city, smart home, and smart factory. Data transmission in TSCH networks is performed according to a tight time schedule. The higher the time schedule length, the higher the energy consumption of the network nodes and the end-to-end transmission delay. The amount of data transferred within a given time period is the data transfer rate, which dictates whether or not a network supports tasks that require complex, data-intensive applications. A higher data throughput improves user experience and increases reliability. Thus is important the use of short-length time-slotted routing topologies.

In this work, we consider the problem of finding tree routing topologies that minimize the time-slotted length. We are given a network and a set of data packets that need to be sent to the root node. In order to reduce interferences, each node is active at most one time at each time-slotted (half-duplex) and once a packet is sent, it never stops and goes directly to the root node. The objective function, to be minimized, is the time-slotted length. We characterize the problem, propose a mixed integer linear programming formulation, and evaluate the influence of the characteristics of the problem on the solution. A computational experience is carried out to assess the solutions obtained and the proposed solution strategies.
TH 09:40 AM1 Auditorium A

David Rey david.rey@skema.edu

SKEMA Business School, Universite Cote d'Azur, Sophia Antipolis,
France

Jian, Sisi, Department of Civil and Environmental Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China; Huang, Wentao, Department of Civil and Environmental Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China

*MaaS network pricing with non-cooperative transportation service providers*

We address a pricing problem in the context of Mobility-as-a-Service (MaaS). The past decade has witnessed a significant increase in the diversity of urban mobility services. Ranging from conventional mass transportation, to shared mobility and on-demand transit services, these mobility solutions coexist and compete with each other in transportation networks. MaaS is an emerging business model that aims to integrate multimodal transportation solutions and provide seamless mobility solutions to users. This motivates the study of path-based pricing mechanisms where users are charged based on their path choice in a multimodal transportation network. Yet, most studies on MaaS have thus focused on characterizing travelers demand for this new service scheme rather than on providing optimized pricing mechanisms.

In this study, we consider a multimodal transportation network where nodes of the network represent trip origins, destinations, or transfer hubs across transportation services. Two nodes may be connected by one or more links representative of different transportation modes. We consider a set of trips representative of origin and destination pairs in the network with known travel demand. Each trip can be accomplished by traveling onto a path in the network connecting the origin and the destination of this trip. We model paths' attractiveness using generalized cost functions that combine path travel time and path cost. We consider that reserve mobility alternatives outside of the MaaS network are available and we use linear elastic travel demand functions to capture the proportion of demand served by a path.

Links of the network are assumed to be controlled by multiple profit-maximizing transportation service providers (TSPs). TSPs can adjust link fares to increase revenue subject to link capacity constraints. We take the perspective of a network regulator which aims to maximize ridership in the MaaS network by providing path-based subsidies to users while anticipating the strategies of non-cooperative TSPs and their effect on path generalized costs. This sets the basis for a Stackelberg game model wherein the leader player represents the network regulator and multiple follower players represent the TSPs. This game-theoretical framework is
known as a single leader multi-follower game (SLMFG).

We conduct a theoretical analysis of this SLMFG by identifying neces-
sary and sufficient conditions for the existence of solutions to the param-
eterized generalized Nash equilibrium problems (GNEP) that is played
amongst TSPs. Notably, we show that this GNEP is jointly convex and
use this property to develop an exact numerical approach to solve the
SLMFG. Numerical results reveal the impact of TSP competition in this
MaaS network pricing problem and shed novel insights into the design of
optimal path-based subsidy policies. We also investigate how subsidies
can be designed to promote equity in the MaaS network.
Continuous and Multiobjective optimization; Contributed Session

TH 10:00 AM1 Auditorium B

Maria Chiara Nasso mc.nasso@dimes.unical.it

University of Calabria

Sergeyev, Yaroslav D., University of Calabria; Lera, Daniela, University of Cagliari

Lipschitz global optimization using space-filling curves

A wide variety of applications in engineering, machine learning, elec-
tronics, optimal control are interested in Lipschitz global optimization
problems (see [1, 3]). In this work, we consider a multidimensional Lip-
shitz global optimization problem where the objective function is a black-
box function which is supposed to be multiextremal and hard to evaluate.
It is known that this optimization problem can be reduced to an equivalent
univariate Holder one through space-filling curves, (see [2, 4]). In this talk,
two different approximations of Peano-Hilbert curve are employed. The
first one is broadly used in global optimization whereas the second one,
the non-univalent approximation, is less known. Each method is tested
on 900 randomly generated test functions taken from the literature. Nu-
merical experiments confirm advantages of the presented algorithms with
respect to their direct competitors.

[1] Lera D. and Sergeyev Y. D. Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants. Communications in Nonlinear Science and Numerical Simulation., 23(1):328-342, 2015. [2] Sergeyev Y. D. An information global optimization algorithm with local tuning. SIAM J. Optim., 5(4):858-870, 1995.
[3] Sergeyev Y. D. and Kvasov. D. E. Deterministic Global Optimization: An Introduction to the Diagonal Approach. Springer, New York, 2017.

[4] Sergeyev Y. D., Strongin R. G. and Lera D. Introduction to Global Optimization Exploiting Space-Filling Curves. Springer, New York, 2013.

[5] Strongin R. G., Sergeyev Y. D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Kluwer Academic Publishers, Dordrecht, 2000.
TH 10:20 AM1 Audtorium B

Sara Mattia sara.mattia@iasi.cnr.it

IASI-CNR

*Optimistic vs Pessimistic Policy in Bilevel Programming*

Bilevel programming problems models situations where two stakeholders hierarchically ordered, known as leader and follower, are involved in a decision process. This leads to a mathematical model with a nested structure. Depending on the cooperation between the leader and the follower, there exists two versions of the same bilevel problem: an optimistic version, where the leader and the follower cooperate, and a pessimistic version, where there is no cooperation. These two policies correspond, in general, to different solutions of the problem. We consider mixed integer linear bilevel programming problems and describe necessary and sufficient conditions ensuring that the policy can be neglected, as the optimistic and the pessimistic problem produce the same solution. We also analyze a simple situation where, contrary to what one may expect, this is not the case.

Continuous and Multiobjective optimization; Contributed Session
TH 09:00 AM1 Audtorium B

Andrea Cristofari andrea.cristofari@uniroma2.it

Univ di Roma Tor Vergata

*A decomposition method for lasso problems with zero-sum constraint*

In this talk, an algorithm is presented to solve lasso problems with a constraint imposing that the sum of all variables is zero. Models of this type are commonly required for the analysis of compositional data in high-dimensional spaces. The proposed method uses a tailored active-set technique to estimate the zero variables in the optimal solution and a 2-coordinate descent scheme to update the variables. At each iteration, the algorithm chooses between two different strategies by a simple test based on the progress in the objective function. In particular, the first strategy requires to compute the whole gradient of the smooth term of the objective function and is more accurate in the active-set estimate, while the second strategy only needs to compute partial derivatives and is computationally more efficient. Global convergence of the algorithm to optimal solutions is proved. Finally, numerical results are presented on synthetic and real datasets, showing the effectiveness of the proposed method.

Continuous and Multiobjective optimization; Contributed Session
TH 09:20 AM1 Audtorium B

Terézia Fulová terezia.fulova@gmail.com

Faculty of Mathematics, Physics and Informatics, Comenius Uni-
versity in Bratislava

Trnovská, Mária, Faculty of Mathematics, Physics and Informatics, Comenius University in Bratislava

*A conic optimization approach for solving Procrustes problems with quadratic constraints*

A Procrustes problem (PP) is a matrix approximation problem that searches for a transformation matrix of the given dataset to fit another dataset. Since their first appearance in psychometrics, PPs have arisen in many applications such as factor analysis, multivariate analysis, computer vision, multidimensional scaling, or global positioning systems. However, there are still subclasses of PPs lacking an effective solving algorithm. In this contribution, we introduce a rank-constrained semidefinite reformulation of the PP with quadratic constraints representing a specific transformation matrix. To solve rank constrained semidefinite problems, we apply a semidefinite relaxation and a modified rank reduction algorithm based on solving semidefinite programs. Unlike other methods, our approach can be applied to a wider class of PPs, including PPs with different types of transformation matrices, weighted PPs, PPs with partially specified targets, or PPs with additional affine constraints. We demonstrate our approach's performance while solving orthogonal Procrustes problems.
TH 09:40 AM1 Auditorium B

Rosario Messana rosario.messana@unimi.it

Università degli Studi di Milano

*Enhancing online combinatorial optimization with linear profits using mathematical programming*

We consider the following class of online optimization problems: the decision maker chooses a vector in {0, 1}^d and then observes a linear profit whose parameters are unknown until the decision maker's choice is made. The goal is to maximize the cumulative profit up to T iterations with respect to the best cumulative profit in hindsight.

The problem and some of its variants have been addressed in several works, including Freund & Shapire 1997, Koolen et al. 2010, and Pasteris et al. 2019. It is in fact suitable to model combinatorial optimization problems such as online facility location, online 0-1 knapsack and many others. A common strategy to address it is to relax the integrality constraints on the decision variables and to interpret the profit as the expected value of the same profit with binary variables. This step is key to enable the use of analytical methods like e.g. online convex optimization algorithms, and to obtain good regret bounds, i.e. sub-linear with respect to T. In fact, previous attempts introduce frameworks that alternate an online optimization step for the update of the relaxed variables with a randomized decision step for the choice of the binary-valued decision vector based on probabilistic interpretation of the updated relaxed variables. These frameworks lack in the capability of being together efficient and open to the insertion of arbitrary constraints on the decision vector.

We investigate both theoretically and experimentally the introduction of methods involving mixed integer programming resolution to address sub-problems of the problem described above. We are indeed motivated by the idea of estimating the applicability and flexibility in similar online settings. The aim of our work is to provide methods that improve on the generality of the existent approaches and that ensure good empirical efficiency.
Variational Inequalities and equilibrium problems;
Contributed Session

TH 11:30 AM2 001

M. Angeles Caraballo mcaraba@us.es

Universidad de Sevilla

Zapata, Asunción, Universidad de Sevilla; Monroy, Luisa, Universidad de Sevilla; Mármol, Amparo, Universidad de Sevilla

*Environmental damage reduction: when countries face conflicting objectives*

Numerous international environmental agreements of countries have been aimed at limiting their polluting emissions. However, this is an arduous goal to achieve since it involves two often conflicting objectives for their governments: maximizing their monetary benefits and minimizing the perception of environmental damage, both of which depend on the level of pollution emitted by the set of all countries. Taking these two objectives into account, the situation is analyzed as a two-criteria game where each country has a tolerance threshold with respect to global emissions. The approach considered makes it possible to deal with a key issue in the analysis: the fact that it is not possible to compare in monetary terms the results obtained when countries act strategically in pursuit of their objectives. We show that depending on the relationships between the thresholds for each country, different sets of equilibria arise. A significant consequence of this research is that all of these equilibria provide strategies with a positive effect on emission reductions and can play an important role in reversing climate change.
TH 11:50 AM2 001

Valerio Dose valerio.dose@uniroma1.it

"Sapienza" - Università di Roma
Cominetti, Roberto, Universidad Adolfo Ibáñez; Scarsini, Marco, LUISS

*Active Network and Price of Anarchy in Multi-Commodity Routing Games with Variable Demands*

Equilibria in nonatomic routing games describe how traffic distributes on a network used by a large number of agents which are interested in minimizing their own delay. The mathematical model where such equilibria arise, is composed of a directed graph representing the network, and cost functions associated to each edge of the graph, which represent the delay experienced on an edge, as a positive nondecreasing function of the amount of traffic traveling on that same edge. In this framework, equilibria can be described as optimal solutions to a minimization problem. Nevertheless, they are usually not optimal with respect to a different, and more meaningful, objective function, which is the total delay experienced by all users of the network. For this reason, the Price of Anarchy has been considered in the literature, as an index of the inefficiency of equilibria. It is defined as the ratio of the total delay in an equilibrium and the optimal total delay.

The traditional way of studying the Price of Anarchy has been determining upper bounds for it, which are tight in the worst case scenario. Recently, the Price of Anarchy has also been considered as a function of the traffic demand. In a previous publication, the authors analyze networks with a single commodity, which means that all users want to travel between the same origin and destination in the graph. In this situation, it is shown that with affine cost functions, the Price of Anarchy as a function of the demand, achieves local maxima only at points where it is not differentiable, and between two such points it can achieve at most one smooth local minimum. This confirms a behavior observed in previous empirical works on the subject. An important concept to be considered in this analysis is the one of active network, which is, for each level of demand, the set of edges which are used in equilibrium. If the active network is not constant in a neighborhood of some demand, we call such a demand a breakpoint. It is exactly at breakpoints that the Price of Anarchy can be non differentiable and achieve a local maximum.

In the work we are presenting, we apply the same approach to networks with multiple commodities. In these type of networks, the users can be of different types, each of them traveling between different pairs of vertices of the graph. We consider the Price of Anarchy not only as a function of every possible vector of demands across all the commodities, but also as functions of a single real parameter where the vector of demands is given by a fixed demand function of the parameter. In both situations we

**Variational Inequalities and equilibrium problems; Contributed Session**
can define the active network and breakpoints analogously to the single
commodity case. We show that, with affine cost functions, if the demand
function keeps the vector of demands on a line through the origin, then the
behavior of the Price of Anarchy is the same as in the single commodity
case. However, this is not true if the vector of demands moves on a line
which does not go through the origin. In networks with continuously
differentiable cost functions and strictly positive derivatives, we prove a
result concerning the left and right derivative of the Price of Anarchy at
breakpoints when the demands vary on a line through the origin. Finally,
we also study how the active network varies in the whole spectrum of
demands, focusing on the case of parallel networks where all types of
users travel between the same two vertices, but each type uses a different
set of paths.

Variational Inequalities and equilibrium problems; Contributed
Session
TH 12:10 AM2 001

Marcello Sanguineti marcello.sanguineti@unige.it

University of Genova

Olga, Matthiopoulou, Vodafone Greece; Benoit, Bardy, University of Montpellier; Antonio, Camurri, University of Genova; Giorgio, Gnecco, IMT Lucca; Denis, Mottet, University of Monptellier

*Detection of the Origin of Movement: Graph-Theoretical Model and Data Processing*

The agreement among participants in a survey is used to define a ground truth for the origin of full-body human movement, as it is perceived by observers. This may differ from the physical origin of movement, as it is defined by experts. Then, a computational model based on the theory of cooperative games is exploited to find automatically the perceived origin of movement. In more details, a transferable-utility game is built over a skeletal representation of the human body, based on a characteristic function related to how movement features change on adjacent vertices of the graph (joints), which are the players of the game. Then, the Shapley values of the joints are evaluated and used to extract a higher-level feature, which provides an estimate of the joint from which movement either originates or propagates. The method developed in [1,2] is refined (as in [3]) by considering a pre-processing of the available motion capture dataset, dealing with issues such as missing data, outlier detection, and noise reduction. This research received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No. 824160 EU (Project EnTimeMent) and from the Università Italo-Francese (project GALILEO 2021 no. G21_89). G. Gnecco and M. Sanguineti are members of Gruppo Nazionale per l'Analisi Matematica, la Probabilità e le loro Applicazioni (GNAMPANational Group for Mathematical Analysis, Probability and their Applications) of the Istituto Nazionale di Alta Matematica (INdAMNational Institute of Higher Mathematics).

[1] Kolykhalova, K., Gnecco, G, Sanguineti, M., Camurri, A., Volpe, G.: Graph-restricted game approach for investigating human movement qualities. Proc. of the 4th Int. Conf. on Movement Computing, 2017. [2] Kolykhalova, K., Gnecco, G, Sanguineti, M., Camurri, A., Volpe, G.: Automated analysis of the origin of movement: An approach based on cooperative games on graphs. IEEE Trans. on Human Machine Systems, 2020. [3] Matthiopoulou, O., Bardy, B, Gnecco, G., Mottet, D., Sanguineti, M., Camurri, A.: A computational method to automatically detect the perceived origin of full-body human movement and its propagation. Proc. of the 1st Int. Workshop on Multi-Scale on Movement Technologies, Utrecht, the Netherlands, 2020.

**Variational Inequalities and equilibrium problems; Contributed Session**
TH 12:30 AM2 001

Ricardo Almeida ricardo.almeida@ua.pt

University of Aveiro, Aveiro, Portugal

*Optimization conditions for functionals dealing with variable order fractional derivatives and with dependence on an arbitrary function*

In this work we combine two ideas: fractional derivatives of variable order and fractional derivatives depending on another function. With such operators, we develop a variational problem theory by presenting necessary conditions of optimization for different kind of problems. An integration by parts formula is also proven, fundamental for the developing of our theory.

Variational Inequalities and equilibrium problems; Contributed Session
Discrete Optimization; Contributed Session

TH 11:30 AM2 002

Elena Rener elena.rener@polito.it

Politecnico di Torino

Salassa, Fabio, Politecnico di Torino; T'kindt, Vincent, Université
de Tours and Politecnico di Torino

*On the solution of optimal timing problems for single machine reschedul-
ing problems with new jobs arrival*

This study on the idle times insertion is motivated by a reschedul-
ing problem on a single machine with unpredicted new jobs arrival. In
the problem, a regular scheduling function is minimized and there is a
constraint on the absolute time deviation of jobs w.r.t. the original op-
timal schedule. This second constraint is an alternative for modelling a
second objective of the rescheduling problem, which is the minimization
of the disruption induced by per-turbing the initial schedule of old jobs.
When the perturbation is computed as the absolute deviation from the
original completion time, then it is given by a non-regular function. At
a first glance, the minimization of a regular objective function leads to
active schedules with no idle times. However, the second objective, even
if it is considered as an εconstraint, may generate idle times in an op-
timal solution. When solving any of the related problems, there is the
need of identifying whether a solution may or may not include idle times
to develop the right model and a suitable solving procedure. This work
presents such an analysis on the above-mentioned rescheduling problem,
with different classical scheduling objective functions. Several underlying
arguments around the insertion of idle times are presented, such as
causes, special cases and examples. The analysis is then extended to
cover all typical objective functions used in scheduling. As a result, for
each objective function, it is presented a list of properties, that include if
the problem belongs to the exceptions of those not containing idle times,
properties on the ordering of the jobs - which is related to the insertion
of idle times if there exist special cases with different properties and,
whenever known, the complexity of the problem.
TH 11:50 AM2 002

Tommaso Schettini tommaso.schettini@polimi.it

Politecnico di Milano

Gendreau, Michel, Polytechnique Montreal, CIRRELT; Jabali, Ola, Politecnico di Milano; Malucelli, Federico, Politecnico di Milano

*A Heuristic Algorithm for the Capacitated Demand-Driven Metro Timetabling Problem*

Metro lines are normally operated with regular timetables, where trains have a constant headway between all stations. Such timetables are typically designed based on aggregate demand forecasts for time periods spanning a number of hours, e.g., morning peak.

Given the recent technological advances in passenger billing and tracking (e.g., smart transit cards), it is now possible to predict passenger demand at a refined temporal level. This possibility prompted research into non-periodic timetabling strategies that directly adapt services to a time-dependent demand profile. However, operating on a refined temporal level necessitates dealing with detailed vehicle scheduling decisions to ensure the feasibility of the resulting timetable. Moreover, a detailed modeling of passengers boarding is required so as to optimize service measures. For these reasons, non-periodic models are far more complex than periodic ones. In this vein, a problem entitled the demand-driven timetabling problem (DDTP) has been proposed by [1]. The DDTP explicitly matches the train timetable to a given passenger demand, so as to minimize the total passenger waiting times. Specifically, the trains are scheduled, without predetermined frequencies, using short-turning operations. These imply that trains are not required to serve the line from terminal to terminal, but instead, may reverse their direction before reaching a terminal of the line.

Trains are assumed to be uncapacitated in the DDTP. In this paper, we explore the capacitated demand-driven timetabling problem (CDDTP). Indeed, the integration of capacities in the DDTP introduces a number of complexities related to modeling and evaluating passenger waiting times. In the CDDTP, capacities are modeled through the instantaneous capacity utilization of the individual trains, assuming a non-centralized boarding policy, i.e., that the boarding decisions of the passengers may not be controlled. This implies that when vehicle capacity is not sufficient to board all waiting passengers, which passengers end up boarding is determined through a fixed boarding policy.

To efficiently solve the CDDTP, we develop an effective Iterated Local Search metaheuristic for the problem. The development of the proposed heuristic involved several algorithmic contributions. We devised a polynomial evaluation procedure for assessing the total passenger waiting time generated by a given timetable, and an effective lower-bound which is evaluated in linear time. The local search phase of the ILS is implemented
through a variable neighborhood search (VNS), for which we developed three tailored neighborhoods. Finally, we present a modified evaluation procedure designed for efficiently evaluating a subset of the timetables that are produced during the local search phase.

Through extensive computational experiments, we evaluate the effec-
tiveness of the developed heuristic and benchmark the achieved solutions
against the results of an exact algorithm for the DTPR. Additionally, we
demonstrate the operational advantages of the CDDTP by comparing it
with periodic timetables.

[1] T. Schettini, O. Jabali and F. Malucelli, “A Benders decomposition algorithm for demand-driven metro scheduling”, Computers & Operations Research 138, 105598, 2022.
TH 12:10 AM2 002

Domenico Serra dserra@unisa.it

University of Salerno

Cerulli, Raffaele, University of Salerno; Gentili, Monica, University of Louisville; Rahamn, Amanatur, University of Louisville; Sorgente, Carmine, University of Salerno

New Approaches for the kidney exchange problem

In this talk, we address the well-known kidney exchange problem (KEP), that arises in the context of transplant programs allowing two or more incompatible patient-donor pairs to swap kidneys. Often when the patient needs a kidney transplant, a possible donor is identified among the family members, but there may be problems related to incompatibility of blood groups or problems related to other pathologies. What is typically done is to swap donors between patients. This problem can be modelled through a directed graph, in which the nodes represent the incompatible patient and relative donor pairs, while there is a directed arc from node i towards node j if the i-th donor can donate to the j-th patient. The probability of success of the transplant is associated with each arc. The problem consists in identifying oriented cycles that do not intersect, with the aim of covering as many nodes as possible, maximizing the probability of success. Identifying cycles guarantees that, if the i-th donor donates a kidney to the j-th patient, the i-th patient receive a kidney, too. Any donor donates a kidney if and only if its related patient receives a compatible one. Prohibiting intersections ensures that a donor can only donate once and a patient receives a kidney from only one donor. This problem has been extensively treated in the literature through both exact and heuristic approaches. We want to provide new models and algorithms based on the arc-deleting approach. The idea behind the arc-deleting approach is to remove arcs from a graph with the aim of identifying a specific sub-structures like oriented cycles. To test the proposed approaches, we used several instances to see how promising they are.
TH 12:30 AM2 002

Alice Raffaele aliceraffaele@univr.it

Department of Computer Science, University of Verona, Strada Le
Grazie 15, 37134 Verona, Italy

Romeo, Rizzi, Department of Computer Science, University of Verona, Strada Le Grazie 15, 37134 Verona, Italy

*On Vertex Enumeration and Hypergraph Dualization: relevance in combinatorial optimization and a new decomposition approach*

Any convex polyhedron can be described through two different equiv-
alent formulations: as the intersection of closed halfspaces or as the
Minkowski sum of the convex hull of a finite set of points, plus a conical
combination of vectors [1]. By asking whether there is a way to pass from
one representation to the other, the Vertex Enumeration and the Facet
Enumeration problems arise. In 1992, Lovasz [2] underlined the similar-
ity between these two problems and the Hypergraph Dualization problem.
Consider the set-covering polyhedron P(A, 1) := Ax >= 1|xinRⁿ, x >= 0
with only integral vertices and A as ideal matrix [3]. These vertices are
in bijection with the minimal transversals of the hypergraph H associated
to the matrix A. Indeed, the columns and the rows of A correspond to
the vertices and the characteristic vectors of the hyperedges of H, respec-
tively. Thus, the problem of enumerating the vertices of P is equivalent
to the problem of computing the minimal transversals of H. Then, an effi-
cient procedure to solve the Hypergraph Dualization problem would lead
to an efficient procedure to also solve this special restriction of the Ver-
tex Enumeration (and vice versa), but may not hold for the general case.
Anyway, given the celebrated result by Fredman and Khachiyan in 1996
[4], the vertices of P can be enumerated in quasi-polynomial time, which
makes the Vertex Enumeration problem unlikely to be NP-hard. In this
talk, first we remark the relevance of such problems in operations research
and combinatorial optimization, and we provide a brief overview about
the main approaches to solve the Vertex (Facet) Enumeration problem.
Then, we present another possible decomposition for the Hypergraph Du-
ality problem, which the Hypergraph Dualization problem can be reduced
to [5]. This decomposition offers a strong bound which, however, in the
worst case, has the same time complexity as [4]. Anyway, these results
encourage the study and the development of other approaches, also to
investigate the exact complexity of the problems, which is still an open
question.

[1] Ziegler, G. M. (2012). Lectures on polytopes, volume 152. Springer Science & Business Media. [2] Lovász, L. (1992). Combinatorial optimization: some problems and trends. DIMACS, Center for Discrete Mathematics and Theoretical Computer Science. [3] Boros, E., Elbassioni, K., Gurvich, V., and Makino, K. (2009). Generating vertices of polyhedra and related problems of monotone generation. Proceedings of the Centre
de Recherches Mathématiques at the Université de Montréal, special issue on Polyhedral Computation (CRM Proceedings and Lecture Notes), 49:15-43. [4] Fredman, M. L., and Khachiyan, L. (1996). On the Complexity of Dualization of Monotone Disjunctive Normal Forms. Journal of Algorithms, 21(3):618-628. [5] Raffaele, A., and Rizzi, R., A new decomposition for the Monotone Boolean Duality problem. Submitted.
# NOML, Nonlinear Optimization and Machine Learning; Invited Session

TH 11:30 AM2 003

Cecilia Salvatore cecilia.salvatore@uniroma2.it

Department of Civil Engineering and Computer Science, University of Rome Tor Vergata, Rome

Piccialli, Veronica, Department of Computer Control and Management Engineering Sapienza University of Rome

*Model Extraction based on Counterfactual Explanations*

Automated decision-making classification systems based on Machine Learning algorithms are often used in many real-life scenarios such as healthcare, credit, or criminal justice. There is thus increasing interest in making Machine Learning systems trustworthy: interpretability, robustness, and fairness are often essential requirements for the deployment of these systems. In particular, according to the European Union's General Data Protection Regulation (GDPR), automated decision-making systems should guarantee the "right to explanations", meaning that those affected by the decision may require an explanation. Counterfactual Explanations are becoming a de-facto standard for a post-hoc explanation. Given an instance of a classification problem, belonging to a class, its counterfactual explanation corresponds to small perturbations of that instance that allow changing the classification outcome. The objective of this work is to try and exploit the information revealed by a small set of examples with their counterfactual explanations to build a surrogate model of the classification system. The idea is to define an optimization problem that provides in output a Forest of Optimal Trees as close as possible to the original classification model, given the information derived from the counterfactual points. This tool can be used either to attack the original model or to improve it, depending on the application context. Preliminary results show the viability of this approach.

NOML, Nonlinear Optimization and Machine Learning; Invited
Session
TH 11:50 AM2 003

Enrico Civitelli enrico.civitelli@unifi.it

Università degli Studi di Firenze
Sortino, Alessio, Università degli Studi di Firenze; Lapucci, Matteo, Università degli Studi di Firenze; Bagattini, Francesco, Flair Tech; Galvan, Giulio, Flair Tech

*A Robust Initialization of Residual Blocks for Effective ResNet Training without Batch Normalization*

Batch Normalization is an essential component of all state-of-the-art neural networks architectures. However, since it introduces many practical issues, much recent research has been devoted to designing normalization-free architectures. In this paper, we show that weights initialization is key to train ResNet-like normalization-free networks. In particular, we propose a slight modification to the summation operation of a block output to the skip-connection branch, so that the whole network is correctly initialized. We show that this modified architecture achieves competitive results on CIFAR-10 without further regularization nor algorithmic modifications.
TH 12:10 AM2 003

Sara Venturini sara.venturini@math.unipd.it

University of Padua
Rinaldi, Francesco, University of Padua; Tudisco, Francesco, Gran Sasso Science Institute; Cristofari, Andrea, University of Padua

*Semi-supervised learning in multilayer hypergraphs*

A variety of complex systems has been successfully described as net-
works whose interacting pairs of nodes are connected by links. However,
in real-world applications, we need to describe interactions in more de-
tailed and varied ways. Many real systems display collective actions of
groups of nodes and simplicial complexes or hypergraphs are the natu-
ral candidates to describe these group interactions. Moreover, often we
can measure different types of relationships between the same nodes, and
multilayer networks provide the mathematical formalism to describe these
multi-channel interactions. Evidence show that each of these tools can
improve modelling capacities with respect to standard graphs. However,
relatively few studies simultaneously consider multilayer and higher-order
structures in complex networks so far. This is also due to the fact that
such a sophisticated structure comes at the cost of an additional com-
plexity and a harder treatability. In this work we take a first step in the
study of semi-supervised learning over multilayer hypergraphs, trying to
deal with this additional complexity.
TH 12:30 AM2 003

Leonardo Galli galli@mathc.rwth-aachen.de

RWTH Aachen

Rauhut, Holger, RWTH Aachen; Schmidt, Mark, UBC

Robustness and Generalization in Training Deep Neural Networks

Deep Learning (DL) models are nowadays the key to achieve state-of-the-art performances in a wide range of real problems. Despite their extensive use, the understanding of DL is limited and the theoretical guarantees are few. Moreover, performances of DL models are very sensible to various training algorithmic choices, for instance and above all, the learning rate. The robust selection of the learning rate is indeed a very central topic in DL and it is still one of the main concern of optimization researchers working in this area. In this project, we will study non-monotone Stochastic Gradient Descent (SGD) algorithms to improve the robustness of the training method w.r.t. the learning rate. Despite these methods are a very natural choice for highly nonlinear models, this is the first time in which they are applied on the top of a SGD-like algorithm. A new theory has been developed to adapt the convergence rates of deterministic nonmonotone methods to the stochastic setting. Numerical results are showing that the intrinsic properties of nonmonotone methods are extremely well suited when dealing with large-scale highly-nonlinear stochastic problems.

NOML, Nonlinear Optimization and Machine Learning; Invited Session
# PRPI, Path and routing problems in industry;
Invited Session

TH 11:30 AM2 Auditorium A

Stefano Ardizzoni stefano.ardizzoni@unipr.it

Università degli Studi di Parma
Consolini, Luca, Università degli Studi di Parma; Laurini, Mattia, Università degli Studi di Parma; Locatelli, Marco, Università degli Studi di Parma

*Shortest path with acceleration constraints: Complexity and approximation algorithms*

We introduce a variant of the Shortest Path Problem (SPP), in which we impose additional constraints on the acceleration and speed over the arcs, and call it Bounded Acceleration SPP (BASP). This variant is inspired by an industrial application: a vehicle needs to travel from its current position to a target one in minimum-time, following pre-defined geometric paths connecting positions within a facility, while satisfying some speed and acceleration constraints, depending on the vehicle position along the currently traveled path. The motivation for studying this problem is related to the fact that the shortest path is not always the fastest one. BASP is the combination of two different problems. The first is the combinatorial one of detecting the best path from a source to a destination node over an oriented graph with constant costs associated to its arcs (i.e., the SPP). The second is the continuous one of minimum-time speed planning over a fixed path, under speed and acceleration constraints. We characterize the complexity of BASP, proving its NP-hardness. Indeed, in BASP we still have the combinatorial search for a best path as in SP. However, differently from SP, the cost of an arc (more precisely, the time to traverse it) is not a constant value, but depends on the travel speed along the arc itself. This, in turn, depends on the speed and acceleration constraints not only over the same arc, but also over those preceding and following it, along the selected path. We also show that, under additional hypotheses on problem data, the problem admits a pseudo-polynomial time-complexity algorithm. Moreover, we present an approximation algorithm with polynomial time-complexity with respect to the data of the original problem, and the inverse of the approximation factor $\epsilon$. The idea is to discretize the squared speeds, in order to obtain a finite set of possible squared speeds at each node of the graph. In this way, imposing that the initial and final squared speeds along each arc belong to the discretized set of squared speeds, the set of possible speed profiles over each arc becomes finite. Hence, we can define an extended graph that enables us to solve this discretized version of the problem by means of Dijkstra's algorithm.

PRPI, Path and routing problems in industry; Invited Session
TH 11:50 AM2 Auditorium A

Francesco Gallesi francesco.gallesi@unimore.it

DISMI University of Modena and Reggio Emilia
Côté, Jean-François, CIRRELT and Laval University; Alves de Queiroz, Thiago, IMTec Federal University of Catalão; Iori, Manuel, DISMI University of Modena and Reggio Emilia

*A Branch-and-Regret Algorithm for the Same-Day Delivery Problem*

In the last years, the number of e-commerce sellers has increased, and many companies changed their focus to direct-to-customer deliveries to improve their business. Online purchases have been a more and more common practice to request services or goods at home. This trend has increased because of the Covid-19 pandemic, which made people reluctant to leave their homes. Online purchases have become a crucial logistic activity and managing the problem in an efficient way is not an easy task. Historically, this type of problem has been addressed in the field of stochastic dynamic vehicle routing problems. In the problem we face, the requests arrive dynamically during the day and must be served within a strict time window. The aim is to use a fleet of vehicles to maximize the number of served requests and minimize the traveled distance. This problem is known in the literature as the Same-Day Delivery problem (SDDP). We first solve the SDDP by means of a simple but efficient reoptimization heuristic that locks past decisions, adds newly revealed requests, and then optimizes the routing plan with an adaptive large neighborhood search (ALNS). We then propose a scenario-based planning approach (SBPA) that considers fictive requests sampled by a probability distribution. In each scenario, a routing plan is optimized with the ALNS, and a consensus function chooses which plan to adopt. Finally, we propose a branch-and-regret (BR) algorithm that extends the SBPA by evaluating different possible alternatives for each request. We consider as alternatives a vehicle departing now, a vehicle departing in the future, and the assignment of a request to third-party logistic operator. We create different routing plans by branching on these alternatives and invoking the ALNS. The plan to implement is chosen again with the help of a consensus function. The algorithms are also adapted to solve the problem variant where vehicles are allowed to perform preemptive returns to the depot. Extensive computational experiments on a large variety of instances prove the outstanding performance of the BR, also in comparison with recent literature, in terms of served requests, traveled distance, and computing time.

PRPI, Path and routing problems in industry; Invited Session
TH 12:10 AM2 Auditorium A

Tobia Marcucci tobiam@mit.edu

MIT, Cambridge (MA), USA

*Shortest paths in graphs of convex sets, and their applications in control and robotics*

Given a graph, the Shortest-Path Problem (SPP) requires finding a sequence of edges with minimum cumulative length that connects a source to a target vertex. We consider a generalization of this classical problem in which each vertex in the graph is paired with: i) a convex set, and ii) a point in the convex set that represents the spatial location of the vertex. As opposed to the classical SPP, where edge lengths are constants, we let the length of an edge be a convex function of the location of its endpoint vertices. The problem we obtain is then mixed discrete-continuous, as it requires to simultaneously identify a discrete path in the graph and optimize the continuous location of the vertices visited by the path. We name this family of optimization problems "SPPs in graphs of convex sets," and we show how this framework encompasses a wide variety of decision problems in control, robotics, networks, and logistics.

The versatility of the framework we propose is reflected in the problem complexity: contrarily to the classical SPP, the SPP in graphs of convex sets is easily seen to be NP-hard. Our main contribution is formulating this problem as a Mixed-Integer Convex Program (MICP) whose convex relaxation is very tight, but also lightweight; making it possible to efficiently find globally-optimal paths in large graphs and in high-dimensional spaces.

The first application we consider is optimal control of hybrid systems (i.e., dynamical systems that exhibit both continuous and discrete behaviors). This topic has been intensively studied in the last two decades, and has already had a strong impact in the automotive industry, in power systems, and in robotics. We show that optimal control problems for hybrid systems are naturally formulated as SPPs in graphs of convex sets, and therefore can be tackled using the optimization framework we propose. In our computational experience, this leads to MICPs that are orders of magnitude faster to solve than state-of-the-art formulations of these control problems.

The second application we discuss is robot motion planning in environments with obstacles. Using existing algorithms, we efficiently decompose the robot environment into a collection of collision-free convex regions. Then we design a continuous trajectory within the union of these "safe" regions using Bezier curves and our SPP framework. In stark contrast with existing mixed-integer motion planners, in the great majority of the practical applications, the convex relaxation of our MICPs is extremely tight, if not exact. The solution of a single convex program, possibly followed

PRPI, Path and routing problems in industry; Invited Session
by a simple rounding step, is then typically sufficient to detect a globally-
optimal collision-free trajectory. From a practical perspective, planning
problems that were previously tackled with mixed-integer semidefinite
programming can now be reliably solved via a single second-order-cone
program. We demonstrate our planning algorithm on a variety of robotic
systems, including quadrotors flying in cluttered environments and robot
arms in high-dimensional manipulation tasks.
TH 12:30 AM2 Auditorium A

Irene Saccani irene.saccani@unipr.it

Università degli Studi di Parma

Ardizzoni, Stefano, Università degli studi di Parma; Consolini, Luca, Università degli studi di Parma; Locatelli, Marco, Università degli studi di Parma

*Multi-agent Path Finding on Strongly Connected Digraphs*

We consider a set of agents moving along the edges of a directed graph. Each agent is not allowed to move in a node occupied by another agent. The Multi-Agent Path Finding (MAPF) consists in finding a sequence of moves that brings the agents to assigned target positions, avoiding collisions. It is known that finding a solution with the minimum number of moves is NP-hard. Indeed, the various optimal solvers considered in literature have a computational time that grows exponentially with the number of agents. The literature also presents suboptimal solvers with lower computational time. Anyway, they are not complete, that is, they are not always able to find a feasible solution. Complete, suboptimal algorithms that run in polynomial time exist for undirected graphs and for biconnected directed graphs. In this paper, we will show a new way of combining these algorithms to find a feasible solution for strongly connected directed graphs in polynomial time. The proposed method always finds a feasible solution, if it exists. Essentially, our approach generalizes the method presented in [3] to digraphs. Namely, we decompose the graph into biconnected components, and use some methods presented in [1] to reconfigure the agents in each biconnected component. We present a method, based on [2], that checks the problem feasibility in linear time with respect to the number of nodes. Also, we present an algorithm (diSC) that finds a solution for all admissible problems with at least two holes, generalizing the method in [3]. We ran the algorithm on a set of random graphs. The results show that the solution length and the computational time grow polynomially with respect to the number of nodes and the number of agents.

[1] Adi Botea, Davide Bonusi, and Pavel Surynek. Solving multi-agent path finding on strongly biconnected digraphs. Journal of Artificial Intelligence Research, 62:273314, 2018. [2] Gilad Goraly and Refael Hassin. Multi-color pebble motion on graphs. Algorithmica, 58(3):610–636, 2010. [3] Athanasios Krontiris, Ryan Luna, and Kostas Bekris. From feasibility tests to path planners for multi-agent pathfinding. In International Symposium on Combinatorial Search, volume 4, 2013.

PRPI, Path and routing problems in industry; Invited Session
Applications: Sustainability, Health Care; Contributed Session

TH 11:30 AM2 Auditorium B

Caterina Tamburini caterina.tamburini@optit.net

Optit

Bettinelli, Andrea, Optit; Pozzi, Matteo, Optit

CHP Systems Optimization in Presence of Time Binding Constraints

As decarbonization becomes a global priority, there is a need to increase the efficiency of energy production. Combined Heat and Power (CHP) is an energy efficient technology that generates electricity and captures the heat that would be wasted otherwise in order to provide thermal energy, often used to feed district heating networks. Unit Commitment (UC) is a key problem in this context. The goal in UC is to determine a schedule for the machines that maximize the operative margin, satisfying a forecasted heat demand coming from a district heating network as well as functional and regulatory constraints deriving from system composition and placement. This gives rise to Unit Commitment (UC) problems. In this work, we formulate and solve Mixed Integer Linear Problems for the short-term optimization of real world CHP systems. We present some key features that make the problem hard to be solved in practice with particular attention to time binding constraints, e.g., limitations on the number of turn-ons over a period, minimum time on/off permanence, ramp-up and ramp-down constraints, heat storage, regulatory limitations defined over the legislative year. As for the latter, we study how Primary Energy Saving (PES) limitations introduced by the European Parliament Directives can be modeled in a MILP formulation and which are the critical aspects to consider. We then present a time-based decomposition meta-heuristic for the optimization of mid-term (i.e., one year budgeting) UC problems, with computational results obtained over real world problem optimizations. A relevant factor for the accuracy of the energy production plan is the ability to forecast the heat demand of the network. Thus, we developed a forecasting module that, given the historical heat demand and other relevant data, automatically builds accurate prediction models. Specifically, each predictive model is trained and tuned using the most appropriate machine learning technique among a pool of state-of-the-art algorithms. The methodology proposed is implemented within a Decision Support System currently in use by plant managers of several CHP systems connected to district heating networks dislocated in Italy. We give an overlook of the DSS interfaces and relative use cases. Further, we will introduce current development directions, such as the support for the integration with the power markets sessions, and enhancement to deal with plants where machines are operated in series and operating temperatures

Applications: Sustainability, Health Care; Contributed Session
become important decision variables along with the amount of energy produced.

Applications: Sustainability, Health Care; Contributed Session
TH 11:50 AM2 Auditorium B

Tine Meersman tine.meersman@ugent.be

Ghent University

Maenhout, Broos, Ghent University

*Multi-objective optimisation for constructing cyclic appointment schedules for elective and urgent patients*

In this paper, we study the construction of a cyclic appointment sched-
ule in an outpatient department. In particular, we determine the capacity
distribution between elective and urgent patients and the scheduling of
the time slots reserved for these patients such that the operational wait-
ing times of elective and urgent patients are minimised. The proposed
solution methodology devises a Pareto set of cyclic appointment sched-
ules based on these waiting times with different capacity allocations for
urgent patients. An approximation of the Pareto set of non-dominated
schedules is obtained using a multi-objective archived simulated annealing
heuristic. To accurately validate the cyclic appointment schedules, we in-
corporate operational decision-making via scheduling individual patients.
To this end, we simulate operational variability, i.e., patient arrivals, no-
show behaviour, punctuality and scan durations, based on real-life input
data. The patients are assigned one-by-one using an online scheduling
rule. Computational experiments are conducted with a real-life case study.
We compare different appointment scheduling rules and discuss the im-
pact of the capacity distribution between elective and urgent patients and
the timing of urgent slots in the cyclic appointment schedules. The results
show that the distribution of capacity between patient types, the timing of
urgent slots and appointment rules all have significant impacts on patient
waiting times. Appointment waiting times improve when urgent slots are
spread equally over and throughout the days considered and when the
BaileyWelch rule is used to schedule patients. Trade-offs between elective
and urgent waiting times resulting from different capacity distributions
or slot timing are exemplified via a Pareto front. The proposed method
outperforms relevant single-pass methodologies, and we demonstrate that
its performance is strengthened thanks to the integrated optimisation of
strategic, tactical and operational decisions.
TH 12:10 AM2 Auditorium B

Andrea Mancuso andrea.mancuso@unina.it

Department of Electrical Engineering and Information Technology,
University of Naples "Federico II"

M., Boccia, Department of Electrical Engineering and Information
Technology, University of Naples "Federico II"; A., Masone, Depart-
ment of Electrical Engineering and Information Technology, Univer-
sity of Naples "Federico II"; F., Messina, Betania Evangelical Hospi-
tal; A., Sforza, Optimization and Problem Solving Laboratory; C.,
Sterle, Department of Electrical Engineering and Information Tech-
nology, University of Naples "Federico II"

*Optimization for surgery department management: an application
to a hospital in Naples*

Surgery department with its operating rooms represents the financial
backbone of modern hospitals accounting the main part of a hospital cost
and revenue. Therefore, maximizing its efficiency is of vital importance
since it can have important implications on cost saving and patient sat-
isfaction. In this context, Operations Research methodologies can play a
relevant role supporting hospital executives in operating room manage-
ment and surgery scheduling issues. In particular, great relevance has
been given in literature to the Surgery Scheduling Problem. In its general
form, it consists in determining a day, an operating room and a starting
time of a set of surgeries. In this work, we address the Surgery Scheduling
Problem faced by a local hospital of Naples. The aim of the hospital is
to determine a surgery schedule capable of handling unforeseeable events
(e.g., the arrival of an emergency) while maximizing the number of per-
formed surgeries, according to some medical guidelines. This problem has
been modelled by an original integer linear programming formulation that
has been tested and validated on several instances derived from real data
provided by the hospital. Finally, the proposed formulation can be used
to simulate different surgery operating scenarios. The results of this sim-
ulation can be used to provide useful managerial insights for an efficient
schedule of the hospital surgeries.

Applications: Sustainability, Health Care; Contributed Session
TH 12:30 AM2 Auditorium B

Gabriele Zangara gabriele.zangara@unical.it

Department of Mechanical, Energy and Management Engineering,
University of Calabria

Rosita, Guido, Department of Mechanical, Energy and Management
Engineering, University of Calabria; Giuseppina, Ambrogio, Depart-
ment of Mechanical, Energy and Management Engineering, Univer-
sity of Calabria; Domenico, Conforti, Department of Mechanical,
Energy and Management Engineering, University of Calabria

*A flexible job shop scheduling model for Sustainable Manufacturing*

The research work was carried out with particular attention to the
use of energy in production processes and the costs deriving from its con-
sumption. The discussion was verticalized within a case study in the man-
ufacturing sector, developing and implementing an optimization model to
support the planning and scheduling of processing activities of heat ex-
changers with the aim of minimizing costs due to energy consumption.
The formulated model was in fact tested on real data collected considering
the products made at multinational corporate operating in the manufac-
turing industry. Following the formulation and testing of the customized
optimization model, the results obtained showed that the cost due to the
energy required for production is about 10% lower than the current pro-
duction.
# Keynote

TH 14:30 PM0 Auditorium A

Dick Den Hertog d.denhertog@uva.nl

Faculty of Economics and Business, University of Amsterdam

## *Analytics for a Better World*

In this talk I will describe two Analytics applications that contribute to one or more of the 17 Sustainable Development Goals (SDGs) of the United Nations. The first application is an optimization model to optimize the food supply chain for the World Food Programme. This application received the INFORMS Franz Edelman award in 2021. The second application is an optimization model to optimize health care facility locations in Timor-Leste and stroke center locations in Vietnam. This project is carried out in collaboration with the World Bank. If time permits I will shortly describe current and future activities of the recently initiated Analytics for a Better World Institute (analyticsbw.org).

## Keynote
# Stochastics, Equilibria, Applications; Contributed Session

TH 15:40 PM1 001

Emel Savku esavku@gmail.com

University of Oslo, Department of Mathematics

A constrained nonzero-sum game application: Bancassurance

We develop an approach for two player constraint zero-sum and nonzero-sum stochastic differential games, which are modeled by Markov regime-switching jump-diffusion processes. We provide the relations between a usual stochastic optimal control setting and a Lagrangian method. In this context, we prove corresponding theorems for two different type of constraints, which lead us to find real valued and stochastic Lagrange multipliers, respectively. Then, we illustrate our results for an example of cooperation between a bank and an insurance company, which is a popular, well-known business agreement type, called Bancassurance. We found out a Nash equilibrium for this game and solved the adjoint equations explicitly for each state. It is well known that the timing and the amount of dividend payments are strategic decisions for companies. The announcement of a dividend payment may reduce or increase the stock prices of a company. From the side of the bank, it is clear that creating a cash flow with high returns would be the main goal. Hence, in our formulation, we provide an insight to both of the bank and the insurance company about their best moves in a bancassurance commitment under specified technical conditions.

[1] E. Savku, A stochastic control approach for constrained stochastic differential games with jump and regimes. Submitted 2022.
TH 16:00 PM1 001

Milan Hladík hladik@kam.mff.cuni.cz

Charles University, Faculty of Mathematics and Physics, Department of Applied Mathematics

*Complexity Issues in Interval Linear Programming*

Interval linear programming studies linear programming problems with interval coefficients. Herein, the intervals represent a range of possible values the coefficients may attain, independently of each other. They usually originate from a certain uncertainty of obtaining the data, but they can also be used in a type of a sensitivity analysis. The goal of interval linear programming is to provide tools for analysing the effects of data variations on the optimal value, optimal solutions and other characteristics. This paper is a contribution to computational complexity theory. Some problems in interval linear programming are known to be polynomially solvable, but some were proved to be NP-hard. We help to improve this classification by stating several novel complexity results. In particular, we show NP-hardness of the following problems: checking whether a particular value is attained as an optimal value; testing connectedness and convexity of the optimal solution set; and checking whether a given solution is robustly optimal for each realization of the interval values.
TH 16:20 PM1 001

Nikola Obrenovi nikola.obrenovic@biosense.rs

University of Novi Sad, BioSense Institute

Selin, Ataç, École Polytechnique Fédérale de Lausanne, Transport and Mobility Laboratory; Stefano, Bortolomiol, École Polytechnique Fédérale de Lausanne, Transport and Mobility Laboratory; Sanja, Brdar, University of Novi Sad, BioSense Institute; Oskar, Marko, University of Novi Sad, BioSense Institute; Vladimir, Crnojevi, University of Novi Sad, BioSense Institute

The Crop Plant Scheduling Problem

With the increase in world population, the efficient production of food becomes an ever more important goal. One of the particular tasks associated with this goal is to find an optimal crop planting time, considering the allowed planting time windows and the following objectives: 1) weekly harvest must not surplus the available storage capacity and produce waste, and 2) the labor force should be utilized in the efficient manner. To tackle this problem, we define the crop plant scheduling problem (CPSP), in the form of mixed integer linear problem, and solve it with a commercial mathematical programming solver. To estimate the harvest time, we also predict the time needed for accumulation of the sufficient amount of growing degree units (GDUs), using an ARIMA model. In this paper, we present the developed GDU forecasting and CPSP models, and the obtained results for the two selected problem instances.
TH 16:40 PM1 001

Rosario Scatamacchia rosario.scatamacchia@polito.it

Dipartimento di Ingegneria Gestionale e della Produzione, Politec-
nico di Torino, Torino, Italy

Dragotto, Gabriele, Canada Excellence Research Chair in Data Sci-
ence for Real-time Decision-making, École Polytechnique de Mon-
tréal, Montréal, Canada

ZERO Regrets Algorithm: Optimizing over Pure Nash Equilibria via
Integer Programming

In Algorithmic Game Theory (AGT), designing efficient algorithms to compute Nash equilibria poses considerable challenges. We make progress in the field and shed new light on the intersection between Algorithmic Game Theory and Integer Programming. We introduce ZERO Regrets, a general cutting plane algorithm to compute, enumerate, and select Pure Nash Equilibria (PNEs) in Integer Programming Games, a class of simul-taneous and non-cooperative games. We present a theoretical foundation for our algorithmic reasoning and provide a polyhedral characterization of the convex hull of the Pure Nash Equilibria. We introduce the concept of equilibrium inequality and devise an equilibrium separation oracle to separate non-equilibrium strategies from PNEs. We test ZERO Regrets on problems in the literature such as, among others, the Knapsack Game, an Integer Programming Game where each player solves a knapsack prob-lem, and paradigmatic classes of games in AGT such as the Network Formation Game, where players build a network over a graph via a cost-sharing mechanism. Our algorithm successfully solves relevant instances of the considered games and shows promising applications for equilibria selection.
Discrete Optimization; Contributed Session

TH 15:40 PM1 002

Yasmine Alaouchiche yasmine.alaouchiche@utt.fr

University of Technology of Troyes

Ouazene, Yassine, University of Technology of Troyes; Yalaoui, Farouk,

University of Technology of Troyes.

*Throughput evaluation of large series-parallel production lines: a fast and efficient approach*

Introduction Efficient performance of manufacturing systems is of cru-
cial importance. Throughput evaluation of serial production lines has
been largely treated in the literature. In contrast, parallel manufacturing
systems are important but complex structures and the literature dedi-
cated to there study is more scarce. Existing studies either use aggre-
gation techniques to transform each parallel station into an equivalent
one and then implement serial line evaluation tools, or directly evaluate
the series-parallel system through decomposition methods. Nevertheless,
Most available methods either study limited and sometimes unrealistic
systems (small, unbuffered, or reliable), or require important computa-
tional time. Therefore, we propose a fast and accurate throughput eval-
uation method for large series-parallel production lines with unreliable
non-identical machines.

Problem description and solution method The manufacturing system studied is a series-parallel production line with S parallel machine workstations separated by and S 1 intermediate buffers of finite capacities. Each workstation Si may have Ki unreliable and non-identical parallel machines following the exponential reliability model. To study the series-parallel system, each parallel workstation is aggregated into an equivalent station using aggregation techniques of parallel machines from the literature ([1], [5], and [3]). After aggregating each parallel workstation into an equivalent station, the throughput of the flow system is evaluated based on the Equivalent Machine Method [4] where buffer states are analyzed using a birth death Markov process. State space cardinality is drastically reduced through the consideration of only full and empty buffer states rather than all buffer states. Then, each station Si is replaced by an equivalent one taking into account the probabilities of blockage and starvation. The throughput of the system is defined as the bottleneck between the effective production rates of all the stations.

Numerical experiments and results The proposed method is formulated
as a non linear program which is implemented on a mathematical solver for
conducting numerical experiments. A benchmark introduced in [2] is used
to compare the performance of the approach with the evaluation method
proposed in [2] against an implemented simulation model on FlexSim.
Numerical results of throughput estimation for both balanced and asyn-
chronous configurations with up to 50 parallel workstations, demonstrate
the great accuracy and efficiency of the proposed method compared to the
evaluation method in [2]. Indeed, the proposed algorithm performs very
well with total average errors of 4.91% and 2.64%, whereas [2] evaluation
method registers total average errors of 7.87% and 5.41%, for the balanced
configurations and the asynchronous configurations respectively. In addi-
tion, the computational time for all cases is reduced drastically. Indeed,
it ranges between 3.51s up to 15.30s, whereas in [2] evaluation method
computational time ranges between 8.2s up to 1.67h.

Conclusion The proposed approach offers the possibility to evaluate
with good accuracy the performance of large complex series-parallel pro-
duction lines in few seconds. We believe that this evaluation tool could
be the key to solving efficiently design problems in real manufacturing
systems. Future research includes using the proposed method as an eval-
uation tool to solve design problems such as the buffer and/or server
allocation problem in complex production systems.

[1] B. Ancelin and A. Semery. Calcul de la productivité dune ligne intégrée de fabrication : Calif, un logiciel industriel basé sur une nouvelle heuristique. Automatique-productique informatique industrielle, 21(3):209238, 1987. [2] A. Diamantidis, J.-H. Lee, C. T. Papadopoulos, J. Li, and C. Heavey. Performance evaluation of flow lines with non-identical and unreliable parallel machines and finite buffers. International Journal of Production Research, 58(13):38813904, 2020. [3] J. Li. Modeling and analysis of manufacturing systems with parallel lines. IEEE transactions on automatic control, 49(10):18241832, 2004. [4] Y. Ouazene, H. Chehade, A. Yalaoui, and F. Yalaoui. Equivalent machine method for ap- proximate evaluation of buffered unreliable production lines. In 2013 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS), pages 3339. IEEE, 2013. [5] A. Patchong and D. Willaeys. Modeling and analysis of an unreliable flow line composed of parallel-machine stages. Iie Transactions, 33(7):559568, 2001.
TH 16:00 PM1 002

Carmine Sorgente csorgente@unisa.it

University of Salerno

Ambrosio, Giuseppe, University of Salerno; Cerulli, Raffaele, Uni-
versity of Salerno; Serra, Domenico, University of Salerno; Vaccaro,
Ugo, University of Salerno

Cluster Deletion Problem

Clustering deals with partitioning a given set of items into homoge-
neous subsets on the basis of their relations. If such items are regarded as
the nodes of a graph, the output of the clustering task is a disjoint union
of cliques and is also referred to as cluster graph. This talk addresses
the Cluster Deletion problem, which aims to identify the minimum set of
edges whose removal from the original graph produces a cluster graph.
It is known that minimizing the total number of edges between the clus-
ters is equivalent to maximizing the total number of edges within the
clusters. The problem belongs to a family of cluster graph modification
problems, it finds application in DNA clone classification and is known to
be NP-hard on generic graphs. We address the Cluster Deletion problem
by designing an Integer Linear Programming formulation and a heuristic
approach based on edge contraction operations which iteratively merge
promising nodes in order to obtain good quality clique partitions. We fi-
nally compare the performances of the proposed approaches on both real
and randomly generated instances.
TH 16:20 PM1 002

Mauro Gaggero mauro.gaggero@cnr.it

National Research Council of Italy, Geno

Elena, Ausonio, University of Genoa, Genoa; Patrizia, Bagnerini, University of Genoa, Genoa

*A MILP Formulation and a Metaheuristic Approach for the Scheduling of Drone Landings and Payload Changes on an Automatic Platform*

We present a mixed-integer linear programming formulation and a metaheuristic approach based on direct search to schedule landings and payload changes of a set of unmanned aerial vehicles that cooperate to achieve given mission objectives. In more detail, such vehicles require landing on an automatic platform able to rapidly substitute batteries and switch the payload they are currently carrying with another one, if required by the mission at hand. Preliminary numerical results are presented to show the effectiveness of the metaheuristic algorithm as a compromise between accuracy of suboptimal solutions and computational effort.
TH 16:40 PM1 002

Alessio Sortino alessio.sortino@unifi.it

DINFO, University of Florence

Cappanera, Paola, DINFO University of Florence; Di Gangi, Leonardo,

DINFO University of Florence; Lapucci, Matteo, DINFO University of Florence; Pellegrini, Giulia, DINFO University of Florence;

Schoen, Fabio, DINFO University of Florence

*Scheduling Airport Personnel by Exact Optimization Models*

Defining shifts and assigning jobs to personnel in large companies is a common problem, yet not trivial to handle. Effective and efficient approaches have been proposed through the years by operations research experts. In this work, the rostering problem is considered as an activity-based scheduling in the specific case of the ground staff in a large Italian airport. This case study, compared to the classical scheduling problem, shows significant additional complexities, such as highly specialized personnel and great granularity of jobs to be carried out. Within this work, exact mathematical optimization models are proposed to tackle this problem. In particular, an integer linear programming model is defined, starting from a set of possible shifts calibrated on the basis of demand. In addition, computationally effective valid inequalities defined on groups of overlapped jobs and clique-based are introduced in order to reduce the computational burden of the ILP solver. Experimental results show how the proposed model is effective and able to produce the desired planning, with good optimality guarantees and the employment of reasonable computational resources.
# OML, Optimization for machine learning; Invited Session

TH 15:40 PM1 003

Enis Chenchene enis.chenchene@uni-graz.at

Institute of Mathematics and Scientific Computing, University of Graz
Bredies, Kristian, University of Graz; Naldi, Emanuele, TU Braunschweig

*Distributed extension of the Douglas-Rachford method with applications.*

In this talk, we describe how the graph-based extension of the Douglas-Rachford method introduced at our companion's talk provides new fully distributed decentralized schemes for solving non-smooth convex optimization and monotone inclusion problems composed of many terms.

The proposed method is based on a two layers architecture, consisting of what we call base and state graphs. We discuss the role of the two layers in detail, showing that while the state graph fixes the communication structure of the method, the choice of the base graph leads to essentially different schemes with different convergence properties. In particular, we observe both from explicit convergence rates and numerical experiments that choosing a base graph with higher algebraic connectivity seems to improve the convergence speed of the method. However, the main drawback of having higher connectivity is the higher amount of information that flows through the communication graph, which we formalize in the notion of communication cost. Here, the design of a distributed scheme with low communication cost intertwines with purely graph-theoretical challenges. In fact, the proposed definition of communication cost depends on the sparsity of a class of faithful orthogonal representations of the base graph in the sense of Lovász, which can be hard to bound. As a first example, we show that a distributed protocol with minimal communication cost can be designed without effort when the base graph is a tree. Then, we focus on the case of the so-called chordal or monotone transitive base graphs, where a distributed optimization protocol with low communication cost can be designed via QR decomposition of the incidence matrix.

In the experiments, we first apply the devised method to a congested optimal transport problem showing that: (i) the algebraic connectivity of the base graph does indeed affect the convergence performance of the method, (ii) before convergence, each node provides different estimates of the solution which inherit the properties of the corresponding operator. We conclude with an application to distributed Support Vector Machines showing that the proposed method is highly competitive with state-of-art methods such as P-EXTRA and a distributed Primal-Dual Hybrid
Gradient method while requiring significantly lower storage capabilities.

OML, Optimization for machine learning; Invited Session
TH 16:00 PM1 003

Jonathan Chirinos Rodriguez jonathanchirinosrodriguez@gmail.com

Università degli studi di Genova

Bredies, Kristian, University of Graz; Naldi, Emanuele, TU Braunschweig

*Learning Resolvent Operators*

In the past years, Machine Learning techniques have became a break-
through in various fields of Applied Mathematics, such as Convex/Non-
convex optimization, Inverse problems, PDEs or Optimal transport. In
particular, when solving variational inverse problems, there has been a
huge attempt to use Neural Networks in a wide variety of situations:
by learning the parameters of a regularizer, by learning the regularizer
itself, or even the data-discrepancy term. In paralell, and motivated
by the Forward-Backward-Splitting algorithm, Plug-and-play algorithms
have been introduced. Many authors have understood that, actually, the
step involving the proximal operator of the regularizer acts as a data-
denoising step and, therefore, such proximal operator may be replaced by
a learned denoiser. To do so, different techniques and approaches have
been observed and applied. In this talk, we focus on exploiting the prop-
erties that the proximal operator of any convex function may have. Such
properties may be derived by simply studying properties of the space of
nonexpansive operators. Given this observation, we consider Supervised
Learning techniques to construct nonexpansive operators with theoreti-
cal guarantees. Moreover, we propose a constructive method to do so by
considering Triangulation Techniques. We guarantee partial convergence
results of our method to the minimizer of the empirical risk and, finally,
propose applications where our method could be applied and compete
with state of the art regularizers.
TH 16:20 PM1 003

Emanuele Naldi e.naldi@tu-braunschweig.de

TU Braunschweig

Kristian, Bredies, UniGraz and Enis Chenchene, UniGraz

*Graph extension of the Douglas-Rachford method with minimal lifting*

In this talk, we propose several generalizations of the Douglas-Rachford method to solve monotone inclusion problems involving $N$ maximal monotone operators. In particular, our objective is to show that, starting from an ordered undirected connected graph, it is possible to construct a generalization of the Douglas-Rachford algorithm with a communication structure that respects the connections of such a graph. The resulting schemes we present are unconditionally stable frugal resolvent splitting methods with minimal lifting in the sense of Ryu. Indeed, every scheme is required to store only $N-1$ variables at a time. We describe our methods in the (degenerate) Preconditioned Proximal Point framework and, in this way, we are able to prove convergence of every derived algorithm in a unifying way. Specifically, we show that the proposed methods are instances of the proximal point algorithm. We start our talk by introducing the general convergence analysis of degenerate Preconditioned Proximal Point algorithms. We then derive the convergence analysis for the graph generalization of Douglas-Rachford as an application. To do so, starting from the ordered undirected connected graph, we construct a maximal monotone operator in a large product space (of dimension $2N-1$) and a degenerate preconditioner in such a way that the correspondent reduced Preconditioned Proximal Point algorithm will involve only $N-1$ variables and will have the communication structure dictated by the graph. The graph generalization of Douglas-Rachford we introduce has its own interest since it gives rise to several generalizations of the well-known Douglas-Rachford method. In fact, we show that we can achieve at least one distinct generalization for every ordered undirected connected graph. In addition, our companion talk focus on the applications that such extensions can have in distributed optimization.

OML, Optimization for machine learning; Invited Session
# Optimization on Graphs; Contributed Session

TH 15:40 PM1 Auditorium A

Roberto Zanotti roberto.zanotti@unibs.it

University of Brescia - Department of Information Engineering Bonomi, Valentina, University of Brescia - Department of Information Engineering; Mansini, Renata, University of Brescia - Department of Information Engineering

*A matheuristic approach for a Vehicle Routing Problem with Parcel Lockers and Green Customers*

Due to the COVID 19 pandemic, the volume of online purchases has increased dramatically in the last couple of years. As a consequence, the impact of last-mile logistics on city centers and main roads has further increased, both in terms of traffic jams and increased pollution. Several solutions are being evaluated, such as the use of alternative delivery means, like electric vehicles and drones, or the introduction of incentives for less impactful delivery practices, including very flexible delivery times or wide time windows [1] Among the solutions identified to reduce this negative impact of last-mile deliveries, parcel lockers are receiving considerable attention. Instead of delivering parcels directly to customers' homes, a last-mile delivery company can leave them in secure parcel lockers where customers can pick them up later. The company needs to decide the number and location of the locker stations to minimize its delivery costs. This delivery solution can be extremely beneficial for the company, given the expected reduction in traveled distances, and this has been the most analyzed side of the problem in the literature. However, an often-neglected impact of the introduction of lockers is the environmental one, since the distances traveled by customers to pick up parcels are usually not considered. In this work, we focus on a location and routing problem that jointly considers as objective function the minimization of the overall emissions due to both the delivery company and the customers that need to collect their parcels. A key aspect of the problem is the introduction of different customer profiles, that define the distance that a customer is willing to travel with or without using zero-emission transportation means. We adapt a mathematical formulation from the literature and propose several ways to improve it. Then, we introduce a hybrid matheuristic algorithm based on the Kernel Search framework [2] and local search heuristics to solve it. The solution algorithm is tested on a comprehensive set of instances that considers different customer profiles and behaviors. The computational results are promising and show the effectiveness of the devised framework. Additionally, interesting insights can be derived from the experimental analysis, especially regarding the fact that the role of customers is one of the main drivers for controlling the environmental impact.

Optimization on Graphs; Contributed Session
[1] Daniele Manerba, Renata Mansini, Roberto Zanotti, 2018. Attended Home Delivery: reducing last-mile environmental impact by changing customer habits, IFAC-PapersOnLine, Volume 51, Issue 5, Pages 55-60.
[2] Enrico Angelelli, Renata Mansini, M. Grazia Speranza, Kernel search: A general heuristic for the multi-dimensional knapsack problem, Computers & Operations Research, Volume 37, Issue 11, 2010, Pages 2017-2026.
TH 16:00 PM1 Audtorium A

Orlando Marco Belcore mdigangi@unime.it

Department of Engineering, University of Messina
Di Gang Massimo Antonio; Polimeni, Department of Engineering,
University of Messina

*C-Weibit discrete choice model: a path based approach*

In traffic assignment a key role is played by the path choice that sim-
ulate the path chosen by users in relation to the perceived costs. Var-
ious models are proposed in literature in order to accomplish this task
(e.g., those obtained from generalized extreme value model). One of the
main problems encountered is the overlap among paths between the same
origin-destination pair. In order to overcome this problem, the research
was directed towards models like C-logit, Path-Size Logit or Probit that
are able to take into account this aspects. In this paper the use of a
C-Weibit model is proposed, by introducing a commonality factor that
modify the utility function when the paths overlap. From the benefits
of this model, is to highlight that the probability can be calculated in a
closed form. The C-Weibit was used within a stochastic user equilibrium
assignment procedure. The results and some comparisons are reported,
in these tests C-Weibit had better performances than other models.
TH 16:20 PM1 Auditorium A

David Di Lorenzo david.dilorenzo@verizonconnect.com

Verizon Connect Research, Florence, Italy
Tommaso, Bianconcini, Verizon Connect Research, Florence, Italy;
Leonardo, Taccari, Verizon Connect Research, Florence, Italy; Marco,
Gualtieri, Verizon Connect Research, Florence, Italy; Paolo, Raiconi,
Verizon Connect Research, Florence, Italy; Alessandro, Lori, Veri-
zon Connect Research, Florence, Italy

*Ten years of Routist: vehicle routing lessons learned from practice*

The Vehicle Routing Problem (VRP) has been intensively studied for more than five decades, and many variants have been introduced over the years, spanning from simple specializations such as the Capacitated Vehicle Routing Problem (CVRP) or Vehicle Routing Problem with Time Windows (VRPTW) to more exotic ones. VRP dramatic implications on perational costs explain the significant effort that has been put in researching effective and efficient solution methods, both from academia and businesses worldwide. Most companies have adopted third party software solutions, others, e.g. delivery fleets, keep developing internal tools to keep operational costs as low as possible and increase margins. In erizon Connect we have been working for ten years on Routist, a VRP Software-as-a-Service product, and we have learnt many lessons from our customers along the way. Most of all, we discovered that useful optimization algorithms need to fit customer needs and problems. Thus, they require optimization techniques that are not often addressed in the scientific literature. In this work we retrace the path that led us to where we are today, highlighting some of those challenges after all, it is the journey that matters.
TH 16:40 PM1 Audtorium A

Carla De Francesco carla@math.unipd.it

Università di Padova, Dipartimento di Matematica "Tullio Levi-Civita"

Luigi, De Giovanni, Università di Padova, Dipartimento di Matematica "Tullio Levi-Civita"

*Integer Linear Programming Formulations for the Fleet Quickest Routing Problem on Grids*

In an automated transportation system, a fleet of vehicles moves on a grid, each from its starting point on one side, to its destination on the opposite side. For the sake of efficiency, the only allowed routes are nonstop shortest paths. Among these, one route for each vehicle has to be properly chosen, avoiding that two vehicles cross the same node or move on the same edge at the same time. Therefore, an assignment of origin-to-destination nonstop collision-free shortest path routes is required. The Fleet Quickest Routing Problem on Grids aims at finding the minimum number of grid lanes allowing for such an assignment. We present two Integer Linear Programming models that exploit some combinatorial properties of conflicting shortest paths: the first one has binary variables and refines a multicommodity flow formulation; the second one exploits a compact representation of shortest paths with a reduced number of integer variables. We compare the two formulations through test on random and on purpose generated instances, showing the better performance of the compact formulation, and we discuss their potential towards more efficient methods.
Sustainability; Contributed session

TH 15:40 PM1 Auditorium B

Ornella Pisacane o.pisacane@univpm.it

Dipartimento di Ingegneria dell'Informazione, Università Politecnica
delle Marche

Bruglieri, Maurizio, Dipartimento di Design, Politecnico di Milano;
Çatay, Bülent, Faculty of Engineering and Natural Sciences, Sa-
banci University; Keskin, Merve, Sheffield University Management
School; Mancini, Simona, Alpen-Adria-Universität Klagenfurt e Di-
partimento per lo Sviluppo Sostenibile e la Transizione Energetica,
Università del Piemonte Orientale

*The Effect of Low Emission Zones on the Routing of Electric and*
*Fossil-Fuel Vehicles*

Due to the recent concerns about the environment and climate change, some countries around the world are implementing policies and rules for promoting the use of Alternative Fuel Vehicles (AFVs), especially in road transport which is responsible for a significant percentage of the total GreenHouse Gas emissions of the transportation sector. Among AFVs, Electric Vehicles (EVs) can significantly contribute to reducing both noise and environmental pollution. Some countries have established restric- tions on the utilization of fossil-fuel powered Traditional Vehicles (TVs) in urban areas such as Low Emission Zones (LEZs) where TVs are either banned from entering or required to pay a toll to enter for the first time. Instead, EVs can travel without any restriction. The aim of our work is supporting the transportation companies toward an ecological transi- tion, providing them with optimization-based approaches suitable to assist them in the process of replacing/integrating their traditional fleet. In fact, we address the problem of efficiently routing a mixed fleet comprising both TVs and EVs based at a common depot, for serving a set of customers at minimum total operating cost. We refer to it as the Mixed Fleet Vehicle Routing Problem with LEZ (MFVRP-LEZ). The operating costs include the cost of electricity recharged to EVs both at the depot and en-route, the fuel cost of TVs, and the tolls paid by TVs for entering the LEZ. Each vehicle starts its tour from the depot, serves a subset of customers, and returns to the depot before the end of its shift. Moreover, we assume that each customer must be served within a specified time window and an EV can recharge (also partially) en-route. We mathematically formulate MFVRP-LEZ as an arc-based Mixed Integer Linear Program (MILP) by allowing multiple visits to a station without cloning it and by identifying a-priori the set of non-dominated stations between each pair of customers. We solve small-sized instances using CPLEX. For solving large-sized in- stances, we design an Adaptive Large Neighborhood Search (ALNS) that extends the set of moves, already proposed in the related literature, with

Sustainability; Contributed session
problem-specific new mechanisms. The experimental campaign is carried
out on a set of benchmark instances of varying sizes derived from those al-
ready presented in the related literature by adding LEZs and arcs avoiding
LEZs. Numerical results validate the effectiveness of ALNS and provide
managerial insights.
TH 16:00 PM1 Auditorium B

Matteo Pozzi matteo.pozzi@optit.net

OPTIT

Bischi, Aldo, University of Pisa; Gordini, Angelo, OPTIT

*Integrated planning of multi-energy systems (PlaMES): a comprehensive modelling framework and decision support tool*

The European Unions commitment towards a carbon-neutral economy can only be accomplished by a synergistic implementation of measures where Renewable Energy Sources expansion, integration of different energy systems and Transmission/Distribution infrastructure development are calibrated to meet future (2050) energy needs. The high complexity of the task comes from problem dimension, where future national demand and supply must be managed taking into account the interconnection between electricity, gas, heat and mobility sectors, with an hourly granularity to take into account multi-energy coupling dynamics. The Horizon 2020 project PlaMES, currently in its last year, aims to determine the optimal target system, including the investment trade-off between different technologies, infrastructure configurations and emissions reductions that minimize overall system costs. Introducing the overall business challenge, further explored in its detailed modelling and resolution strategies by the academic partners of the project during the session. Particular focus will be devoted to the decision support tool, that must handle extremely large quantities of data to provide significant scenario management capability to perspective decision makers, be them Transmission System Operators designing optimal infrastructure plans or Country Planners identifying what technology mix guarantees effective future energy systems that meet the challenges of decarbonisation.

Sustainability; Contributed session
TH 16:20 PM1 Audtorium B

Antonio Punzo antonio.punzo5@unibo.it

DEI, University of Bologna

Monaci, Michele, University of Bologna; Vigo, Daniele, University of Bologna

Transmission expansion planning for future European energy grid

PlaMES is an Horizon 2020 project aimed at developing an integrated planning tool for multi-energy systems on a European scale, taking into account both the expansion of generation and storage technologies and the related infrastructure in an integrated manner, so as to deliver to the European Unions COP21 commitments. The PlaMES architecture consists of six tools. In this talk we will introduce the module designed for solving the Transmission Expansion Planning (TEP), which aims at identifying cost-efficient expansion and congestion management measures to ensure the system security and reliability of future electrical transmission grids. Our modelling approach considers different expansion and reinforcement measures and yields to an integer linear programming formulation, which is solved by using an exact enumerative algorithm in which a Benders decomposition scheme is used to compute a dual bound. The method is enhanced by means of a metaheuristic algorithm, and is computationally tested on realistic instances of large size.
TH 16:40 PM1 Audtorium B

Silvia Anna Cordieri *silviaanna.cordieri2@unibo.it*

DEI, University of Bologna

Monaci, Michele, University of Bologna; Paronuzzi, Paolo, University of Bologna; Vigo, Daniele, University of Bologna

*A decomposition approach for the Central Energy System planning*

The Central Energy System (CES) planning is a problem including both unit commitment problem and generation expansion planning, and it is formulated as a linear program. The system consists of a set of nodes, each one with a set of available energy production technologies, a set of time steps, and a transmission network topology. For each node and time step a demand is given, and the objective is to minimize the sum of operational and installation costs, while satisfying the demand and respecting the maximum limit on CO2 emissions. Given the scale at which the problem is treated, a heuristic algorithm exploiting the block-structure presented by the mathematical formulation of the problem has been designed. In particular, the procedure works in two distinct phases. In the first phase, the considered time-horizon is divided in a number of subperiods, each one defining a subproblem presenting the same characteristic of the original problem. Then, these subproblems are solved (possibly in parallel) and their solution are used to define the values of all the design variables (i.e., the amount of capacity for each technology installed at each node and the possible expansion of the network). After the design variables has been fixed, in the second phase of the algorithm, the same subproblems are solved again (possibly in parallel), this way operational variables are also defined and a feasible solution is found.
Assemblea AIRO - AIRO Council meeting

TH 17:30 PM2 Auditorium A

Assemblea AIRO

*AIRO council meeting*

** NO ABSTRACT PROVIDED **

Assemblea AIRO - AIRO Council meeting
# Applications of OR; Contributed Session

FR 10:00 AM1 001

Lionel Amodeo matthieu.godichaud@utt.fr

ICD-LOSI, University of Technology of Troyes (UTT)
Meisam, Pour-Massahian-Tafti, ICD-LOSI, University of Technology of Troyes (UTT); Godichaud, Matthieu, ICD-LOSI, University of Technology of Troyes (UTT)

*Capacitated Disassembly Lot-Sizing Problem with Disposal Decisions for Multiple Product Types with Parts Commonality*

This paper addresses capacitated disassembly lot sizing problem for multiproduct structure with parts commonality. Disposal decisions are considered to manage the accumulation of unnecessary items obtained after disassembly operations during the planning horizon. A new mixed-integer programming (MIP) model is given to formulate the problem. Exact method by using CPLEX solver can be applied to obtain optimal solutions for the small-sized problem. A fix-and-optimize heuristic is proposed for larger sizes of the problem, it solves successively a series of sub-problems. In each sub-problem, a subset of variables are fixed while the remaining are optimized using an exact method. Computational tests are performed on a number of randomly generated instances and the results demonstrate the performance of the proposed model and methods.
FR 10:20 AM1 001

Roberto Roberti roberto.roberti@unipd.it

Department of Information Engineering - University of Padova
Paradiso, Rosario, Department of Operations Analytics - Vrije Universiteit Amsterdam; Ulmer, Marlin, Chair of Management Science - Otto-von-Guericke-Universitat Magdeburg

*Anticipatory Time Window Assignment for Next-Day Service Routing*

In many home delivery services, customers must be present when the Logistics Service Provider (LSP) arrives and operates. This type of service is known as Attended Home Delivery (AHD) services. Examples of AHD are the delivery of large, valuable, or perishable items, technician services for installment, repair, maintenance, or meter reading, and several healthcare applications. In most AHD applications, customers are not entitled to select the time at which the service takes place, but a service time window is assigned to the customer by the LSP. From an operational viewpoint, whenever a new customer requests service, the LSP must decide whether the request should be accepted or rejected and, if accepted, on which day and within which time window to serve the customer. If a time window is offered, then all accepted requests must be served within the corresponding offered time windows. Yet, to guarantee efficient operations, the LSP should assign the time windows to the customers to serve as many customers as possible while maintaining flexibility for future unknown requests.

The dynamic assignment of time windows to customers poses several optimization challenges, such as how many drivers should be scheduled per day? On which day (if any) should a new customer be served? Which time window should be offered to a customer on that day? In this talk, we address this last question. In particular, throughout a capture phase (today), customers request service within a fullllment phase (tomorrow). Each customer is either assigned a time window from a predened set (9-10 a.m., 10-11 a.m., 11-12 a.m., ...) or the customer is postponed to another day (outside of the scope of this work). A time window can only be assigned if a vehicle routing plan that serves the new customer and the previous customers within their respective time windows can be found. The goal is to maximize the number of customers that can be served in the fullllment phase.

The problem we address can be formulated as a stochastic dynamic decision problem. However, finding an optimal policy is a challenging task for two main reasons. First, in every state, checking the feasibility of offering a time window to the new customer calls for solving a Vehicle Routing Problem with Time Windows (VRPTW), which is NP-hard. Second, evaluating the impact of offering a (feasible) time window at a given state requires the anticipation of future customers and future time-window

Applications of OR; Contributed Session
decisions, on which only limited stochastic information is known. We pro-
pose a solution method that addresses these two issues by (a) checking
the feasibility of a time window with an exact solution method and (b)
assessing the quality of a decision (i.e., offering a given time window) at a
given state through Bellman equations of immediate reward (1 or 0) and
an approximation of the expected future reward (value). In particular,
the future reward is approximated by generating a set of scenarios, each
corresponding to a team-orienteering problem (TOP) with multiple time
windows and mandatory customers. We approximate the reward of each
TOP by deriving fast upper bounds provided by the linear relaxation of
a set packing formulation solved via column generation.

We test our algorithm on artificial data and real-life data from Iowa
city. The results show that our method increases the number of customers
served significantly compared to a rolling horizon approach without antic-
ipation. Our algorithm can also provide solutions that, on average, serve
90% of the customers when compared to an ex-post upper on the static
counterpart of the problem.
FR 09:00 AM1 001

Mirko Mucciarini mirko.mucciarini@unimore.it

Marco Biagi Foundation, University of Modena and Reggio Emilia,
Largo Marco Biagi 10, 41121 Modena, Italy

Caselli, Giulia, University of Modena and Reggio Emilia; Iori, Manuel,
University of Modena and Reggio Emilia; Lippi, Marco, University
of Modena and Reggio Emilia

*Demand Forecasting Methods: A Case Study in the Italian Processed Meat Industry*

Demand forecasting is acquiring more and more importance in the fast-changing business world, where market instability and economic shocks such as Covid-19 pandemic require firms to be both efficient and flexible. This work is based on a research project aiming at the development of a demand forecasting model for a company that operates in the Italian processed meat segment. The purpose is to obtain a forecast as accurate as possible and then use it at a later stage to carry out an optimal production scheduling (see, e.g., [1], [2]). Especially in the food sector, a proper integration of forecast and production management is essential, because the perishable nature of the items does not allow for over production. In this work, we compared different Machine Learning forecasting algorithms, including Linear Regressor, Random Forest Regressor, Support Vector Regressor and Multi-layer Perceptron Regressor. We compared these methods with the ones used in the literature to define a baseline, like random walk and seasonal mean. Extensive computational tests on a two-year real-world data series prove the effectiveness of the algorithms, especially the Support Vector Regressor, in providing an accurate forecast. The resulting model is now used by the company on a daily basis.

Acknowledgements: We thank Inalca S.p.A. for financial support.

[1] W. Wong, Z. Guo, A hybrid intelligent model for medium-term sales forecasting in fashion retail supply chains using extreme learning machine and harmony search algorithm, International Journal of Production Economis 128(2) (2010) 614624. [2] G. Tsoumakas, A survey of machine learning techniques for food sales prediction, Artificial Intelligence Review, 52(1), (2019) 441-447.

Applications of OR; Contributed Session
FR 09:20 AM1 001

Roberto Ronco roberto.ronco@edu.unige.it

Department of Informatics, Bioengineering, Robotics and System
Engineering (DIBRIS), University of Genoa

Catanzaro, Daniele, Center for Operations Research and Econometric (CORE) Université Catholique de Louvain; Pesenti, Raffaele, Department of Management University Ca Foscari

*A new efficient heuristic for the Automatic Scene Detection Problem*

Nowadays, the automatic extraction of semantic and metadata in-
formation from video content has become essential in tackling the huge
amount of audio and visual data that are produced every day. The several
applications of this task range from video management and advertising
insertions to automatic audio description and fast video browsing. As a
result, its automation constitutes a compelling matter for video industry
and consumers as well. The Automatic Scene Detection Problem (ASDP),
first introduced in the literature of video processing in [1], is a combinato-
rial optimization problem that consists in segmenting a set of shots, each
constituted by a sequence of frames ideally taken from the same viewpoint,
into semantically consistent scenes, by optimizing a measure of similar-
ity between shots. We specifically consider the ASDP variant introduced
in [2], that is nontrivial for a generic number of scenes, and deciding its
complexity is still an open question. We present an approximate solution
algorithm [3] able to outperform the previous state-of-the-art one [2] both
in terms of speed and quality of the solution. We also provide a complete
characterization of the computational complexity of the two algorithms,
by laying out fundamental concepts on the combinatorics of the ASDP.

[1] Daniel Rotman, Dror Porat, and Gal Ashour. Robust and efficient video scene detection using optimal sequential grouping. In Proceedings of the 2016 IEEE International Symposium on Multimedia (ISM), pages 275280, 2016. [2] Daniel Rotman, Dror Porat, Gal Ashour, and Udi Barzelay. Optimally grouped deep features using normalized cost for video scene detection. In Proceedings of the 2018 ACM on International Conference on Multimedia Retrieval, pages 187195, 2018. [3] Daniele Catanzaro, Raffaele Pesenti, and Roberto Ronco. A new fast and accurate heuristic for the automatic scene detection problem. Computers and Operations Research, 136:105495, 2021.
FR 09:40 AM1 001

Maria Trnovska trnovska@fmph.uniba.sk

Faculty of Mathematics, Physics and Informatics, Comenius Uni-
versity in Bratislava

Halicka, Margareta, Faculty of Mathematics, Physics and Informat-
ics, Comenius University in Bratislava

A unified approach to data envelopment analysis models

Data envelopment analysis (DEA) defines a variety of models to assess
the performance of decision-making units. The models take form of math-
ematical programming problems that link together an efficiency measure
and a given technology set in the input-output space. DEA defines two
basic classes of models. The models in the first class assume proportional
change of inputs and outputs and search for the benchmark by following a
parametric path. The models in the second class allow individual change
of each input and output component and integrate the input excesses and
output shortfalls into an overall efficiency measure. We analyze properties
of models in each of the two classes by means of a unified framework and
offer a generalized dual (multiplier) form of models in each class.

Applications of OR; Contributed Session
Applications: Health Care; Contributed Session

FR 10:00 AM1 002

Valentina Bonomi v.bonomi001@unibs.it

University of Brescia

Mansini, Renata, University of Brescia; Manerba, Daniele, University of Brescia

A Two-Stage Stochastic approach for the Integrated Multi-Period
Combinatorial Auction and Nurse Routing Problem

We study a Nurse Routing Problem (NRP) where a hospital man-
ages patients assignments through a Multi-Period Combinatorial Auction
(MPCA) that allows the outsourcing of visits. In the MPCA, external
providers offers are composed of a subset of visits and the total cost re-
quired to perform them. For the patients not externally assigned, the
NRP schedules daily routes for each nurse [1]. Additional consistency
constraints limit the maximum number of nurses assigned to a patient in
performing his/her visits [2]. The goal of the hospital is to select external
bids to minimize the auction cost and the travelling costs to serve pa-
tients. In the deterministic version of the problem, both the hospital and
the providers have access, at the beginning of the time horizon, to the
exact information regarding patients and their required visits. However,
to capture the complexity of real-life application, we introduce a degree
of uncertainty in the model. Due to the multi-periodicity of the problem,
each day the number of visits and their service time may vary from what
previously agreed with the hospital [3]. Thus, we propose a two-stage
stochastic formulation where we model the number of visits and their
length as stochastic variables while the total number of patients remains
deterministic. At the first stage, the hospital needs to make decisions
about the bid based on the expected values of the random variables. The
quality of these decisions can be evaluated at the second stage with the
realization of such variables in a specific scenario. Our objective is to
study how different hospital recourse policies affect the final solutions and
the overall costs.

[1]A. Gobbi, D. Manerba, R. Mansini, R. Zanotti (2019). A Kernel Search for a patient satisfaction-oriented Nurse Routing Problem with Time Windows. In: IFAC-PapersOnLine 52 (13):1669-1674. Proceedings of MIM2019, 9th IFAC Conference on Manufacturing, Modelling, Management and Control. August 28-30, 2019. Berlin (Germany). [2]Y. Song, M. W. Ulmer, B. W. Thomas, and S. W. Wallace (2020). Building trust in home services - Stochastic team-orienteering with consistency constraints. Transportation Science, 54(3):823-838. [3]Lars M. Hvattum, Arne Løkke-tangen, Gilbert Laporte, (2006) Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic. Transportation Science 40(4):421-438.

Applications: Health Care; Contributed Session
FR 09:00 AM1 002

Roberto Bargetto roberto.bargetto@polito.it

LIMOS UMR CNRS 6158 Center for Biomedical and Health Care
Engineering EMSE

Garaix, Thierry, LIMOS UMR CNRS 6158 Center for Biomedical and Health Care Engineering EMSE; Xie, Xiaolan, LIMOS UMR CNRS 6158 Center for Biomedical and Health Care Engineering EMSE

*A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints*

Operating theater scheduling may be often severely affected by unexpected unavailability of resources. Solving the integrated planning and scheduling problem of an operating theater is an important task to ensure the efficiency of surgical operations.

We define an integrated operating room planning and scheduling problem including constraints commonly considered, for similar problems, both in practical contexts and in the literature. We focus particularly on constraints on human resources, i.e., surgeons, and nurses. The defined problem considers surgeries with different infection levels and sequence-dependent operating room cleaning times.

For this integrated planning and scheduling problem, we devise a branch-and-price-and-cut algorithm based on a problems time-indexed formulation. The proposed column generation scheme relies on a label-correcting algorithm purposely designed for solving the related strongly NP-Hard pricing problems. The pricing problems are formulated as single operating room scheduling problems with time-dependent costs and sequence-dependent cleaning times as required.

The efficiency of the label-correcting algorithm is ensured by dominance rules for labels and by two procedures for computing the upper and the lower bound of the labels. The upper-bound computation is based on the linear programming relaxation of a multidimensional 0-1 knapsack problem and the lower-bound is computed by means of a greedy heuristic procedure. For tightening the linear relaxation of the problem, we develop an effective cutting procedure inspired by Benders decomposition and based on duality theory for linear programming.

We conduct a numerical study both on instances from the literature and on newly generated instances to demonstrate the computational effectiveness of the solution method. The Benders-like cutting procedure is shown to be effective in tightening the linear programming bound of the problem and improves the linear programming relaxation of the problem even though the computation time is not negligible. The label correcting algorithm is efficient for generating columns. The column generation stops even for large-sized instances (up to 160 surgeries) with a moderately reduced number of columns added to the restricted master problem,
typically about thousands of columns. The devised branch-and-price-and-cut algorithm outperforms both competing methods from the literature and a commercial solver.

The approach of the Benders-like cutting procedure is sufficiently generic to be applied in the case of an arbitrary number of resources for the generation of resource-related cuts, surgeon and nurse cuts in our case, improving the linear programming relaxation of the procedure master problem.
FR 09:20 AM1 002

Mirko Cavechia mirko.cavecchia@unimore.it

Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia

Autelitano, Federico, University of Parma; Consolini, Luca, University of Parma; Giuliani, Felice, University of Parma; Iori, Manuel, University of Modena and Reggio Emilia; Locatelli, Marco, University of Parma

*A Facility Location Problem to support Helicopter Emergency Medical Services*

Locating helipads in strategic positions, especially in mountain areas, is a crucial decision to reduce transport time of injured people to hospitals. The problem has been largely studied in the literature. Many researches focus on identifying the optimal set of locations to cover a given population percentage by implementing a maximal covering location problem, while other studies aim to minimize the average response time over the entire population or minimize the total rescue time. This work originates from the need of the Parma Helicopter Emergency Medical Service (PHEMS) to identify which existing helipads should be equipped with modern infrastructures for night landing and, if necessary, where to build new helipads. PHEMS provided us with the historical data referring to the rescue interventions carried out in the last years in the province of Parma. We used this large data set to build two different bi-objective optimization models: the first minimizes the cost of equipped helipads and the total rescue time; whereas the second minimizes the cost of equipped helipads and the total delay with respect to given target due-dates identified on the basis of the injured urgency levels. Both models have been solved via an epsilon-constrained method and tested on the PHEMS case. The resulting solutions are characterized by relevant improvements with respect to the existing real-world solutions, both in terms of total rescue time and total delay.

Applications: Health Care; Contributed Session
FR 09:40 AM1 002

Alessandro Gobbi alessandro.gobbi@unibs.it

Dipartimento di Ingegneria Meccanica e Industriale, Università degli
Studi di Brescia

Manerba, Daniele, Dipartimento di Ingegneria dell'Informazione,
Università degli Studi di Brescia; Mansini, Renata, Dipartimento di
Ingegneria dell'Informazione, Università degli Studi di Brescia; Zan-
otti, Roberto, Dipartimento di Ingegneria dell'Informazione, Univer-
sità degli Studi di Brescia

Nurse Routing Problem with Incompatible Services and Mini-mum Demand: An ALNS+Kernel Search solution approach

In recent decades, the average age of the population has grown steadily along with the number of people suffering from chronic diseases and asking for treat-ments. Hospital care is expensive and often unsafe, especially for older individuals and particularly during a pandemic as the SARS-CoV-2 one. Hence, hospitalization at home has become a valuable alternative for several treatment requests with lower risk to fragile patients [1], while guaranteeing a high quality of service. This new care process clearly re-quires the redefinition of health services organization and the optimization of scarce resources, such as the available nurses. In this work, we study a Nurse Routing Problem [2] aiming at finding a good balance between hospital costs reduction and the well-being of patients, also considering re-alistic operational restrictions like maximum working times for the nurses and possible incompatibilities between services jointly provided to the same patient. We first propose a MILP formulation for the problem, strengthened by some cuts. Then, we propose a simple branch-and-cut algorithm to derive ground benchmarks. Finally, to efficiently solve the problem, we develop an ALNS hybridized with a Kernel Search [3]. The algorithm performance is tested over a large set of different realistic work-ing scenarios. Such numerical experiments show that our matheuristic manages to find good solutions in a reasonable amount of time (even for the most difficult instances) and allow us to derive some interesting man-agerial insights for the healthcare provider.

[1] Landers S. et al. (2016). The future of home health care: A strategic frame-work for optimizing value. Home Health Care Manage-ment and Practice 28, 4, 262278. [2] Manerba D., Mansini R. (2016). The nurse routing problem with workload constraints and incompatible services. IFAC-PapersOnLine 49, 12, 11921197. [3] Angelelli E., Mansini R., Speranza M.G. (2010). Kernel search: A general heuristic for the multi-dimensional knapsack problem. Computers & Operations Research 37, 11, 20172026.
# OML, Optimization for machine learning; Invited Session

FR 10:00 AM1 003

Mouna Gharbi mouna.gharbi@centralesupelec.fr

Universite Paris-Saclay, Inria, CentraleSupelec, CVN, France
Emilie, Chouzenoux; Jean-Christophe, Pesquet; Laurent, Duval

GPU-based Implementations of MM Algorithms. Application to Spectroscopy Signal Restoration

Restoration of analytical chemistry data from degraded physical acquisitions is an important task for chemists to obtain accurate component analysis and sound interpretation. The high-dimensional nature of these signals and the large amount of data to be processed call for fast and efficient reconstruction methods. Existing works have primarily relied on optimization algorithms to solve a penalized formulation. Although very powerful, such methods can be computationally heavy, and hyperparameter tuning can be a tedious task for non-experts. Another family of approaches explored recently consists in adopting deep learning to perform the signal recovery task in a supervised fashion. Although fast, thanks to their formulations amenable to GPU implementations, these methods usually need large annotated databases and are not explainable. In this work, we propose to combine the best of both worlds, by proposing unfolded Majorization-Minimization (MM) algorithms with the aim to reach fast and accurate methods for sparse spectroscopy signal restoration. Two state-of-the-art iterative MM algorithms are unfolded onto deep network architectures. This allows both the deployment of GPU-friendly tools for accelerated implementation, as well as the introduction of a supervised learning strategy for tuning automatically the regularization parameter. The effectiveness of our approach is demonstrated on the restoration of a large dataset of realistic mass spectrometry data.
FR 10:20 AM1 003

Vassilis Apidopoulos vassilis.apid@gmail.com

Università di Genova

*Iterative regularization in classification via hinge loss diagonal methods*

Iterative (implicit) regularization is a classic idea in regularization theory, that has recently become popular in machine learning. On the one hand, it allows to design efficient algorithms controlling at the same time numerical and statistical accuracy. On the other hand it allows to shed light on the learning curves observed while training neural networks. In this talk, we focus on iterative regularization in the context of classification. After contrasting this setting with that of inverse problems, we develop an iterative regularization approach based on using the hinge loss function. More precisely we present an inertial diagonal approach for which we show convergence as also rates of convergence. Our approach compares favorably with other alternatives, as confirmed also in numerical simulations.

OML, Optimization for machine learning; Invited Session
FR 09:00 AM1 003

Lionel Tondji l.ngoupeyou-tondji@tu-braunschweig.de

TU Braunschweig
Dirk, Lorenz

Faster Randomized Block Sparse Kaczmarz by Averaging

The standard randomized sparse Kaczmarz (RSK) method is an algo-
rithm to compute sparse solutions of linear systems of equations and uses
sequential updates, and thus, does not take advantage of parallel com-
putations. In this work, we introduce a parallel (mini batch) version of
RSK based on averaging several Kaczmarz steps. Naturally, this method
allows for parallelization and we show that it can also leverage large over-
relaxation. We prove linear expected convergence and show that, given
that parallel computations can be exploited, the method provably provides
faster convergence than the standard method. This method can also be
viewed as a variant of the linearized Bregman algorithm, a randomized
dual block coordinate descent update, a stochastic mirror descent update,
or a relaxed version of RSK and we recover the standard RSK method
when the batch size is equal to one. We also provide estimates for incon-
sistent systems and show that the iterates convergence to an error in the
order of the noise level. Finally, numerical examples illustrate the benefits
of the new algorithm.

OML, Optimization for machine learning; Invited Session
FR 09:20 AM1 003

Cheik Traoré traore@dima.unige.it

Università di Genova

Asynchronous parallel block-coordinate forward-backward algorithm

We are going to present our work on the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block- coordinates are up-dated in parallel, asynchronously and randomly according to an arbitrary probability distribution. In that work, we prove that the iterates gen-erated by the algorithm form a stochastic quasi-Fejér sequence and thus converge almost surely to a minimizer of the objective function. More-over, we prove a general sublinear rate of convergence in expectation for the function values and a linear rate of convergence in expectation under an error bound condition of Tseng type. Under the same condition strong convergence of the iterates is provided as well as their linear convergence rate.

OML, Optimization for machine learning; Invited Session