Search

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.

This paper describes a class of novel initializations in Deterministic Particle Swarm Optimization (DPSO) for approximately solving costly unconstrained global optimization problems. The initializations are based on choosing specific dense initial positions and velocities for particles. These choices tend to induce in some sense orthogonality of particles’ trajectories, in the early iterations, in order to better explore the search space. Our proposal is inspired by both a theoretical analysis on a reformulation of PSO iteration, and by possible limits of the proposals reported in Campana et al. (2010); Campana et al. (2013). We explicitly show that, in comparison with other initializations from the literature, our initializations tend to scatter PSO particles, at least in the first iterations. The latter goal is obtained by imposing that the initial choice of particles’ position/velocity satisfies specific conjugacy conditions, with respect to a matrix depending on the parameters of PSO. In particular, by an appropriate condition on particles’ velocities, our initializations also resemble and partially extend a general paradigm in the literature of exact methods for derivative-free optimization. Moreover, we propose dense initializations for DPSO, so that the final approximate global solution obtained is possibly not too sparse, which might cause troubles in some applications. Numerical results, on both Portfolio Selection and Computational Fluid Dynamics problems, validate our theory and prove the effectiveness of our proposal, which applies also in case different neighborhood topologies are adopted in DPSO.

The Automatic Scene Detection Problem (ASDP) is a combinatorial optimization problem that arises in the context of video processing and that has a central role in the management, storing and content retrieval of videos. The problem consists of partitioning the shots of a given video into scenes by optimizing a measure related to the similarity between the given shots. In this article, we build up upon the results from the literature on the ASDP in order to design a new approximate solution algorithm able to outperform the current state-of-the-art both in terms of speed and quality of the solution.

We present a market model of a liberalized aviation market with independent decision makers. The model consists of a hierarchical, trilevel optimization problem where perfectly competitive budget-constrained airports decide (in the first level) on optimal runway capacity extensions and airport charges by anticipating long-term fleet investment and medium-term aircraft scheduling decisions taken by a set of imperfectly competitive airlines (in the second level). Both airports and airlines anticipate the short-term outcome of a perfectly competitive ticket market (in the third level). We compare our trilevel model to an integrated single-level (benchmark) model in which investments, scheduling, and market-clearing decisions are simultaneously taken by a welfare-maximizing social planner. Using a simple six airports example from the literature, we illustrate the inefficiency of long-run investments in both runway capacity and aircraft fleet which may be observed in aviation markets with imperfectly competitive airlines.

Parameter uncertainty is common to several optimization problems, especially in health care where patients’ conditions and service times are highly uncertain. Moreover, in Home Health Care services, where patients are treated over a long time horizon, their clinical condition may change and result in uncertain but also highly time-correlated service times. To include time-correlated uncertain parameters is a difficult task in robust optimization. It has been only marginally addressed, especially in the health care management literature. In this paper, we address the nurse-to-patient assignment problem in Home Health Care services under three types of continuity of care, focusing on uncertain and time-correlated service times. In the literature, this problem has been tackled with stochastic programming, robust optimization, and heuristics; however, service times at different time periods have been treated as independent so far. We propose a robust assignment model that accounts for the time-dependency of patients’ service times, with either constant or increasing overtime cost, and an approach based on the implementor-adversary framework to solve it. Service times are modeled as stochastic parameters and time-correlation is included by limiting the difference in the service time requested by the same patient in two consecutive time periods. The goals are to minimize the cost of staff overtime and the number of reassignments that impair patients’ continuity of care. Results from a relevant realistic case show that the approach does not always converge, but the robust solutions provided, under suitable parameters for the uncertainty description, always outperform the deterministic ones even without full convergence.

Generation and Transmission Expansion Planning (GTEP) to achieve decarbonisation targets in the power sector requires installing relevant shares of production from Renewable Energy Sources (RES). GTEP optimization models determine expansion plans over a long-term horizon so as to minimize the total investment and operation cost. In the presence of high shares of non-dispatchable RES power plants, operation costs must be evaluated taking into account the different operating conditions due to the intermittency of RES power generations. In this work we consider a GTEP model for a power system based on thermal, solar and wind power generation and we introduce a novel approach to select representative days (RDs), discretized in hours, in order to obtain accurate estimates of the operational costs. The RDs are not connected, in order to get a decomposable problem. A procedure is introduced to assign the ON/OFF status of every thermal unit at the beginning of each RD. Numerical results on a test case of suitable dimension show that the proposed method provides expansion plans very close to those obtained by the complete hourly model, while dramatically reducing computational costs.

This paper is concerned with the generation and transmission expansion planning of large-scale energy systems with high penetration of renewable energy sources. Since expansion plans are usually provided for a long-term planning horizon, the system conditions are generally uncertain at the time the expansion plans are decided. In this work, we focus on the uncertainty of thermal power plants production costs, because of the important role they play in the generation and transmission expansion planning by affecting the merit order of thermal plants and the economic viability of renewable generation. To deal with this long-term uncertainty, we consider different scenarios and we define capacity expansion decisions using a two-stage stochastic programming model that aims at minimizing the sum of investment, decommissioning and fixed costs and the expected value of operational costs. To be computationally tractable most of the existing expansion planning models employ a low level of temporal and technical detail. However, this approach is no more an appropriate approximation for power systems analysis, since it does not allow to accurately study all the challenges related to integrating high shares of intermittent energy sources, underestimating the need for flexible resources and the expected costs. To provide more accurate expansion plans for power systems with large penetration of renewables, in our analysis, we consider a high level of temporal detail and we include unit commitment constraints on a plant-by-plant level into the expansion planning framework. To maintain the problem computationally tractable, we use representative days and we implement a multi-cut Benders decomposition algorithm, decomposing the original problem both by year and by scenario. Results obtained with our methodology in the Italian energy system under a 21-year planning horizon show how the proposed model can offer professional guidance and support in strategic decisions to the different actors involved in electricity transmission and generation.

In this paper, we study the agility of evacuation routes in relation to dynamically changing unpredictable hazardous conditions in smart space networks. Infrastructure safety conditions may unpredictably change through time. Due to unpredictability, evacuees’ safety can get jeopardized at any point of the evacuation route. Thus, it is not sufficient only to find the shortest evacuation routes considering present safety conditions and evacuation flow, but we should also consider other relevant characteristics that make the evacuation routes sufficiently safe through time. With this aim, we propose two new node importance metrics: evacuation betweenness centrality and evacuation centrality, both inspired by betweenness centrality. The first metric represents the fraction of k efficient evacuation routes between all origin–destination pairs different from the given node that pass through that node, while the second represents the importance of the given node for evacuation considering the availability of alternative efficient evacuation paths (routes) from that node towards safe exits. Moreover, given a set of evacuees’ positions and safe exits, we find shortest agile evacuation routes, where by agile route we mean the ability to efficiently and safely reroute from intermediate nodes in case of unpredictable safety drops through maximizing the value of the evacuation centrality of the route’s intermediate nodes. In addition, we propose an algorithm for that problem and discuss its capability to react to the changes in safety circumstances along recommended routes.

Subcutaneous 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 seconds to measure the T:R ratio, determining the patients' eligibility for S-ICD implantation. Due to temporal variations in the T:R ratio, 10 seconds is not long enough 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 behaviour 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.

Within the realm of smart buildings and smart cities,\ud dynamic response management is playing an ever-increasing\ud role thus attracting the attention of scientists from different\ud disciplines. Dynamic demand response management involves a\ud set of operations aiming at decentralizing the control of loads\ud in large and complex power networks. Each single appliance\ud is fully responsive and readjusts its energy demand to the\ud overall network load. A main issue is related to mains frequency\ud oscillations resulting from an unbalance between supply and\ud demand. In a nutshell, this paper contributes to the topic by\ud equipping each signal consumer with strategic insight. In particular,\ud we highlight three main contributions and a few other minor\ud contributions. First, we design a mean-field game for a population\ud of thermostatically controlled loads (TCLs), study the mean-field\ud equilibrium for the deterministic mean-field game and investigate\ud on asymptotic stability for the microscopic dynamics. Second, we\ud extend the analysis and design to uncertain models which involve\ud both stochastic or deterministic disturbances. This leads to robust\ud mean-field equilibrium strategies guaranteeing stochastic and\ud worst-case stability, respectively. Minor contributions involve the\ud use of stochastic control strategies rather than deterministic, and\ud some numerical studies illustrating the efficacy of the proposed\ud strategies.

For a large population of players we consider a collective decision making process with three possible choices: option A or B or no option. The more popular option is more likely to be chosen by uncommitted players and cross-inhibitory signals can be sent to attract players committed to a different option. This model originates in the context of honeybees swarms, and we generalise it to accommodate other applications such as duopolistic competition and opinion dynamics. The first contribution is an evolutionary game model and a corresponding new game dynamics called expected gain pairwise comparison dynamics explaining how the strategic behaviour of the players may lead to deadlocks or consensus. The second contribution is the study of equilibrium points and stability in the case of symmetric or asymmetric cross-inhibitory signals. The third contribution is the extension of the results to the case of structured environment in which the players are modelled via a complex network with heterogeneous connectivity.

The new mobile gates at the inlets of the Venice lagoon and the new previous environmental laws issued in response of the Costa Concordia wreckage in 2012 have forced the Port Authority of Venice to rethink the harbor activities. In this paper, we tackle the Port Scheduling Problem that the Port Authority faces in scheduling both ships’ and tugs’ movements within its canal harbor in this new context. We introduce the problem, explain which data it needs, and provide the description of an original heuristic algorithm for its solution. Finally, we present some practical applications.

This study addresses the Ambulance Location and Dispatching Problem (ALDP), which jointly determines the location of available ambulances and their dispatching policy. The latter takes the form of a dispatching list that defines, for each zone of the covered territory, an ordered list providing a hierarchy of ambulances to be chosen whenever a call arrives. While decisions concerning the ambulance locations are of a tactical nature and often based on static information (i.e. average demand), ambulance dispatching is a real-time decision that must take into consideration the current state of the system (i.e. busy and idle ambulances) when selecting the ambulance to respond to the incoming emergency call. Although only few works have considered these two decisions jointly, they all conclude that the system’s performance can be improved and the fleet management decisions streamlined by doing so. However, one of the challenges of the ALDP lies in the estimation of the ambulance availability, which has been addressed in previous papers by means of queueing approaches. In this paper, we propose a recursive simulation-optimization framework which encompasses a mathematical formulation for the ALDP and a discrete event simulation model that produces both empirical estimations of the ambulance availability and the system’s performance. Extensive numerical experiments on a set of realistic instances show the potential of the proposed approach as an effective tool for dealing with EMS decision-making.

Home health care (HHC) consists of care services provided to patients at their domicile rather than in hospitals or other health facilities. HHC human resources are largely studied in the optimization literature, to improve service quality and efficiency. However, the growth of complex HHC services that include the delivery of devices and disposable materials makes it necessary to include them in the decision-making process together with human resources. In fact, they may represent a high cost item, and their release may affect the scheduling of HHC visits. Unfortunately, as far as our knowledge, devices and materials are not considered together with the technical staff required to support their utilization. In this paper, we address the dimensioning problem for new HHC services that also involve devices and materials, considering the joint dimensioning of human and material resources. We include three categories of staff (nurses, physicians and technicians), a set of devices and a set of materials; also, we assume that the requirements from patients are in terms of frequencies, i.e., the maximum number of days between two consecutive visits, two supplies of a material or two uses of a device. We propose a linear programming model and a matheuristic approach for solving instances of realistic dimension. The model allows determining the number of nurses, physicians, and technicians to be hired, as well as the number of devices to be acquired to meet the demand. As for the matheuristics, we combine a decomposition step and a heuristics inspired by the Local Branching idea. Results show the capability of the approach to solve the problem and provide good dimensioning solutions, which can be actually adopted in real-life problems. Moreover, the matheuristic approach performs well in a variety of instances.

The ability of TCP’s congestion control scheme to adapt the rate of traffic flows and fairly use all the available resources is one of the Internet’s pillars. So far, however, the elasticity of traffic has been disregarded in traffic engineering (TE) methodologies mainly because, only recently, the increase in access capacity has moved the bottlenecks from the access network to the operator network and hungry cloud-based applications have begun to use all the available bandwidth. We propose a new approach to TE with elastic demands which models the interaction between the network operator and the end-to-end congestion control scheme as a Stackelberg game . Given a set of elastic traffic demands only specified by their origin-destination pairs, the network operator chooses a set of routing paths (leader’s problem) which, when coupled with the fair bandwidth allocation that the congestion control scheme would determine for the chosen routing (follower’s problem), maximizes a network utility function. We present bilevel programming formulations for the above TE problem with two widely-adopted bandwidth allocation models, namely, max-min fairness and proportional fairness, and derive corresponding exact and approximate single-level mathematical programming reformulations. After discussing some key properties, we report on computational results obtained for different network topologies and instance sizes. Interestingly, even feasible solutions to our bilevel TE problems with large optimality gaps yield substantially higher network utility values than those obtained by solving a standard single-level TE problem and then fairly reallocating the bandwidth a posteriori .

Crowdsourcing marketplaces have emerged as an effective tool for high-speed, low-cost labeling of massive data sets. Since the labeling accuracy can greatly vary from worker to worker, we are faced with the problem of assigning labeling tasks to workers so as to maximize the accuracy associated with their answers. In this work, we study the problem of assigning workers to tasks under the assumption that workers' reliability could change depending on their workload, as a result of, e.g., fatigue and learning. We offer empirical evidence of the existence of a workload-dependent accuracy variation among workers, and propose solution procedures for our Crowdsourced Labeling Task Assignment Problem, which we validate on both synthetic and real data sets.

The Machine Loading Problem (MLP) refers to the allocation of operative tasks and tools to machines for the production of parts. Since the uncertainty of processing times might affect the quality of the solution, this paper proposes a robust formulation of an MLP, based on the cardinality-constrained approach, to evaluate the optimal solution in the presence of a given number of fluctuations of the actual processing time with respect to the nominal one. The applicability of the model in the practice has been tested on a case study.

In this paper, we study the Periodic Petrol Station Replenishment Problem (PPSRP), an important real problem relative to logistics in the fuel oil distribution. It consists, under suitable assumptions and subject to certain operational constraints, of determining the fuel oil procurement plans of a set of petrol stations and planning the delivering routes of petrol products to the stations along a certain planning horizon. The considered problem belongs to the class of Inventory Routing Problems (IRP), of which it is a particularization. In particular, it draws its concepts from two different classes of distribution problems, the Periodic Vehicle Routing Problem (PVRP) and the Petrol Station Replenishment Problem (PSRP). We provide a mathematical formulation of the problem, and due to the large size of the real instances which in general an oil company has to deal with we heuristically solve it. We propose different heuristic strategies based on a common partitioning-then-routing paradigm, and in order to assess their performances we test them on a set of scenarios coming from Italian fuel oil distribution real cases and compare the results with those obtained by using other known heuristic approaches.

This work explores a Principal Component Analysis (PCA) in combination with two post-processing techniques for the prediction of wind power produced over Sicily, and of solar irradiance measured by Oklahoma Mesonet measurements’ network. For wind power, the study is conducted over a 2-year long period, with hourly data of the aggregated wind power output of the Sicily island. The 0–72 h wind predictions are generated with the limited-area Regional Atmospheric Modeling System (RAMS), with boundary conditions provided by the European Centre for Medium-Range Weather Forecasts (ECMWF) deterministic forecast. For solar irradiance, we consider daily data of the aggregated solar radiation energy output (based on the Kaggle competition dataset) over an 8-year long period. Numerical Weather Prediction data for the contest come from the National Oceanic & Atmospheric Administration – Earth System Research Laboratory (NOAA/ESRL) Global Ensemble Forecast System (GEFS) Reforecast Version 2. The PCA is applied to reduce the datasets dimension. A Neural Network (NN) and an Analog Ensemble (AnEn) post-processing are then applied on the PCA output to obtain the final forecasts. The study shows that combining PCA with these post-processing techniques leads to better results when compared to the implementation without the PCA reduction.

In event-related potentials based brain–computer interfaces, the responses evoked by a well defined stimuli sequence are usually averaged to overcome the limitations caused by the intrinsic poor EEG signal-to-noise ratio. This, however, implies that the time necessary to detect the brain signals increases and then that the communication rate can be dramatically reduced. A common approach is then at first to estimate an optimal fixed number of responses to be averaged on a calibration data set and then to use this number on the online/testing dataset. In contrast to this strategy, several early stopping methods have been successfully proposed, aiming at dynamically stopping the stimulation sequence when a certain condition is met. We propose an efficient and easy to implement early stopping method that outperforms the ones proposed in the literature, showing its effectiveness on several publicly available datasets recorded from either healthy subjects or amyotrophic lateral sclerosis patients.

We propose three strategies by which a professor of a university course can assign final letter grades taking into account the natural uncertainty in students’ individual assignment and final numerical grades. The first strategy formalizes a common technique that identifies large gaps in the final numerical grades. For the second and third strategies, we introduce the notion of a borderline student, that is, a student who is close to, but below, the breakpoint for the next highest letter grade. Using mixed-integer linear programming and a tailor-made branch-and-bound algorithm, we choose the letter-grade breakpoints to minimize the number of borderline students. In particular, the second strategy treats the uncertainty implicitly and minimizes the number of borderline students, while the third strategy uses a robust-optimization approach to minimize the maximum number of borderline students that could occur based on an explicit uncertainty set. We compare the three strategies on realistic instances and identify overall trends as well as some interesting exceptions. While no strategy appears best in all cases, each can be computed in a reasonable amount of time for a moderately sized course. Moreover, they collectively provide the professor important insight into how uncertainty affects the assignment of final letter grades.

Flood damage assessments are often based on stage-damage curve (SDC) models that estimate economic damage as a function of flood characteristics (typically flood depths) and land use. SDCs are developed through a site-specific analysis, but are rarely adjusted to economic circumstances in areas to which they are applied. In Italy, assessments confide in SDC models developed elsewhere, even if empirical damage reports are collected after every major flood event. In this paper, we have tested, adapted and extended an up-to-date SDC model using flood records from Northern Italy. The model calibration is underpinned by empirical data from compensation records. Our analysis takes into account both damage to physical assets and losses due to foregone production, the latter being measured amidst the spatially distributed gross added value.

International audience; Different approaches have been proposed in the literature to handle uncertain parameters in health care optimisation problems. Among them, the cardinality-constrained approach to robust optimisation seems suitable for handling several of these problems because it allows a trade-off between the level of robustness and the cost of the solution, and an easy implementation that can be understood by clinicians and planners without any background in operations research. Thus far, however, cardinality-constrained approach has rarely been applied to health care. We recently applied the cardinality-constrained approach to two relevant health care management problems, namely, the operating room planning problem and the nurse-to-patient assignment problem in home care services. In this communication, we briefly describe our experience and focus on general considerations, advantages, and remarks that can help operations researchers in evaluating the approach for other applications in health care management.

Blood is fundamental in several care treatments and surgeries, and plays a crucial role in the health care system. It is a limited resource, as it can be produced only by donors and its shelf life is short; thus, the blood donation (BD) system aims at providing adequate supply of blood units to transfusion centers and hospitals. An effective collection of blood units from donors is fundamental for adequately feeding the entire BD system and optimizing blood usage. However, despite its relevance, donation scheduling is only marginally addressed in the literature. In this paper we consider the Blood Donation Appointment Scheduling (BDAS) problem, aiming at balancing the production of the different blood types among days in order to provide a quite constant feeding of blood units to the BD system. We propose a framework for the appointment reservation that accounts for both booked donors and donors arriving without a reservation. It consists of an offline Mixed Integer Linear Programming (MILP) model for preallocating time slots to blood types, and an online prioritization policy to assign a preallocated slot when the donor calls to make the reservation. © 2017 Elsevier B.V.

This paper presents two applications of Optimal Power Flow analysis for active and reactive power redispatch in medium-voltage distribution networks and shows how this tool can be used to efficiently manage the selection and operation of network resources as well as the definition of a market interface with the transmission network. The description of the frameworks is complemented by the analysis of a case study for the optimal selection and operation of available devices.

Emergency Medical Services (EMS) are responsible of providing medical assistance to any person who requires it in case of emergency, with the main goal of reducing the response time. To do so, several management strategies have been proposed, e.g., districting and preassigned dispatching lists. However, districts are often a priori defined at the strategical or tactical level, without considering the dynamics of service provisioning in detail. This may create problems at the operational level, e.g., the need to send ambulances out of their district to compensate local criticalities and keep a good service quality. To overcome this problem, we propose a data-driven districting that minimizes out-of-district assignments while compacting the districts and balancing their workloads. The approach consists of an iterative matheuristic in which, at each iteration, we first solve the operational problem (location and allocation of ambulances) for a given districting, and then we redistrict based on the operational solution. To validate our proposal, we apply the approach considering realistic data from the city of Montreal, Canada, working on a small region with 30 demand zones extracted from the entire city. Results show that the approach generates balanced districts in which the ambulances satisfy the emergency calls within a low response time. Results also suggest that the increment of the response time to keep the workloads balanced is limited.

E-commerce is a sector in continual growth in all countries and, in particular, the increase in B2C (Business to Consumer) e-commerce market has important effects on last-mile deliveries in city areas. The delivery of a parcel to a consumer’s address involves not only high costs for both couriers (extended car routes) and consumers (high prices) and also greater environmental pollution. The growing demand for deliveries in urban areas involves increases in traffic and congestion problems and, consequently, environmental issues. In recent years, many studies have focused on alternative measures to reduce the negative aspects and impact of last-mile deliveries. Good practice to rationalize last-mile delivery should involve the use of various systems, such as reception boxes, delivery boxes, controlled access systems, collection points and lockers. This paper compares two alternative options to home delivery. In particular, it makes comparisons between point-to-point and lockers, states the pro and cons of both, and defines the best positions to locate lockers to reduce consumers’ deviations. The proposed method is applied to a real case: the Italian municipality of Dolo (near Venice).

Three stakeholders are involved in health care services: patients, operators and service provider managers. They usually have conflicting needs: patients aim at obtaining good quality of service, operators require fair workloads, and managers try to reduce costs. Moreover, a fourth stakeholder, i.e., the contracting authority, pays for the service and fixes the requirements in terms of costs, quality of service and working conditions, to guarantee that the needs of the three actors are all taken into account and well balanced. Home care services represent a relevant example in which all of the different stakeholder perspectives should be included in the decision process, whereas they have been never compared nor considered together in the literature. We propose a set of mathematical models for the nurse-to-patient assignment problem in home care under continuity of care, inspired to multi-criteria optimization, to investigate the effect of each stakeholder’s goal on the others and their interactions. The three stakeholder perspectives are modeled as alternative objective functions of an integer linear programming model, and a threshold method to include all of them is proposed. The approach is then tested on real-life instances, and both deterministic and uncertain patient demands are considered. For the considered setting, results show that the service provider can achieve good quality of service and fair workloads with limited cost increase. Thus, including the other perspectives in the decision making process and respecting the service authority’s requirements is not as costly as expected.

Support vector machine (SVM) is one of the most important class of machine learning models and algorithms, and has been successfully applied in various fields. Nonlinear optimization plays a crucial role in SVM methodology, both in defining the machine learning models and in designing convergent and efficient algorithms for large-scale training problems. In this paper we present the convex programming problems underlying SVM focusing on supervised binary classification. We analyze the most important and used optimization methods for SVM training problems, and we discuss how the properties of these problems can be incorporated in designing useful algorithms.

International audience; A Global Optimization approach of membrane gas separation processes, based on a general process superstructure including a wide array of possible configurations, and solved by a Nonlinear Programming formulation is presented. The capacity of the proposed approach to provide optimal configurations at minimum separation cost is first validated by comparing the obtained solutions with those of a reference study in the domain. The optimization approach is then applied to the optimization of CO2 capture from blast furnace gas considering multistage processes with up to four membrane stages. The optimal process configuration and main process variables, upstream and downstream pressure and membrane area, are determined for processes with CO2 recoveries of 90%, 95% and 99% and N2 residual contents of 1%, 0.5% and 0.1%. The resulting separation cost is in the range of 29–45 EUR/ton CO2 based on a NETL type cost model. Two stage permeate cascades (enrichers) with retentate recycle are shown to be the optimal configuration for N2 residual contents down to 1% at any recovery and down to 0.5% at 90% recovery. For larger recovery or purity levels, three stage processes offered the lowest separation cost. Four stage processes offered no marked improvement over three stage processes.

In this paper the authors consider the final distribution of fuel oil from a storage depot to a set of petrol stations faced by an oil company, which has to decide the weekly replenishment plan for each station, and determine petrol station visiting sequences (vehicle routes) for each day of the week, assuming a fleet of homogeneous vehicles (tankers). The aim is to minimize the total distance travelled by tankers during the week, while loading tankers possibly near to their capacity in order to maximize the resource utilization. The problem is modelled as a generalization of the Periodic Vehicle Routing Problem (PVRP). Due to the large size of the real instances which the company has to deal with, the authors solve the problem heuristically. The authors propose a hybrid genetic algorithm that successfully addresses the problem inspired to a known hybrid genetic algorithm from the literature for the PVRP. However, the proposed algorithm adopts some techniques and features tailored for the particular fuel oil distribution problem, and it is specifically designed to deal with real instances derived from the fuel oil distribution in the European context that are profoundly different from the PVRP instances available from literature. The proposed algorithm is evaluated on a set of real case studies and on a set of randomly generated instances that hold the same characteristics of the former.

We propose a novel way to consider the max-min fairness (MMF) paradigm in traffic engineering. Since MMF appears as a reference model for a fair capacity allocation when the traffic flows are elastic and rates are adapted based on resource availability, we consider it as a requirement due to the way resources are shared by the distributed rate control scheme (like that of the transport protocol), rather than the routing objective. In particular, we define the traffic engineering problem where, given a network topology with link capacities and a set of elastic traffic demands to route, we must select a single path for each demand so as to maximize a network utility function, assuming an MMF bandwidth allocation. We propose a compact mixed-integer linear programming formulation as well as a restricted path formulation. We show with computational experiments that the exact formulation can be solved in a reasonable amount of computing time for medium-size networks and that the restricted path model provides solutions of comparable quality much faster.

In this paper, we propose SOSTA, an integer linear programming model for optimisation of the airport slot allocation process on the European scale. The main contribution of SOSTA is the simultaneous allocation of slots at all Europan airports, while applying the existing regulation and practices. Additionally, SOSTA considers aircraft rotations through the turnaround time constraints, which is another novel contribution. In an experimental analysis based on real data, we show the benefits of the simultaneous allocation, and the flexibility and capabilities of SOSTA, along with the extremely good computational performance.

Emergency Medical Service (EMS) systems aim at providing immediate medical care in case of emergency. A careful planning is a major prerequisite for the success of an EMS system, in particular to reduce the response time to emergency calls. Unfortunately, the demand for emergency services is highly variable and uncertainty should not be neglected while planning the activities. Thus, it is of fundamental importance to predict the number of future emergency calls and their interarrival times to support the decision-making process. In this paper, we propose a Bayesian model to predict the number of emergency calls in future time periods. Calls are described by means of a generalized linear mixed model, whose posterior densities of parameters are obtained through Markov Chain Monte Carlo simulation. Moreover, predictions are given in terms of their posterior predictive probabilities. Results from the application to a relevant real case show the applicability of the model in the practice and validate the approach.

This paper addresses convergence and equilibrium properties of game theoretic learning algorithms in robot populations using simple and broadly applicable reward/cost models of cooperation between robotic agents. New models for robot cooperation are proposed by combining regret based learning methods and network evolution models. Results of mean-field game theory are employed in order to show the asymptotic second moment boundedness in the variation of cooperative behaviour. The behaviour of the proposed models are tested in simulation results, which are based on sample networks and a single lane traffic flow case study.

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.

Each company continually has to choose the projects in which to invest, among the numerous proposals submitted by company departments. Just a few projects among those put forward for funding can be actually accepted, due to the unavoidable discrepancy between available money and required investments. Though overall profit maximization could appear as the natural allocation goal, it is to be considered that such an allocation may eventually produce a rather unbalanced distribution of the overall budget, where some departments get most of it and others get a very small slice or no money at all. In this paper, we examine how the search for fairness in budget allocation impacts the overall profit, to assess whether a greater degree of satisfaction among departments can be achieved while pursuing profit maximization at the same time. We adopt a constrained knapsack model and the Herfindahl-Hirschman Index (HHI) as a measure of fairness, and perform a MonteCarlo simulation to measure the extent of profit sacrifice in the quest for fairness. We find that just a small sacrifice in profit is often needed to achieve a balanced distribution of the overall budget.

Emergency Medical Services (EMS) systems aim to provide immediate care in case of emergency. A careful planning is a major prerequisite for the success of an EMS system, in particular to reduce the response time. Unfortunately, the demand for emergency services is highly variable and uncertainty should not be neglected while planning the activities. Several optimization models have been proposed in the literature to deal with EMS planning-related problems, e.g. the Ambulance Location and Dispatching Problem (ALDP). However, most of the models are deterministic and neglect demand uncertainty. In this paper, we formulate and validate a robust counterpart of the ALDP to deal with demand uncertainty, exploiting the cardinality-constrained approach. Numerical experiments inspired by a real case show promising results and prove the practical applicability of the approach.

We consider a liberalized electricity market, divided in zones interconnected by capacitated transmission links, where a large dimensional power producer operates. We introduce a model for determining the optimal bidding strategies of the large dimensional producer, so as to maximize his own market share, while guaranteeing an annual profit target and satisfying technical constraints. The model determines the optimal medium-term resource scheduling and yields the hourly zonal electricity prices, as it includes constraints representing the Market Clearing process. In order to compute the global solution, the complementarity conditions are formulated as mixed integer linear constraints and the revenue terms are expressed by piece-wise linear functions. The model can be used for analyzing the behavior of market prices in electricity markets where a large dimensional producer can exert market power. It can also be used by investors as a simulation tool for evaluating both the impact on the market and the profitability of investment decisions in the zonal electricity market. A case study related to the Italian electricity market is discussed.

In this paper, we propose an approach based on mathematical programming and local search to cope with the truck and trailer vehicle routing problem. The mathematical programming framework models two subproblems that are solved sequentially, that is, the customer-route assignment problem (CAP), with the objective of minimizing the fleet size used to service clients, and the route definition problem, with the objective of minimizing the total tour length given the set of clients assigned to each vehicle. Since the route assignment model can return infeasible solutions, the local search plays the role of possibly retrieving a feasible solution. The mathematical formulations and the local search work iteratively, embedded in a multiple restarting mechanism able to diversify solutions by (i) identifying additional constraints for the CAP formulation to be taken into account during the algorithm progress, (ii) using a tabu like customer-route matrix to avoid assignments already analysed in the previous iterations of the algorithm. Also a lower bound to assess the solution quality is given. Experiments and comparison with competing approaches suggest that the results of the proposed machinery are promising, producing, on average, a smaller total tour lengths on benchmarks.

It is known that the resource‐unconstrained project scheduling problem with generalized precedence constraints (RUPSP) and minimum completion time objective function can be solved in time O(n·m), where n is the number of activities and m is the number of precedence relations. In this article, we propose a new network formulation for RUPSP based on a transformation that maps the original problem into a standardized acyclic network where precedence relationships between each pair of activities are only of the finish‐to‐start type with zero time lags. With this network, we then associate a mathematical program that can be solved in O(m) time by means of dynamic programing. Exploiting the dual formulation of this mathematical program we further prove that the minimum completion time can also be computed, with the same computational complexity O(m), by finding an augmenting path of longest length in the proposed acyclic network by installing unit capacities on arcs. Computational results on benchmarks are presented. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010 © 2010 Wiley Periodicals, Inc.

This paper studies a long-haul freight transportation problem stimulated by a real-life application, whose underlying vehicle routing problem is a multi-objective one, where travel time and route cost are to be minimized together with the maximization of a transportation mean sharing index, related to the capability of the transportation system of generating economy scale solutions. In terms of constraints, besides vehicle capacity and time windows, transportation jobs have to obey additional constraints related to mandatory nodes (e.g., logistic platform nearest to the origin or the destination) and forbidden nodes (e.g., logistic platforms not compatible with the operations required). Based on the network definition, routes can be multimodal. To solve this problem, we propose a heuristic algorithm that can be applied in the tactical and the operational planning phase, and present the results of an extensive experimentation.

The telecommunications world is expecting the take off of broadband services, beyond typical telephone, both mobile and fixed, and IPTV. The expectations on huge growth of data traffic will lead the evolution of the network towards the next generation multi-service network. The cornerstone of future network infrastructure will be the possibility of provide carrier grade performance, for those services that require such features. This means to guarantee the QoS performance and the resilience of a circuit-switched network even in a packet-based scenario. Beyond that, key requirements are the capacity of tailoring the QoS to different services, and flexibility, that is the effective utilization of network resources, as well as the ability to react to changes in the traffic demands. This paper addresses the issue of providing adequate levels of protection to data flows in multi-layer networks composed of MPLS and optical layers and based on the GMPLS paradigm. A new approach is proposed allowing for an efficient use of network resources and providing adequate levels of protection, starting from the high standard required for real-time traffic.

Each living cell needs to solve a resource allocation problem, in which multiple inputs (uptake fluxes) and outputs (secretion fluxes) are the outcome of the stoichiometry of biochemical pathways and the regulation of metabolic enzymes. Quantifying the efficiency with which a cell solves this resource allocation problem constitutes a basic question in “cellular economics.” In this letter, we propose the use of data envelopment analysis (DEA) to define multidimensional yields that can capture the multidimensional nature of cell input–output processes. The DEA, by treating cells as decision-making units, enables one to introduce the concept of efficiency frontier that is both intimately connected to the shadow prices of flux balance analysis and useful to estimate the phenotypic phase space from experimental measurements of fluxes.

We consider a three-tier architecture for mobile and pervasive computing scenarios, consisting of a local tier of mobile nodes, a middle tier (cloudlets) of nearby computing nodes, typically located at the mobile nodes access points but characterized by a limited amount of resources, and a remote tier of distant cloud servers, which have practically infinite resources. This architecture has been proposed to get the benefits of computation offloading from mobile nodes to external servers while limiting the use of distant servers whose higher latency could negatively impact the user experience. For this architecture, we consider a usage scenario where no central authority exists and multiple non-cooperative mobile users share the limited computing resources of a close-by cloudlet and can selfishly decide to send their computations to any of the three tiers. We define a model to capture the users interaction and to investigate the effects of computation offloading on the users' perceived performance. We formulate the problem as a generalized Nash equilibrium problem and show existence of an equilibrium. We present a distributed algorithm for the computation of an equilibrium which is tailored to the problem structure and is based on an in-depth analysis of the underlying equilibrium problem. Through numerical examples, we illustrate its behavior and the characteristics of the achieved equilibria.

Simulation-based design optimization methods integrate computer simulations, design modification tools, and optimization algorithms. In hydrodynamic applications, often objective functions are computationally expensive and noisy, their derivatives are not directly provided, and the existence of local minima cannot be excluded a priori, which motivates the use of deterministic derivative-free global optimization algorithms. The enhancement of two algorithms of this type, DIRECT (DIviding RECTangles) and DPSO (Deterministic Particle Swarm Optimization), is presented based on global/local hybridization with derivative-free line search methods. The hull-form optimization of the DTMB 5415 model is solved for the reduction of the calm-water resistance at Fr = 0.25, using potential flow and RANS solvers. Six and eleven design variables are used respectively, modifying both the hull and the sonar dome. Hybrid algorithms show a faster convergence towards the global minimum than the original global methods and are a viable option for ship hydrodynamic optimization. A significant resistance reduction is achieved both by potential flow and RANS-based optimizations, showing the effectiveness of the optimization procedure.

In this paper we address a problem arising in a manufacturing environment in which the owner of a machining resource, besides its own jobs, must process also jobs belonging to an external party. Due to contract commitments, the jobs of the external party must be processed within a certain due date, that can be considered as a deadline. Moreover, these jobs have a given release date corresponding to their actual availability in the manufacturing system. The external party jobs arrive with an estimate of their durations and the owner of the machining resource, when planning the schedule of its jobs, must take into account possible deviations from the nominal values of the external processing times. It is therefore important to determine a schedule which is robust to any possible changes in the durations of the external jobs. We consider the total completion time objective for the owner of the machining resource. However, due to the uncertainty on the external jobs processing times, we seek for a solution minimizing the maximum absolute deviation from an optimal schedule. We derive some properties of such robust schedules and evaluate the performance two mixed integer linear programming formulations.

We consider a variant of the single item lot sizing problem where the product, when stored, suffers from a proportional loss, and in which the product demand is affected by uncertainty. This setting is particularly relevant in the energy sector, where the demands must be satisfied in a timely manner and storage losses are, often, unavoidable. We propose a two-stage robust optimization approach to tackle the problem with second stage storage variables. We first show that, in the case of uncertain demands, the robust problem can be solved as an instance of the deterministic one. We then address an application of robust lot sizing arising in the context of heat and power cogeneration and show that, even in this case, we can solve the problem as an instance of the deterministic lot sizing problem. Computational experiments are reported and illustrated.

This work addresses a multi agent allocation problem in which multiple departments compete for shares of a company budget. Each department has its own portfolio of projects with given expected profits and costs and selects an optimal subset of its projects consuming its assigned budget share. Besides considering the total profit of the company a central decision maker should also take fairness issues into account. Thus, we introduce an equity criterion based on maximin fairness. The resulting trade-off between total profit and fairness indicators is studied in this contribution. To this purpose a bicriteria ILP model is presented where one of the objectives is the maximization of the overall profit and the other is the maximization of the minimum budget allocated to one of the departments. We perform an experimental analysis showing a nearly perfect linear anticorrelation between profit and fairness index values.