The Deep Learning (DL) paradigm gained remarkable popularity in recent years. DL models are used to tackle increasingly complex problems, making the training process require considerable computational power. The parallel computing capabilities offered by modern GPUs partially fulfill this need, but the high costs related to GPU as a Service solutions in the cloud call for efficient capacity planning and job scheduling algorithms to reduce operational costs via resource sharing. In this work, we jointly address the online capacity planning and job scheduling problems from the perspective of cloud end-users. We present a Mixed Integer Linear Programming (MILP) formulation, and a path relinking-based method aiming at optimizing operational costs by (i) rightsizing Virtual Machine (VM) capacity at each node, (ii) partitioning the set of GPUs among multiple concurrent jobs on the same VM, and (iii) determining a due-date-aware job schedule. An extensive experimental campaign attests the effectiveness of the proposed approach in practical scenarios: costs savings up to 97% are attained compared with first-principle methods based on, e.g., Earliest Deadline First, cost reductions up to 20% are obtained with respect to a previously proposed Hierarchical Method and up to 95% against a dynamic programming-based method from the literature. Scalability analyses show that systems with up to 100 nodes and 450 concurrent jobs can be managed in less than 7 seconds. The validation in a prototype cloud environment shows a deviation below 5% between real and predicted costs.

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.

We study a new multiobjective job scheduling problem on nonidentical machines with applications in the car industry, inspired by the problem proposed by the car manufacturer Renault in the ROADEF 2005 Challenge. Makespan, smoothing costs and setup costs are minimized following a lexicographic order, where smoothing costs are used to balance resource utilization. We first describe a mixed integer linear programming (MILP) formulation and a network interpretation as a variant of the well‐known vehicle routing problem. We then propose and compare several solution methods, ranging from greedy procedures to a tabu search and an adaptive memory algorithm. For small instances (with up to 40 jobs) whose MILP formulation can be solved to optimality, tabu search provides remarkably good solutions. The adaptive memory algorithm, using tabu search as an intensification procedure, turns out to yield the best results for large instances. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 246–261 2016

We address a traffic engineering problem where, given a communication network and a set of origin-destination demands, we have to select a single-path routing for each demand and decide which communication interfaces to switch off or run at partial load so as to minimize the total operational costs. We account for the presence of renewable energy plants at some nodes of the network, as well as feed-in-tariffs, rebates and variable energy prices. We also consider the related problem of deciding where renewable energy sources (photovoltaic modules in this case) have to be installed so as to maximize the profit, while respecting a maximum investment budget constraint. We propose mixed integer optimization models for these two problems and we report results for two different network topologies.

Given n points in ℝd and a maximum allowed tolerance ϵ > 0, the minimum hyperplanes clustering problem consists in finding a minimum number of hyperplanes such that the Euclidean distance between each point and the nearest hyperplane is at most ϵ. We present a column generation approach for this problem based on a mixed integer nonlinear formulation in which the master is a set covering problem and the pricing subproblem is a mixed integer program with a nonconvex normalization constraint. We propose different ways of generating the initial pool of columns and investigate their impact on the overall algorithm. Since the pricing subproblem is substantially complicated by the ℓ2-norm constraint, we consider approximate pricing subproblems involving different norms. Some strategies for refining the solution and speeding-up the overall method are also discussed. The performance of our column generation algorithm is assessed on realistic randomly generated instances as well as on real-world instances.

We consider surveillance applications through wireless sensor networks (WSNs) where the areas to be monitored are fully accessible and the WSN topology can be planned a priori to maximize application efficiency. We propose an optimization framework for selecting the positions of wireless sensors to detect mobile targets traversing a given area. By leveraging the concept of path exposure as a measure of detection quality, we propose two problem versions: the minimization of the sensors installation cost while guaranteeing a minimum exposure, and the maximization of the exposure of the least-exposed path subject to a budget on the sensors installation cost. We present compact mixed-integer linear programming formulations for these problems that can be solved to optimality for reasonable-sized network instances. Moreover, we develop Tabu Search heuristics that are able to provide near-optimal solutions of the same instances in short computing time and also tackle large size instances. The basic versions are extended to account for constraints on the wireless connectivity as well as heterogeneous devices and nonuniform sensing. Finally, we analyze an enhanced exposure definition based on mobile target detection probability.

Internet energy consumption is rapidly becoming an issue due to the exponential traffic growth and the rapid expansion of communication infrastructures worldwide. In this paper we propose an off-line IP traffic engineering approach that allows to adapt the network energy consumption to different daily traffic scenarios (e.g., night, morning), by switching off and on (putting in sleeping mode and waking up) communication interfaces (links) and entire routers. We focus on routing domains where OSPF (Open Shortest Path First) protocol is adopted and we aim at optimizing energy consumption and network congestion by efficiently configuring the OSPF link weights. We present two heuristics, the Greedy Algorithm for Energy Saving (GA-ES) and the Two-stage Algorithm for Energy Saving (TA-ES). The computational results for three real network topologies show that it is possible to switch off up to 80% of the core nodes during low traffic periods (night hours), while moderately increasing the network congestion.

Abstract The concept of reload cost, that is of a cost incurred when two consecutive arcs along a path are of different types, naturally arises in a variety of applications related to transportation, telecommunication, and energy networks. Previous work on reload costs is devoted to the problem of finding a spanning tree of minimum reload cost diameter (with no arc costs) or of minimum reload cost. In this article, we investigate the complexity and approximability of the problems of finding optimum paths, tours, and flows under a general cost model including reload costs as well as regular arc costs. Some of these problems, such as shortest paths and minimum cost flows, turn out to be polynomially solvable while others, such as minimum shortest path tree and minimum unsplittable multicommodity flows, are NP ‐hard to approximate within any polynomial‐time computable function. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(3), 254–260 2011

In this paper we define a mathematical notion of ectropy for classifying diversity measures in terms of the extent to which they tend to penalize point collocation, we investigate the advantages and disadvantages of several known measures and we propose some novel ones. In particular, we introduce a measure based on Euclidean minimum spanning trees, a class of power mean based measures and three measures based on discrepancy from uniform distribution. All considered measures are tested and compared on a large set of random and structured populations. Special attention is also devoted to the complexity of computing the measures. The measure based on Euclidean minimum spanning trees turns out to be the most promising one in terms of the tradeoff between the computational complexity and the ectropic behavior.

We consider surveillance applications through wireless sensor networks (WSNs) with fully accessible areas to be monitored. In this context, the WSN topology can be planned a priori to maximize application efficiency. We propose an optimization framework for selecting the positions of wireless sensors to detect mobile targets traversing a given area. By leveraging the concept of exposure as a measure of coverage quality, we propose two problem versions: the minimization of the sensors installation cost while guaranteeing a minimum exposure, and the maximization of the exposure of the least exposed path subject to a budget on the sensors installation cost. We present compact mixed integer-linear programming formulations for these problems that can be solved to optimality for reasonable-sized network instances. Moreover, we develop a heuristic that is able to provide near-optimal solutions of the same instances in short computing time and also to tackle large size instances.

Abstract We investigate a network design problem under traffic uncertainty that arises when provisioning Virtual Private Networks (VPNs): given a set of terminals that must communicate with one another, and a set of possible traffic matrices, sufficient capacity has to be reserved on the links of the large underlying public network to support all possible traffic matrices while minimizing the total reservation cost. The problem admits several versions depending on the desired topology of the reserved links, and the nature of the traffic data uncertainty. We present compact linear mixed‐integer programming formulations for the problem with the classical hose traffic model and for a less conservative robust variant relying on the traffic statistics that are often available. These flow‐based formulations allow us to solve optimally medium‐to‐large instances with commercial MIP solvers. We also propose a combined branch‐and‐price and cutting‐plane algorithm to tackle larger instances. Computational results obtained for several classes of instances are reported and discussed. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 100–115 2007

Wireless local area networks (WLANs) are spreading all over the planet with impressive speed and market penetration. They will replace traditional indoor wired local networks and allow flexible access outdoor, eventually competing with classical cellular systems (GSM, GPRS, UMTS, etc.) in the provision of wireless services. Although the small systems currently installed are planned using rules of thumb, their rapid spread and size increase requires quantitative methods to determine proper access points (AP) positioning. Previously proposed approaches to the coverage planning neglect the effect of the IEEE802.11 access mechanism, which limits system capacity when access points coverage areas overlap. Here we propose a new modelling approach that directly accounts system capacity and show that the resulting optimization problems of WLAN coverage planning can be seen as extensions of the classical set covering or maximum coverage problems. We present and discuss different formulations based on quadratic and hyperbolic objective functions and report some preliminary results on synthetic instances we generated.

Beam forming techniques of adaptive antenna arrays (smart antennas) allow to reduce the mutual interference of simultaneous transmission in wireless access systems exploiting angular separation of user terminals. At the radio resource management layer the information on the arrival direction of signals can be taken into account by the scheduling algorithm so that transmissions of too close user terminals can be scheduled in different time-slots, while transmissions of users with an enough angular separation can be simultaneous. In other words, time diversity is exploited by the scheduling algorithm when spatial diversity is not sufficient to obtain good quality transmissions. In this paper we propose a novel approach to the problem of packet scheduling with smart antennas using mathematical programming. Based on a simplified system model we formulate two combinatorial optimization problems. In the first problem we have to select a subset of users, which can be simultaneously served in a given time slot so as to maximize the number or the total priority of the users served. An arc-circular model is proposed together with an exact polynomial-time algorithm, which searches for a path of maximum total weight in an appropriate graph. In the second problem users must be partitioned into non-interfering subsets so as to minimize the number of time slots needed to transmit all the given packets. For both problems heuristics have been devised in order to obtain approximate solutions in the short time available for packet scheduling in real systems.

The problem of planning third generation UMTS networks with a W-CDMA radio interface in investigated. In previous work, we have proposed discrete optimization models and algorithms for supporting the decisions on where to locate base stations in which antenna configuration to select considering quality constraints for the uplink (mobile to base station) direction. The signal-to-interference ratio (SIR) is considered as quality measure and we aim at a trade-off between maximizing coverage and minimizing installation costs. In this paper we present two mathematical programming models for locating directive base stations considering downlink (base station to mobile) direction and assuming a power-based as well or a SIR-based power control mechanism. The downlink direction is expected to be particularly relevant in the presence of asymmetrical traffic deriving, for instance, from data service. A randomized greedy procedure as well as a Tabu search algorithm is adapted to find good approximate solution of the resulting NP-hard downlink BS location problem. Experimental results obtained for realistic instances with voice as well as data traffic are reported and they are compared with those provided by the uplink models and algorithms.

Classical coverage models, adopted for second-generation cellular systems, are not suited for planning Universal Mobile Telecommunication System (UMTS) base station (BS) location because they are only based on signal predictions and do not consider the traffic distribution, the signal quality requirements, and the power control (PC) mechanism. We propose discrete optimization models and algorithms aimed at supporting the decisions in the process of planning where to locate new BSs. These models consider the signal-to-interference ratio as quality measure and capture at different levels of detail the signal quality requirements and the specific PC mechanism of the wideband CDMA air interface. Given that these UMTS BS location models are nonpolynomial (NP)-hard, we propose two randomized greedy procedures and a tabu search algorithm for the uplink (mobile to BS) direction which is the most stringent one from the traffic point of view in the presence of balanced connections such as voice calls. The different models, which take into account installation costs, signal quality and traffic coverage, and the corresponding algorithms, are compared on families of small to large-size instances generated by using classical propagation models.

Due to the W-CDMA radio interface, the area covered by a set of UMTS base stations depends on the signal quality requirements, the power control mechanism as well as on the traffic distribution. In previous work we have proposed discrete optimization models and algorithms for locating base stations in UMTS networks. In this paper we address the general problem of optimizing base station locations as well as their configurations, such as antenna height, tilt, and sector orientation. The proposed model, which can also be used to only optimize the base station configurations, accounts for the power control mechanism typical of W-CDMA and considers the signal-to-interference ratio (SIR) as quality measure. To find good approximate solutions of this NP-hard problem, we develop a Tabu Search algorithm which takes into account traffic coverage and installation costs. Experimental results showing the effect of considering base station configurations in the planning process are reported.

Classical coverage models based on signal predictions, adopted for second generation cellular systems, are not suitable for planning the universal mobile telecommunication system (UMTS) base station location since the area actually covered by each base station depends on the traffic distribution, the power control mechanism as well as the signal quality constraints. In a previous paper Amaldi, Capone and Malucelli (see. Proceedings of IEEE VTC Spring 2001, 2001) presented a discrete optimization model for the UMTS base station location problem. In this paper we propose enhanced models which consider the signal-to-interference ratio (SIR) as quality measure and capture at different levels of detail the specific power control mechanism of the CDMA air interface. Moreover, we propose a tabu search algorithm for the uplink (mobile to base station) direction. The different models and algorithms are compared on realistic instances generated using classical propagation models.

We investigate the computational complexity of two closely related classes of combinatorial optimization problems for linear systems which arise in various fields such as machine learning, operations research and pattern recognition. In the first class (Min ULR) one wishes, given a possibly infeasible system of linear relations, to find a solution that violates as few relations as possible while satisfying all the others. In the second class (Min RVLS) the linear system is supposed to be feasible and one looks for a solution with as few nonzero variables as possible. For both Min ULR and Min RVLS the four basic types of relational operators =, ⩾, > and ≠ are considered. While Min RVLS with equations was mentioned to be NP-hard in (Garey and Johnson, 1979), we established in (Amaldi; 1992; Amaldi and Kann, 1995) that min ULR with equalities and inequalities are NP-hard even when restricted to homogeneous systems with bipolar coefficients. The latter problems have been shown hard to approximate in (Arora et al., 1993). In this paper we determine strong bounds on the approximability of various variants of Min RVLS and min ULR, including constrained ones where the variables are restricted to take binary values or where some relations are mandatory while others are optional. The various NP-hard versions turn out to have different approximability properties depending on the type of relations and the additional constraints, but none of them can be approximated within any constant factor, unless P = NP. Particular attention is devoted to two interesting special cases that occur in discriminant analysis and machine learning. In particular, we disprove a conjecture of van Horn and Martinez (1992) regarding the existence of a polynomial-time algorithm to design linear classifiers (or perceptrons) that involve a close-to-minimum number of features.

We propose two algorithms for constructing and training compact feedforward networks of linear threshold units. The SHIFT procedure constructs networks with a single hidden layer while the PTI constructs multilayered networks. The resulting networks are guaranteed to perform any given task with binary or real-valued inputs. The various experimental results reported for tasks with binary and real-valued inputs indicate that our methods compare favorably with alternative procedures deriving from similar strategies, both in terms of size of the resulting networks and of their generalization properties.