ABSTRACT In hazardous material transport on road networks, two conflicting objectives must be addressed simultaneously: minimizing risk and minimizing cost. Risk mitigation policies may yield as a secondary outcome uneven flow distribution on the network. This study empowers an existing risk mitigation policy based on gateways (GBP) to improve fairness. According to GBP, each vehicle is obliged to traverse a compulsory node (a gateway) on its minimum cost itinerary from origin to destination. Gateways must be located on a few network nodes and assigned to vehicles to minimize total risk, yielding a bi‐level optimization problem. GBP already proved able to reduce total risk by opening just a few gateways and to a limited detriment of total cost. However, gateways may end up acting as flow concentrators, thus hampering equity. This study aims to bridge the gap between risk mitigation and fairness. To this aim, we generalize the multi‐commodity flow formulation of the problem by imposing a capacity constraint on the nodes, discuss its impact on the model structure, and experimentally investigate whether it is possible to achieve a more equitable risk distribution and how total risk and total cost are affected.

The Network Function Virtualisation (NFV) paradigm has revolutionised the way networks are designed, deployed, operated and managed by leveraging the flexibility, scalability and cost efficiencies of the cloud. The emergence of the Cloud-Edge Continuum allows network services, or parts of them, to be delivered close to the end user, especially when latency and throughput requirements are stringent. However, this perspective also poses several resource orchestration challenges, such as the need to cope with rapid changes in the infrastructure status, network and computing resource shortage, and diverse service requirements. In a previous paper, we demonstrated through simulations that a more flexible matching of network service requests with available resources can be enabled by the concept of multi-flavoured network services, i.e. services whose specifications include a full-fledged version and possibly alternative, less demanding versions (with less stringent resource requirements and/or fewer offered features). Since the VNF chain placement problem is known to be NP-hard, we propose a genetic algorithm-based metaheuristic to efficiently solve this variant of the VNF chain placement problem. Simulation results suggest that our genetic algorithm can achieve a profit improvement over a greedy solution of up to 8% in a 28-node topology and up to 6.6% in a 50-node topology.

In dealing with personnel management in companies, two fundamental planning issues have to be handled: staff rostering and activities assignment. These two problems have historically been treated separately, in a sequential way; however, it is evident how strongly they are tied to each other and that solution quality inevitably drops if this connection is not taken into proper account. For this reason, also taking advantage of the massive recent advances in software and hardware technologies, the integrated task scheduling and personnel rostering problem (TSPR) has been formalized along with suitable algorithmic approaches to tackle both planning stages altogether. In this paper, we describe how the peculiar and complex case of airport ground staff was handled in a scenario defined by real-world data from a large airport in Italy. Specifically, we show that the problem can be cast into a mixed integer linear programming model. We then show that, to make the problem computationally tractable, the introduction within the model of a set of suitable valid inequalities is crucial. Indeed, as opposed to the base model from the literature, the novel, improved formulation allowed to effectively obtain near-optimal solutions in reasonable time even for the considered large-scale and real-world scenario.

Abstract Chronic patients suffering from non-communicable diseases are often enrolled into a diagnostic and therapeutic care program featuring a personalized care plan. Healthcare is mostly provided at the patient’s home, but those examinations and treatments that must be delivered at the hospital have to be explicitly booked. Booking is not trivial due to, on the one hand, the several time constraints that become particularly tight in the case of comorbidity, on the other hand, the limited availability of both staff and equipment at the hospital care units. This suggests that the scheduling of the clinical pathways for enrolled outpatients should be managed in a centralized manner, taking advantage of the fact that demand for services is known well in advance. The aim is to serve as many requests as possible (unattended requests are supplied by contracted private health facilities) in a timely manner, taking patients priority into account. Booking involves setting a date and a time for each selected health service, which is rather complex. In this work, we provide a declarative approach by encoding the problem in Answer Set Programming (ASP). In order to improve the scalability of the ASP approach, we present and compare two heuristic approaches, respectively based on service demand and time decomposition. All approaches are tested on instances of increasing size to assess scalability with respect to time horizon and number of requests.

Abstract In answer set programming (ASP), the user can define declaratively a problem and solve it with efficient solvers; practical applications of ASP are countless and several constraint problems have been successfully solved with ASP. On the other hand, solution time usually grows in a superlinear way (often, exponential) with respect to the size of the instance, which is impractical for large instances. A widely used approach is to split the optimization problem into subproblems (SPs) that are solved in sequence, some committing to the values assigned by others, and reconstructing a valid assignment for the whole problem by juxtaposing the solutions of the single SPs. On the one hand, this approach is much faster due to the superlinear behavior; on the other hand, it does not provide any guarantee of optimality: committing to the assignment of one SP can rule out the optimal solution from the search space. In other research areas, logic-Based Benders decomposition (LBBD) proved effective; in LBBD, the problem is decomposed into a master problem (MP) and one or several SPs. The solution of the MP is passed to the SPs that can possibly fail. In case of failure, a no-good is returned to the MP that is solved again with the addition of the new constraint. The solution process is iterated until a valid solution is obtained for all the SPs or the MP is proven infeasible. The obtained solution is provably optimal under very mild conditions. In this paper, we apply for the first time LBBD to ASP, exploiting an application in health care as case study. Experimental results show the effectiveness of the approach. We believe that the availability of LBBD can further increase the practical applicability of ASP technologies.

The adoption of Network Function Virtualization and Software Defined Networking technologies allow network infrastructure operator flexibly orchestrating resources to provide tenants with their own virtual network. However, access to computing and network resource management APIs is typically allowed only within the infrastructure domain and rarely disclosed to tenants for security and performance reasons. This may severely limit tenants capability in coping with demands of application-tailored network services, including Service Function Chaining (SFC). While the literature extensively addressed the challenges of SFC in the infrastructure domain, tenant-side SFC management is quite unexplored yet, although discussed also by a standardization group. This work proposes an SFC platform (called SFCLola) providing tenants with a latency-aware SFC management while minimizing support required from infrastructure operators. The platform encompasses two main levels: an end-to-end chain management level featuring a VNF selection algorithm and a forwarding mechanism that can be programmed and enforced within the tenant network of VMs without requiring access to the switches at the network infrastructure data plane. SFCLola has been implemented as software prototype and experimentally evaluated on a multi-DC infrastructure provided by the 5GINFIRE project.

The adoption of virtualization technologies in networking is promoting a radical innovation in the way network services are managed and delivered. Indeed, some network services may be provisioned to cope with complex and unpredictable traffic demands by dynamically creating a sequence of Virtual Network Functions (VNFs) and steering traffic flows through them. In this context, the optimized deployment of network services, composed of VNFs that may be instantiated in multiple Data Centers (DCs), is one of the most challenging orchestration target. VNF placement is the problem of choosing the set of optimal locations for a chain of VNFs according to the service request and the current characteristics of available computing resources and network links. With respect to the state of the art, our original contribution reflects a multi-stakeholder perspective (subscriber, service providers, infrastructure providers) in a multi-DC environment. We thus consider the problem of placing VNFs to maximize primarily the number of accepted requests from a set of incoming requests and secondarily the satisfaction of subscribers’ preferences. Our model also allows to differentiate service requests in priority levels and guarantees that Quality of Service objectives for accepted service requests are fulfilled, including also a requirement on network service instantiation time. We provide an integer linear programming formulation of this problem that leverages a layered auxiliary graph built for each request in a set. Experimental evaluation is described in detail and an assessment of the proposed placement approach is performed along three main directions: (i) service acceptance ratio in online and offline placement, (ii) preferences’ satisfaction, and (iii) scalability expressed in terms of computational time. The performance of the approach is also compared to a greedy heuristic.

The process of manually labeling instances, essential to a supervised classifier, can be expensive and time-consuming. In such a scenario the semisupervised approach, which makes the use of unlabeled patterns when building the decision function, is a more appealing choice. Indeed, large amounts of unlabeled samples often can be easily obtained. Many optimization techniques have been developed in the last decade to include the unlabeled patterns in the support vector machines formulation. Two broad strategies are followed: continuous and combinatorial. The approach presented in this paper belongs to the latter family and is especially suitable when a fair estimation of the proportion of positive and negative samples is available. Our method is very simple and requires a very light parameter selection. Several medium- and large-scale experiments on both artificial and real-world data sets have been carried out proving the effectiveness and the efficiency of the proposed algorithm.

The adoption of the virtualization paradigm in both computing and networking domains portends a landscape of heterogeneous service capabilities and resources pervasively distributed and interconnected and deeply integrated through the 5G network infrastructure. In this service ecosystem, dynamic service demand can be flexibly and elastically accomplished by composing heterogeneous services provisioned over a distributed and virtualized resource infrastructure. Indeed, with the term Virtual Functions we refer to virtual computing as well as network service capabilities (e.g., routers and middlebox functions provided as Virtual Network Functions). In order to cope with the increasingly resource intensive demand, these virtual functions will be deployed in distributed clusters of small-scale datacenters typically located in current exchanges at the network edge and will supplement those deployed in traditional large cloud datacenters. In this work we formulate the problem of composing, computing and networking Virtual Functions to select those nodes along the path that minimizes the overall latency (i.e. network and processing latency) in the above mentioned scenario. The optimization problem is formulated as a Resource Constrained Shortest Path problem on an auxiliary layered graph accordingly defined. The layered structure of the graph ensures that the order of VFs specified in the request is preserved. Additional constraints can be also taken into account in the graph construction phase. Finally, we provide a use case preliminary evaluation of the proposed model.

In this paper, we evaluate the schedulability of traffic with arbitrary end-to-end deadline constraints in Wireless Mesh Networks (WMNs). We formulate the problem as a mixed integer linear optimization problem, and show that, depending on the flow aggregation policy used in the network, the problem can be either convex or non-convex. We optimally solve the problem in both cases, and prove that the schedulability does depend on the aggregation policy. This allows us to derive rules of thumb to identify which policy improves the schedulability with a given traffic. Furthermore, we propose a heuristic solution strategy that allows good suboptimal solutions to the scheduling problem to be computed in relatively small times, comparable to those required for online admission control in relatively large WMNs.

Given a weighted directed network G, we consider the problem of computing k balanced paths from given source nodes to given destination nodes of G, i.e., k paths such that the difference in cost between the longest path and the shortest path is minimized. Although not yet investigated by the OR scientific community, except for some preliminary theoretical results concerning the special case of acyclic networks, balanced path problems arise in several interesting applications, such as in transportation and in telecommunication settings. In this work, the focus is on the computation of node-disjoint balanced paths in the general case, where the input graph G could have any structure. Starting from some algorithmic ideas proposed for acyclic networks, a general framework based on the color-coding method for computing simple paths is first described. Then the general framework is specialized, and a pool of algorithms is designed that includes both an exact approach as well as alternative heuristics. The algorithms have been tested on a large suite of instances generated from some benchmark telecommunication instances. An additional set of instances, generated from some benchmark crew scheduling instances, has been used to get an idea of the behavior of the algorithms in the context of transportation applications. The obtained computational results are very interesting. For the telecommunication instances, in some cases the exact algorithm produced the optimal solution very rapidly; in the remaining cases, some of the proposed heuristics were able to generate high-quality solutions in a very quick time. As for the crew scheduling instances, which are larger and sometimes appear more difficult than the telecommunication ones, a suitable combination of the proposed color-coding issues allowed us to compute the optimal solutions in very short times.

In this paper we investigate link scheduling for Wireless Mesh Networks (WMNs) carrying real-time (i.e., delay-constrained) traffic. We show that the problem of computing a conflict-free link schedule with end-to-end delay constraints can be formulated as a mixed-integer non linear problem that can be optimally solved in reasonable time (i.e., minutes) for relatively large WMNs (up to 20-30 nodes). We use the above result to explore the schedulability region of a WMN with a given routing and input traffic, assessing whether and when aggregating flows which traverse the same path makes a given input flow set schedulable. Furthermore, we devise a heuristic solution strategy, which computes good suboptimal solutions within up to few seconds, thus being amenable for online admission control.

Link scheduling is used in wireless mesh networks (WMNs) to guarantee interference-free transmission on the shared wireless medium in a time division multiple access approach. Several papers in the literature address the problem of link scheduling guaranteeing a minimum throughput to the flows traversing the WMN. However, none of the existing works address the problem of computing a schedule that guarantees that prespecified end-to-end delay constraints are met. In this paper, we make a first step forward in this direction by defining a link scheduling algorithm that works in sinktree WMNs, i.e. those whose traffic is routed towards a common sink (i.e., the Internet gateway). Our iterative algorithm exploits a delay-based admission control procedure, devised through network calculus, which tests the feasibility of a schedule from the point of view of delay guarantees. Preliminary analyses reported in this paper show that the algorithm finds feasible solutions in few iterations.

We consider an extension of the 0–1 multidimensional knapsack problem in which there are greater-than-or-equal-to inequalities, called demand constraints, in addition to the standard less-than-or-equal-to constraints. Moreover, the objective function coefficients are not constrained in sign. This problem is worth considering because it is embedded in models of practical application, it has an intriguing combinatorial structure, and it appears to be a challenging problem for commercial ILP solvers. Our approach is based on a nested tabu-search algorithm in which neighborhoods with different structures are exploited. First, a tabu-search procedure is carried out in which mainly the infeasible region is explored. Once feasibility has been established, a second tabu-search procedure, which analyzes only feasible solutions, is applied. The algorithm has been tested on a wide set of instances. Computational results are discussed.

Given a weighted acyclic network G and two nodes s and t in G, we consider the problem of computing k balanced paths from s to t, that is, k paths such that the difference in cost between the longest and the shortest path is minimized. The problem has several variants. We show that, whereas the general problem is solvable in pseudopolynomial time, both the arc-disjoint and the node-disjoint variants (i.e., the variants where the k paths are required to be arc-disjoint and node-disjoint, respectively) are strongly NP-Hard. We then address some significant special cases of such variants, and propose exact as well as approximate algorithms for their solution. The proposed approaches are also able to solve versions of the problem in which k origin-destination pairs are provided, and a set of k paths linking the origin-destination pairs has to be computed in such a way to minimize the difference in cost between the longest and the shortest path in the set. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 104-111 2005

We study the coarse-grained parallelization of an efficient bundle-based cost-decomposition algorithm for the solution of multicommodity min-cost flow (MMCF) problems. We show that a code exploiting only the natural parallelism inherent in the cost-decomposition approach, i.e., solving the min-cost flow subproblems in parallel, obtains satisfactory efficiencies even with many processors on large, difficult MMCF problems with many commodities. This is exactly the class of instances where the decomposition approach attains its best results in sequential. The parallel code we developed is highly portable and flexible, and it can be used on different machines. We also show how to exploit a common characteristic of current supercomputer facilities, i.e., the side-to-side availability of massively parallel and vector supercomputers, to implement an asymmetric decomposition algorithm where each architecture is used for the tasks for which it is best suited.