Due to the environmental impact of fossil fuels and high variability in their prices, there is rising interest in adopting electric vehicles (EVs) by both individuals and governments. Despite the advances in vehicle efficiency and battery capacity, a key hurdle is the inherent interdependence between EV adoption and charging station deployment–EV adoption (and hence, charging demand) increases with the availability of charging stations (operated by service providers) and vice versa. Thus, effective placement of charging stations plays a key role in EV adoption. In the placement problem, given a set of candidate sites, an optimal subset needs to be selected with respect to the concerns of both (a) the charging station service provider, such as the demand at the candidate sites and the budget for deployment, and (b) the EV user, such as charging station reachability and short waiting times at the station. This work addresses these concerns, making the following three novel contributions: (i) a supervised multi-view learning framework using Canonical Correlation Analysis (CCA) for demand prediction at candidate sites, using multiple datasets such as points of interest information, traffic density, and the historical usage at existing charging stations; (ii) a “mixed-packing-and-covering” optimization framework that models competing concerns of the service provider and EV users, which is also extended to optimize government grant allocation to multiple service providers; (iii) an iterative heuristic to solve these problems by alternately invoking knapsack and set cover algorithms. The performance of the demand prediction model and the placement optimization heuristic are evaluated using real world data. In most cases, and especially when budget is scarce, our heuristic achieves an improvement of 10-20 over a naive heuristic, both in finding feasible solutions and maximizing demand.
The optimization problem considered in this work contains both packing and covering constraints, with integer decision variables. Mixed packing and covering problems have been studied for fractional decision variables @cite_33 @cite_15 , as well as for integer decision variables @cite_17 @cite_25 . However, this work introduces an optimization problem with a knapsack packing constraint and a set covering constraint, which has not been studied earlier.
@cite_15 @cite_25 @cite_33 @cite_17
1806207712 1545232017 2163656645 2241989584
Recent work has shown that the classical framework of solving optimization problems by obtaining a fractional solution to a linear program (LP) and rounding it to an integer solution can be extended to the online setting using primal-dual techniques. The success of this new framework for online optimization can be gauged from the fact that it has led to progress in several longstanding open questions. However, to the best of our knowledge, this framework has previously been applied to LPs containing only packing or only covering constraints, or minor variants of these. We extend this framework in a fundamental way by demonstrating that it can be used to solve mixed packing and covering LPs online, where packing constraints are given offline and covering constraints are received online. The objective is to minimize the maximum multiplicative factor by which any packing constraint is violated, while satisfying the covering constraints. Our results represent the first algorithm that obtains a polylogarithmic competitive ratio for solving mixed LPs online. We then consider two canonical examples of mixed LPs: unrelated machine scheduling with startup costs, and capacity constrained facility location. We use ideas generated from our result for mixed packing and covering to obtain polylogarithmic-competitive algorithms for these problems. We also give lower bounds to show that the competitive ratios of our algorithms are nearly tight. We consider the problem of fair resource allocation for tasks where a resource can be assigned to at most one task, without any fractional allocation. The system is heterogeneous: capacity and cost may vary across resources, and different tasks may have different resource demand. Due to heterogeneity of resources, the cost of allocating a task in isolation, without any other competing task, may differ significantly from its allocation cost when the task is allocated along with other tasks. In this context, we consider the problem of allocating resource to tasks, while ensuring that the cost is distributed fairly across the tasks, namely, the ratio of allocation cost of a task to its isolation cost is minimized over all tasks. We show that this fair resource allocation problem is strongly NP-Hard even when the resources are of unit size by a reduction from 3-partition. Our central results are an LP rounding based algorithm with an approximation ratio of 2+ O(a#x03B5;) for the problem when resources are of unit size, and a near-optimal greedy algorithm for a more restricted version. The above fair allocation problem arises for resource allocation in various context, such as, allocating computing resources for reservations requests from tenants in a data centre, allocating resources to computing tasks in grid computing, or allocating personnel for tasks in service delivery organizations. We describe sequential and parallel algorithms that approximately solve linear programs with no negative coefficients (a.k.a. mixed packing and covering problems).For explicitly given problems, our fastest sequential algorithm returns a solution satisfying all constraints within a 1 factor in 0(md (m) ^2 ) time, where m is the number of constraints and d is the maximum number of constraints any variable appears in.Our parallel algorithm runs in time polylogarithmic in the input size times ^4 and uses a total number of operations comparable to the sequential algorithm.The main contribution is that the algorithms solve mixed packing and covering problems (in contrast to pure packing or pure covering problems, which have only or only inequalities, but not both) and run in time independent of the so-called width of the problem. We consider the Knapsack Covering problem subject to a matroid constraint. In this problem, we are given an universe U of n items where item i has attributes: a cost c(i) and a size s(i). We also have a demand D. We are also given a matroid M = (U, I) on the set U. A feasible solution S to the problem is one such that (i) the cumulative size of the items chosen is at least D, and (ii) the set S is independent in the matroid M (i.e. S is in I). The objective is to minimize the total cost of the items selected, sum_ i in S c(i). Our main result proves a 2-factor approximation for this problem. The problem described above falls in the realm of mixed packing covering problems. We also consider packing extensions of certain other covering problems and prove that in such cases it is not possible to derive any constant factor pproximations.