In this work we propose a bi-objective variant of the well-known 0/1 Knapsack Problem, that finds application in cases in which some item pairs may be seen as mutually conflicting. Previous variants considered in this scenario proposed to either avoid all conflicts, or to deal with them by considering the payment of appropriate penalty costs. We propose a different approach where the maximization of the profit and the minimization of the accepted conflicts are considered two different objective functions. We aim at identifying all Pareto-optimal solutions, so that a decision maker may choose a posteriori the optimal trade-off. We propose an exact resolution method based on the epsilon-constraint approach. Computational results on a wide set of instances show that our approach can be used in practice to identify and analyze their Pareto front.

In this work, we propose a novel Biased Random-Key Genetic Algorithm (BRKGA) to solve the Maximum Flow with Minimum Number of Labels (MF-ML) problem, a challenging NP-Complete variant of the classical Maximum Flow problem defined on graphs in which arcs have both capacities and labels assigned. Labels give a qualitative characterization of each connection, in contexts where a solution that is as homogeneous as possible is sought. The MF-ML problem aims to maximize the flow from a source to a sink on a capacitated network while minimizing the number of distinct arc labels used, a modeling framework with applications such as water purification in distribution systems. Our proposed algorithm encodes solutions as random-key vectors, which are decoded into feasible solutions. The BRKGA demonstrates superior performance when compared to a Skewed Variable Neighborhood Search (VNS) approach previously proposed to solve MF-ML. In particular, on the largest considered graphs, BRKGA-MFML outperformed VNS in 55 out of 81 scenarios, with an average improvement per scenario that reaches 7.18%.

A meticulous description of a real network with respect to its heterogeneous physical infrastructure and properties is necessary for network design assessment. Quantifying the costs of making these structures work together effectively, and taking into account any hidden charges they may incur, can lead to improve the quality of service and reduce mandatory maintenance requirements, and mitigate the cost associated with finding a valid solution. For these reasons, we devote our attention to a novel approach to produce a more complete representation of the overall costs on the reload cost net-work. This approach considers both the cost of reloading due to linking structures and their internal charges, which we refer to as the penalized reload cost. We investigate the complexity and approximability of finding an optimal path, walk, tour, and maxi-mum flow problems under penalized reload cost. All these problems turn out to be NP-complete. We prove that, unless P=NP, even if the reload cost matrix is symmetric and satisfies the triangle inequality, the problem of finding a path, tour, and a maxi-mum flow with a minimum penalized reload cost cannot be approximated within any constant alpha < 2 , and finding a walk is not approximable within any factor beta <= 3.

Nowadays, Predictive Maintenance is a mandatory tool to reduce the cost of production in the semiconductor industry. This paper considers as a case study a critical part of the electrochemical deposition system, namely, the four Pins that hold a wafer inside a chamber. The aim of the study is to replace the schedule of replacement of Pins presently based on fixed timing (Preventive Maintenance) with a Hardware/Software system that monitors the conditions of the Pins and signals possible conditions of failure (Predictive Maintenance). The system is composed of optical sensors endowed with an image processing methodology. The prototype built for this study includes one optical camera that simultaneously takes images of the four Pins on a roughly daily basis. Image processing includes a pre-processing phase where images taken by the camera at different times are coregistered and equalized to reduce variations in time due to movements of the system and to different lighting conditions. Then, some indicators are introduced based on statistical arguments that detect outlier conditions of each Pin. Such indicators are pixel-wise to identify small artifacts. Finally, criteria are indicated to distinguish artifacts due to normal operations in the chamber from issues prone to a failure of the Pin. An application (PINapp) with a user friendly interface has been developed that guides industry experts in monitoring the system and alerting in case of potential issues. The system has been validated on a plant at STMicroelctronics in Catania (Italy). The study allowed for understanding the mechanism that gives rise to the rupture of the Pins and to increase the time of replacement of the Pins by a factor at least 2, thus reducing downtime.

This paper considers a Multiple Objective variant of the Critical Disruption Path problem to extend itssuitability in a range of security operations relying on path-based network interdiction, including flight patternoptimisation for surveillance. Given a pair of nodes s and t from the network to be monitored, the problemseeks for loopless s - t paths such that, within the induced subgraph obtained via deletion of the path, thesize of the largest connected component is minimised, the number of connected components is maximised,while concurrently reducing as much as possible the cost of such disruption path. These three objectives arepossibly in conflict with each other, and the scope of this work is to allow for an efficient and insightfulapproximation of the Pareto front, looking for a trade-off between costs and effectiveness to secure the mostconvenient paths for security and surveillance operations. We first introduce and formulate the Multi-ObjectiveCritical Disruption Path Problem (Multi-Objs-CDP) as a mixed integer programming formulation (MO-CDP),then we propose an original evolutionary metaheuristic algorithm hybridising modified-NSGA-II and VNS forfinding an approximation of the Pareto front, as well as a procedure securing the efficient generation of a highquality pool of initial solutions. The experimental performance of the proposed algorithm, as compared witha variety of competing approaches, proves to be fully satisfactory in terms of time efficiency and quality ofthe solutions obtained on a set of medium to large benchmark instances.

Mathematical models have the potential to contribute to design and evaluate the infectivity spreading and growth of human immunodeficiency virus (HIV). Providing a better understanding of the dynamics of HIV infection in vivo and the immune system interactions with the virus can improve the classification of the infected cells and drive to an early diagnosis of the disease and drug evaluations. We analyze a two-dimensional environment HIV model from a new perspective, in terms of a multi-objective optimization problem, by introducing a linear modeling approach and providing numerical evidence for its suitability by introducing a general Instantaneous Control Algorithm.

We introduce a multi-platform portable implementation of the NonLocal Means methodology aimed at noise removal from remotely sensed images. It is particularly suited for hyperspectral sensors for which real-time applications are not possible with only CPU based algorithms. In the last decades computational devices have usually been a compound of cross-vendor sets of specifications (heterogeneous system architecture) that bring together integrated central processing (CPUs) and graphics processor (GPUs) units. However, the lack of standardization resulted in most implementations being too specific to a given architecture, eliminating (or making extremely difficult) code re-usability across different platforms. In order to address this issue, we implement a multi option NonLocal Means algorithm developed using the Open Computing Language (OpenCL) applied to Hyperion hyperspectral images. Experimental results demonstrate the dramatic speed-up reached by the algorithm on GPU with respect to conventional serial algorithms on CPU and portability across different platforms. This makes accurate real time denoising of hyperspectral images feasible.

A critical issue in image restoration is noise removal, whose state-of-art algorithm, NonLocal Means, is highly demanding in terms of computational time. Aim of the present paper is to boost its performance by an efficient algorithm tailored to GPU hardware architectures. This algorithm adapts itself to several variants of the methodologies in terms of different strategies for estimating the involved filtering parameter, type of noise affecting data, multicomponent signals, spatial dimension of the images. Numerical experiments on brain Magnetic Resonance images are provided.

Abstract In this paper the Bi-Objective k-Length-Bounded Critical Disruption Path (BO-kLB-CDP) optimization problem is proposed, aimed at maximizing the interdiction effects provided on a network by removing a simple path connecting a given source and destination whose length does not exceed a certain threshold. The BO-kLB-CDP problem extends the Critical Disruption Path (CDP) problem introduced by Granata et al. in [Granata, D. and Steeger, G. and Rebennack, S., Network interdiction via a Critical Disruption Path: Branch-and-Price algorithms, Computers & Operations Research, Volume 40, Issue 11, November 2013, Pages 2689-2702]. Several real applications of this class of optimization problems arise in the field of security, surveillance, transportation and evacuation operations. In order to overcome some limits of the original {CDP} problem and increase its suitability for practical purposes, first we consider a length limitation for Critical Disruption Paths. Second, we generalize the concept of network interdiction considered in the CDP: beside minimizing the cardinality of the maximal connected component after the removal of the CDP, now we are also interested in maximizing the number of connected components in the residual graph. A Mixed Integer Programming formulation for the BO-kLB-CDP problem is therefore proposed and discussed, presenting the results of a multiple objective analysis performed through a computational experience on a large set of instances.

This work investigates the capability of supervised classification methods in detecting both major tissues and subcortical structures using multispectral brain magnetic resonance images. First, by means of a realistic digital brain phantom, we investigated the classification performance of various Discriminant Analysis methods, K-Nearest Neighbor and Support Vector Machine. Then, using phantom and real data, we quantitatively assessed the benefits of integrating anatomical information in the classification, in the form of voxels coordinates as additional features to the intensities or tissue probabilistic atlases as priors. In addition we tested the effect of spatial correlations between neighbouring voxels and image denoising. For each brain tissue we measured the classification performance in terms of global agreement percentage, false positive and false negative rates and kappa coefficient. The effectiveness of integrating spatial information or a tissue probabilistic atlas has been demonstrated for the aim of accurately classifying brain magnetic resonance images.

This paper presents an innovative approach to maximally disconnect a given network. More specifically, this work introduces the concept of a Critical Disruption Path, a path between a source and a destination vertex whose deletion minimizes the cardinality of the largest remaining connected component. Network interdiction models seek to optimally disrupt network operations. Existing interdiction models disrupt network operations by removing vertices or edges. We introduce the first problem and formulation that optimally fragments a network via interdicting a path. Areas of study in which this work can be applied include transportation and evacuation networks, surveillance and reconnaissance operations, anti-terrorism activities, drug interdiction, and counter human-trafficking operations. In this paper, we first address the complexity associated with the Critical Disruption Path problem, and then provide a Mixed-Integer Linear Programming formulation for finding its optimal solution. Further, we develop a tailored Branch-and-Price algorithm that efficiently solves the Critical Disruption Path problem. We demonstrate the superiority of the developed Branch-and-Price algorithm by comparing the results found via our algorithm with the results found via the monolith formulation. In more than half of the test instances that can be solved by both the monolith and our Branch-and-Price algorithm, we outperform the monolith by two orders of magnitude. (c) 2013 Elsevier Ltd. All rights reserved.

The aim of this chapter is to present an overview of the main results for a well-known optimization problem and an emerging optimization area, as well as introducing a new problem which is related to both of them. The first part of the chapter presents an overview of the main existing results for the classical maximum flow problem. The maximum flow problem is one of the most studied optimization problems in the last decades. Besides its many practical applications, it also arises as a subproblem of several other complex problems (e.g., min cost flow, matching, covering on bipartite graphs). Subsequently, the chapter introduces some problems defined on edge-labeled graphs by reviewing the most relevant results in this field. Edge-labeled graphs are used to model situations where it is crucial to represent qualitative differences (instead of quantitative ones) among different regions of the graph itself. Finally, the maximum flow problem with the minimum number of labels (MF-ML) problem is presented and discussed. The aim is to maximize the network flow as well as the homogeneity of the solution on a capacitated network with logic attributes.

We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into X(G) stable subsets, where X(G) denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes. © Springer Science+Business Media, LLC 2011.