Search

The outbreak of SARS-CoV-2 and the corresponding surge in patients with severe symptoms of COVID-19 put a strain on health systems, requiring specialized material and human resources, often exceeding the locally available ones. Motivated by a real emergency response system employed in Northern Italy, we propose a mathematical programming approach for rebalancing the health resources among a network of hospitals in a large geographical area. It is meant for tactical planning in facing foreseen peaks of patients requiring specialized treatment. Our model has a clean combinatorial structure. At the same time, it considers the handling of patients by a dedicated home healthcare service, and the efficient exploitation of resource sharing. We introduce mathematical programming heuristic based on decomposition methods and column generation to drive very large-scale neighborhood search. We evaluate its embedding in a multi-objective optimization framework. We experiment on real world data of the COVID-19 in Northern Italy during 2020, whose aggregation and post processing is made openly available to the community. Our approach proves to be effective in tackling realistic instances, thus making it a reliable basis for actual decision support tools.

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This problem generalizes the problem introduced by Ahmed S, Atamtürk A (Mathematical programming 128(1-2):149–169, 2011), and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. It has applications to, among others, maximal covering location, and influence maximization problems. In the paper, we propose a double-hypograph decomposition which allows for projecting out the variables associated with the items by separately exploiting the structural properties of the utility function and of the set-union operator. Thanks to it, the utility function is linearized via an exact outer-approximation technique, whereas the set-union operator is linearized in two ways: either (i) via a reformulation based on submodular cuts, or (ii) via a Benders decomposition. We analyze from a theoretical perspective the strength of the inequalities of the resulting reformulations, and embed them into two branch-and-cut algorithms. We also show how to extend our reformulations to the case where the utility function is not necessarily increasing. We then experimentally compare our algorithms inter se, to a standard reformulation based on submodular cuts, to a state-of-the-art global-optimization solver, and to the greedy algorithm for the maximization of a submodular function. The results reveal that, on our testbed, the method based on combining an outer approximation with Benders cuts significantly outperforms the other ones.

Warehouses are key elements of supply chain networks, and great attention is paid to increase their efficiency. Highly volatile space requirements are enablers of innovative resource sharing concepts, where warehouse capacities are traded on online platforms. In this context, our paper introduces the on-demand warehousing problem from the perspective of platform providers. The objective prioritises demand–supply matching with maximisation of the number of transactions. If there is a tie, the secondary objective maximises the number of suppliers matched with at least one customer and the number of customers that have matches within a specific threshold with respect to the minimum achievable cost. Besides the mathematical integer programming formulation, a myopic list-based heuristic and an efficient matheuristic approach are presented and benchmarked against the performance of a commercial optimisation solver. The impact of several parameters on the platform’s objective is analysed. A particularly relevant finding is that the pricing flexibility on the demand side does not necessarily imply higher payments to the supply side. All data instances are made available publicly to encourage more researchers to work on this timely and challenging topic.

It is standard cardiology practice for patients suffering from ventricular arrhythmias (the main cause of sudden cardiac death) belonging to high risk populations to be treated via the implantation of Subcutaneous Implantable cardioverter-defibrillators (S-ICDs). S-ICDs carry a risk of so-called T wave over sensing (TWOS), which can lead to inappropriate shocks that carry an inherent health risk. For this reason, according to current practice patients’ Electrocardiograms (ECGs) are manually screened by a cardiologist over 10 s to assess the T:R ratio—the ratio between the amplitudes of the T and R waves which is used as a marker for the likelihood of TWOS—with a plastic template. Unfortunately, the temporal variability of a patient’ T:R ratio can render such a screening procedure, which relies on an inevitably short ECG segment due to its manual nature, unreliable. In this paper, we propose and investigate a tool based on deep learning for the automatic prediction of the T:R ratios from multiple 10-second segments of ECG recordings capable of carrying out a 24-hour automated screening. Thanks to the significantly increased screening window, such a screening would provide far more reliable T:R ratio predictions than the currently utilized 10-second, template-based, manual screening is capable of. Our tool is the first, to the best of our knowledge, to fully automate such an otherwise manual and potentially inaccurate procedure. From a methodological perspective, we evaluate different deep learning model architectures for our tool, assess a range of stochastic-gradient-descent-based optimization methods for training their underlying deep-learning model, perform hyperparameter tuning, and create ensembles of the best performing models in order to identify which combination leads to the best performance. We find that the resulting model, which has been integrated into a prototypical tool for use by clinicians, is able to predict T:R ratios with very high accuracy. Thanks to this, our automated T:R ratio detection tool will enable clinicians to provide a completely automated assessment of whether a patient is eligible for S-ICD implantation which is more reliable than current practice thanks to adopting a significantly longer ECG screening window which better and more accurately captures the behavior of the patient’s T:R ratio than the current manual practice.

We apply a dynamic stochastic control (DSC) approach based on an open-loop linear feedback policy to a classical asset-liability management problem as the one faced by a defined-benefit pension fund (PF) manager. We assume a PF manager seeking an optimal investment policy under random market returns and liability costs as well as stochastic PF members’ survival rates. The objective function is formulated as a risk-reward trade-off function resulting in a quadratic programming problem. The proposed methodology combines a stochastic control approach, due to Primbs and Sung (IEEE Trans Autom Control 54(2):221–230, 2009), with a chance constraint on the PF funding ratio (FR) and it is applied for the first time to this class of long-term financial planning problems characterized by stochastic asset and liabilities. Thanks to the DSC formulation, we preserve the underlying risk factors continuous distributions and avoid any state space discretization as is typically the case in multistage stochastic programs (MSP). By distinguishing between a long-term PF liability projection horizon and a shorter investment horizon for the FR control, we avoid the curse-of-dimensionality, in-sample instability and approximation errors that typically characterize MSP formulations. Through an extended computational study, we present in- and out-of-sample results which allows us to validate the proposed methodology. The collected evidences confirm the potential of this approach when applied to a stylized but sufficiently realistic long-term PF problem.

In the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a right-hand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is [Formula: see text]-hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovász’s Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities. Summary of Contribution: This paper proposes two original methods for solving a challenging cut-separation problem (of bilevel type) for a large class of inequalities valid for one of the key operations research problems, namely, the max stable set problem. An extensive set of experimental results validates the proposed methods. All the source code and data sets are available online on GitHub.

EWGT 2021, 24th Euro Working Group on Transportation Meeting, Aveiro, PORTUGAL, 08-/09/2021 - 10/09/2021; In a railway network, traffic is often perturbed and trains must be rerouted and rescheduled. Doing so in large networks is a challenging task, which has been tackled through various decomposition approaches in the literature. In this paper, we propose an algorithm for managing traffic considering dynamic problem decompositions. It is an asynchronous algorithm based on the decomposition of the problem considering at each time step the smallest possible portion of the network and subset of trains. We prove that this algorithm guarantees to find an overall feasible solution if it exists, for single track networks with passing loops.

In this paper, we consider the problem of completely flying over an area just hit by an earthquake with a fleet of Unmanned Aerial Vehicles (UAVs) to opportunely direct rescue teams. The cooperation between UAVs ensures that the search for possible survivors can be faster and more effective than the solutions currently implemented by civil protection. To study this scenario, we introduce the Cover by Multitrips with Priorities (CMP) problem, which tries to keep into account all the main real-life issues connected to the flight and coordination of the UAVs. We conduct a theoretical study to estimate the best number of UAVs and additional batteries, to give indications to the organization that leads the rescue teams to be able to guarantee rapid and effective rescue. Finally, based on some theoretical considerations, we propose some heuristics that tackle the problem of flying over the whole area with a fleet of UAVs in the shortest possible time. Simulations show that they work efficiently in both the proposed scenarios and provide better performance than previous solutions once they are arranged to work in our scenarios. The main advantages of our approach w.r.t. the current drone-based solutions used by the civil defense are that UAVs do not need drivers so the time of all available rescue workers can be invested in doing something else. In our model, we take into account that some sites (e.g. buildings with a high fire risk or schools and hospitals) have a higher priority and must be inspected first, and the possibility that UAVs can make a decision based on what they detect. Finally, our approach allows UAVs to collaborate so that the same sites will be flown over exactly once in order to speed up the rescue mission.

In this article, we propose a mean field game approach for modeling the flows of excursionists within a network of tourist attractions. We prove the existence of an equilibrium within the network using a balance ordinary differential equation together with optimality conditions in terms of the value function. We also propose a bi-level formulation of the problem where we aim at achieving a sustainable-oriented control strategy in the upper level and at maximizing excursionists’ satisfaction in the lower level. Our proposed model may provide an effective management tool for local authorities who deal with the challenging problem of finding an optimal control policy to the often conflicting objectives of ensuring the maximum excursionists’ satisfaction while pursuing the highest sustainability benefits.

This paper introduces SigMaNet, a generalized Graph Convolutional Network (GCN) capable of handling both undirected and directed graphs with weights not restricted in sign nor magnitude. The cornerstone of SigMaNet is the Sign-Magnetic Laplacian ($L^{\sigma}$), a new Laplacian matrix that we introduce ex novo in this work. $L^{\sigma}$ allows us to bridge a gap in the current literature by extending the theory of spectral GCNs to (directed) graphs with both positive and negative weights. $L^{\sigma}$ exhibits several desirable properties not enjoyed by other Laplacian matrices on which several state-of-the-art architectures are based, among which encoding the edge direction and weight in a clear and natural way that is not negatively affected by the weight magnitude. $L^{\sigma}$ is also completely parameter-free, which is not the case of other Laplacian operators such as, e.g., the Magnetic Laplacian. The versatility and the performance of our proposed approach is amply demonstrated via computational experiments. Indeed, our results show that, for at least a metric, SigMaNet achieves the best performance in 15 out of 21 cases and either the first- or second-best performance in 21 cases out of 21, even when compared to architectures that are either more complex or that, due to being designed for a narrower class of graphs, should -- but do not -- achieve a better performance., Comment: 22 pages, 6 tables

We describe a special class of quasi-equilibrium problems in metric spaces and propose a novel simple threshold descent method for solving these problems. Due to the framework, the convergence of the method cannot be established with the usual convexity or generalized convexity assumptions. Under mild conditions, the iterative procedure gives solutions of the quasi-equilibrium problem. We apply this method to scalar and vector generalized quasi-equilibrium problems and to some classes of relative optimization problems.

S-ICD eligibility is assessed at pre-implant screening where surface ECG traces are used as surrogates for S-ICD vectors. In heart failure (HF) patients undergoing diuresis, electrolytes and fluid shifts can cause changes in R and T waves. Subsequently, T:R ratio, a major predictor of S-ICD eligibility, can be dynamic.This is a prospective study of patients with structurally normal hearts and HF patients undergoing diuresis. All patients were fitted with Holters® to record their S-ICD vectors. Our deep learning model was used to analyze the T:R ratios across the recordings. Welch two sample t-test and Mann-Whitney U were used to compare the data between the two groups.Twenty-one patients (age 58.43 ± 18.92, 62% male, 14 HF, 7 normal hearts) were enrolled. There was a significant difference in the T:R ratios between both groups. Mean T: R was higher in the HF group (0.18 ± 0.08 vs 0.10 ± 0.05, p .001). Standard deviation of T: R was also higher in the HF group (0.09 ± 0.05 vs 0.07 ± 0.04, p = .024). There was no difference between leads within the same group.T:R ratio, a main determinant for S-ICD eligibility, is higher and has more tendency to fluctuate in HF patients undergoing diuresis. We hypothesize that our novel neural network model could be used to select HF patients eligible for S-ICD by better characterization of T:R ratio reducing the risk of T-wave over-sensing (TWO) and inappropriate shocks. Further work is required to consolidate our findings before applying to clinical practice.

In this paper, we consider the problem of tax evasion, which occurs whenever an individual or business ignores tax laws. Fighting tax evasion is the main task of the Economic and Financial Military Police, which annually performs fiscal controls to track down and prosecute evaders at national level. Due to limited financial resources, the tax inspector is unable to audit the population entirely. In this article, we propose a model to assist the Italian tax inspector (Guardia di Finanza, G.d.F.) in allocating its budget among different business clusters, via a controller-controlled Stackelberg game. The G.d.F. is seen as the leader, while potential evaders are segmented into classes according to their business sizes, as set by the Italian regulatory framework. Numerical results on the real Italian case for fiscal year 2015 are provided. Insights on the optimal number of controls the inspector will have to perform among different business clusters are discussed and compared to the strategy implemented by the G.d.F.

Rescheduling can help to improve the quality of a schedule with respect to an initially given sequence. In this paper, we consider the possibility of rescheduling jobs arriving for processing at a single machine under the following limitations: (a) jobs can only be moved toward the end of the schedule and not toward the front, and (b) when a job is taken out of the sequence, it is put on a buffer of limited capacity before being reinserted in its new position closer to the end of the sequence. The buffer is organized as a stack with a last-in/first-out policy. As an objective function, we consider the minimization of the weighted number of late jobs. For this NP-hard problem, we first provide two different integer linear programming (ILP) formulations. Furthermore, we develop a branch-and-bound algorithm with a branching rule based on the movement of jobs. Then a new pseudo-polynomial dynamic programming algorithm is presented which utilizes dominance criteria and an efficient handling of states. Our computational experiments with up to 100 jobs show that this algorithm performs remarkably well and can be seen as the current method of choice.

A novel framework is introduced for the supervisory control (SC) of timed discrete event systems, based on Time Petri nets. The method encompasses both logical (markings to reach or avoid) and temporal specifications (arrival and departure times in specific markings). It relies on the construction of a partial forward reachability graph, of the Modified State Class Graph type, and the formulation of integer linear programming problems to establish suitable firing time intervals (FTIs) for the controllable transitions. The SC algorithm provides for each enabled controllable transition the largest FTI that guarantees that the specifications are met, irrespectively of the firing times of the uncontrollable transitions.

In this paper, we amend a multi-criteria methodology known as MURAME, to evaluate the creditworthiness of a large sample of Italian Small and Medium-sized Enterprises, using as input their balance sheet data. This methodology produces results in terms of scoring and of classification into homogeneous rating classes. A distinctive goal of this paper is to consider a preference disaggregation method to endogenously determine some parameters of MURAME, by solving a nonsmooth constrained optimization problem. Because of the complexity of the involved mathematical programming problem, for its solution we use an evolutionary metaheuristic, coupled with a specific efficient initialization. This is combined with an unconstrained reformulation of the problem, which provides a reasonable compromise between the quality of the solution and the computational burden. An extensive numerical experience is reported, comparing an exogenous choice of MURAME parameters with our approach.

In this paper we propose a hybrid metaheuristic based on Particle Swarm Optimization, which we tailor on a portfolio selection problem. To motivate and apply our hybrid metaheuristic, we reformulate the portfolio selection problem as an unconstrained problem, by means of penalty functions in the framework of the exact penalty methods. Our metaheuristic is hybrid as it adaptively updates the penalty parameters of the unconstrained model during the optimization process. In addition, it iteratively refines its solutions to reduce possible infeasibilities. We report also a numerical case study. Our hybrid metaheuristic appears to perform better than the corresponding Particle Swarm Optimization solver with constant penalty parameters. It performs similarly to two corresponding Particle Swarm Optimization solvers with penalty parameters respectively determined by a REVAC-based tuning procedure and an irace-based one, but on average it just needs less than 4% of the computational time requested by the latter procedures.

Structural topology optimization (STO) is usually treated as a constrained minimization problem, which is iteratively addressed by solving the equilibrium equations for the problem under consideration. To reduce the computational effort, several reduced basis approaches that solve the equilibrium equations in a reduced space have been proposed. In this work, we apply functional principal component analysis (FPCA) to generate the reduced basis, and we couple FPCA with a gradient-based optimization method for the first time in the literature. The proposed algorithm has been tested on a large STO problem with 4.8 million degrees of freedom. Results show that the proposed algorithm achieves significant computational time savings with negligible loss of accuracy. Indeed, the density maps obtained with the proposed algorithm capture the larger features of maps obtained without reduced basis, but in significantly lower computational times, and are associated with similar values of the minimized compliance.

Home care (HC) services represent an effective solution to face the health issues related to population aging. However, several scheduling problems arise in HC, and the providers must make several scheduling and routing decisions, e.g., the assignment of caregivers to clients, in order to balance operating costs and client satisfaction. Starting from the analysis of a real HC provider operating in New York City, NY, USA, this article addresses a scheduling problem with chargeable overtime and preference matching and formulates it as an integer programming model. The objective is to minimize a cost function that includes traveling costs, the overtime cost paid by the provider, the preference mismatch, and a penalty related to the continuity of care violation. To solve this problem, we design a matheuristic algorithm that integrates a specific variable neighborhood search with a set covering model. The results demonstrate the applicability and efficiency of our approach to solving real-size instances. Sensitivity analyses are also performed to discuss practical insights. Note to Practitioners —This article provides a decision support tool to HC managers, which appropriately assigns caregivers to clients and makes routing decisions over a long horizon. Chargeable overtimes and preference matching enclosed in this tool are rarely considered in the literature, despite matching is relevant in HC caregiver-to-client assignments and chargeable overtime has potential in tailoring the service level based on the specific client. We formulate the scheduling problem as a mathematical model. Then, we propose a matheuristic algorithm to efficiently solve the problem in real-size instances. The results show the applicability and efficiency of our method. Thus, HC managers can exploit it to efficiently make assignment and routing decisions and to analyze the impact on other operating costs when adjusting any of them.

A well-known property of linear resistive electrical networks is that the current distribution minimizes the total dissipated power. When the circuit includes resistors with nonlinear monotonic characteristic, the current distribution minimizes in general a different functional. We show that, if the nonlinear characteristic is a threshold-like function and the current generator is concentrated in a single point, as in the case of lightning or dielectric discharge, then the current flow is concentrated along a single path, which is a minimum path to the ground with respect to the threshold. We also propose a dynamic model that explains and qualitatively reproduces the lightning transient behavior: initial generation of several plasma branches and subsequent dismissal of all branches but the one reaching the ground first, which is the optimal one.

Background A major predictor of eligibility of subcutaneous implantable cardiac defibrillators (S-ICD) is the T:R ratio. The eligibility cut-off of the T:R ratio incorporates a safety margin to accommodate for fluctuations of ECG signal amplitudes. We introduce a deep learning-based tool that accurately measures the degree of T:R ratio fluctuations and explore its role in S-ICD screening. Methods Patients were fitted with Holters for 24 h to record their S-ICD vectors. Our tool was used to assess the T:R ratio over the duration of the recordings. Multiple T:R ratio cut-off values were applied, identifying patients at high risk of T-wave oversensing (TWO) at each of the proposed values. The purpose of our study is to identify the ratio that recognises patients at high risk of TWO while not inappropriately excluding true S-ICD candidates. Results Thirty-seven patients (age 54.5 + / − 21.3 years, 64.8% male) were recruited. Fourteen patients had heart-failure, 7 hypertrophic cardiomyopathy, 7 had normal hearts, 6 had congenital heart disease, and 3 had prior inappropriate S-ICD shocks due to TWO. 54% of patients passed the screening at a T: R of 1:3. All patients passed the screening at a T: R of 1:1. The only subgroup to wholly pass the screening utilising all the proposed ratios are the participants with normal hearts. Conclusion We propose adopting prolonged screening to select patients eligible for S-ICD with low probability of TWO and inappropriate shocks. The appropriate T:R ratio likely lies between 1:3 and 1:1. Further studies are required to identify the optimal screening thresholds.

Previous analysis suggested the opportunity to consider the preferences of different stakeholders (hospital, patients, doctors and nurses) through the adoption of both patient priority maximisation and workload balance as performance criteria. The aim of this paper is to develop an effective and efficient solution approach for the operating room planning and scheduling capable to take into account the patient priority maximisation and workload balance criteria at the same time. This work is inspired by the need of a deeper understanding of the quality of the solutions obtained when a combination of the two criteria leads the OR planning decisions. Starting from a hierarchical multi-objective optimisation model for the combined master surgical scheduling and surgical cases assignment problems, we develop a class of new multi-neighbourhood local search based matheuristic algorithms, whose main feature is to exploit an ad hoc neighbourhood to generate better solutions in a significant shorter running time. A broad quantitative analysis on new realistic instances proves the effectiveness and the efficiency of the proposed matheuristic algorithms as well as to evaluate the quality of the computed solution from an operating room management perspective.

The main aim of this thesis is to investigate some problems relevant in enumeration and optimization, for which I present new theoretical results. First, I focus on a classical enumeration problem in graph theory with several applications, such as network reliability. Given an undirected graph, the objective is to list all its bonds, i.e., its minimal cuts. I provide two new algorithms, the former having the same time complexity as the state of the art by [Tsukiyama et al., 1980], whereas the latter offers an improvement. Indeed, by refining the branching strategy of [Tsukiyama et al., 1980] and relying on some dynamic data structures by [Holm et al., 2001], it is possible to define an eO(n)-delay algorithm to output each bond of the graph as a bipartition of the n vertices. Disregarding the polylogarithmic factors hidden in the eO notation, this is the first algorithm to list bonds in a time linear in the number of vertices. Then, I move to studying two well-known problems in theoretical computer science, that are checking the duality of two monotone Boolean functions, and computing the dual of a monotone Boolean function. Also these are relevant in many fields, such as linear programming. [Fredman and Khachiyan, 1996] developed the first quasi-polynomial time algorithm to solve the decision problem, thus proving that it is not coNP-complete. However, no polynomial-time algorithm has been discovered yet. Here, by focusing on the symmetry of the two input objects and exploiting full covers introduced by [Boros and Makino, 2009], I define an alternative decomposition approach. This offers a strong bound which, however, in the worst case, is still the same as [Fredman and Khachiyan, 1996]. Anyway, I also show how to adapt it to obtain a polynomial-space algorithm to solve the dualization problem. Finally, as extra content, this thesis contains an appendix about the topic of communicating operations research. By starting from two side projects not related to enumeration, and by comparing some relevant considerations and opinions by researchers and practitioners, I discuss the problem of properly promoting, fostering, and communicating findings in this research area to laypeople.