Inspired by prior work by Tian and by Cao and Xu, this paper presents an efficient computer-aided framework to characterize the fundamental limits of coded caching systems under the constraint of linear coding. The proposed framework considers non-Shannon-type inequalities which are valid for representable polymatroids (and hence for linear codes), and leverages symmetric structure and problem-specific constraints of coded caching to reduce the complexity of the linear program. The derived converse bounds are tighter compared to previous known analytic methods, and prove the optimality of some achievable memory-load tradeoff points under the constraint of linear coding placement and delivery. These results seem to indicate that small, structured demand subsets combined with minimal common information constructions may be sufficient to characterize optimal tradeoffs under linear coding.

The Electric Vehicle Shortest Path Problem (EVSPP) aims at finding the shortest path for an electric vehicle (EV) from a given origin to a given destination. During long trips, the limited autonomy of the EV may imply several stops for recharging its battery. We consider combining such stops with visiting points of interest near charging stations (CSs). Specifically, we address a version of the EVSPP in which the charging decisions are harmonized with the driver’s preferences. The goal is to maximize the total gained score (assigned by the driver to the CSs), while respecting the time windows and the EV autonomy constraints. We define the problem as a MILP and develop an A* search heuristic to solve it.We evaluate the method by means of extensive computational experiments on realistic instances.

Information-Centric Networking (ICN) has recently gained momentum as a promising paradigm for the next-generation Internet architecture. The first prototypes for ICN-capable routers have already been developed, and network operators will soon have the opportunity to experience the advantages introduced by this technology. However, to migrate the devices to this novel architecture, non-negligible investments should be made. Therefore, it is of utter importance to provide clear quantitative insights of the expected economic benefits that operators will experience by switching to the ICN paradigm. For these reasons, in this paper we tackle the content-aware network-planning problem, and we formulate a novel optimization model to study the migration to an ICN, in a budget-constrained scenario. Our formulation takes into account 1) traffic routing and 2) content caching. We further complement our contribution by designing a Randomized Rounding heuristic that scales up to realistic topologies composed of hundreds of nodes.

We consider two approaches for solving the classical minimum vertex coloring problem—that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors—namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but suffers from a lack of effective bounding methods. On the contrary, column generation provides tight lower bounds by solving the fractional vertex coloring problem exploited in a branch-and-price algorithm, as already proposed in the literature. The column generation approach is here enhanced by using constraint programming to solve the pricing subproblem and to compute heuristic solutions. Moreover, new techniques are introduced to improve the performance of the column generation approach in solving both the linear relaxation and the integer problem. We report extensive computational results applied to the benchmark instances: we are able to prove optimality of 11 new instances and to improve the best-known lower bounds on 17 other instances. Moreover, we extend the solution approaches to a generalization of the problem known as the minimum vertex graph multicoloring problem, where a given number of colors has to be assigned to each vertex.

Abstract This article presents a column generation approach to a resource allocation problem arising in managing Wireless Mesh Networks. The problem consists in routing the given demands over the network and to allocate time resource to pairs of nodes. Half‐duplex constraints are taken into account together with the aggregate interference due to simultaneous transmissions, which affects the signal quality. Different problems are considered, according to the assumptions on the transmission power and rate. The resource allocation problem can be formulated as a Mixed Integer Linear Programming (MILP) problem and dealt with a column generation‐based approach. The pricing problem, due to signal quality constraints, turns out to be computationally demanding. To tackle these difficulties, besides a classical mathematical programming approach, we have applied a hybrid column generation approach where the pricing subproblem is solved using Constraint Programming. Numerical results show that the two methods are comparable. The results of the column generation are then used to solve heuristically the problem. The obtained results provide very small gaps (between lower bounds and Heuristic solutions) for two of the three considered problems and reasonable gaps for the third problem. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract Although there is an extensive literature dealing with network design, little attention has been devoted to networks with complicated node costs. Although node costs, depending linearly on the total passing flow, can be easily embedded into the more usual framework of networks with link costs, when the node costs are, for instance, a stepwise function of the facilities installed into the nodes, this is no longer possible. This feature seems to be crucial in modern telecommunications networks, but has also applications in other fields, where a limited set of technologies is available with discrete values of capacities and costs. In our specific application, we propose a mathematical programming model that explicitly accounts for node costs that are stepwise with nonlinear increments. Two families of valid inequalities are then introduced, one of which is an extension of those presented in a previous work by Stoer and Dahl for multifacility network models. As the separation problem for these inequalities is difficult, we develop a heuristic separation procedure. We devise a branch‐and‐cut method and test it on a set of real‐world instances found in the network design literature. This new method proves to be efficient when compared to a commercial general purpose MIP algorithm. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 90–99 2007

The demand-adaptive systems studied in this paper attempt to offer demand-responsive services within the framework of traditional scheduled bus transportation: Users call to request service between two given points and, in so doing, induce detours in the vehicle routes; at the same time, though, a given set of compulsory stops is always served according to a predefined schedule, regardless of the current set of active requests. The model developed to select requests and determine the routing of the vehicle yields a difficult formulation but with a special structure that may be used to develop efficient algorithms. In this paper, we develop, test, and compare several solution strategies for the single line-single vehicle problem that belong to two general meta-heuristic classes, memory-enhanced greedy randomized multistart constructive procedures, and tabu search methods. Hybrid meta-heuristics combining the two methods are also analyzed.

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.