Discrete Optimization II

Contributed Session

Time Slot: Thursday Morning

Room: 002

Chair: Alice Raffaele

On the solution of optimal timing problems for single machine rescheduling problems with new jobs arrival

Time: 11:30

Elena Rener (Politecnico di Torino), Salassa Fabio, T’kindt Vincent

This study on the idle times insertion is motivated by a rescheduling 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 optimal 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 optimal 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 anal-ysis 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 dif-ferent properties and, whenever known, the complexity of the problem.

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

Time: 11:50

Tommaso Schettini (Politecnico di Milano), Gendreau Michel, Jabali Ola, Malucelli Federico

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 DDPT 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 effectiveness 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.

New Approaches for the kidney exchange problem

Time: 12:10

Domenico Serra (University of Salerno), Cerulli Raffaele, Gentili Monica,Rahamn Amanatur,Sorgente Carmine

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.

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

Time: 12:30

Alice Raffaele (Department of Computer Science, University of Verona, Strada Le Grazie 15, 37134 Verona, Italy), Romeo Rizzi

Any convex polyhedron can be described through two different equivalent 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 similarity between these two problems and the Hypergraph Dualization problem. Consider the set-covering polyhedron 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, respectively. Thus, the problem of enumerating the vertices of P is equivalent to the problem of computing the minimal transversals of H. Then, an efficient procedure to solve the Hypergraph Dualization problem would lead to an efficient procedure to also solve this special restriction of the Vertex 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 Duality 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.