Publications
2022 |
Yang, Lin; Zeynali, Ali; Hajiesmaili, Mohammad H; Sitaraman, Ramesh; Towsley, Don Competitive Algorithms for Online Multidimensional Knapsack Problems Conference Forthcoming ACM Sigmetrics, Forthcoming. @conference{Yang2022Competitive, title = {Competitive Algorithms for Online Multidimensional Knapsack Problems}, author = {Lin Yang and Ali Zeynali and Mohammad H. Hajiesmaili and Ramesh Sitaraman and Don Towsley}, year = {2022}, date = {2022-06-09}, booktitle = {ACM Sigmetrics}, abstract = {In this paper, we study the online multidimensional knapsack problem OMdKP in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and mm-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem and finds several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop two algorithms for OMdKP that use linear and exponential reservation functions to make online admission decisions. Our competitive analysis shows that the linear and exponential algorithms achieve the competitive ratios of $O(\sqrt{\theta\alpha})$ and $O(\log\left(\theta\alpha\right))$, respectively, where \alphaα is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and $\theta$ is the ratio between the maximum and minimum item unit values. We also characterize a lower bound for the competitive ratio of any online algorithm solving OMdKP and show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } In this paper, we study the online multidimensional knapsack problem OMdKP in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and mm-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem and finds several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop two algorithms for OMdKP that use linear and exponential reservation functions to make online admission decisions. Our competitive analysis shows that the linear and exponential algorithms achieve the competitive ratios of $O(sqrt{thetaalpha})$ and $O(logleft(thetaalpharight))$, respectively, where alphaα is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and $theta$ is the ratio between the maximum and minimum item unit values. We also characterize a lower bound for the competitive ratio of any online algorithm solving OMdKP and show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor. |
2021 |
Sun, Bo; Lee, Russell; Hajiesmaili, Mohammad H; Wierman, Adam; Tsang, Danny HK Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems Conference Forthcoming Advances in Neural Information Processing Systems (NeurIPS), Forthcoming. @conference{Sun2021Pareto, title = {Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems}, author = {Bo Sun and Russell Lee and Mohammad H Hajiesmaili and Adam Wierman and Danny HK Tsang }, year = {2021}, date = {2021-12-06}, booktitle = {Advances in Neural Information Processing Systems (NeurIPS)}, abstract = {This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion. |
Yang, Lin; Chen, Yu-Zhen; Pasteris, Stephen; Hajiesmaili, Mohammad H; Lui, John; Towsley, Don Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback Conference Forthcoming Advances in Neural Information Processing Systems (NeurIPS), Forthcoming. @conference{Yang2021Cooperatibe, title = {Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback}, author = {Lin Yang and Yu-Zhen Chen and Stephen Pasteris and Mohammad H Hajiesmaili and John Lui and Don Towsley}, year = {2021}, date = {2021-12-06}, booktitle = {Advances in Neural Information Processing Systems (NeurIPS)}, abstract = {This paper studies a cooperative multi-armed bandit problem with M agents cooperating together to solve the same instance of a K-armed stochastic bandit problem with the goal of maximizing the cumulative reward of agents. The agents are heterogeneous in (i) their limited access to a local subset of arms; and (ii) their decision-making rounds, i.e., agents are asynchronous with different decision-making gaps. The goal is to find the global optimal arm and agents are able to pull any arm, however, they observe the reward only when the selected arm is local. The challenge is a tradeoff for agents between pulling a local arm with the possibility of observing the feedback, or relying on the observations of other agents that might occur at different rates. Naive extensions of traditional algorithms lead to an arbitrarily poor regret as a function of aggregate action frequency of any suboptimal arm located in slow agents. We resolve this issue by proposing a novel two-stage learning algorithm, called the CO-LCB algorithm, whose regret is a function of the aggregate action frequency of agents containing the optimal arm. We also show that the regret of CO-LCB matches the regret lower bound up to a K factor.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } This paper studies a cooperative multi-armed bandit problem with M agents cooperating together to solve the same instance of a K-armed stochastic bandit problem with the goal of maximizing the cumulative reward of agents. The agents are heterogeneous in (i) their limited access to a local subset of arms; and (ii) their decision-making rounds, i.e., agents are asynchronous with different decision-making gaps. The goal is to find the global optimal arm and agents are able to pull any arm, however, they observe the reward only when the selected arm is local. The challenge is a tradeoff for agents between pulling a local arm with the possibility of observing the feedback, or relying on the observations of other agents that might occur at different rates. Naive extensions of traditional algorithms lead to an arbitrarily poor regret as a function of aggregate action frequency of any suboptimal arm located in slow agents. We resolve this issue by proposing a novel two-stage learning algorithm, called the CO-LCB algorithm, whose regret is a function of the aggregate action frequency of agents containing the optimal arm. We also show that the regret of CO-LCB matches the regret lower bound up to a K factor. |
Wang, Lingdong; Hajiesmaili, Mohammad H; Sitaraman, Ramesh FOCAS: Practical Video Super Resolution using Foveated Rendering Conference Forthcoming ACM Multimedia 2021, Forthcoming. @conference{FOCAS2021, title = {FOCAS: Practical Video Super Resolution using Foveated Rendering}, author = {Lingdong Wang and Mohammad H Hajiesmaili and Ramesh Sitaraman}, year = {2021}, date = {2021-11-18}, booktitle = {ACM Multimedia 2021}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } |
Bashir, Noman; Guo, Tian; Hajiesmaili, Mohammad; Irwin, David; Shenoy, Prashant; Sitaraman, Ramesh; Souza, Abel; Wierman, Adam Enabling Sustainable Clouds: The Case for Virtualizing the Energy System Conference Forthcoming ACM SoCC, Forthcoming. @conference{SusCloud2021, title = {Enabling Sustainable Clouds: The Case for Virtualizing the Energy System}, author = {Noman Bashir and Tian Guo and Mohammad Hajiesmaili and David Irwin and Prashant Shenoy and Ramesh Sitaraman and Abel Souza and Adam Wierman }, url = {https://groups.cs.umass.edu/hajiesmaili/2106-08872-2/}, year = {2021}, date = {2021-11-11}, booktitle = {ACM SoCC}, abstract = {Cloud platforms’ growing energy demand and carbon emissions are raising concern about their environmental sustainability. The current approach to enabling sustainable clouds focuses on improving energy-efficiency and purchasing carbon offsets. These approaches have limits: many cloud data centers already operate near peak efficiency, and carbon offsets cannot scale to near zero carbon where there is little carbon left to offset. Instead, enabling sustainable clouds will require applications to adapt to when and where unreliable low-carbon energy is available. Applications cannot do this today because their energy use and carbon emissions are not visible to them, as the energy system provides the rigid abstraction of a continuous, reliable energy supply. This vision paper instead advocates for a “carbon first” approach to cloud design that elevates carbon-efficiency to a first-class metric. To do so, we argue that cloud platforms should virtualize the energy system by exposing visibility into, and software-defined control of, it to applications, enabling them to define their own abstractions for managing energy and carbon emissions based on their own requirements.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } Cloud platforms’ growing energy demand and carbon emissions are raising concern about their environmental sustainability. The current approach to enabling sustainable clouds focuses on improving energy-efficiency and purchasing carbon offsets. These approaches have limits: many cloud data centers already operate near peak efficiency, and carbon offsets cannot scale to near zero carbon where there is little carbon left to offset. Instead, enabling sustainable clouds will require applications to adapt to when and where unreliable low-carbon energy is available. Applications cannot do this today because their energy use and carbon emissions are not visible to them, as the energy system provides the rigid abstraction of a continuous, reliable energy supply. This vision paper instead advocates for a “carbon first” approach to cloud design that elevates carbon-efficiency to a first-class metric. To do so, we argue that cloud platforms should virtualize the energy system by exposing visibility into, and software-defined control of, it to applications, enabling them to define their own abstractions for managing energy and carbon emissions based on their own requirements. |
Lee, Russell; Zhou, Yutao; Yang, Lin; Hajiesmaili, Mohammad; Sitaraman, Ramesh Competitive Bidding Strategies for Online Linear Optimization with Inventory Management Constraints Conference Forthcoming IFIP Performance , Forthcoming. @conference{Competitive2021Lee, title = {Competitive Bidding Strategies for Online Linear Optimization with Inventory Management Constraints}, author = {Russell Lee and Yutao Zhou and Lin Yang and Mohammad Hajiesmaili and Ramesh Sitaraman}, year = {2021}, date = {2021-11-04}, booktitle = {IFIP Performance }, abstract = {This paper develops competitive bidding strategies for an online linear optimization problem with inventory management constraints in both cost minimization and profit maximization settings. In the minimization problem, a decision maker should satisfy its time-varying demand by either purchasing units of an asset from the market or producing them from a local inventory with limited capacity. In the maximization problem, a decision maker has a time-varying supply of an asset that may be sold to the market or stored in the inventory to be sold later. In both settings, the market price is unknown in each timeslot and the decision maker can submit a finite number of bids to buy/sell the asset. Once all bids have been submitted, the market price clears, and the amount bought/sold is determined based on the clearing price and submitted bids. From this setup, the decision maker must minimize/maximize their cost/profit in the market, while also devising a bidding strategy in the face of an unknown clearing price. We propose \dembid and \supbid, two competitive bidding strategies for these online linear optimization problems with inventory management constraints for the minimization and maximization setting respectively. We then analyze the competitive ratios of the proposed algorithms and show that the performance of our algorithms approaches the best possible competitive ratio as the maximum number of bids increases. As a case study, we use energy data traces from Akamai data centers, renewable outputs from NREL, and energy prices NYISO to show the effectiveness of our bidding strategies in the context of energy storage management for a large energy customer participating in a real-time electricity market.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } This paper develops competitive bidding strategies for an online linear optimization problem with inventory management constraints in both cost minimization and profit maximization settings. In the minimization problem, a decision maker should satisfy its time-varying demand by either purchasing units of an asset from the market or producing them from a local inventory with limited capacity. In the maximization problem, a decision maker has a time-varying supply of an asset that may be sold to the market or stored in the inventory to be sold later. In both settings, the market price is unknown in each timeslot and the decision maker can submit a finite number of bids to buy/sell the asset. Once all bids have been submitted, the market price clears, and the amount bought/sold is determined based on the clearing price and submitted bids. From this setup, the decision maker must minimize/maximize their cost/profit in the market, while also devising a bidding strategy in the face of an unknown clearing price. We propose dembid and supbid, two competitive bidding strategies for these online linear optimization problems with inventory management constraints for the minimization and maximization setting respectively. We then analyze the competitive ratios of the proposed algorithms and show that the performance of our algorithms approaches the best possible competitive ratio as the maximum number of bids increases. As a case study, we use energy data traces from Akamai data centers, renewable outputs from NREL, and energy prices NYISO to show the effectiveness of our bidding strategies in the context of energy storage management for a large energy customer participating in a real-time electricity market. |
Lee, Russell; Maghakian, Jessica; Hajiesmaili, Mohammad H; and Ramesh Sitaraman, Jian Li; Liu, Zhenhua Online Peak-Aware Energy Scheduling with Untrusted Advice Conference Proceedings of the Twelfth ACM International Conference on Future Energy Systems (eEnergy), 2021, (Best paper runner-up). @conference{lee2021Online, title = {Online Peak-Aware Energy Scheduling with Untrusted Advice}, author = {Russell Lee and Jessica Maghakian and Mohammad H. Hajiesmaili and Jian Li and Ramesh Sitaraman and Zhenhua Liu}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/06/eenergy21-final70-1.pdf}, year = {2021}, date = {2021-06-24}, booktitle = {Proceedings of the Twelfth ACM International Conference on Future Energy Systems (eEnergy)}, abstract = {This paper studies the online energy scheduling problem in a hybrid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the proposed algorithms using two performance metrics: textit{robustness} that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and textit{consistency} for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimality of the proposed algorithms. Our results show that the proposed deterministic algorithm is Pareto-optimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Pareto-optimal deterministic algorithm. Our large-scale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms outperform algorithms optimized for worst-case and fully data-driven algorithms.}, note = {Best paper runner-up}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper studies the online energy scheduling problem in a hybrid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the proposed algorithms using two performance metrics: textit{robustness} that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and textit{consistency} for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimality of the proposed algorithms. Our results show that the proposed deterministic algorithm is Pareto-optimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Pareto-optimal deterministic algorithm. Our large-scale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms outperform algorithms optimized for worst-case and fully data-driven algorithms. |
Sun, Bo; Zeynali, Ali; Li, Tongxin; Hajiesmaili, Mohammad; Wierman, Adam; Tsang, Danny HK Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging Journal Article ACM on Measurement and Analysis of Computing Systems (POMACS), 4 (3), 2021, (Also in ACM Sigmetrics 2021). @article{Competitive2021Sun, title = {Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging}, author = {Bo Sun and Ali Zeynali and Tongxin Li and Mohammad Hajiesmaili and Adam Wierman and Danny HK Tsang }, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/12/Sigmetrics2021.pdf}, year = {2021}, date = {2021-06-14}, journal = {ACM on Measurement and Analysis of Computing Systems (POMACS)}, volume = {4}, number = {3}, abstract = {We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of one of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literature. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, we illustrate the proposed algorithm via trace-based experiments of EV charging.}, note = {Also in ACM Sigmetrics 2021}, keywords = {}, pubstate = {published}, tppubtype = {article} } We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of one of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literature. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, we illustrate the proposed algorithm via trace-based experiments of EV charging. |
Zeynali, Ali; Sun, Bo; Hajiesmaili, Mohammad; Wierman, Adam Data-driven Competitive Algorithms for Online Knapsack and Set Cover Inproceedings AAAI Conference on Artificial Intelligence, 2021. @inproceedings{Data2021Zeynali, title = {Data-driven Competitive Algorithms for Online Knapsack and Set Cover}, author = {Ali Zeynali and Bo Sun and Mohammad Hajiesmaili and Adam Wierman}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/12/2012.05361.pdf}, year = {2021}, date = {2021-02-04}, booktitle = {AAAI Conference on Artificial Intelligence}, abstract = {The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack, and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack, and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging |
Wambouru, John; Lee, Stephen; Hajiesmaili, Mohammad; Irwin, David; Shenoy, Prashant Ride Substitution Using Electric Bike Sharing: Feasibility, Cost and Carbon Analysis Journal Article Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies (IMWUT) (also in ACM UbiComp), 2021. @article{ride2021, title = {Ride Substitution Using Electric Bike Sharing: Feasibility, Cost and Carbon Analysis}, author = {John Wambouru and Stephen Lee and Mohammad Hajiesmaili and David Irwin and Prashant Shenoy}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/06/ride-ubicomp.pdf}, year = {2021}, date = {2021-01-12}, journal = {Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies (IMWUT) (also in ACM UbiComp)}, abstract = {While ride-sharing has emerged as a popular form of transportation in urban areas due to its on-demand convenience, it has become a major contributor to carbon emissions, with recent studies suggesting it is 47% more carbon-intensive than personal car trips. In this paper, we examine the feasibility, costs, and carbon benefits of using electric bike-sharing—a low carbon form of ride-sharing—as a potential substitute for shorter ride-sharing trips, with the overall goal of greening the ride-sharing ecosystem. Using public datasets from New York City, our analysis shows that nearly half of the taxi and rideshare trips in New York are shorts trips of less than 3.5km, and that biking is actually faster than using a car for ultra-short trips of 2km or less. We analyze the cost and carbon benefits of different levels of ride substitution under various scenarios. We find that the additional bikes required to satisfy increased demand from ride substitution increases sub-linearly and results in 6.6% carbon emission reduction for 10% taxi ride substitution. Moreover, this reduction can be achieved through a hybrid mix that requires only a quarter of the bikes to be electric bikes, which reduces system costs. We also find that expanding bike-share systems to new areas that lack bike-share coverage requires additional investments due to the need for new bike stations and bike capacity to satisfy demand but also provides substantial carbon emission reductions. Finally, frequent station repositioning can reduce the number of bikes needed in the system by up to a third for a minimal increase in carbon emissions of 2% from the trucks required to perform repositioning, providing an interesting tradeoff between capital costs and carbon emissions.}, keywords = {}, pubstate = {published}, tppubtype = {article} } While ride-sharing has emerged as a popular form of transportation in urban areas due to its on-demand convenience, it has become a major contributor to carbon emissions, with recent studies suggesting it is 47% more carbon-intensive than personal car trips. In this paper, we examine the feasibility, costs, and carbon benefits of using electric bike-sharing—a low carbon form of ride-sharing—as a potential substitute for shorter ride-sharing trips, with the overall goal of greening the ride-sharing ecosystem. Using public datasets from New York City, our analysis shows that nearly half of the taxi and rideshare trips in New York are shorts trips of less than 3.5km, and that biking is actually faster than using a car for ultra-short trips of 2km or less. We analyze the cost and carbon benefits of different levels of ride substitution under various scenarios. We find that the additional bikes required to satisfy increased demand from ride substitution increases sub-linearly and results in 6.6% carbon emission reduction for 10% taxi ride substitution. Moreover, this reduction can be achieved through a hybrid mix that requires only a quarter of the bikes to be electric bikes, which reduces system costs. We also find that expanding bike-share systems to new areas that lack bike-share coverage requires additional investments due to the need for new bike stations and bike capacity to satisfy demand but also provides substantial carbon emission reductions. Finally, frequent station repositioning can reduce the number of bikes needed in the system by up to a third for a minimal increase in carbon emissions of 2% from the trucks required to perform repositioning, providing an interesting tradeoff between capital costs and carbon emissions. |
2020 |
Yang, Lin; Hajiesmaili, Mohammad H; Talebi, Mohammad Sadegh; Lui, John C S; Wong, Wing Shing Adversarial Bandits with Corruptions: Regret Lower Bound and No-regret Algorithm Conference Advances in Neural Information Processing Systems (NeurIPS), 2020. @conference{Lin2020Adversarial, title = {Adversarial Bandits with Corruptions: Regret Lower Bound and No-regret Algorithm}, author = {Lin Yang and Mohammad H. Hajiesmaili and Mohammad Sadegh Talebi and John C. S. Lui and Wing Shing Wong}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2021/01/paper_final-1.pdf}, year = {2020}, date = {2020-12-31}, booktitle = {Advances in Neural Information Processing Systems (NeurIPS)}, abstract = {This paper studies adversarial bandits with corruptions. In the basic adversarial bandit setting, the reward of arms is predetermined by an adversary who is oblivious to the learner’s policy. In this paper, we consider an extended setting in which an attacker sits in-between the environment and the learner, and is endowed with a limited budget to corrupt the reward of the selected arm. We have two main results. First, we derive a lower bound on the regret of any bandit algorithm that is aware of the budget of the attacker. Also, for budget-agnostic algorithms, we characterize an impossibility result demonstrating that even when the attacker has a sublinear budget, i.e., a budget growing sublinearly with time horizon T, they fail to achieve a sublinear regret. Second, we propose ExpRb, a bandit algorithm that incorporates a biased estimator and a robustness parameter to deal with corruption. We characterize the regret of ExpRb as a function of the corruption budget and show that for the case of a known corruption budget, the regret of ExpRb is tight.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper studies adversarial bandits with corruptions. In the basic adversarial bandit setting, the reward of arms is predetermined by an adversary who is oblivious to the learner’s policy. In this paper, we consider an extended setting in which an attacker sits in-between the environment and the learner, and is endowed with a limited budget to corrupt the reward of the selected arm. We have two main results. First, we derive a lower bound on the regret of any bandit algorithm that is aware of the budget of the attacker. Also, for budget-agnostic algorithms, we characterize an impossibility result demonstrating that even when the attacker has a sublinear budget, i.e., a budget growing sublinearly with time horizon T, they fail to achieve a sublinear regret. Second, we propose ExpRb, a bandit algorithm that incorporates a biased estimator and a robustness parameter to deal with corruption. We characterize the regret of ExpRb as a function of the corruption budget and show that for the case of a known corruption budget, the regret of ExpRb is tight. |
Jha, Rishikesh; Lee, Stephen; Iyengar, Srinivasan; Hajiesmaili, Mohammad H; Irwin, David; Shenoy, Prashant Emission-aware Energy Storage Scheduling for a Greener Grid Conference Proceedings of the Eleventh ACM International Conference on Future Energy Systems (eEnergy), 2020, (Best paper runner-up). @conference{Jha2020Emission, title = {Emission-aware Energy Storage Scheduling for a Greener Grid}, author = {Rishikesh Jha and Stephen Lee and Srinivasan Iyengar and Mohammad H Hajiesmaili and David Irwin and Prashant Shenoy}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/08/2005.12234-1.pdf}, doi = {10.1145/3396851.3397755}, year = {2020}, date = {2020-06-01}, booktitle = {Proceedings of the Eleventh ACM International Conference on Future Energy Systems (eEnergy)}, abstract = {Reducing our reliance on carbon-intensive energy sources is vital for reducing the carbon footprint of the electric grid. Although the grid is seeing increasing deployments of clean, renewable sources of energy, a significant portion of the grid demand is still met using traditional carbon-intensive energy sources. In this paper, we study the problem of using energy storage deployed in the grid to reduce the grid’s carbon emissions. While energy storage has previously been used for grid optimizations such as peak shaving and smoothing intermittent sources, our insight is to use distributed storage to enable utilities to reduce their reliance on their less efficient and most carbon-intensive power plants and thereby reduce their overall emission footprint. We formulate the problem of emission-aware scheduling of distributed energy storage as an optimization problem, and use a robust optimization approach that is well-suited for handling the uncertainty in load predictions, especially in the presence of intermittent renewables such as solar and wind. We evaluate our approach using a state of the art neural network load forecasting technique and real load traces from a distribution grid with 1,341 homes. Our results show a reduction of> 0.5 million kg in annual carbon emissions–equivalent to a drop of 23.3% in our electric grid emissions.}, note = {Best paper runner-up}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Reducing our reliance on carbon-intensive energy sources is vital for reducing the carbon footprint of the electric grid. Although the grid is seeing increasing deployments of clean, renewable sources of energy, a significant portion of the grid demand is still met using traditional carbon-intensive energy sources. In this paper, we study the problem of using energy storage deployed in the grid to reduce the grid’s carbon emissions. While energy storage has previously been used for grid optimizations such as peak shaving and smoothing intermittent sources, our insight is to use distributed storage to enable utilities to reduce their reliance on their less efficient and most carbon-intensive power plants and thereby reduce their overall emission footprint. We formulate the problem of emission-aware scheduling of distributed energy storage as an optimization problem, and use a robust optimization approach that is well-suited for handling the uncertainty in load predictions, especially in the presence of intermittent renewables such as solar and wind. We evaluate our approach using a state of the art neural network load forecasting technique and real load traces from a distribution grid with 1,341 homes. Our results show a reduction of> 0.5 million kg in annual carbon emissions–equivalent to a drop of 23.3% in our electric grid emissions. |
Ambati, Pradeep; Bashir, Noman; Irwin, David; Hajiesmaili, Mohammad H; Shenoy, Prashant Hedge Your Bets: Optimizing Long-term Cloud Costs by Mixing VM Purchasing Options Conference IEEE International Conference on Cloud Engineering (IC2E), 2020. @conference{Ambati2020Hedge, title = {Hedge Your Bets: Optimizing Long-term Cloud Costs by Mixing VM Purchasing Options}, author = {Pradeep Ambati and Noman Bashir and David Irwin and Mohammad H. Hajiesmaili and Prashant Shenoy}, url = {https://ieeexplore.ieee.org/abstract/document/9096448}, doi = { 10.1109/IC2E48712.2020.00018}, year = {2020}, date = {2020-04-01}, booktitle = {IEEE International Conference on Cloud Engineering (IC2E)}, abstract = {Cloud platforms offer the same VMs under many purchasing options that specify different costs and time commitments, such as on-demand, reserved, sustained-use, scheduled reserve, transient, and spot block. In general, the stronger the commitment, i.e., longer and less flexible, the lower the price. However, longer and less flexible time commitments can increase cloud costs for users if future workloads cannot utilize the VMs they committed to buying. Large cloud customers often find it challenging to choose the right mix of purchasing options to reduce their long-term costs, while retaining the ability to adjust capacity up and down in response to workload variations.To address the problem, we design policies to optimize long-term cloud costs by selecting a mix of VM purchasing options based on short- and long-term expectations of workload utilization. We consider a batch trace spanning 4 years from a large shared cluster for a major state University system that includes 14k cores and 60 million job submissions, and evaluate how these jobs could be judiciously executed using cloud servers using our approach. Our results show that our policies incur a cost within 41% of an optimistic optimal offline approach, and 50% less than solely using on-demand VMs.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Cloud platforms offer the same VMs under many purchasing options that specify different costs and time commitments, such as on-demand, reserved, sustained-use, scheduled reserve, transient, and spot block. In general, the stronger the commitment, i.e., longer and less flexible, the lower the price. However, longer and less flexible time commitments can increase cloud costs for users if future workloads cannot utilize the VMs they committed to buying. Large cloud customers often find it challenging to choose the right mix of purchasing options to reduce their long-term costs, while retaining the ability to adjust capacity up and down in response to workload variations.To address the problem, we design policies to optimize long-term cloud costs by selecting a mix of VM purchasing options based on short- and long-term expectations of workload utilization. We consider a batch trace spanning 4 years from a large shared cluster for a major state University system that includes 14k cores and 60 million job submissions, and evaluate how these jobs could be judiciously executed using cloud servers using our approach. Our results show that our policies incur a cost within 41% of an optimistic optimal offline approach, and 50% less than solely using on-demand VMs. |
Yang, Lin; Hajiesmaili, Mohammad H; Sitaraman, Ramesh; Wierman, Adam; Mallada, Enrique; Wong, Wing S Online Linear Optimization with Inventory Management Constraints Journal Article ACM on Measurement and Analysis of Computing Systems (POMACS), 3 (2), 2020, (Also in ACM Sigmetrics 2020). @article{Yang:2020, title = {Online Linear Optimization with Inventory Management Constraints}, author = {Lin Yang and Mohammad H. Hajiesmaili and Ramesh Sitaraman and Adam Wierman and Enrique Mallada and Wing S. Wong}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/03/paper.final_.pdf}, year = {2020}, date = {2020-03-01}, journal = {ACM on Measurement and Analysis of Computing Systems (POMACS)}, volume = {3}, number = {2}, publisher = {ACM}, address = {New York, NY, USA}, abstract = {This paper considers the problem of online linear optimization with inventory management constraints. Specifically, we consider an online scenario where a decision-maker needs to satisfy her time-varying demand for some units of an asset, either from a market with a time-varying price or from her own inventory. In each time slot, the decision-maker is presented a (linear) price and must immediately decide the amount to purchase to cover the demand and/or to store in inventory for future use. The inventory has a limited capacity and can be used to buy and store assets at a low price and in order to cover the demand when the price is high. The ultimate goal of the decision-maker is to cover the demand at each time slot while minimizing the cost of buying assets from the market. We propose ARP, an online algorithm for linear programming with inventory constraints, and ARPRate, an extended version that handles rate constraints to/from the inventory. Both ARP and ARPRate achieve optimal competitive ratios, meaning that no other online algorithm can achieve a better theoretical guarantee. To illustrate the results, we use the proposed algorithms in a case study focused on energy procurement and storage management strategies for data centers.}, note = {Also in ACM Sigmetrics 2020}, keywords = {}, pubstate = {published}, tppubtype = {article} } This paper considers the problem of online linear optimization with inventory management constraints. Specifically, we consider an online scenario where a decision-maker needs to satisfy her time-varying demand for some units of an asset, either from a market with a time-varying price or from her own inventory. In each time slot, the decision-maker is presented a (linear) price and must immediately decide the amount to purchase to cover the demand and/or to store in inventory for future use. The inventory has a limited capacity and can be used to buy and store assets at a low price and in order to cover the demand when the price is high. The ultimate goal of the decision-maker is to cover the demand at each time slot while minimizing the cost of buying assets from the market. We propose ARP, an online algorithm for linear programming with inventory constraints, and ARPRate, an extended version that handles rate constraints to/from the inventory. Both ARP and ARPRate achieve optimal competitive ratios, meaning that no other online algorithm can achieve a better theoretical guarantee. To illustrate the results, we use the proposed algorithms in a case study focused on energy procurement and storage management strategies for data centers. |
Alinia, Bahram ; Hajiesmaili, Mohammad H; Lee, Zachary ; Crespi, Noel ; Mallada, Enrique Online EV Scheduling Algorithms for Adaptive Charging Networks with Global Peak Constraints Journal Article Forthcoming IEEE Transactions on Sustainable Computing, Forthcoming. @article{Alinia2020Online, title = {Online EV Scheduling Algorithms for Adaptive Charging Networks with Global Peak Constraints}, author = {Alinia, Bahram and Hajiesmaili, Mohammad H. and Lee, Zachary and Crespi, Noel and Mallada, Enrique}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/03/TSUSC-2018-12-0140.R1-main.pdf}, year = {2020}, date = {2020-01-01}, journal = {IEEE Transactions on Sustainable Computing}, publisher = {ACM}, address = {New York, NY, USA}, abstract = {This paper tackles the online scheduling of electric vehicles (EVs) in an adaptive charging network (ACN) with local and global peak constraints. Given the aggregate charging demand of the EVs and the peak constraints of the ACN, it might be infeasible to fully charge all the EVs according to their charging demand. Two alternatives in such resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). The critical challenge is the need for online solution design since in practical scenarios the scheduler has no information of future arrivals of EVs in a time-coupled underlying problem. For the fractional model, we devise both offline and online algorithms. We prove that the offline algorithm is optimal. Using competitive ratio as the performance measure, we prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is strongly NP-hard due to the 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in an offline setting. We devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases. Extensive trace-driven experimental results show that the performance of the proposed online algorithms is close to the offline optimum, and outperform the existing solutions.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {article} } This paper tackles the online scheduling of electric vehicles (EVs) in an adaptive charging network (ACN) with local and global peak constraints. Given the aggregate charging demand of the EVs and the peak constraints of the ACN, it might be infeasible to fully charge all the EVs according to their charging demand. Two alternatives in such resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). The critical challenge is the need for online solution design since in practical scenarios the scheduler has no information of future arrivals of EVs in a time-coupled underlying problem. For the fractional model, we devise both offline and online algorithms. We prove that the offline algorithm is optimal. Using competitive ratio as the performance measure, we prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is strongly NP-hard due to the 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in an offline setting. We devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases. Extensive trace-driven experimental results show that the performance of the proposed online algorithms is close to the offline optimum, and outperform the existing solutions. |
2019 |
Yekkehkhany, Ali; Arian, Ebrahim; Hajiesmaili, Mohammad H; Nagi, Rakesh Risk-Averse Explore-Then-Commit Algorithms for Finite-Time Bandits Conference Proc. of IEEE Annual Conference on Decision and Control (CDC), 2019. @conference{yekke2019cdc, title = {Risk-Averse Explore-Then-Commit Algorithms for Finite-Time Bandits}, author = {Ali Yekkehkhany and Ebrahim Arian and Mohammad H Hajiesmaili and Rakesh Nagi}, url = {https://arxiv.org/abs/1904.13387}, year = {2019}, date = {2019-12-06}, booktitle = {Proc. of IEEE Annual Conference on Decision and Control (CDC)}, abstract = {In this paper, we study multi-armed bandit problems in explore-then-commit setting. In our proposed explore-then-commit setting, the goal is to identify the best arm after a pure experimentation (exploration) phase and exploit it once or for a given finite number of times. We identify that although the arm with the highest expected reward is the most desirable objective for infinite exploitations, it is not necessarily the one that is most probable to have the highest reward in a single or finite-time exploitations. Alternatively, we advocate the idea of risk-aversion where the objective is to compete against the arm with the best risk-return trade-off. Then, we propose two algorithms whose objectives are to select the arm that is most probable to reward the most. Using a new notion of finite-time exploitation regret, we find an upper bound for the minimum number of experiments before commitment, to guarantee an upper bound for the regret. As compared to existing risk-averse bandit algorithms, our algorithms do not rely on hyper-parameters, resulting in a more robust behavior in practice, which is verified by the numerical evaluation. }, keywords = {}, pubstate = {published}, tppubtype = {conference} } In this paper, we study multi-armed bandit problems in explore-then-commit setting. In our proposed explore-then-commit setting, the goal is to identify the best arm after a pure experimentation (exploration) phase and exploit it once or for a given finite number of times. We identify that although the arm with the highest expected reward is the most desirable objective for infinite exploitations, it is not necessarily the one that is most probable to have the highest reward in a single or finite-time exploitations. Alternatively, we advocate the idea of risk-aversion where the objective is to compete against the arm with the best risk-return trade-off. Then, we propose two algorithms whose objectives are to select the arm that is most probable to reward the most. Using a new notion of finite-time exploitation regret, we find an upper bound for the minimum number of experiments before commitment, to guarantee an upper bound for the regret. As compared to existing risk-averse bandit algorithms, our algorithms do not rely on hyper-parameters, resulting in a more robust behavior in practice, which is verified by the numerical evaluation. |
Alinia, Bahram ; Hajiesmaili, Mohammad H; Crespi, Noel Online EV Charging Scheduling With On-Arrival Commitment Journal Article IEEE Transactions on Intelligent Transportation Systems, 20 (12), 2019. @article{, title = {Online EV Charging Scheduling With On-Arrival Commitment}, author = {Alinia, Bahram and Hajiesmaili, Mohammad H. and Crespi, Noel}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2019/12/its.2019-1.pdf}, doi = {10.1109/TITS.2018.2887194}, year = {2019}, date = {2019-12-01}, journal = {IEEE Transactions on Intelligent Transportation Systems}, volume = {20}, number = {12}, publisher = {ACM}, address = {New York, NY, USA}, abstract = {The rapid proliferation of electric vehicles has resulted in a drastic increase in the total energy demand of EVs. Given the limited charging rate capacity of charging stations and uncertainty of EV arrivals, the aggregate demand might go beyond the charging station capacity, even with proper scheduling. This paper formulates a social welfare maximization problem for EV charging scheduling with charging capacity constraint. Even though the underlying problem is linear, it is difficult to tackle since the input to the problem, i.e., the charging profile of EVs, reveals in online fashion. We devise charging scheduling algorithms that not only work in the online scenario, but also provide the following two key features: 1) on-arrival commitment; respecting the capacity constraint may hinder fulfilling charging requirement of the deadline-constrained EVs entirely. Therefore, committing a guaranteed charging amount upon arrival of each EV is highly essential; 2) (group)-strategy-proofness as a salient feature to promote EVs to reveal their true type and do not collude with other EVs. Extensive simulations using real traces demonstrate the effectiveness of our online scheduling algorithms as compared to the optimal non-committed offline solution.}, keywords = {}, pubstate = {published}, tppubtype = {article} } The rapid proliferation of electric vehicles has resulted in a drastic increase in the total energy demand of EVs. Given the limited charging rate capacity of charging stations and uncertainty of EV arrivals, the aggregate demand might go beyond the charging station capacity, even with proper scheduling. This paper formulates a social welfare maximization problem for EV charging scheduling with charging capacity constraint. Even though the underlying problem is linear, it is difficult to tackle since the input to the problem, i.e., the charging profile of EVs, reveals in online fashion. We devise charging scheduling algorithms that not only work in the online scenario, but also provide the following two key features: 1) on-arrival commitment; respecting the capacity constraint may hinder fulfilling charging requirement of the deadline-constrained EVs entirely. Therefore, committing a guaranteed charging amount upon arrival of each EV is highly essential; 2) (group)-strategy-proofness as a salient feature to promote EVs to reveal their true type and do not collude with other EVs. Extensive simulations using real traces demonstrate the effectiveness of our online scheduling algorithms as compared to the optimal non-committed offline solution. |
Ji, Chengda; Hajiesmaili, Mohammad H; Gayme, Dennice F; Mallada, Enrique Proc. of American Control Conference (ACC), Philadelphia, PA, USA, 2019. @conference{8815242, title = {Coordinating Distribution System Resources for Co-optimized Participation in Energy and Ancillary Service Transmission System Markets}, author = {Chengda Ji and Mohammad H Hajiesmaili and Dennice F Gayme and Enrique Mallada}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/acc2019.pdf}, doi = {10.23919/ACC.2019.8815242}, year = {2019}, date = {2019-07-01}, booktitle = {Proc. of American Control Conference (ACC)}, pages = {1315-1322}, address = {Philadelphia, PA, USA}, abstract = {This paper investigates the potential of using aggregate controllable loads and energy storage systems from multiple heterogeneous feeders to jointly optimize a utility’s energy procurement cost from the real-time market and their revenue from ancillary service markets. Toward this, we formulate an optimization problem that co-optimizes real-time and energy reserve markets based on real-time and ancillary service market prices, along with available solar power, storage and demand data from each of the feeders within a single distribution network. The optimization, which includes all network system constraints, provides real/reactive power and energy storage set-points for each feeder as well as a schedule for the aggregate system’s participation in the two types of markets. We evaluate the performance of our algorithm using several trace-driven simulations based on a real-world circuit of a New Jersey utility. The results demonstrate that active participation through controllable loads and storage significantly reduces the utility’s net costs, i.e., real-time energy procurement costs minus ancillary market revenues.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper investigates the potential of using aggregate controllable loads and energy storage systems from multiple heterogeneous feeders to jointly optimize a utility’s energy procurement cost from the real-time market and their revenue from ancillary service markets. Toward this, we formulate an optimization problem that co-optimizes real-time and energy reserve markets based on real-time and ancillary service market prices, along with available solar power, storage and demand data from each of the feeders within a single distribution network. The optimization, which includes all network system constraints, provides real/reactive power and energy storage set-points for each feeder as well as a schedule for the aggregate system’s participation in the two types of markets. We evaluate the performance of our algorithm using several trace-driven simulations based on a real-world circuit of a New Jersey utility. The results demonstrate that active participation through controllable loads and storage significantly reduces the utility’s net costs, i.e., real-time energy procurement costs minus ancillary market revenues. |
Yang, Lin; Hajiesmaili, Mohammad H; Wong, Wing. S Online Linear Programming with Uncertain Constraints Conference Proc. of IEEE Conference on Information Sciences and Systems (CISS), Baltimore, MD, USA, 2019, (Invited paper). @conference{Yang2019CISS, title = {Online Linear Programming with Uncertain Constraints}, author = {Lin Yang and Mohammad H. Hajiesmaili and Wing. S Wong}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2019/12/ciss.2019.pdf}, doi = {10.1109/CISS.2019.8693056}, year = {2019}, date = {2019-04-18}, booktitle = {Proc. of IEEE Conference on Information Sciences and Systems (CISS)}, journal = {Proc. ACM Meas. Anal. Comput. Syst.}, address = {Baltimore, MD, USA}, abstract = {There are many applications scenarios in different disciplines where the critical knowledge of decision making arrives in a sequential manner, so the optimization must be done in an online fashion. An important class of online optimization problems that have been extensively studied in the past is online linear programs. This paper tackles a general class of online linear programs that take into account the online arrival of the constraint entries related to the available budget and demand for different problem settings. This generalization is motivated by many recent applications on revenue management or resource allocation problems with the unknown and time-varying budget. As the main contribution of this paper, we propose a decoupling strategy that can be used to reduce the general problem into a series of subproblems with offline entries for the budget and demand. Using the proposed strategy, one can decouple the general problem, leverage the state-of-the-art algorithms for the online subproblems with fixed constraints, and achieve the same performance for the general problem. As for a case study, we apply the strategy to an extension of the one-way trading problem with the dynamic budget.}, note = {Invited paper}, keywords = {}, pubstate = {published}, tppubtype = {conference} } There are many applications scenarios in different disciplines where the critical knowledge of decision making arrives in a sequential manner, so the optimization must be done in an online fashion. An important class of online optimization problems that have been extensively studied in the past is online linear programs. This paper tackles a general class of online linear programs that take into account the online arrival of the constraint entries related to the available budget and demand for different problem settings. This generalization is motivated by many recent applications on revenue management or resource allocation problems with the unknown and time-varying budget. As the main contribution of this paper, we propose a decoupling strategy that can be used to reduce the general problem into a series of subproblems with offline entries for the budget and demand. Using the proposed strategy, one can decouple the general problem, leverage the state-of-the-art algorithms for the online subproblems with fixed constraints, and achieve the same performance for the general problem. As for a case study, we apply the strategy to an extension of the one-way trading problem with the dynamic budget. |
Ahmad, Sohaib; Rosenthal, Arielle; Hajiesmaili, Mohammad H; Sitaraman, Ramesh K Learning from Optimal: Energy Procurement Strategies for Data Centers Conference Proceedings of the Tenth ACM International Conference on Future Energy Systems (eEnergy), Phoenix, AZ, USA, 2019, (Notes paper). @conference{Ahmad:2019:LOE:3307772.3328308, title = {Learning from Optimal: Energy Procurement Strategies for Data Centers}, author = {Sohaib Ahmad and Arielle Rosenthal and Mohammad H Hajiesmaili and Ramesh K Sitaraman}, url = {http://doi.acm.org/10.1145/3307772.3328308}, doi = {10.1145/3307772.3328308}, year = {2019}, date = {2019-01-01}, booktitle = {Proceedings of the Tenth ACM International Conference on Future Energy Systems (eEnergy)}, pages = {326–330}, address = {Phoenix, AZ, USA}, abstract = {Environmental concerns and rising grid prices have motivated data center owners to invest in on-site renewable energy sources. However, these sources present challenges as they are unreliable and intermittent. In an effort to mitigate these issues, data centers are incorporating energy storage systems. This introduces the opportunity for electricity bill reduction, as energy storage can be used for power market arbitrage. We present two supervised learning-based algorithms, LearnBuy, that learns the amount to purchase, and LearnStore, that learns the amount to store, to solve this energy procurement problem. These algorithms utilize the idea of “learning from optimal” by using the values generated by the offline optimization as a label for training. We test our algorithms on a general case, considering buying and selling back to the grid, and a special case, considering only buying from the grid. In the general case, LearnStore achieves a 10–16% reduction compared to baseline heuristics, whereas in the special case, LearnBuy achieves a 7% reduction compared to prior art.}, note = {Notes paper}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Environmental concerns and rising grid prices have motivated data center owners to invest in on-site renewable energy sources. However, these sources present challenges as they are unreliable and intermittent. In an effort to mitigate these issues, data centers are incorporating energy storage systems. This introduces the opportunity for electricity bill reduction, as energy storage can be used for power market arbitrage. We present two supervised learning-based algorithms, LearnBuy, that learns the amount to purchase, and LearnStore, that learns the amount to store, to solve this energy procurement problem. These algorithms utilize the idea of "learning from optimal" by using the values generated by the offline optimization as a label for training. We test our algorithms on a general case, considering buying and selling back to the grid, and a special case, considering only buying from the grid. In the general case, LearnStore achieves a 10–16% reduction compared to baseline heuristics, whereas in the special case, LearnBuy achieves a 7% reduction compared to prior art. |
2018 |
Yi, Hanling; Hajiesmaili, Mohammad H; Zhang, Ying; Chen, Minghua; Lin, Xiaojun Impact of Uncertainty of Distributed Renewable Generation on Deregulated Electricity Supply Chain Journal Article IEEE Transactions on Smart Grid, 9 (6), pp. 6183 – 6193, 2018, ISSN: 1949-3053, (Also appeared in 2018 IEEE Power & Energy Society General Meeting (PESGM)). @article{yi2017impact, title = {Impact of Uncertainty of Distributed Renewable Generation on Deregulated Electricity Supply Chain}, author = {Hanling Yi and Mohammad H Hajiesmaili and Ying Zhang and Minghua Chen and Xiaojun Lin}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/tsg2018.pdf}, doi = { 10.1109/TSG.2017.2705289}, issn = {1949-3053}, year = {2018}, date = {2018-11-01}, journal = {IEEE Transactions on Smart Grid}, volume = {9}, number = {6}, pages = {6183 – 6193}, abstract = {Active districts are districts that have a system in place to coordinate distributed energy generation and external grid to meet the local energy demand. They are now widely recognized as a clear opportunity toward distributed renewable integration. Despite apparent benefits of incorporating renewable sources in an active district, uncertainty in renewable generation can impose unprecedented challenges in efficient operation of the existing deregulated electricity supply chain, which is designed to operate with no or little uncertainty in both supply and demand. While most previous studies focused on the impact of renewables on the supply side of the supply chain, we investigate the impact of distributed renewable generation on the demand side. In particular, we study how the uncertainty from distributed renewable generation in an active district affects the average buying cost of utilities and the cost-saving of the active district. Our analysis shows that the renewable uncertainty in an active district can: 1) increase the average buying cost of the utility serving the active district, termed as local impact and 2) somewhat surprisingly, reduce the average buying cost of other utilities participating in the same electricity market, termed as global impact. Moreover, the local impact will lead to an increase in the electricity retail price of active district, resulting in a cost-saving less than the case without renewable uncertainty. These observations reveal an inherent economic incentive for utilities to improve their load forecasting accuracy, in order to avoid economic loss and even extract economic benefit in the electricity market. We verify our theoretical results by extensive experiments using real-world traces. Our experimental results show that a 9% increase in load forecasting error (modeled by the standard deviation of the mismatch between real-time actual demand and day-ahead purchased supply) will increase the average buying cost of the utility by 10%. }, note = {Also appeared in 2018 IEEE Power & Energy Society General Meeting (PESGM)}, keywords = {}, pubstate = {published}, tppubtype = {article} } Active districts are districts that have a system in place to coordinate distributed energy generation and external grid to meet the local energy demand. They are now widely recognized as a clear opportunity toward distributed renewable integration. Despite apparent benefits of incorporating renewable sources in an active district, uncertainty in renewable generation can impose unprecedented challenges in efficient operation of the existing deregulated electricity supply chain, which is designed to operate with no or little uncertainty in both supply and demand. While most previous studies focused on the impact of renewables on the supply side of the supply chain, we investigate the impact of distributed renewable generation on the demand side. In particular, we study how the uncertainty from distributed renewable generation in an active district affects the average buying cost of utilities and the cost-saving of the active district. Our analysis shows that the renewable uncertainty in an active district can: 1) increase the average buying cost of the utility serving the active district, termed as local impact and 2) somewhat surprisingly, reduce the average buying cost of other utilities participating in the same electricity market, termed as global impact. Moreover, the local impact will lead to an increase in the electricity retail price of active district, resulting in a cost-saving less than the case without renewable uncertainty. These observations reveal an inherent economic incentive for utilities to improve their load forecasting accuracy, in order to avoid economic loss and even extract economic benefit in the electricity market. We verify our theoretical results by extensive experiments using real-world traces. Our experimental results show that a 9% increase in load forecasting error (modeled by the standard deviation of the mismatch between real-time actual demand and day-ahead purchased supply) will increase the average buying cost of the utility by 10%. |
Hajiesmaili, Mohammad H; Talebi, Sadegh M; Khonsari, Ahmad Multiperiod Network Rate Allocation With End-to-End Delay Constraints Journal Article IEEE Transactions on Control of Network Systems, 5 (3), pp. 1087 – 1097, 2018, ISBN: 2325-5870, (Preliminary version appeared in IEEE CDC 2015). @article{hajiesmaili2017multi, title = {Multiperiod Network Rate Allocation With End-to-End Delay Constraints}, author = {Mohammad H Hajiesmaili and Sadegh M Talebi and Ahmad Khonsari}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/TCNS2018.pdf}, doi = { 10.1109/TCNS.2017.2677202}, isbn = {2325-5870}, year = {2018}, date = {2018-09-01}, journal = {IEEE Transactions on Control of Network Systems}, volume = {5}, number = {3}, pages = {1087 – 1097}, abstract = {QoS-aware networking applications such as real-time streaming and video surveillance systems require nearly fixed average end-to-end delay over long periods to communicate efficiently, although may tolerate some delay variations in short periods. This variability exhibits complex dynamics that makes rate control of such applications a formidable task. This paper addresses rate allocation for heterogeneous QoS-aware applications that preserves the long-term end-to-end delay constraint while seeking the maximum network utility cumulated over a fixed time interval. To capture the temporal dynamics of sources, we incorporate a novel time-coupling constraint in which delay sensitivity of sources is considered such that a certain end-to-end average delay for each source over a prespecified time interval is satisfied. We propose an algorithm, as a dual-based solution, which allocates source rates for the next time interval in a distributed fashion, given the knowledge of network parameters in advance. Also, we extend the algorithm to the case that the problem data is not known fully in advance to capture more realistic scenarios. Through numerical experiments, we show that our proposed algorithm attains higher average link utilization and a wider range of feasible scenarios in comparison with the best, to our knowledge, rate control schemes that may guarantee such constraints on delay. }, note = {Preliminary version appeared in IEEE CDC 2015}, keywords = {}, pubstate = {published}, tppubtype = {article} } QoS-aware networking applications such as real-time streaming and video surveillance systems require nearly fixed average end-to-end delay over long periods to communicate efficiently, although may tolerate some delay variations in short periods. This variability exhibits complex dynamics that makes rate control of such applications a formidable task. This paper addresses rate allocation for heterogeneous QoS-aware applications that preserves the long-term end-to-end delay constraint while seeking the maximum network utility cumulated over a fixed time interval. To capture the temporal dynamics of sources, we incorporate a novel time-coupling constraint in which delay sensitivity of sources is considered such that a certain end-to-end average delay for each source over a prespecified time interval is satisfied. We propose an algorithm, as a dual-based solution, which allocates source rates for the next time interval in a distributed fashion, given the knowledge of network parameters in advance. Also, we extend the algorithm to the case that the problem data is not known fully in advance to capture more realistic scenarios. Through numerical experiments, we show that our proposed algorithm attains higher average link utilization and a wider range of feasible scenarios in comparison with the best, to our knowledge, rate control schemes that may guarantee such constraints on delay. |
Deng, Lei; Hajiesmaili, Mohammad H; Chen, Minghua; Zeng, Haibo Energy-Efficient Timely Transportation of Long-Haul Heavy-Duty Trucks Journal Article IEEE Transactions on Intelligent Transportation Systems, 19 (7), pp. 2099 – 2113, 2018, ISBN: 1558-0016, (Preliminary version appeared in ACM eEnergy 2015). @article{deng2017energy, title = {Energy-Efficient Timely Transportation of Long-Haul Heavy-Duty Trucks}, author = {Lei Deng and Mohammad H Hajiesmaili and Minghua Chen and Haibo Zeng}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/its2017.pdf}, doi = { 10.1109/TITS.2017.2749262}, isbn = {1558-0016}, year = {2018}, date = {2018-07-01}, journal = {IEEE Transactions on Intelligent Transportation Systems}, volume = {19}, number = {7}, pages = {2099 – 2113}, abstract = {We consider a timely transportation problem where a heavy-duty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our objective is to minimize the total fuel consumption of the truck, by optimizing both route planning and speed planning. The problem is important for cost-effective and environment-friendly truck operation, and it is uniquely challenging due to its combinatorial nature as well as the need of considering hard deadline constraint. We first show that the problem is NP-complete; thus exact solution is computational prohibited unless P = NP. We then design a fully polynomial time approximation scheme (FPTAS) to solve it. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time when applying to national-wide highway systems with tens of thousands of nodes and edges. Leveraging elegant insights from studying the dual of the original problem, we design a heuristic with much lower complexity. The proposed heuristic allows us to tackle the energy-efficient timely transportation problem on large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. We carry out extensive numerical experiments using real-world truck data over the actual U.S. highway network. The results show that our proposed solutions achieve 17% (resp. 14%) fuel consumption reduction, as compared with a fastest path (resp. shortest path) algorithm adapted from common practice. }, note = {Preliminary version appeared in ACM eEnergy 2015}, keywords = {}, pubstate = {published}, tppubtype = {article} } We consider a timely transportation problem where a heavy-duty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our objective is to minimize the total fuel consumption of the truck, by optimizing both route planning and speed planning. The problem is important for cost-effective and environment-friendly truck operation, and it is uniquely challenging due to its combinatorial nature as well as the need of considering hard deadline constraint. We first show that the problem is NP-complete; thus exact solution is computational prohibited unless P = NP. We then design a fully polynomial time approximation scheme (FPTAS) to solve it. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time when applying to national-wide highway systems with tens of thousands of nodes and edges. Leveraging elegant insights from studying the dual of the original problem, we design a heuristic with much lower complexity. The proposed heuristic allows us to tackle the energy-efficient timely transportation problem on large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. We carry out extensive numerical experiments using real-world truck data over the actual U.S. highway network. The results show that our proposed solutions achieve 17% (resp. 14%) fuel consumption reduction, as compared with a fastest path (resp. shortest path) algorithm adapted from common practice. |
Yang, Lin; Wong, Wing S; Hajiesmaili, Mohammad H An Optimal Randomized Online Algorithm for QoS Buffer Management Conference Proc. of ACM Sigmetrics, Irvine, CA, USA, 2018. @conference{Lin2018Optimal, title = {An Optimal Randomized Online Algorithm for QoS Buffer Management}, author = {Lin Yang and Wing S. Wong and Mohammad H. Hajiesmaili }, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/sigmetrics181-1.pdf}, doi = {10.1145/3219617.3219629}, year = {2018}, date = {2018-06-14}, booktitle = {Proc. of ACM Sigmetrics}, address = {Irvine, CA, USA}, abstract = {The QoS (Quality of Service) buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic online admission control problem in the presence of resource constraints. In its basic setting, packets with different values according to their QoS requirements, arrive in online fashion to a switching node with limited buffer size. Then, the switch needs to make an immediate decision to either admit or reject the incoming packet based on the value of the packet and its buffer availability. The objective is to maximize the cumulative profit of the admitted packets, while respecting the buffer constraint. Even though the QoS buffer management problem was proposed more than a decade ago, no optimal online solution has been proposed in the literature. This paper contributes to this problem by proposing: 1) A fixed threshold-based online algorithm with smaller competitive ratio than the existing results; 2) an optimal deterministic online algorithm under fractional admission model in which a packet could be admitted partially; and 3) an optimal randomized online algorithm for the general problem. We consider the last result being the main contribution of this paper.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The QoS (Quality of Service) buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic online admission control problem in the presence of resource constraints. In its basic setting, packets with different values according to their QoS requirements, arrive in online fashion to a switching node with limited buffer size. Then, the switch needs to make an immediate decision to either admit or reject the incoming packet based on the value of the packet and its buffer availability. The objective is to maximize the cumulative profit of the admitted packets, while respecting the buffer constraint. Even though the QoS buffer management problem was proposed more than a decade ago, no optimal online solution has been proposed in the literature. This paper contributes to this problem by proposing: 1) A fixed threshold-based online algorithm with smaller competitive ratio than the existing results; 2) an optimal deterministic online algorithm under fractional admission model in which a packet could be admitted partially; and 3) an optimal randomized online algorithm for the general problem. We consider the last result being the main contribution of this paper. |
Yang, Lin; Deng, Lei; Hajiesmaili, Mohammad H; Tan, Cheng; Wong, Wing Shing An Optimal Algorithm for Online Non-Convex Learning Journal Article ACM on Measurement and Analysis of Computing Systems (POMACS), 2 (2), 2018, (Also appeared in ACM Sigmetrics 2018). @article{yang2018online, title = {An Optimal Algorithm for Online Non-Convex Learning}, author = {Lin Yang and Lei Deng and Mohammad H Hajiesmaili and Cheng Tan and Wing Shing Wong}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2019/12/Sigmetrics182-4.pdf}, doi = {10.1145/3224420}, year = {2018}, date = {2018-06-01}, journal = {ACM on Measurement and Analysis of Computing Systems (POMACS)}, volume = {2}, number = {2}, abstract = {In many online learning paradigms, convexity plays a central role in the derivation and analysis of online learning algorithms. The results, however, fail to be extended to the non-convex settings, while non-convexity is necessitated by a large number of recent applications. The Online Non-Convex Learning (ONCO) problem generalizes the classic Online Convex Optimization (OCO) framework by relaxing the convexity assumption on the cost function (to a Lipschitz continuous function) and the decision set. The state-of-the-art result for the ONCO demonstrates that the classic online exponential weighting algorithm attains a sublinear regret of $O(sqrt Tłog T)$. The regret lower bound for the OCO, however, is $Omega(sqrtT )$, and to the best of our knowledge, there is no result in the context of the ONCO problem achieving the same bound. This paper proposes the Online Recursive Weighting (ARW) algorithm with regret of $O(sqrtT )$, matching the tight regret lower bound for the OCO problem, and fills the regret gap between the state-of-the-art results in the online convex and non-convex optimization problems. }, note = {Also appeared in ACM Sigmetrics 2018}, keywords = {}, pubstate = {published}, tppubtype = {article} } In many online learning paradigms, convexity plays a central role in the derivation and analysis of online learning algorithms. The results, however, fail to be extended to the non-convex settings, while non-convexity is necessitated by a large number of recent applications. The Online Non-Convex Learning (ONCO) problem generalizes the classic Online Convex Optimization (OCO) framework by relaxing the convexity assumption on the cost function (to a Lipschitz continuous function) and the decision set. The state-of-the-art result for the ONCO demonstrates that the classic online exponential weighting algorithm attains a sublinear regret of $O(sqrt Tłog T)$. The regret lower bound for the OCO, however, is $Omega(sqrtT )$, and to the best of our knowledge, there is no result in the context of the ONCO problem achieving the same bound. This paper proposes the Online Recursive Weighting (ARW) algorithm with regret of $O(sqrtT )$, matching the tight regret lower bound for the OCO problem, and fills the regret gap between the state-of-the-art results in the online convex and non-convex optimization problems. |
Zhang, Ying; Hajiesmaili, Mohammad H; Cai, Sinan; Chen, Minghua; Zhu, Qi Peak-Aware Online Economic Dispatching for Microgrids Journal Article IEEE Transactions on Smart Grid, 9 (1), pp. 323-335, 2018, ISSN: 1949-3053, (Also appeared in ACM eEnergy 2015). @article{zhang2018peak, title = {Peak-Aware Online Economic Dispatching for Microgrids}, author = {Ying Zhang and Mohammad H Hajiesmaili and Sinan Cai and Minghua Chen and Qi Zhu}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/tsg2016.pdf}, doi = { 10.1109/TSG.2016.2551282}, issn = {1949-3053}, year = {2018}, date = {2018-01-01}, journal = {IEEE Transactions on Smart Grid}, volume = {9}, number = {1}, pages = {323-335}, abstract = {By employing local renewable energy sources and power generation units while connected to the central grid, microgrid can usher in great benefits in terms of cost efficiency, power reliability, and environmental awareness. Economic dispatching is a central problem in microgrid operation, which aims at effectively scheduling various energy sources to minimize the operating cost while satisfying the electricity demand. Designing intelligent economic dispatching strategies for microgrids; however, it is drastically different from that for conventional central grids due to two unique challenges. First, the demand and renewable generation uncertainty emphasizes the need for online algorithms. Second, the widely-adopted peak-based pricing scheme brings out the need for new peak-aware strategy design. In this paper, we tackle these critical challenges and devise peak-aware online economic dispatching algorithms. We prove that our deterministic and randomized algorithms achieve the best possible competitive ratios 2 – β and e/(e – 1 + β) in the fast responding generator scenario, where β ∈ [0, 1] is the ratio between the minimum grid spot price and the local-generation price. By extensive empirical evaluations using real-world traces, we show that our online algorithms achieve near offline-optimal performance. In a representative scenario, our algorithm achieves 17.5% and 9.24% cost reduction as compared with the case without local generation units and the case using peak-oblivious algorithms, respectively.}, note = {Also appeared in ACM eEnergy 2015}, keywords = {}, pubstate = {published}, tppubtype = {article} } By employing local renewable energy sources and power generation units while connected to the central grid, microgrid can usher in great benefits in terms of cost efficiency, power reliability, and environmental awareness. Economic dispatching is a central problem in microgrid operation, which aims at effectively scheduling various energy sources to minimize the operating cost while satisfying the electricity demand. Designing intelligent economic dispatching strategies for microgrids; however, it is drastically different from that for conventional central grids due to two unique challenges. First, the demand and renewable generation uncertainty emphasizes the need for online algorithms. Second, the widely-adopted peak-based pricing scheme brings out the need for new peak-aware strategy design. In this paper, we tackle these critical challenges and devise peak-aware online economic dispatching algorithms. We prove that our deterministic and randomized algorithms achieve the best possible competitive ratios 2 – β and e/(e – 1 + β) in the fast responding generator scenario, where β ∈ [0, 1] is the ratio between the minimum grid spot price and the local-generation price. By extensive empirical evaluations using real-world traces, we show that our online algorithms achieve near offline-optimal performance. In a representative scenario, our algorithm achieves 17.5% and 9.24% cost reduction as compared with the case without local generation units and the case using peak-oblivious algorithms, respectively. |
Alinai, Bahram; Talebi, Sadegh M; Hajiesmaili, Mohammad H; Yekkehkhany, Ali; Crespi, Noel Competitive Online Scheduling Algorithms with Applications in Deadline-Constrained EV Charging Conference Proc. of IEEE/ACM International Symposium on Quality of Service (IWQoS), Banff, Alberta, Canada, 2018. @conference{alinia2018competitive, title = {Competitive Online Scheduling Algorithms with Applications in Deadline-Constrained EV Charging}, author = {Bahram Alinai and Sadegh M Talebi and Mohammad H Hajiesmaili and Ali Yekkehkhany and Noel Crespi}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/iwqos2018.pdf}, doi = { 10.1109/IWQoS.2018.8624184}, year = {2018}, date = {2018-01-01}, booktitle = {Proc. of IEEE/ACM International Symposium on Quality of Service (IWQoS)}, address = {Banff, Alberta, Canada}, abstract = {This paper studies the classical problem of online scheduling of deadline-sensitive jobs with partial values and investigates its extension to Electric Vehicle (EV) charging scheduling by taking into account the processing rate limit of jobs and charging station capacity constraint. The problem lies in the category of time-coupled online scheduling problems without availability of future information. This paper proposes two online algorithms, both of which are shown to be (2-[1/U])-competitive, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. The first proposed algorithm is deterministic, whereas the second is randomized and enjoys a lower computational complexity. When U grows large, the performance of both algorithms approaches that of the state-of-the-art for the case where there is processing rate limits on the jobs. Nonetheless, in realistic cases, where U is typically small, the proposed algorithms enjoy a much lower competitive ratio. To carry out the competitive analysis of our algorithms, we present a proof technique, which is novel to the best of our knowledge. This technique could also be used to simplify the competitive analysis of some existing algorithms, and thus could be of independent interest. }, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper studies the classical problem of online scheduling of deadline-sensitive jobs with partial values and investigates its extension to Electric Vehicle (EV) charging scheduling by taking into account the processing rate limit of jobs and charging station capacity constraint. The problem lies in the category of time-coupled online scheduling problems without availability of future information. This paper proposes two online algorithms, both of which are shown to be (2-[1/U])-competitive, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. The first proposed algorithm is deterministic, whereas the second is randomized and enjoys a lower computational complexity. When U grows large, the performance of both algorithms approaches that of the state-of-the-art for the case where there is processing rate limits on the jobs. Nonetheless, in realistic cases, where U is typically small, the proposed algorithms enjoy a much lower competitive ratio. To carry out the competitive analysis of our algorithms, we present a proof technique, which is novel to the best of our knowledge. This technique could also be used to simplify the competitive analysis of some existing algorithms, and thus could be of independent interest. |
2017 |
Hajiesmaili, Mohammad H; Mak, Lok T; Wang, Zhi; Wu, Chuan; Chen, Minghua; Khonsari, Ahmad Cost-Effective Low-Delay Design for Multiparty Cloud Video Conferencing Journal Article IEEE Transactions on Multimedia, 19 (12), pp. 2760-2774, 2017, ISSN: 1520-9210, (Preliminary version appeared in IEEE ICDCS 2015). @article{hajiesmaili2017cost, title = {Cost-Effective Low-Delay Design for Multiparty Cloud Video Conferencing}, author = {Mohammad H. Hajiesmaili and Lok T. Mak and Zhi Wang and Chuan Wu and Minghua Chen and Ahmad Khonsari}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/tmm2017.pdf}, doi = { 10.1109/TMM.2017.2710799}, issn = {1520-9210}, year = {2017}, date = {2017-12-01}, journal = {IEEE Transactions on Multimedia}, volume = {19}, number = {12}, pages = {2760-2774}, abstract = {Multiparty cloud video conferencing architecture has been recently advocated to exploit rich computing and bandwidth resources in the cloud to effectively improve video conferencing performance. As a typical design in this architecture, multiple agents, i.e., virtual machines, are deployed in different cloud sites, and users are assigned to the agents. Then, the users communicate through the agents, and the agents might transcode the recorded videos given the heterogeneities among devices in terms of hardware specification and connectivity. In this architecture, two critical and nontrivial challenges are: 1) assigning users to agents to reduce the operational cost and the user-to-user conferencing delay and 2) identifying best agents to perform transcoding tasks, taking into account the heterogeneous bandwidth and processing availabilities. To address these challenges, we cast a joint problem of user-to-agent assignment and transcoding-agent selection. The ultimate objective is to simultaneously minimize the cost of the service provider and the conferencing delay. The problem is combinatorial in nature, which belongs to the NP-hard node assignment problems. We leverage the Markov approximation framework and devise an adaptive parallel algorithm that finds a close-to-optimal solution to our problem with a bounded performance guarantee. To evaluate the performance of our solution, we implement a prototype video conferencing system and carry out trace-driven experiments. In a set of largescale experiments using PlanetLab traces, our solution decreases the operational cost by 77% and simultaneously yields lower conferencing delay compared with an existing alternative. }, note = {Preliminary version appeared in IEEE ICDCS 2015}, keywords = {}, pubstate = {published}, tppubtype = {article} } Multiparty cloud video conferencing architecture has been recently advocated to exploit rich computing and bandwidth resources in the cloud to effectively improve video conferencing performance. As a typical design in this architecture, multiple agents, i.e., virtual machines, are deployed in different cloud sites, and users are assigned to the agents. Then, the users communicate through the agents, and the agents might transcode the recorded videos given the heterogeneities among devices in terms of hardware specification and connectivity. In this architecture, two critical and nontrivial challenges are: 1) assigning users to agents to reduce the operational cost and the user-to-user conferencing delay and 2) identifying best agents to perform transcoding tasks, taking into account the heterogeneous bandwidth and processing availabilities. To address these challenges, we cast a joint problem of user-to-agent assignment and transcoding-agent selection. The ultimate objective is to simultaneously minimize the cost of the service provider and the conferencing delay. The problem is combinatorial in nature, which belongs to the NP-hard node assignment problems. We leverage the Markov approximation framework and devise an adaptive parallel algorithm that finds a close-to-optimal solution to our problem with a bounded performance guarantee. To evaluate the performance of our solution, we implement a prototype video conferencing system and carry out trace-driven experiments. In a set of largescale experiments using PlanetLab traces, our solution decreases the operational cost by 77% and simultaneously yields lower conferencing delay compared with an existing alternative. |
Yang, Lin; Wong, Wing Shing; Hajiesmaili, Mohammad H An Optimal Randomized Online Algorithm for QoS Buffer Management Journal Article ACM on Measurement and Analysis of Computing Systems (POMACS), 1 (2), pp. 36:1–36:26, 2017, ISSN: 2476-1249, (Also appeared in ACM Sigmetrics 2018). @article{yang2017optimal, title = {An Optimal Randomized Online Algorithm for QoS Buffer Management}, author = {Lin Yang and Wing Shing Wong and Mohammad H Hajiesmaili}, url = {http://doi.acm.org/10.1145/3154494https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/sigmetrics181.pdf}, doi = {10.1145/3154494}, issn = {2476-1249}, year = {2017}, date = {2017-12-01}, journal = {ACM on Measurement and Analysis of Computing Systems (POMACS)}, volume = {1}, number = {2}, pages = {36:1–36:26}, publisher = {ACM}, address = {New York, NY, USA}, abstract = {The QoS (Quality of Service) buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic online admission control problem in the presence of resource constraints. In its basic setting, packets with different values according to their QoS requirements, arrive in online fashion to a switching node with limited buffer size. Then, the switch needs to make an immediate decision to either admit or reject the incoming packet based on the value of the packet and its buffer availability. The objective is to maximize the cumulative profit of the admitted packets, while respecting the buffer constraint. Even though the QoS buffer management problem was proposed more than a decade ago, no optimal online solution has been proposed in the literature. This paper contributes to this problem by proposing: 1) A fixed threshold-based online algorithm with smaller competitive ratio than the existing results; 2) an optimal deterministic online algorithm under fractional admission model in which a packet could be admitted partially; and 3) an optimal randomized online algorithm for the general problem. We consider the last result being the main contribution of this paper.}, note = {Also appeared in ACM Sigmetrics 2018}, keywords = {}, pubstate = {published}, tppubtype = {article} } The QoS (Quality of Service) buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic online admission control problem in the presence of resource constraints. In its basic setting, packets with different values according to their QoS requirements, arrive in online fashion to a switching node with limited buffer size. Then, the switch needs to make an immediate decision to either admit or reject the incoming packet based on the value of the packet and its buffer availability. The objective is to maximize the cumulative profit of the admitted packets, while respecting the buffer constraint. Even though the QoS buffer management problem was proposed more than a decade ago, no optimal online solution has been proposed in the literature. This paper contributes to this problem by proposing: 1) A fixed threshold-based online algorithm with smaller competitive ratio than the existing results; 2) an optimal deterministic online algorithm under fractional admission model in which a packet could be admitted partially; and 3) an optimal randomized online algorithm for the general problem. We consider the last result being the main contribution of this paper. |
Hajiesmaili, Mohammad H; Cai, Desmond; Mallada, Enrique Understanding the inefficiency of security-constrained economic dispatch Conference Proc. IEEE Annual Conference on Decision and Control (CDC), Melbourne, Australia, 2017. @conference{hajiesmaili2017understanding, title = {Understanding the inefficiency of security-constrained economic dispatch}, author = {Mohammad H Hajiesmaili and Desmond Cai and Enrique Mallada}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/cdc.2017.pdf}, doi = { 10.1109/CDC.2017.8263947}, year = {2017}, date = {2017-12-01}, booktitle = {Proc. IEEE Annual Conference on Decision and Control (CDC)}, pages = {2035-2040}, address = {Melbourne, Australia}, abstract = {The security-constrained economic dispatch (SCED) problem tries to maintain the reliability of a power network by ensuring that a single failure does not lead to a global outage. The previous research has mainly investigated SCED by formulating the problem in different modalities, e.g. preventive or corrective, and devising efficient solutions for SCED. In this paper, we tackle a novel and important direction, and analyze the economic cost of incorporating security constraints in economic dispatch. Inspired by existing inefficiency metrics in game theory and computer science, we introduce notion of price of security as a metric that formally characterizes the economic inefficiency of SCED as compared to the original problem without security constraints. Then, we focus on the preventive approach in a simple topology comprising two buses and two lines, and investigate the impact of generation availability and demand distribution on the price of security. Moreover, we explicitly derive the worst-case input instance that leads to the maximum price of security. By experimental study on two test-cases, we verify the analytical results and provide insights for characterizing the price of security in general networks.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The security-constrained economic dispatch (SCED) problem tries to maintain the reliability of a power network by ensuring that a single failure does not lead to a global outage. The previous research has mainly investigated SCED by formulating the problem in different modalities, e.g. preventive or corrective, and devising efficient solutions for SCED. In this paper, we tackle a novel and important direction, and analyze the economic cost of incorporating security constraints in economic dispatch. Inspired by existing inefficiency metrics in game theory and computer science, we introduce notion of price of security as a metric that formally characterizes the economic inefficiency of SCED as compared to the original problem without security constraints. Then, we focus on the preventive approach in a simple topology comprising two buses and two lines, and investigate the impact of generation availability and demand distribution on the price of security. Moreover, we explicitly derive the worst-case input instance that leads to the maximum price of security. By experimental study on two test-cases, we verify the analytical results and provide insights for characterizing the price of security in general networks. |
Yang*, Lin; Hajiesmaili*, Mohammad H; Yi, Hanling; Chen, Minghua Proc. of ACM Sigmetrics , Urbana, IL, USA, 2017, (*equal contribution, poster paper). @conference{yang2017offering, title = {Hour-Ahead Offering Strategies in Electricity Market for Power Producers with Storage and Intermittent Supply}, author = {Lin Yang* and Mohammad H Hajiesmaili* and Hanling Yi and Minghua Chen}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/sigmetrics.2017.pdf}, doi = {10.1145/3143314.3078543}, year = {2017}, date = {2017-06-17}, booktitle = {Proc. of ACM Sigmetrics }, journal = {SIGMETRICS Perform. Eval. Rev.}, address = {Urbana, IL, USA}, abstract = {This paper proposes online offering strategies for a storage-assisted renewable power producer that participates in hour-ahead electricity market. The online strategy determines the offering price and volume, while no exact or stochastic future information is available in a time-coupled setting in the presence of the storage. The proposed online strategy achieves the best possible competitive ratio of O(log θ), where θ is the ratio between the maximum and minimum clearing prices. Trace-driven experiments demonstrate that the proposed strategy achieves close-to-optimal performance. }, note = {*equal contribution, poster paper}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper proposes online offering strategies for a storage-assisted renewable power producer that participates in hour-ahead electricity market. The online strategy determines the offering price and volume, while no exact or stochastic future information is available in a time-coupled setting in the presence of the storage. The proposed online strategy achieves the best possible competitive ratio of O(log θ), where θ is the ratio between the maximum and minimum clearing prices. Trace-driven experiments demonstrate that the proposed strategy achieves close-to-optimal performance. |
Alinia, Bahram; Hajiesmaili, Mohammad H; Khonsari, Ahmad; Crespi, Crespi Maximum-Quality Tree Construction for Deadline-Constrained Aggregation in WSNs Journal Article IEEE Sensors Journal, 17 (12), pp. 3930-3943, 2017, ISSN: 1558-1748, (Preliminary version appeared in IEEE Infocom 2015). @article{alinia2017maximum, title = {Maximum-Quality Tree Construction for Deadline-Constrained Aggregation in WSNs}, author = {Bahram Alinia and Mohammad H Hajiesmaili and Ahmad Khonsari and Crespi Crespi}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/sensors2017.pdf}, doi = {10.1109/JSEN.2017.2701552}, issn = {1558-1748}, year = {2017}, date = {2017-06-01}, journal = {IEEE Sensors Journal}, volume = {17}, number = {12}, pages = {3930-3943}, abstract = {In deadline-constrained wireless sensor networks (WSNs), the quality of aggregation (QOA) is determined by the number of participating nodes in the data aggregation process. The previous studies have attempted to propose optimal scheduling algorithms to obtain the maximum QOA assuming a fixed underlying aggregation tree. However, there exists no prior work to address the issue of constructing optimal aggregation tree in deadline-constraints WSNs. The structure of underlying aggregation tree is important since our analysis demonstrates that the ratio between the maximum achievable QOAs of different trees could be as large as O(2 D ), where D is the deadline. This paper casts a combinatorial optimization problem to address the optimal tree construction for deadline-constrained data aggregation in WSNs. While the problem is proved to be NP-hard, we employ the Markov approximation framework and devise two distributed algorithms with different computation overheads to find close-to-optimal solution with bounded approximation gap. To further improve the convergence of the Markov-based algorithms, we devise another initial tree construction algorithm with low-computational complexity. Our experimental results from a set of randomly-generated scenarios demonstrate that the proposed algorithms achieve near optimal performance and appreciably outperform methods that work on a fixed aggregation tree by obtaining better quality of aggregation. }, note = {Preliminary version appeared in IEEE Infocom 2015}, keywords = {}, pubstate = {published}, tppubtype = {article} } In deadline-constrained wireless sensor networks (WSNs), the quality of aggregation (QOA) is determined by the number of participating nodes in the data aggregation process. The previous studies have attempted to propose optimal scheduling algorithms to obtain the maximum QOA assuming a fixed underlying aggregation tree. However, there exists no prior work to address the issue of constructing optimal aggregation tree in deadline-constraints WSNs. The structure of underlying aggregation tree is important since our analysis demonstrates that the ratio between the maximum achievable QOAs of different trees could be as large as O(2 D ), where D is the deadline. This paper casts a combinatorial optimization problem to address the optimal tree construction for deadline-constrained data aggregation in WSNs. While the problem is proved to be NP-hard, we employ the Markov approximation framework and devise two distributed algorithms with different computation overheads to find close-to-optimal solution with bounded approximation gap. To further improve the convergence of the Markov-based algorithms, we devise another initial tree construction algorithm with low-computational complexity. Our experimental results from a set of randomly-generated scenarios demonstrate that the proposed algorithms achieve near optimal performance and appreciably outperform methods that work on a fixed aggregation tree by obtaining better quality of aggregation. |
Hajiesmaili, Mohammad H; Deng, Lei; Chen, Minghua; Li, Zongpeng Incentivizing Device-to-Device Load Balancing for Cellular Networks: An Online Auction Design Journal Article IEEE Journal on Selected Areas in Communications, 35 (2), pp. 265-279, 2017, ISBN: 1558-0008. @article{hajiesmaili2012Incentivizing, title = {Incentivizing Device-to-Device Load Balancing for Cellular Networks: An Online Auction Design}, author = {Mohammad H Hajiesmaili and Lei Deng and Minghua Chen and Zongpeng Li}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/jsac.2017.pdf}, doi = { 10.1109/JSAC.2017.2659558}, isbn = {1558-0008}, year = {2017}, date = {2017-02-01}, journal = {IEEE Journal on Selected Areas in Communications}, volume = {35}, number = {2}, pages = {265-279}, abstract = {The device-to-device load balancing (D2D-LB) paradigm has been advocated in recent small-cell architecture design for cellular networks. The idea is to exploit inter-cell D2D communication and dynamically relay traffic of a busy cell to adjacent under-utilized cells to improve spectrum temporal efficiency, addressing a fundamental drawback of small-cell architecture. Technical challenges of D2D-LB have been studied in previous works. The potential of D2D-LB, however, cannot be fully realized without providing proper incentive mechanism for device participation. In this paper, we address this economical challenge using an online procurement auction framework. In our design, multiple sellers (devices) submit bids to participate in D2D-LB and the auctioneer (cellular service provider) evaluates all the bids and decides to purchase a subset of them to fulfill load balancing requirement with the minimum social cost. Different from similar auction design studies for cellular offloading, battery limit of relaying devices imposes a time-coupled capacity constraint that turns the underlying problem into a challenging multi-slot one. Furthermore, the dynamics in the input to the multi-slot auction problem emphasize the need for online algorithm design. We first tackle the single-slot version of the problem, show that it is NP-hard, and design a polynomial-time offline algorithm with a small approximation ratio. Building upon the single-slot results, we design an online algorithm for the multi-slot problem with sound competitive ratio. Our auction algorithm design ensures that truthful bidding is a dominant strategy for devices. Extensive experiments using real-world traces demonstrate that our proposed solution achieves near offline-optimum and reduces the cost by 45% compared with an alternative heuristic.}, keywords = {}, pubstate = {published}, tppubtype = {article} } The device-to-device load balancing (D2D-LB) paradigm has been advocated in recent small-cell architecture design for cellular networks. The idea is to exploit inter-cell D2D communication and dynamically relay traffic of a busy cell to adjacent under-utilized cells to improve spectrum temporal efficiency, addressing a fundamental drawback of small-cell architecture. Technical challenges of D2D-LB have been studied in previous works. The potential of D2D-LB, however, cannot be fully realized without providing proper incentive mechanism for device participation. In this paper, we address this economical challenge using an online procurement auction framework. In our design, multiple sellers (devices) submit bids to participate in D2D-LB and the auctioneer (cellular service provider) evaluates all the bids and decides to purchase a subset of them to fulfill load balancing requirement with the minimum social cost. Different from similar auction design studies for cellular offloading, battery limit of relaying devices imposes a time-coupled capacity constraint that turns the underlying problem into a challenging multi-slot one. Furthermore, the dynamics in the input to the multi-slot auction problem emphasize the need for online algorithm design. We first tackle the single-slot version of the problem, show that it is NP-hard, and design a polynomial-time offline algorithm with a small approximation ratio. Building upon the single-slot results, we design an online algorithm for the multi-slot problem with sound competitive ratio. Our auction algorithm design ensures that truthful bidding is a dominant strategy for devices. Extensive experiments using real-world traces demonstrate that our proposed solution achieves near offline-optimum and reduces the cost by 45% compared with an alternative heuristic. |
Hajiesmaili, Mohammad H; Chen, Minghua; Mallada, Enrique; Chau, Chi-Kin Crowd-Sourced Storage-Assisted Demand Response in Microgrids Conference Proc. of the Eighth International Conference on Future Energy Systems (ACM eEnergy), Shatin, Hong Kong, 2017, (Short version appeared in ACM Greenmetrics 2017). @conference{hajiesmaili2017crowd, title = {Crowd-Sourced Storage-Assisted Demand Response in Microgrids}, author = {Mohammad H Hajiesmaili and Minghua Chen and Enrique Mallada and Chi-Kin Chau}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/eEnergy2017.pdf}, doi = {10.1145/3077839.3077841}, year = {2017}, date = {2017-01-01}, booktitle = {Proc. of the Eighth International Conference on Future Energy Systems (ACM eEnergy)}, pages = {91–100}, address = {Shatin, Hong Kong}, abstract = {This paper studies the problem of utilizing heterogeneous energy storage systems, including electric vehicles and residential batteries, to perform demand-response in microgrids. The objective is to minimize the operational cost while fulfilling the demand-response requirement. The design space is to select and schedule a subset of available storage devices that are heterogeneous in operating cost, capacity, and availability in time. Designing a performance-optimized solution, however, is challenging due to the combinatorial nature of the problem with mixed packing and covering constraints, and the essential need for online solution design in practical scenarios where both demand-response requirement and the profile of user-owned storage systems arrive online. We tackle these challenges and design several online algorithms by leveraging a recent theoretical computer science technique which uses a problem-specific exponential potential function to solve online mixed packing and covering problems. We show that the fractional version of the algorithm achieves a logarithmic bi-criteria competitive ratio. Empirical trace-driven experiments demonstrate that our algorithms perform much better than the theoretical bounds and achieve close-to-optimal performance.}, note = {Short version appeared in ACM Greenmetrics 2017}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper studies the problem of utilizing heterogeneous energy storage systems, including electric vehicles and residential batteries, to perform demand-response in microgrids. The objective is to minimize the operational cost while fulfilling the demand-response requirement. The design space is to select and schedule a subset of available storage devices that are heterogeneous in operating cost, capacity, and availability in time. Designing a performance-optimized solution, however, is challenging due to the combinatorial nature of the problem with mixed packing and covering constraints, and the essential need for online solution design in practical scenarios where both demand-response requirement and the profile of user-owned storage systems arrive online. We tackle these challenges and design several online algorithms by leveraging a recent theoretical computer science technique which uses a problem-specific exponential potential function to solve online mixed packing and covering problems. We show that the fractional version of the algorithm achieves a logarithmic bi-criteria competitive ratio. Empirical trace-driven experiments demonstrate that our algorithms perform much better than the theoretical bounds and achieve close-to-optimal performance. |
2016 |
Hajiesmaili, Mohammad H; Chau, Chi-Kin; Chen, Minghua; Huang, Longbo Proc. of the Seventh International Conference on Future Energy Systems (ACM eEnergy), Waterloo, Ontario, Canada, 2016, ISBN: 978-1-4503-4393-0, (Best paper candidate). @conference{hajiesmaili2016Online, title = {Online Microgrid Energy Generation Scheduling Revisited: The Benefits of Randomization and Interval Prediction}, author = {Mohammad H Hajiesmaili and Chi-Kin Chau and Minghua Chen and Longbo Huang}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/eEnergy2016.1.pdf}, doi = {10.1145/2934328.2934329}, isbn = {978-1-4503-4393-0}, year = {2016}, date = {2016-01-01}, booktitle = {Proc. of the Seventh International Conference on Future Energy Systems (ACM eEnergy)}, pages = {1:1–1:11}, address = {Waterloo, Ontario, Canada}, abstract = {Energy generation scheduling is a fundamental problem in microgrid design that determines the on/off status and the output level of energy sources with the goal of minimizing the cost and satisfying both electricity and heat demand. The uncertainty in both renewable generation and microgrid demand makes the problem drastically different from its counterparts and in traditional power systems and brings out the essential need of online algorithm design. In the literature, an online deterministic algorithm called CHASE has achieved a competitive ratio of 3, which is the best possible among deterministic algorithms. In addition, it has been shown the accurate prediction can improve performance. This paper revisits the problem by investigating the benefits of randomization and interval prediction, i.e., relaxing accurate prediction assumption by considering an interval of valid ranges for future demand. We propose rCHASE, a randomized algorithm that achieves competitive ratio of around 2.128, improving beyond the best deterministic algorithm. Then, we propose iCHASE, an interval prediction-aware algorithm that is built upon rCHASE and a new extension we developed for the classic ski-rental problem. Our trace-driven experiments demonstrate that iCHASE outperforms CHASE; the average cost reduction of iCHASE is 15.85%, while CHASE reduces the cost by 9.1%.}, note = {Best paper candidate}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Energy generation scheduling is a fundamental problem in microgrid design that determines the on/off status and the output level of energy sources with the goal of minimizing the cost and satisfying both electricity and heat demand. The uncertainty in both renewable generation and microgrid demand makes the problem drastically different from its counterparts and in traditional power systems and brings out the essential need of online algorithm design. In the literature, an online deterministic algorithm called CHASE has achieved a competitive ratio of 3, which is the best possible among deterministic algorithms. In addition, it has been shown the accurate prediction can improve performance. This paper revisits the problem by investigating the benefits of randomization and interval prediction, i.e., relaxing accurate prediction assumption by considering an interval of valid ranges for future demand. We propose rCHASE, a randomized algorithm that achieves competitive ratio of around 2.128, improving beyond the best deterministic algorithm. Then, we propose iCHASE, an interval prediction-aware algorithm that is built upon rCHASE and a new extension we developed for the classic ski-rental problem. Our trace-driven experiments demonstrate that iCHASE outperforms CHASE; the average cost reduction of iCHASE is 15.85%, while CHASE reduces the cost by 9.1%. |
Deng, Lei; Hajiesmaili, Mohammad H; Chen, Minghua; Zeng, Haibo Energy-efficient Timely Transportation of Long-haul Heavy-duty Trucks Conference Proc. of the Seventh International Conference on Future Energy Systems (ACM eEnergy), Waterloo, Ontario, Canada, 2016, ISBN: 978-1-4503-4393-0, (Best paper candidate). @conference{deng2016energy, title = {Energy-efficient Timely Transportation of Long-haul Heavy-duty Trucks}, author = {Lei Deng and Mohammad H Hajiesmaili and Minghua Chen and Haibo Zeng}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/eEnergy.2016.2.pdf}, doi = {10.1145/2934328.2934338}, isbn = {978-1-4503-4393-0}, year = {2016}, date = {2016-01-01}, booktitle = {Proc. of the Seventh International Conference on Future Energy Systems (ACM eEnergy)}, pages = {10:1–10:12}, address = {Waterloo, Ontario, Canada}, abstract = {We consider a timely transportation problem where a heavy-duty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our objective is to minimize the total fuel consumption of the truck, by optimizing both route planning and speed planning. The problem is important for cost-effective and environment-friendly truck operation, and it is uniquely challenging due to its combinatorial nature as well as the need of considering hard deadline constraint. We first show that the problem is NP-Complete; thus exact solution is computational prohibited unless P=NP. We then design a fully polynomial time approximation scheme (FPTAS) that attains an approximation ratio of 1 + ∈ with a network-size induced complexity of O(mn2/∈2), where m and n are the numbers of nodes and edges, respectively. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time when applying to national-wide highway systems with tens of thousands of nodes and edges. Leveraging elegant insights from studying the dual of the original problem, we design a fast heuristic solution with O(m + n log n) complexity. The proposed heuristic allows us to tackle the energy-efficient timely transportation problem on large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of the practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. We carry out extensive numerical experiments using real-world truck data over the actual U.S. highway network. The results show that our proposed solutions achieve 17% (resp. 14%) fuel consumption reduction, as compared to the fastest path (resp. shortest path) algorithm adapted from common practice.}, note = {Best paper candidate}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We consider a timely transportation problem where a heavy-duty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our objective is to minimize the total fuel consumption of the truck, by optimizing both route planning and speed planning. The problem is important for cost-effective and environment-friendly truck operation, and it is uniquely challenging due to its combinatorial nature as well as the need of considering hard deadline constraint. We first show that the problem is NP-Complete; thus exact solution is computational prohibited unless P=NP. We then design a fully polynomial time approximation scheme (FPTAS) that attains an approximation ratio of 1 + ∈ with a network-size induced complexity of O(mn2/∈2), where m and n are the numbers of nodes and edges, respectively. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time when applying to national-wide highway systems with tens of thousands of nodes and edges. Leveraging elegant insights from studying the dual of the original problem, we design a fast heuristic solution with O(m + n log n) complexity. The proposed heuristic allows us to tackle the energy-efficient timely transportation problem on large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of the practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. We carry out extensive numerical experiments using real-world truck data over the actual U.S. highway network. The results show that our proposed solutions achieve 17% (resp. 14%) fuel consumption reduction, as compared to the fastest path (resp. shortest path) algorithm adapted from common practice. |
2015 |
Hajiesmaili, Mohammad H; Talebi, Mohammad Sadegh; Khonsari, Ahmad Utility-optimal dynamic rate allocation under average end-to-end delay requirements Conference Proc. IEEE Conference on Decision and Control (CDC), Osaka, Japan, 2015. @conference{hajiesmaili2015utility, title = {Utility-optimal dynamic rate allocation under average end-to-end delay requirements}, author = {Mohammad H Hajiesmaili and Mohammad Sadegh Talebi and Ahmad Khonsari}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/cdc2015.pdf}, doi = {10.1109/CDC.2015.7402975}, year = {2015}, date = {2015-12-01}, booktitle = {Proc. IEEE Conference on Decision and Control (CDC)}, pages = {4842-4847}, address = {Osaka, Japan}, abstract = {QoS-aware networking applications such as real-time streaming and video surveillance systems require nearly fixed average end-to-end delay over long periods to communicate efficiently, although may tolerate some delay variations in short periods. This variability exhibits complex dynamics that makes rate control of such applications a formidable task. This paper addresses rate allocation for heterogeneous QoS-aware applications that preserves the long-term average end-to-end delay constraint while, similar to Dynamic Network Utility Maximization (DNUM), strives to achieve the maximum network utility aggregated over a fixed time interval. Since capturing temporal dynamics in QoS requirements of sources is allowed in our system model, we incorporate a novel time-coupling constraint in which delay-sensitivity of sources is considered such that a certain end-to-end average delay for each source over a pre-specified time interval is satisfied. We propose DA-DNUM algorithm, as a dual-based solution, which allocates source rates for the next time interval in a distributed fashion, given the knowledge of network parameters in advance. Through numerical experiments, we show that DA-DNUM gains higher average link utilization and a wider range of feasible scenarios in comparison with the best, to our knowledge, rate control schemes that may guarantee such constraints on delay. }, keywords = {}, pubstate = {published}, tppubtype = {conference} } QoS-aware networking applications such as real-time streaming and video surveillance systems require nearly fixed average end-to-end delay over long periods to communicate efficiently, although may tolerate some delay variations in short periods. This variability exhibits complex dynamics that makes rate control of such applications a formidable task. This paper addresses rate allocation for heterogeneous QoS-aware applications that preserves the long-term average end-to-end delay constraint while, similar to Dynamic Network Utility Maximization (DNUM), strives to achieve the maximum network utility aggregated over a fixed time interval. Since capturing temporal dynamics in QoS requirements of sources is allowed in our system model, we incorporate a novel time-coupling constraint in which delay-sensitivity of sources is considered such that a certain end-to-end average delay for each source over a pre-specified time interval is satisfied. We propose DA-DNUM algorithm, as a dual-based solution, which allocates source rates for the next time interval in a distributed fashion, given the knowledge of network parameters in advance. Through numerical experiments, we show that DA-DNUM gains higher average link utilization and a wider range of feasible scenarios in comparison with the best, to our knowledge, rate control schemes that may guarantee such constraints on delay. |
Hajiesmaili, Mohammad H; Mak, Lok To; Wang, Zhi; Wu, Chuan; Chen, Minghua; Khonsari, Ahmad Cost-Effective Low-Delay Cloud Video Conferencing Conference Prof. of IEEE International Conference on Distributed Computing Systems (IEEE ICDCS), Columbus, OH, USA, 2015. @conference{hajiesmaili2015cost, title = {Cost-Effective Low-Delay Cloud Video Conferencing}, author = {Mohammad H Hajiesmaili and Lok To Mak and Zhi Wang and Chuan Wu and Minghua Chen and Ahmad Khonsari}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/icdcs2015.pdf}, doi = {10.1109/ICDCS.2015.19}, year = {2015}, date = {2015-06-01}, booktitle = {Prof. of IEEE International Conference on Distributed Computing Systems (IEEE ICDCS)}, pages = {103-112}, address = {Columbus, OH, USA}, abstract = {The cloud computing paradigm has been advocated in recent video conferencing system design, which exploits the rich on-demand resources spanning multiple geographic regions of a distributed cloud, for better conferencing experience. A typical architectural design in cloud environment is to create video conferencing agents, i.e., Virtual machines, in each cloud site, assign users to the agents, and enable inter-user communication through the agents. Given the diversity of devices and network connectivities of the users, the agents may also transcode the conferencing streams to the best formats and bitrates. In this architecture, two key issues exist on how to effectively assign users to agents and how to identify the best agent to perform a Transcoding task, which are nontrivial due to the following: (1) the existing proximity-based assignment may not be optimal in terms of inter-user delay, which fails to consider the whereabouts of the other users in a conferencing session, (2) the agents may have heterogeneous bandwidth and processing availability, such that the best Transco ding agents should be carefully identified, for cost minimization while best serving all the users requiring the transcoded streams. To address these challenges, we formulate the user-to-agent assignment and Transco ding-agent selection problems, which targets at minimizing the operational cost of the conferencing provider while keeping the conferencing delay low. The optimization problem is combinatorial in nature and difficult to solve. Using Markov approximation framework, we design a decentralized algorithm that provably converges to a bounded neighborhood of the optimal solution. An agent ranking scheme is also proposed to properly initialize our algorithm so as to improve its convergence. The results from a prototype system implementation show that our design in a set of Internet-scale scenarios reduces the operational cost by 77% as compared to a commonly-adopted alternative, while sim… }, keywords = {}, pubstate = {published}, tppubtype = {conference} } The cloud computing paradigm has been advocated in recent video conferencing system design, which exploits the rich on-demand resources spanning multiple geographic regions of a distributed cloud, for better conferencing experience. A typical architectural design in cloud environment is to create video conferencing agents, i.e., Virtual machines, in each cloud site, assign users to the agents, and enable inter-user communication through the agents. Given the diversity of devices and network connectivities of the users, the agents may also transcode the conferencing streams to the best formats and bitrates. In this architecture, two key issues exist on how to effectively assign users to agents and how to identify the best agent to perform a Transcoding task, which are nontrivial due to the following: (1) the existing proximity-based assignment may not be optimal in terms of inter-user delay, which fails to consider the whereabouts of the other users in a conferencing session, (2) the agents may have heterogeneous bandwidth and processing availability, such that the best Transco ding agents should be carefully identified, for cost minimization while best serving all the users requiring the transcoded streams. To address these challenges, we formulate the user-to-agent assignment and Transco ding-agent selection problems, which targets at minimizing the operational cost of the conferencing provider while keeping the conferencing delay low. The optimization problem is combinatorial in nature and difficult to solve. Using Markov approximation framework, we design a decentralized algorithm that provably converges to a bounded neighborhood of the optimal solution. An agent ranking scheme is also proposed to properly initialize our algorithm so as to improve its convergence. The results from a prototype system implementation show that our design in a set of Internet-scale scenarios reduces the operational cost by 77% as compared to a commonly-adopted alternative, while sim… |
Alinia, Bahram; Hajiesmaili, Mohammad H; Khonsari, Ahmad On the Construction of Maximum-Quality Aggregation Trees in Deadline-Constrained WSNs Conference Proc. IEEE Conference on Computer Communications (INFOCOM), Hong Kong, 2015. @conference{alinia2015construction, title = {On the Construction of Maximum-Quality Aggregation Trees in Deadline-Constrained WSNs}, author = {Bahram Alinia and Mohammad H Hajiesmaili and Ahmad Khonsari}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/infocom.2015.pdf}, doi = { 10.1109/INFOCOM.2015.7218386}, year = {2015}, date = {2015-04-01}, booktitle = {Proc. IEEE Conference on Computer Communications (INFOCOM)}, pages = {226-234}, address = {Hong Kong}, abstract = {In deadline-constrained data aggregation in wireless sensor networks (WSNs), the imposed sink deadline in an interference-limited network hinders participation of all sensor nodes in data aggregation. Thus, a subset of nodes can contribute in aggregation and quality of aggregation (QoA) increases with the growth of the number of participating nodes. Scheduling the nodes’ transmissions is a central problem, which aims to maximize the QoA, while satisfying the sink deadline, i.e., on-time delivery of the sensed data to the sink node. Although the previous studies have proposed optimal scheduling algorithms to this problem given a particular aggregation tree, there is no work on constructing optimal tree in this context. The underlying aggregation tree can make a big difference on QoA since we demonstrate that the ratio between the maximum achievable QoAs of different trees could be as large as O(2 D ), where D is the sink deadline. In this paper, we cast an optimization problem to address optimal tree construction for deadline-constrained data aggregation in WSNs. The problem is combinatorial in nature and difficult to solve as we prove its NP-hardness. We employ Markov approximation framework and devise two distributed algorithms with different computation overheads to find bounded close-to-optimal solutions. Simulation experiments in a set of representative randomly-generated scenarios show that the proposed algorithms significantly improve QoA by 101% and 93% on average compared to the best, to our knowledge, existing alternative methods. }, keywords = {}, pubstate = {published}, tppubtype = {conference} } In deadline-constrained data aggregation in wireless sensor networks (WSNs), the imposed sink deadline in an interference-limited network hinders participation of all sensor nodes in data aggregation. Thus, a subset of nodes can contribute in aggregation and quality of aggregation (QoA) increases with the growth of the number of participating nodes. Scheduling the nodes’ transmissions is a central problem, which aims to maximize the QoA, while satisfying the sink deadline, i.e., on-time delivery of the sensed data to the sink node. Although the previous studies have proposed optimal scheduling algorithms to this problem given a particular aggregation tree, there is no work on constructing optimal tree in this context. The underlying aggregation tree can make a big difference on QoA since we demonstrate that the ratio between the maximum achievable QoAs of different trees could be as large as O(2 D ), where D is the sink deadline. In this paper, we cast an optimization problem to address optimal tree construction for deadline-constrained data aggregation in WSNs. The problem is combinatorial in nature and difficult to solve as we prove its NP-hardness. We employ Markov approximation framework and devise two distributed algorithms with different computation overheads to find bounded close-to-optimal solutions. Simulation experiments in a set of representative randomly-generated scenarios show that the proposed algorithms significantly improve QoA by 101% and 93% on average compared to the best, to our knowledge, existing alternative methods. |
Zhang, Ying; Hajiesmaili, Mohammad Hassan; Chen, Minghua Peak-Aware Online Economic Dispatching for Microgrids Conference Proc.of the Sixth International Conference on Future Energy Systems (ACM eEnergy), Bangalore, India, 2015, (Best paper candidate). @conference{zhang2015peak, title = {Peak-Aware Online Economic Dispatching for Microgrids}, author = {Ying Zhang and Mohammad Hassan Hajiesmaili and Minghua Chen}, url = {https://groups.cs.umass.edu/hajiesmaili/wp-content/uploads/sites/24/2020/01/eEnergy.2015.pdf}, doi = {10.1145/2768510.2768538}, year = {2015}, date = {2015-01-01}, booktitle = {Proc.of the Sixth International Conference on Future Energy Systems (ACM eEnergy)}, pages = {27–36}, address = {Bangalore, India}, abstract = {By employing local renewable energy sources and power generation units while connected to the central grid, microgrid can usher in great benefits in terms of cost efficiency, power reliability, and environmental awareness. Economic dispatching is a central problem in microgrid operation, which aims at effectively scheduling various energy sources to minimize the operating cost while satisfying the electricity demand. Designing intelligent economic dispatching strategies for microgrids, however, is drastically different from that for conventional central grids, due to two unique challenges. First, the erratic renewable energy emphasizes the need for online algorithms. Second, the widely-adopted peak-based pricing scheme brings out the need for new peak-aware strategy design. In this paper, we tackle these critical challenges and devise peak-aware online economic dispatching algorithms. For microgrids with fast-responding generators, we prove that our deterministic and randomized algorithms achieve the best possible competitive ratios 2 – β and e/(e – 1 + β), respectively, where β ∈ [0,1] is the ratio between the minimum grid spot price and the local-generation price. Our results characterize the fundamental price of uncertainty of the problem. For microgrids with slow-responding generators, we first show that a large competitive ratio is inevitable. Then we leverage limited prediction of electricity demand and renewable generation to improve the competitiveness of the algorithms. By extensive empirical evaluations using real-world traces, we show that our online algorithms achieve near offline-optimal performance. In a representative scenario, our algorithm achieves 23% and 11% cost reduction as compared to the case without local generation units and the case using peak-oblivious algorithms, respectively. }, note = {Best paper candidate}, keywords = {}, pubstate = {published}, tppubtype = {conference} } By employing local renewable energy sources and power generation units while connected to the central grid, microgrid can usher in great benefits in terms of cost efficiency, power reliability, and environmental awareness. Economic dispatching is a central problem in microgrid operation, which aims at effectively scheduling various energy sources to minimize the operating cost while satisfying the electricity demand. Designing intelligent economic dispatching strategies for microgrids, however, is drastically different from that for conventional central grids, due to two unique challenges. First, the erratic renewable energy emphasizes the need for online algorithms. Second, the widely-adopted peak-based pricing scheme brings out the need for new peak-aware strategy design. In this paper, we tackle these critical challenges and devise peak-aware online economic dispatching algorithms. For microgrids with fast-responding generators, we prove that our deterministic and randomized algorithms achieve the best possible competitive ratios 2 – β and e/(e – 1 + β), respectively, where β ∈ [0,1] is the ratio between the minimum grid spot price and the local-generation price. Our results characterize the fundamental price of uncertainty of the problem. For microgrids with slow-responding generators, we first show that a large competitive ratio is inevitable. Then we leverage limited prediction of electricity demand and renewable generation to improve the competitiveness of the algorithms. By extensive empirical evaluations using real-world traces, we show that our online algorithms achieve near offline-optimal performance. In a representative scenario, our algorithm achieves 23% and 11% cost reduction as compared to the case without local generation units and the case using peak-oblivious algorithms, respectively. |
2012 |
Hajiesmaili, Mohammad H; Khonsari, Ahmad; Sehati, Ali; Talebi, Sadegh M Content-aware rate allocation for efficient video streaming via dynamic network utility maximization Journal Article Journal of Network and Computer Applications, 35 (6), pp. 2016–2027, 2012. @article{hajiesmaili2012content, title = {Content-aware rate allocation for efficient video streaming via dynamic network utility maximization}, author = {Mohammad H Hajiesmaili and Ahmad Khonsari and Ali Sehati and Sadegh M Talebi}, year = {2012}, date = {2012-01-01}, journal = {Journal of Network and Computer Applications}, volume = {35}, number = {6}, pages = {2016–2027}, keywords = {}, pubstate = {published}, tppubtype = {article} } |
2009 |
Talebi, Sadegh M; Khonsari, Ahmad; Hajiesmaili, Mohammad H; Jafarpour, Sina A Suboptimal Network Utility Maximization Approach for Scalable Multimedia Applications Inproceedings Proc. of IEEE Global Telecommunications Conference, pp. 1-6, 2009. @inproceedings{5425607, title = {A Suboptimal Network Utility Maximization Approach for Scalable Multimedia Applications}, author = {Sadegh M Talebi and Ahmad Khonsari and Mohammad H Hajiesmaili and Sina Jafarpour}, year = {2009}, date = {2009-11-01}, booktitle = {Proc. of IEEE Global Telecommunications Conference}, pages = {1-6}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Talebi, Sadegh M; Khonsari, Ahmad; Hajiesmaili, Mohammad H Optimization bandwidth sharing for multimedia transmission supporting scalable video coding Inproceedings Proc. of IEEE Conference on Local Computer Networks, pp. 185-192, 2009. @inproceedings{talebi2009optimization, title = {Optimization bandwidth sharing for multimedia transmission supporting scalable video coding}, author = {Sadegh M Talebi and Ahmad Khonsari and Mohammad H Hajiesmaili}, year = {2009}, date = {2009-10-01}, booktitle = {Proc. of IEEE Conference on Local Computer Networks}, pages = {185-192}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |