323,490 research outputs found
Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
No full textIn 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 righthand 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 4-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 Lovasz'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
Human capital accumulation and migration in a peripheral EU region: the case of Basilicata
No full textWe investigate the challenges that migration flows pose on policymaking aimed at fostering human capital accumulation in peripheral regions. We employ a unique data set generated through a postal survey designed and conducted by the authors. The focus of our analysis is on the micro-level location decisions of a sample of highly educated and skilled individuals residing in Basilicata, an Italian Mezzogiorno region, who have benefited from a locally funded human capital investment policy. Copyright (c) 2007 the author(s).
Discrete optimization methods to fit piecewise affine models to data points
No full textFitting piecewise affine models to data points is a pervasive task in many scientific disciplines. In this work, we address the k-Piecewise Affine Model Fitting with Piecewise Linear Separability problem (k-PAMF-PLS) where, given a set of m points {a1,…,am}?Rn{a1,…,am}?Rn and the corresponding observations {b1,…,bm}?R{b1,…,bm}?R, we have to partition the domain RnRn into k piecewise linearly (or affinely) separable subdomains and to determine an affine submodel (function) for each of them so as to minimize the total linear fitting error w.r.t. the observations bi.To solve k-PAMF-PLS to optimality, we propose a mixed-integer linear programming (MILP) formulation where symmetries are broken by separating shifted column inequalities. For medium-to-large scale instances, we develop a four-step heuristic involving, among others, a point reassignment step based on the identification of critical points and a domain partition step based on multicategory linear classification. Differently from traditional approaches proposed in the literature for similar fitting problems, in both our exact and heuristic methods the domain partitioning and submodel fitting aspects are taken into account simultaneously.Computational experiments on real-world and structured randomly generated instances show that, with our MILP formulation with symmetry breaking constraints, we can solve to proven optimality many small-size instances. Our four-step heuristic turns out to provide close-to-optimal solutions for small-size instances, while allowing to tackle instances of much larger size. The experiments also show that the combined impact of the main features of our heuristic is quite substantial when compared to standard variants not including them. We conclude with an application to the identification of dynamical piecewise affine systems for which we obtain promising results of comparable quality with those achieved with state-of-the-art methods from the literature on benchmark data sets
Correlation analysis of deep learning methods in S-ICD screening
No full textBackground: Machine learning methods are used in the classification of various cardiovascular diseases through ECG data analysis. The concept of varying subcutaneous implantable cardiac defibrillator (S-ICD) eligibility, owing to the dynamicity of ECG signals, has been introduced before. There are practical limitations to acquiring longer durations of ECG signals for S-ICD screening. This study explored the potential use of deep learning methods in S-ICD screening.
Methods: This was a retrospective study. A deep learning tool was used to provide descriptive analysis of the T:R ratios over 24 h recordings of S-ICD vectors. Spearman's rank correlation test was used to compare the results statistically to those of a "gold standard" S-ICD simulator.
Results: A total of 14 patients (mean age: 63.7 +/- 5.2 years, 71.4% male) were recruited and 28 vectors were analyzed. Mean T:R, standard deviation of T:R, and favorable ratio time (FVR)-a new concept introduced in this study-for all vectors combined were 0.21 +/- 0.11, 0.08 +/- 0.04, and 79 +/- 30%, respectively. There were statistically significant strong correlations between the outcomes of our novel tool and the S-ICD simulator (p < .001).
Conclusion: Deep learning methods could provide a practical software solution to analyze data acquired for longer durations than current S-ICD screening practices. This could help select patients better suited for S-ICD therapy as well as guide vector selection in S-ICD eligible patients. Further work is needed before this could be translated into clinical practice
Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
No full textWe 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
Deep learning methods for screening patients' S-ICD implantation eligibility
No full textSubcutaneous Implantable Cardioverter-Defibrillators (S-ICDs) are used for prevention of sudden cardiac death
triggered by ventricular arrhythmias. T Wave Over Sensing (TWOS) is an inherent risk with S-ICDs which can
lead to inappropriate shocks. A major predictor of TWOS is a high T:R ratio (the ratio between the amplitudes of
the T and R waves). Currently, patients' Electrocardiograms (ECGs) are screened over 10 s to measure the T:R
ratio to determine the patients' eligibility for S-ICD implantation. Due to temporal variations in the T:R ratio, 10 s
is not a long enough window to reliably determine the normal values of a patient's T:R ratio. In this paper, we
develop a convolutional neural network (CNN) based model utilising phase space reconstruction matrices to
predict T:R ratios from 10-second ECG segments without explicitly locating the R or T waves, thus avoiding the
issue of TWOS. This tool can be used to automatically screen patients over a much longer period and provide an
in-depth description of the behavior of the T:R ratio over that period. The tool can also enable much more
reliable and descriptive screenings to better assess patients' eligibility for S-ICD implantation
Deep learning-based insights on T:R ratio behaviour during prolonged screening for S-ICD eligibility
No full textBackground
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
- …
