Carlo Mannino

L. Lamorgese, C. Mannino, E. Natvig, An exact micro-macro approach to cyclic and non-cyclic train timetabling, Omega, to appear, 2016.

A. Riise, L. Lamorgese, C. Mannino, Recursive logic-based Benders' decomposition for multi-modal outpatient scheduling, European Journal on Operational Research, 255, pp. 719-728, 2016

L. Lamorgese, C. Mannino, M. Piacentini, Optimal Train Dispatching by Benders' like reformulation, Transportation Science, 50 (3), pp. 910-925, 2016. 

A. Riise, E. Burke, C. Mannino, Modelling and Solving Generalised Operational Surgery Scheduling Problems, Computers & Operations Research, 66, pp. 1-11, 2016 .

L. Lamorgese, C. Mannino, An exact decomposition approach for the real-time Train Dispatching problem, Operations Research, 63 (1), pp. 48-64, 2015

M. Boccia, C. Mannino, I. Vasiliev, The dispatching problem on multitrack territories: Heuristic approaches based on mixed integer linear programming, Networks, 62 (4), pp. 315-326, 2013.

L. Lamorgese, C. Mannino, The track formulation for the Train Dispatching problem, Electronic Notes in Discrete Mathematics, 41, pp. 559-566, 2013

F. D'Andreagiovanni, C. Mannino, A. Sassano, GUB Covers and Power-Indexed formulations for Wireless Network Design, Management Science, 59 (1), pp. 142-156, 2013, INFORMS Telecommunication Section Best Paper Award 2014.

M. Holte, C. Mannino, The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care, European Journal of Operational Research 226, pp. 551-559, 2013.

F. Bernt, G. Dahl, C. Mannino, Computing optimal recovery policies for financial markets, Operations Research, 60, 2012.

C. Mannino, E. Nilssen, T. E. Nordlander, A pattern based, robust approach to cyclic master surgery scheduling, Journal of Scheduling, 15 (5), pp. 553-563, 2012

C. Mannino, S. Mattia, A. Sassano, Planning Wireless Networks by Shortest Path, Computational Optimization and Applications 48(3):533-551, 2011

C. Mannino, A. Mascis, Optimal Real-Time Trac Control in Metro Stations, Operations Research, 57 (4), pp. 1026-1039, 2009, EURO Excellence in Practice Award 2009.

C. Mannino, F. Rossi, A. Sassano, S. Smriglio, The time-oset optimization problem in digital broadcasting, Discrete Applied Mathematics, 156 (3), pp. 339-351, 2008.

K. Aardal, S.P.M. van Hoesel, A. Koster, C. Mannino, and A. Sassano, Models and Solution Techniques for Frequency Assignment Problems, Annals of Operations Research 153 (1), pp. 79-129, 2007.

C. Mannino, G. Oriolo, F. Ricci, S. Chandran. The stable set problem and the thinness of a graph. Operations Research Letters 35 (1), 1-9, 2007.

C. Mannino, F. Rossi, S. Smriglio, The Network Packing Problem in Terrestrial Broadcasting, Operations Research 54 (4), 611-626, (2006)

• Mannino, Carlo; Lamorgese, Leonardo Cameron; Dal Sasso, Veronica; Onofri, Andrea & Ventura, Paolo (2021). The Tick Formulation for Deadlock Detection and Avoidance in railways traffic control. Journal of Rail Transport Planning & Management.  ISSN 2210-9706.
• Fauske, Maria Fleischer; Mannino, Carlo & Ventura, Paolo (2020). Generalized periodic vehicle routing and maritime surveillance. Transportation Science.  ISSN 0041-1655.  54(1), s 164- 183 . doi: 10.1287/trsc.2019.0899 Full text in Research Archive.
• Huang, Yeran; Mannino, Carlo; Yang, Lixing & Tang, Tao (2020). Coupling time-indexed and big-M formulations for real-time train scheduling during metro service disruptions. Transportation Research Part B: Methodological.  ISSN 0191-2615.  133, s 38- 61 . doi: 10.1016/j.trb.2019.12.005 Show summary

  Track disruptions in metro systems may lead to severe train delays with many passengers stranded at platforms, unable to board on overloaded trains. Dispatchers may put in place different recovery actions, such as alternating train directions and allowing short turns. The objective is to alleviate the inconvenience for passengers and to regain the nominal train regularity. To characterize this process, this paper develops nonlinear mixed integer programming (NMIP) models with two different recovery strategies to reschedule trains during the disruption. For solving models in real time, the hybrid formulation, which couples big-M and time-indexed formulations, is proposed to linearize the proposed model as the mixed integer linear programming (MILP) model. Then, a two-stage approach is designed for handling the real-time detected information (like dynamic arriving passengers and end time of the disruption), including offline task (to select the best recovery strategy) and online task (to implement the best strategy and update timetable). Finally, the numerical experiments from Beijing metro Line 2 are implemented to verify the performance and effectiveness of the proposed hybrid formulation and two-stage approach.

• Mannino, Carlo; Nakkerud, Andreas & Sartor, Giorgio (2020). Air Traffic Flow Management with Layered Workload Constraints. Computers & Operations Research.  ISSN 0305-0548.  127 . doi: 10.1016/j.cor.2020.105159 Full text in Research Archive. Show summary

  Many regions of the world are currently struggling with congested airspace, and Europe is no exception. Motivated by our collaboration with relevant European authorities and companies in the Single European Sky ATM Research (SESAR) initiative, we investigate novel mathematical models and algorithms for supporting the Air Traffic Flow Management in Europe. In particular, we consider the problem of optimally choosing new (delayed) departure times for a set of scheduled flights to prevent en-route congestion and high workload for air traffic controllers while minimizing the total delay. This congestion is a function of the number of flights in a certain sector of the airspace, which in turn determines the workload of the air traffic controller(s) assigned to that sector. We present a MIP model that accurately captures the current definition of workload, and extend it to overcome some of the drawbacks of the current definition. The resulting scheduling problem makes use of a novel formulation, Path&Cycle, which is alternative to the classic big-M or time-indexed formulations. We describe a solution algorithm based on delayed variable and constraint generation to substantially speed up the computation. We conclude by showing the great potential of this approach on randomly generated, realistic instances.

• Sartor, Giorgio; Mannino, Carlo & Bach, Lukas (2020). Combinatorial Learning in Traffic Management. Lecture Notes in Computer Science (LNCS).  ISSN 0302-9743.  11943 LNCS, s 384- 395 . doi: 10.1007/978-3-030-37599-7_32 Show summary

  We describe an exact combinatorial learning approach to solve dynamic job-shop scheduling problems arising in traffic management. When a set of vehicles has to be controlled in real-time, a new schedule must be computed whenever a deviation from the current plan is detected, or periodically after a short amount of time. This suggests that each two (or more) consecutive instances will be very similar. We exploit a recently introduced MILP formulation for job-shop scheduling (called path&cycle) to develop an effective solution algorithm based on delayed row generation. In our re-optimization framework, the algorithm maintains a pool of combinatorial cuts separated during the solution of previous instances, and adapts them to warm start each new instance. In our experiments, this adaptive approach led to a 4-time average speedup over the static approach (where each instance is solved independently) for a critical application in air traffic management.

• Karahasanovic, Amela; Eide, Aslak Wegner; Schittekat, Patrick; Swendgaard, Hans Erik; Bakhrankova, Krystsina; Kjenstad, Dag; Mannino, Carlo; Zeh, Theodor; Grantz, Volker; Rokitansky, Carl-Herbert & Gräupl, Thomas (2019). Can Holistic Optimization Improve Airport Air Traffic Management Performance?. IEEE Aerospace and Electronic Systems Magazine.  ISSN 0885-8985.  34(5), s 12- 20 . doi: 10.1109/MAES.2019.2918039 Full text in Research Archive. Show summary

  Air transportation is an important factor in the economic growth of the European Union; however, the current system is already approaching its capacity and cost limits, and therefore needs to be reformed to meet the demands of further sustainable development. According to the European Commission, airspace congestion and the delays caused by it cost airlines between €1.3 and €1.9 billion a year. Several research initiatives have been launched to address air traffic management (ATM) challenges. The Single European Sky ATM Research (SESAR) program -a joint effort of the European Commission, EUROCONTROL, air navigation service providers, and the manufacturing industry -aims to define, develop, and deploy what is needed to increase the ATM performance and build Europe's intelligent air transport system. In this paper, we focus on the impact of such holistic optimization on the overall decision process and performance of air traffic control at the airport. To better understand how the algorithm can support ATCOs in their work, we analyzed the ATCOs self -reported descriptions of the current decision-making process.

• Lamorgese, Leonardo & Mannino, Carlo (2019). A non-compact formulation for job-shop scheduling problems in traffic management. Operations Research.  ISSN 0030-364X.  67(6) . doi: 10.1287/opre.2018.1837 Full text in Research Archive.
• Lamorgese, Leonardo Cameron; Mannino, Carlo; Pacciarelli, Dario & Krasemann, Johanna Törnquist (2018). Train Dispatching, In Ralf Borndörfer; Torsten Klug; Leonardo Lamorgese; Carlo Mannino; Markus Reuther & Thomas Schlechte (ed.),  Handbook of optimization in the railway industry.  Springer.  ISBN 978-3-319-72153-8.  artikkel.  s 265 - 283 Full text in Research Archive. Show summary

  Train rescheduling problems have received significant attention in the operations research community during the past 20–30 years. These are complex problems with many aspects and constraints to consider. This chapter defines the problem and summarizes the variety of model types and solution approaches developed over the years, in order to address and solve the train dispatching problem from the infrastructure manager perspective. Despite all the research efforts, it is, however, only very recently that the railway industry has made significant attempts to explore the large potential in using optimization-based decision-support to facilitate railway traffic disturbance management. This chapter reviews state-of-practice and provides a discussion about the observed slow progress in the application of optimization-based methods in practice. A few successful implementations have been identified, but their performance as well as the lessons learned from the development and implementation of those system are unfortunately only partly available to the research community, or potential industry users

• Mannino, Carlo; Nakkerud, Andreas; Sartor, Giorgio & Schittekat, Patrick (2018). Hotspot Resolution with Sliding Window Capacity Constraints using the Path&Cycle Algorithm. SESAR Innovation Days.  ISSN 0770-1268. Full text in Research Archive. Show summary

  We extend the new, efficient Path&Cycle formulation for the Hotspot Problem with two methods for dealing with windowed capacity constraints. We also discuss how to combine constraints to allow two-level capacity restricions for peak and average load respectively. Finally, we present computational results for the sliding window capacity constraint.

• Mannino, Carlo & Sartor, Giorgio (2018). The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management. OpenAccess Series in Informatics.  ISSN 2190-6807.  65 . doi: 10.4230/OASIcs.ATMOS.2018.14
• Mannino, Carlo; Sartor, Giorgio & Schittekat, Patrick (2018). Modelling and Solving the Hotspot Problem in Air Traffic Control., In Massimiliano Caramia; Lucio Bianco & Stefano Giordani (ed.),  Proceedings of the 16th International Conference on Project Management and Scheduling.  TexMat.  ISBN 9788894982022.  KAPITTEL.
• Avella, Pasquale; Boccia, Maurizio; Mannino, Carlo & Vasiliev, Igor (2017). Time-indexed formulations for the Runway Scheduling Problem. Transportation Science.  ISSN 0041-1655.  51(4), s 1196- 1209 . doi: 10.1287/trsc.2017.0750 Full text in Research Archive. Show summary

  The problem of sequencing and scheduling airplanes landing and taking off on a runway is a major challenge for air traffic management. This difficult real-time task is still carried out by human controllers, with little help from automatic tools. Several methods have been proposed in the literature, including mixed-integer programming (MIP)–based approaches. However, there is an opinion that MIP is unattractive for real-time applications, since computation times are likely to grow too large. In this paper, we reverse this claim, by developing a MIP approach able to solve to optimality real-life instances from congested airports in the stringent times allowed by the application. To achieve this, it was mandatory to identify new classes of strong valid inequalities, along with developing effective fixing and lifting procedures

• Bach, Lukas; Kjenstad, Dag & Mannino, Carlo (2017). The "Orchestrator" approach to multimodal continental trip planning.. Proceedings of the Multidisciplinary International Conference on Scheduling.  ISSN 2305-249X.  8, s 362- 366
• Borndörfer, Ralf; Klug, Torsten; Lamorgese, Leonardo Cameron; Mannino, Carlo; Reuther, Markus & Schlechte, Thomas (2017). Recent success stories on integrated optimization of railway systems. Transportation Research Part C: Emerging Technologies.  ISSN 0968-090X.  74, s 196- 211 . doi: 10.1016/j.trc.2016.11.015 Show summary

  Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain developing mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice (e.g. Cacchiani et al., 2014; Borndörfer et al., 2010), with a few notable exceptions. In this paper we address three individual success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will discuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that mathematical optimization can support the planning of railway resources. Thus, mathematical models and optimization can lead to a greater efficiency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.

• Fedeli, Francesca; Mancini, Roberto; Mannino, Carlo; Ofria, Paolo; Oriolo, Gianpaolo; Pacifici, Andrea & Piccialli, Veronica (2017). Optimal design of a regional railway service in Italy. Journal of Rail Transport Planning & Management.  ISSN 2210-9706.  7(4), s 308- 319 . doi: 10.1016/j.jrtpm.2017.10.001 Full text in Research Archive. Show summary

  In order to assess the actual ability of planned infrastructure investments to satisfy the required demand of service, railway engineers also need to plan the new offer of train services. In turn, this requires a full re-planning of the line system and of the frequency of each line. In cooperation with the Sales and Network Management department of the Italian infrastructure manager, we developed a model to determine an optimal set of lines and the corresponding train frequencies. The model has been successfully applied to evaluate alternative infrastructure enhancements in the metropolitan rail network of Rome. A set of computational experiments has been carried out, providing interesting insights on the effects of different infrastructural intervention policies.

• Lamorgese, Leonardo Cameron; Mannino, Carlo & Piacentini, Mauro (2017). Integer Programming Techniques for Train Dispatching in Mass Transit and Main Line, In Tamás Terlaky; Miguel Anjos & Shabbir Ahmed (ed.),  Advances and trends in optimization with engineering applications.  Society for Industrial and Applied Mathematics.  ISBN 978-1-611974-67-6.  Chapter 6.  s 65 - 75 Full text in Research Archive. Show summary

  Trains moving in railway systems are often affected by delays or cancellations. This in turn may produce knock-on effects and propagate to other trains and other regions of the network. These undesired effects may be alleviated by suitably rerouting and rescheduling trains in real time. Train dispatching is thus a central task in managing railway systems because it allows recovery from undesirable deviations from the timetable and a better exploitation of railway resources. With few exceptions, dispatching is still almost entirely in the hands of human operators, despite the fact that it is a large and complex optimization problem that does not lend itself to manual solution. In this chapter, we describe how integer programming (IP) can be exploited to quickly find optimal solutions to large dispatching problems and describe real-life implementations of these ideas.

• Avella, Pasquale; Boccia, Maurizio; Mannino, Carlo & Vasilyev, Igor (2016). Valid inequalities for time-indexed formulations of the runway scheduling problem. CEUR Workshop Proceedings.  ISSN 1613-0073.  1623, s 787- 790 Full text in Research Archive. Show summary

  The problem of sequencing and scheduling airplanes landing and taking off on a runway is under consideration. We propose a new family of valid inequalities which are obtained from the study of the single machine scheduling problem polytope.

• Lamorgese, Leonardo Cameron; Mannino, Carlo & Piacentini, Mauro (2016). Optimal Train Dispatching by Benders'-Like Reformulation. Transportation Science.  ISSN 0041-1655.  50(3), s 910- 925 . doi: 10.1287/trsc.2015.0605 Show summary

  Train movements on railway lines are generally controlled by human dispatchers. Because disruptions often occur, dispatchers make real-time scheduling and routing decisions in an attempt to minimize deviations from the official timetable. This optimization problem is called train dispatching. We represent it as a mixed integer linear programming model, and solve it with a Benders’-like decomposition within a suitable master/slave scheme. Interestingly, the master and the slave problems correspond to a macroscopic and microscopic representation of the railway, recently exploited in heuristic approaches to the problem. The decomposition, along with some new modeling ideas, allowed us to solve real-life instances of practical interest to optimality. Automatic dispatching systems based on our macro/micro decomposition—in which both master and slave are solved heuristically—have been in operation in several Italian lines since 2011. The exact approach described in this paper outperforms such systems on our test bed of real-life instances. Furthermore, a system based on another version of the exact decomposition approach has been in operation since February 2014 on a line in Norway

• Lamorgese, Leonardo Cameron; Nordlander, Tomas & Mannino, Carlo (2016). A New Modelling Approach Is Required to Help Mobile Network Operators Handle the Growing Demand for Data Traffic, In Begoña Vitoriano; Greg H. Parlier & Dominique De Werra (ed.),  Proceedings of 5th the International Conference on Operations Research and Enterprise Systems, February 23-25, 2016, Rome, Italy.  SciTePress.  ISBN 978-989-758-171-7.  artikkel.  s 402 - 407 Show summary

  Last year, global mobile data traffic grew by 69%, and similar growth rates are expected in the coming years. This growth affects the quality of service, and mobile network operators are finding it increasingly difficult to manage mobile data traffic. To this end, they are drastically increasing the number of sites and antennae, as well as modernising existing networks. This requires selecting the best antenna locations in terms of service area coverage, spectrum availability, installation costs, demographics, etc. In addition, when extending the wireless network with new antennae, the radio-electrical parameter settings of new and neighbouring antennae require (re)calibration to minimise interference—a process that in principle may affect the entire network. Moreover, the antennae must connect to the core network and influence it. This complex optimisation planning problem does not lend itself well to a manual solution approach. Still, these plans are developed “manually”, with the s upport of IT tools, through a time-consuming and inefficient trial-and-error process. Applied optimisation is needed to tackle this problem effectively, but this requires advancing the state-of-the-art: Most papers focus on solving the different sub-problems independently. However, these affect each other heavily and they must be considered simultaneously to maximise the offered service: optimising the location and configuration of new antennae and the configuration of wireless network radio-electrical parameters, while taking into account access to the core network.

• Mannino, Carlo; Lamorgese, Leonardo Cameron & Natvig, Erik (2016). An exact micro-macro approach to cyclic and non-cyclic train timetabling. Omega. The International Journal of Management Science.  ISSN 0305-0483. . doi: 10.1016/j.omega.2016.11.004 Show summary

  When planning new railway infrastructures in order to enhance the network to meet future demand, the capacity departments of railway operators typically have to face a time consuming trial-and-error process. The process involves the computation of a new timetable which satisfies the demand and is feasible w.r.t. the enhanced network, and is typically carried out by expert personnel with little or no assistance by computer tools. The quality of the results is thus very dependent on the skills of the individual planner. In this paper, we describe an exact approach to produce train timetables in short computation time. The approach extends the models and decomposition algorithms previously developed for train dispatching, a deeply related operational problem. The problem is solved at the microscopic level and the final timetable, even if in general non-cyclic, can incorporate cyclicity constraints for any subset of trains. Results are presented for a feasibility study in the Oslo area commissioned by the capacity planning department at Jernbaneverket (Norway׳s infrastructure manager).

• Riise, Atle; Mannino, Carlo & Burke, Edmund K. (2016). Modelling and solving generalised operational surgery scheduling problems. Computers & Operations Research.  ISSN 0305-0548.  66, s 1- 11 . doi: 10.1016/j.cor.2015.07.003 Show summary

  The term 'surgery scheduling' is used to describe a variety of strategic, tactical and operational scheduling problems, many of which are critical to the quality of treatment and to the efficient use of hospital resources. We consider operational surgery scheduling problems. The exact problem formulation varies substantially between hospitals or, even, hospital departments. In addition, the level of detail varies between different planning situations, ranging from long term patient admission planning to the very detailed scheduling of a particular day׳s surgeries. This diversity makes it difficult to design general scheduling methods and software solutions that can be applied without extensive customisation for each application. We approach this challenge by proposing a new generalised model for surgery scheduling problems. We show how this model extends the multi-project, multi-mode resource constrained project scheduling problem with generalised time constraints, including some extensions that to our knowledge have not been previously studied. Furthermore, we present a search method for solving the proposed model. The algorithm uses on-line learning to balance computational loads between a construction and an improvement method, both working on high level solution representations. An adapted schedule generation scheme is used to map these to concrete schedules. We perform computational experiments using realistic problem instances from three surgery scheduling planning situations at a medium sized Norwegian hospital; day scheduling, week scheduling and admission planning. The results show that the algorithm performs well across these quite different problems without any off-line customisation or parameter tuning.

• Riise, Atle; Mannino, Carlo & Lamorgese, Leonardo Cameron (2016). Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling. European Journal of Operational Research.  ISSN 0377-2217.  255(3), s 719- 728 . doi: 10.1016/j.ejor.2016.06.015 Show summary

  Efficient outpatient scheduling is becoming increasingly important for the overall cost effectiveness and treatment efficiency of a hospital. We consider a class of multi-mode appointment scheduling problems, with variable resource availability and resource setup times. These problems are frequently found in hospital outpatient clinics, and they are typically hard to solve. We present an exact method based on a recursive logic-based Benders’ decomposition, where each subproblem is formulated as an integer linear program. We show how such a decomposition can be designed to fully exploit the daily structure of these problems, while at the same time addressing the symmetry issues that arise from having many appointments with similar resource and time requirements. Novel valid inequalities are also added to strengthen each master problem. We demonstrate the efficiency of the overall approach through a case study from a gastroenterology clinic at the University Hospital of Northern Norway, using real life data. The computational results show that the recursive, three-level, decomposition solves the most complex real life test instances to optimality in less than 5 minutes. The method drastically outperforms the corresponding two-level decomposition, which fails to solve all but one of these test instances within the one hour time limit.

• Lamorgese, Leonardo Cameron & Mannino, Carlo (2015). An exact decomposition approach for the Real-Time Train Dispatching problem. Operations Research.  ISSN 0030-364X.  63(1), s 48- 64 . doi: 10.1287/opre.2014.1327 Show summary

  Trains’ movements on a railway network are regulated by official timetables. Deviations and delays occur quite often in practice, demanding fast rescheduling and rerouting decisions in order to avoid conflicts and minimize overall delay. This is the real-time train dispatching problem. In contrast with the classic “holistic” approach, we show how to decompose the problem into smaller subproblems associated with the line and the stations. This decomposition is the basis for a master-slave solution algorithm, in which the master problem is associated with the line and the slave problem is associated with the stations. The two subproblems are modeled as mixed integer linear programs, with specific sets of variables and constraints. Similarly to the classical Benders’ decomposition approach, slave and master communicate through suitable feasibility cuts in the variables of the master. Extensive tests on real-life instances from single and double-track lines in Italy showed significant improvements over current dispatching performances. A decision support system based on this exact approach has been in operation in Norway since February 2014 and represents one of the first operative applications of mathematical optimization to train dispatching.

• Mannino, Carlo & Lamorgese, Leonardo (2015). A non-compact formulation for job-shop scheduling problems in transportation, In Raimund Seidl (ed.),  Dagstuhl Reports.  Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  Presentation Abstract.  s 151 - 151 Show summary

  A central problem in transportation is that of routing and scheduling the movements of vehicles so as to minimize the cost of the schedule. It arises, for instance, in timetabling, dispatching, delay and disruption management, runway scheduling, and many more. For fixed routing, the problem boils down to finding a minimum cost conflict-free schedule, i.e. a schedule where potential conflicts are prevented by a correct timing of the vehicles on the shared resources. A classical mathematical representation involves continuous variables representing times, (time-precedence) linear constraints associated with single vehicles, and disjunctive (precedence) linear constraints associated with pairs vehicles. There are two standard ways to linearize disjunctions, namely by means of BigM formulations or by timeindexed formulations. BigM formulations tend to return notoriously weak relaxations, whereas time-indexed formulations quickly become too large for instances of some practical interest. In this work we develop a new, non-compact formulation for such disjunctive programs with convex piece-wise linear cost, and solve the resulting problems by row-generation. Our initial tests show that the new approach favourably compares with the so-far most effective approach on a large number of real-life test instances from railway traffic management. Moreover, it opens up for several research directions, ranging from investigating polyhedral properties to algorithmic speed-ups.

• Boccia, Maurizio; Mannino, Carlo & Vasilyev, Igor (2013). The dispatching problem on multitrack territories: Heuristic approaches based on mixed integer linear programming. Networks.  ISSN 0028-3045.  62(4), s 315- 326 . doi: 10.1002/net.21528 Show summary

  Trains running through railway lines often accumulate some delay. When this happens, rescheduling and rerouting decisions must be quickly taken in real time. Despite the fact that even a single wrong decision may deteriorate the performance of the whole railway network, this complex optimization task is still basically performed by human operators. In very recent years, the interest of train operators to implement automated decision systems has grown. Not incidentally, the railway application section (RAS) of INFORMS has issued a challenge devoted to this problem concomitantly with the INFORMS Annual Meeting 2012. In this article, we describe two heuristic approaches to solve the RAS problem based on a mixed integer linear programming formulation, and we report computational results on the three RAS instances and on an additional set of instances defined on a more congested network. Computational results on the challenge test bed show that our algorithms positively compare with other approaches to the RAS problem.

• D'Andreagiovanni, Fabio; Mannino, Carlo & Sassano, Antonio (2013). GUB Covers and Power-Indexed formulation for Wireless Network Design. Management science.  ISSN 0025-1909.  59(1), s 142- 156 . doi: 10.1287/mnsc.1120.1571 Show summary

  We propose a pure 0-1 formulation for the wireless network design problem, i.e., the problem of configuring a set of transmitters to provide service coverage to a set of receivers. In contrast with classical mixedinteger formulations, where power emissions are represented by continuous variables, we consider only a finite set of power values. This has two major advantages: it better fits the usual practice and eliminates the sources of numerical problems that heavily affect continuous models. A crucial ingredient of our approach is an effective basic formulation for the single knapsack problem representing the coverage condition of a receiver. This formulation is based on the generalized upper bound (GUB) cover inequalities introduced by Wolsey [Wolsey L (1990) Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints. Discrete Appl. Math. 29(2–3):251–261]; and its core is an extension of the exact formulation of the GUB knapsack polytope with two GUB constraints. This special case corresponds to the very common practical situation where only one major interferer is present. We assess the effectiveness of our formulation by comprehensive computational results over realistic instances of two typical technologies, namely, WiMAX and DVB-T.

• Kjenstad, Dag; Mannino, Carlo; Schittekat, Patrick & Smedsrud, Morten (2013). Integrated surface and departure management at airports by optimization, In  2013 5th International Conference on Modeling, Simulation and Applied Optimization, ICMSAO 2013, Hammamet, 28-30 April. 2013.  IEEE.  ISBN 978-1-4673-5814-9.  artikkel. Show summary

  A key challenge in Air Traffic Management is to provide a swift flow of airplanes at and near the airports. The pressure on existing airports will be higher as demand of air transport is predicted to increase over the next decades. Airline companies compete on delivering improved departure and arrival punctuality for their flights. In this paper we present experimental results where we are comparing the performance of traditional tower control decisions versus decisions supported by optimization technology in a simulation environment. We present a mathematical model for the integrated departure management and surface management problem and a solution algorithm based on a heuristic decomposition of the integrated problem. This represents a first attempt to solve the two problems simultaneously. Our approach is designed for dynamic rescheduling and real-time environment, with corresponding response time requirements. Finally, we present computational results that show significant improvements in punctuality and reductions in taxi times.

• Lamorgese, Leonardo Cameron & Mannino, Carlo (2013). The track formulation for the train dispatching problem. Electronic Notes in Discrete Mathematics.  ISSN 1571-0653.  41, s 559- 566 . doi: 10.1016/j.endm.2013.05.138 Show summary

  With few exceptions, train movements are still controlled by human operators, the dispatchers. They establish routes and precedence between trains in real-time in order to cope with normal operations but also to recover from deviations from the timetable, and minimize overall delays. Implicitly they tackle and solve repeatedly a hard optimization problem, the Train Dispatching Problem. We recently developed a decomposition approach which allowed us to solve real-life instances to optimality or near optimality in times acceptable for dispatchers. We present here some new ideas which appear to significantly reduce computational times while solving to optimality even large instances.

• Benth, Fred Espen; Dahl, Geir & Mannino, Carlo (2012). Computing Optimal Recovery Policies for Financial Markets. Operations Research.  ISSN 0030-364X.  60(6), s 1373- 1388 . doi: 10.1287/opre.1120.1112
• Mannino, Carlo & Holte, Matias (2012). The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care. European Journal of Operational Research.  ISSN 0377-2217.  226, s 551- 559 . doi: 10.1016/j.ejor.2012.10.029 Show summary

  A general problem in health-care consists in allocating some scarce medical resource, such as operating rooms or medical staff, to medical specialties in order to keep the queue of patients as short as possible. A major difficulty stems from the fact that such an allocation must be established several months in advance, and the exact number of patients for each specialty is an uncertain parameter. Another problem arises for cyclic schedules, where the allocation is defined over a short period, e.g. a week, and then repeated during the time horizon. However, the demand typically varies from week to week: even if we know in advance the exact demand for each week, the weekly schedule cannot be adapted accordingly. We model both the uncertain and the cyclic allocation problem as adjustable robust scheduling problems. We develop a row and column generation algorithm to solve this problem and show that it corresponds to the implementor/adversary algorithm for robust optimization recently introduced by Bienstock for portfolio selection. We apply our general model to compute master surgery schedules for a real-life instance from a large hospital in Oslo.

• Mannino, Carlo; Nilssen, Eivind Jodaa & Nordlander, Tomas (2012). A pattern based, robust approach to cyclic master surgery scheduling. Journal of Scheduling.  ISSN 1094-6136.  15(5), s 553- 563 . doi: 10.1007/s10951-012-0275-z Show summary

  The Master Surgery Scheduling problem consists of finding a suitable allocation of operating resources to surgical groups. A myriad of variants of the problem has been addressed in literature. Here we focus on two major variants, arising during a cooperation with Sykehuset Asker og Bærum HF, a large hospital in the city of Oslo. The first variant asks for balancing patient queue lengths among different specialties, whereas the second for minimizing resort to overtime. To cope with these problems we introduce a new mixed integer linear formulation and show its beneficial properties. Both problems require the estimation of demand levels. As such estimation is affected by uncertainty, we also develop a light robustness approach to the second variant. Finally we present computational results on a number of real-world instances provided by our reference hospital.

• Kjenstad, Dag; Mannino, Carlo; Nordlander, Tomas; Schittekat, Patrick & Smedsrud, Morten (2011). Optimizing AMAN-SMAN-DMAN at Hamburg and Arlanda airport, In Dirk Schaefer (ed.),  Proceedings of the SESAR Innovation Days.  Eurocontrol.  ISBN 978-2-87497-024-5.  1. Show summary

  The Third SESAR Innovation Days (SIDs), At Royal Institute of Technology in Stockholm, Sweden, Volume: 3

View all works in Cristin

• Borndörfer, Ralf; Klug, Torsten; Lamorgese, Leonardo; Mannino, Carlo; Reuther, Markus & Schlechte, Thomas (ed.) (2018). Handbook of optimization in the railway industry. Springer.  ISBN 978-3-319-72153-8.  280 s.

View all works in Cristin

• Mannino, Carlo (2020, 02. juli). Ny norskutviklet programvare skal bedre punktligheten på jernbanen. [Tidsskrift].  Teknisk ukeblad.
• Bach, Lukas & Mannino, Carlo (2019). Matematikk kan forbedre jernbanen. Aftenposten (morgenutg. : trykt utg.).  ISSN 0804-3116.
• Bach, Lukas; Mannino, Carlo & Sartor, Giorgio (2019). MILP approaches to practical real-time train scheduling: the Iron Ore Line case.
• Sartor, Giorgio; Mannino, Carlo & Bach, Lukas (2019). Combinatorial Learning in Traffic Management.
• Fauske, Maria Fleischer; Ventura, Paolo & Mannino, Carlo (2018). Solving a Generalized Periodic Vehicle Routing Problem for Maritime Surveillance.
• Kloster, Oddvar; Mannino, Carlo; Riise, Atle & Schittekat, Patrick (2018). Scheduling Vehicles with spatial conflicts, In Massimiliano Caramia; Lucio Bianco & Stefano Giordani (ed.),  Proceedings of the 16th International Conference on Project Management and Scheduling.  TexMat.  ISBN 9788894982022.  KAPITTEL.
• Kloster, Oddvar; Mannino, Carlo; Riise, Atle & Schittekat, Patrick (2018). Scheduling Vehicles with spatial conflicts.
• Kloster, Oddvar; Mannino, Carlo; Riise, Atle & Schittekat, Patrick (2018). Vehicle scheduling: spatial conflicts representation, detection and resolution.
• Mannino, Carlo; Nakkerud, Andreas; Sartor, Giorgio & Schittekat, Patrick (2018). Hotspot Resolution with Sliding Window Capacity Constraints using the Path&Cycle Algorithm. Show summary

  We extend the new, efficient Path&Cycle formulation for the Hotspot Problem with two methods for dealing with windowed capacity constraints. We also discuss how to combine constraints to allow two-level capacity restricions for peak and average load respectively. Finally, we present computational results for the sliding window capacity constraint.

• Mannino, Carlo; Sartor, Giorgio & Schittekat, Patrick (2018). Modelling and Solving the Hotspot Problem in Air Traffic Control..
• Sartor, Giorgio & Mannino, Carlo (2018). The Path&Cycle formulation for the Hotspot Problem in Air Traffic Management. Show summary

  The Hotspot Problem in Air Traffic Management consists of optimally rescheduling a set of airplanes that are forecast to occupy an overcrowded region of the airspace, should they follow their original schedule. We first provide a MILP model for the Hotspot Problem using a standard big-M formulation. Then, we present a novel MILP model that gets rid of the big-M coefficients. The new formulation contains only simple combinatorial constraints, corresponding to paths and cycles in an associated disjunctive graph. We report computational results on a set of randomly generated instances. In the experiments, the new formulation consistently outperforms the big-M formulation, both in terms of running times and number of branching nodes.

• Sartor, Giorgio; Mannino, Carlo & Schittekat, Patrick (2018). A novel formulation for job-shop scheduling in traffic management. Show summary

  A central problem in traffic management is that of scheduling the movements of vehicles so as to minimize the cost of the schedule. This problem can be modeled as a job-shop scheduling problem. We present a new MILP formulation which is alternative to classical approaches such as big-M and time-indexed formulations. It does not make use of artificially large coefficients and its constraints correspond to basic graph structures, namely paths, cycles and trees. The new formulation can be obtained by strengthening and lifting the constraints of a classical Benders’ reformulation. We successfully tested our approach on real-life instances of two relevant traffic management problems: the Hotspot Problem, which consists of rescheduling flight trajectories to prevent congested airborne sectors while minimizing overall delay; and train dispatching, which consists of rescheduling the movements of rolling stocks in railway lines, typically due to delays or disruptions.

• Sartor, Giorgio; Mannino, Carlo & Schittekat, Patrick (2018). The Path&Cycleformulation for the HotspotProblem in Air Traffic Management. Show summary

  Air traffic management involves the coordination of flights in a particular region of the world with the objective of guaranteeing their safety while possibly reducing delays. Each region is subdivided in smaller sectors and the number of airplanes that will occupy each sector in a given time can be forecast taking into account the timetable and the planned route of the airplanes. For safety reasons, a certain capacity is assigned to each sector and a hotspot is defined as a sector in which the predicted number of airplanes is greater than its maximum capacity in at least one point in time. The hotspot problem consists of finding a hotspot-free schedule for the airplanes that minimize delays. In particular, given the route and timetable of a set of flights we assume that the airplanes will fly at constant speed and we focus on choosing their departure times in order prevent hotspots while minimizing the total sum of delays. We present a novel, non-compact formulation for this problem that is alternative to the more conventional big-M. In particular we present a methodology that exploits Benders’ decomposition to obtain a (master) problem only in the binary variables plus a few continuous variables to represent the objective function. The decomposition allows us to get rid of infamous big-M coefficients (at the cost of an increased number of linear constraints). Moreover, the constraints of the reformulated master correspond to basic graph structures, such as paths, cycles and trees. The new formulation is obtained by strengthening and lifting the constraints of a classical Benders’ reformulation. Preliminary computational results on random but realistic instances show that the new approach favorably compares against the big-M formulation.

• Bach, Lukas; Kloster, Oddvar & Mannino, Carlo (2017). Real-time train dispatching on the iron ore line.
• Bach, Lukas & Mannino, Carlo (2017). CO2REOPT: Real-time Train Dispatching on the Iron Ore Line.
• Riise, Atle; Burke, Edmund & Mannino, Carlo (2015). Integrated planning and scheduling in operational patient management.
• Riise, Atle; Mannino, Carlo & Leonardo, Lamorgese (2015). Multi-level Benders Decomposition for Multi-modal Outpatient Scheduling in Hospitals.
• Bakhrankova, Krystsina; Schittekat, Patrick; Karahasanovic, Amela; Eide, Aslak Wegner; Swendgaard, Hans Erik; Grantz, Volker; Ødegård, Stian Støer; Kjenstad, Dag & Mannino, Carlo (2014). Decision support for improving the SESAR Key Performance Areas.
• Lamorgese, Leonardo Cameron; Lium, Arnt-Gunnar & Mannino, Carlo (2014). Prioritization of Trains: mathematical model. SINTEF Rapport. A26384. Full text in Research Archive. Show summary

  We present a mathematical optimization model suitable for providing decision support on train dispatching on small and medium sized regional lines. An implementation of the model has undergone extensive real life testing at the Stavanger train dispatching central on the Stavanger- Mol line from February to October 2014. During this test period the model has been solved about 40 000 times, typically finding the optimal solution within two-four seconds. Oppdragsgiver: Jernbaneverket

• Lamorgese, Leonardo Cameron; Lium, Arnt-Gunnar; Mannino, Carlo & Kloster, Oddvar (2014). An exact decomposition approach for the real-time train dispatching problem.
• Lium, Arnt-Gunnar; Dragland, Åse Kirsti & Mannino, Carlo (2014). Nye kart får togene i rute. Forskning.no.  ISSN 1891-635X. Show summary

  Når et tog blir forsinket, er det ikke alltid like lett for toglederne å løse problemet umiddelbart. Nå skal nye kartsystem gi dem alternativer i løpet av sekunder.

• Lium, Arnt-Gunnar; Dragland, Åse Kirsti & Mannino, Carlo (2014). Prioriterte tog det neste?. Gemini.  ISSN 0802-085X. Show summary

  Et nytt verktøy kan få et forsinket tog tilbake i rute. Nå tester togledersentralen i Stavanger verktøyet som skal gi den optimale løsningen i løpet av sekunder. - See more at: http://gemini.no/2014/05/prioriterte-tog-det-neste/#sthash.pBPTBH3Q.dpuf

• Nordlander, Tomas; Schittekat, Patrick; Kjenstad, Dag; Mannino, Carlo & Smedsrud, Morten (2014). Optimize scheduling and routing at an airport.
• Schittekat, Patrick; Kjenstad, Dag; Mannino, Carlo; Nordlander, Tomas & Smedsrud, Morten (2014). Integrated scheduling and routing at an airport.
• Gaze, Kevin Anders; Hasle, Geir & Mannino, Carlo (2013). Column Generation for the Mixed Capacitated General Routing Problem.
• Lamorgese, Leonardo Cameron & Mannino, Carlo (2013). An exact decomposition approach for the real-time Train Dispatching problem (v.2). SINTEF Rapport. A24355. Full text in Research Archive. Show summary

  Trains movements on a railway network are regulated by official timetables. Deviations and delays occur quite often in practice, demanding fast re-scheduling and re-routing decisions in order to avoid conflicts and minimize overall delay. This is the real-time train dispatching problem. In contrast with the classic ""holistic"" approach, we show how to decompose the problem into smaller subproblems associated with the line and the stations. The decomposition is the basis for a master-slave solution algorithm, in which the master problem is associated with the line and the slave problem is associated with the stations. The two subproblems are modeled as mixed integer linear programs, with their specific sets of variables and constraints. Similarly to the classical Bender's decomposition approach, the slave and the master communicate through suitable feasibility cuts in the variables of the master. By applying our approach to a number of real-life instances from single and double-track lines in Italy, we were able to (quickly) find optimal or near-optimal solutions, with impressive improvements over the performances of the current operating control systems. The new approach will be put in operation in such lines for an extensive on-field test-campaign as of April 2013. Follows SINTEF Technical Report A23274 Oppdragsgiver: Jernbaneverket

• Lamorgese, Leonardo Cameron & Mannino, Carlo (2012). An exact decomposition approach for the real-time train dispatching problem. SINTEF Rapport. A23274. Full text in Research Archive. Show summary

  Trains movement on a railway network are regulated by the official timetables. Deviations and delays occur quite often in practice, asking for fast rescheduling and rerouting decisions in order to avoid conflicts and minimize overall delay. This is the real-time train dispatching problem. In contrast with the classic ""holistic"" approach, we show how to decompose the problem into smaller subproblems associated with the line and the stations. This decomposition allows for the application of suitable simplified models,  which in turn makes it possible to apply Mixed Integer Linear Programming to quickly find optimal or near-optimal solutions to a number of real-life instances from single-track lines in Italy.

• Lium, Arnt-Gunnar; Werner, Adrian & Mannino, Carlo (2012). A survey of approaches for prioritizing trains in congested railroad networks. SINTEF Rapport. A22523. Full text in Research Archive. Show summary

  On potentially highly congested railroad networks, demand for passenger and freight transport is affected not only by the available capacity but also by the consequences of the achieved punctuality and regularity: Poor on-time performance increases travel costs and, hence, makes rail less competitive toward other modes. It is, therefore, paramount to ensure a good punctuality record of the network, also in the case of disruptions and delays of single trains. On the tactical leveL well-planned timetables help to achieve both a high capacity utilization and good punctuality. On the operational level, advanced approaches for rescheduling or prioritizing trains can support dispatchers controlling the traffic flow. In this report, we discuss issues to be considered when prioritizing trains and describe the most common approaches. Furthermore, we give a brief overview of some of the train dispatching systems currently in use and examples of where they are being used. We also present some of the latest academic developments in more advanced decision support far train prioritization on the operational level This also includes results of experimental studies for coordinating decisions over a larger part of the network. Finally, we discuss how to connect the dispatching of trains with incentive systems. Oppdragsgiver: Regionalt Forskningsfond Hovedstaden

• Riise, Atle & Mannino, Carlo (2012). The Surgery Scheduling Problem - A General Model. SINTEF Rapport. A22333. Full text in Research Archive. Show summary

  The term surgery scheduling is used about a variety of strategic, tactical and operational scheduling problems, many of which are critical to an efficient use of hospital resources. Our focus is on operational surgery scheduling problems, which are often NP-hard. The exact problem formulation varies substantially among hospitals, or even hospital departments. In addition, the level of detail vary between different planning situations, ranging from long term patient admission planning to a very detailed planning of the same day's surgeries. This diversity makes it difficult to design scheduling methods and software solutions that are applicable to a wide range of surgery scheduling problems, without extensive customization for each individual application. We approach this challenge by proposing a new generalised model for surgery scheduling problems. The problem can be seen as a rich extension to the resource-constrained project scheduling problem, and we present a structured overview of how our contribution relates to the existing project scheduling literature. We represent this problem by extending the classical disjunctive graph model developed for jobshop scheduling problems. To investigate the power of exact optimization methods in solving generalised surgery scheduling problems, we formulate this disjunctive model as a Mixed Integer Linear Program and solve it by means of a commercial solver. The results show that while it is not capable of solving realistic instances to optimality, the formulation produces good bounds, and promising results were found for interesting sub problems. Oppdragsgiver: Norges Forskningsråd

View all works in Cristin