Bissan Ghaddar

• Ghaddar, B.; Ljubic, I.; Qiu, Y., (Forthcoming), "Three network design problems for community energy storage", Networks
  Abstract: In this article, we develop novel mathematical models to optimize utilization of community energy storage (CES) by clustering prosumers and consumers into energy sharing communities/microgrids in the context of a smart city. Three different microgrid configurations are modeled using a unifying mixed-integer linear programming formulation. These configurations represent three different business models, namely: the island model, the interconnected model, and the Energy Service Companies model. The proposed mathematical formulations determine the optimal households' aggregation as well as the location and sizing of CES. To overcome the computational challenges of treating operational decisions within a multi-period decision making framework, we also propose a decomposition approach to accelerate the computational time needed to solve larger instances. We conduct a case study based on real power consumption, power generation, and location network data from Cambridge, MA. Our mathematical models and the underlying algorithmic framework can be used in operational and strategic planning studies on smart grids to incentivize the communitarian distributed renewable energy generation and to improve the self-consumption and self-sufficiency of the energy sharing community. The models are also targeted to policymakers of smart cities, utility companies, and Energy Service Companies as the proposed models support decision making on renewable energy related projects investments.

  Link(s) to publication:

  http://dx.doi.org/10.1002/net.22242

• Jeong, J.; Premsankar, G.; Ghaddar, B.; Tarkoma, S., 2024, "A robust optimization approach for placement of applications in edge computing considering latency uncertainty", Omega, July 126
  Abstract: Edge computing brings computing and storage resources close to end-users to support new applications and services that require low network latency. It is currently used in a wide range of industries, from industrial automation and augmented reality, to smart cities and connected vehicles, where low latency, data privacy, and real-time processing are critical requirements. The latency of accessing applications in edge computing must be consistently below a threshold of a few tens of milliseconds to maintain an acceptable experience for end-users. However, the latency between users and applications can vary considerably depending on the network load and mode of wireless access. An application provider must be able to guarantee that requests are served in a timely manner by their application instances hosted in the edge despite such latency variations. This article focuses on the placement and traffic allocation problem faced by application providers in determining where to place application instances on edge nodes such that requests are served within a certain deadline. It proposes novel formulations based on robust optimization to provide optimal plans that protect against latency variations in a configurable number of network links. The robust formulations are based on two different types of polyhedral uncertainty sets that offer different levels of protection against variations in latency. Extensive simulations show that our robust models are able to keep the number of chosen edge nodes low while reducing the number of latency violations as compared to a deterministic optimization model that only considers the average latency of network links.

  Link(s) to publication:

  http://dx.doi.org/10.1016/j.omega.2024.103064

• Jeong, J.; Ghaddar, B.; Zufferey, N.; Nathwani, J., 2024, "Adaptive robust electric vehicle routing under energy consumption uncertainty", Transportation Research Part C: Emerging Technologies, March 160
  Abstract: Electric vehicles (EVs) have been highly favoured as a mode of transportation in recent years. EVs offer numerous benefits over traditional fuel-based vehicles, particularly in terms of the environmental impact. Although electric vehicles offer several advantages, there are certain restrictions that limit their usage. One of the significant issues is the uncertainty in their driving range. The driving range of EVs is closely related to their energy consumption, which is highly affected by exogenous and endogenous factors. Since those factors are unpredictable, uncertainty in EVs’ energy consumption should be considered for efficient operation. This paper proposes a two-stage adaptive robust optimization framework for the electric vehicle routing problem. The objective is to minimize the worst-case energy consumption while guaranteeing that services are delivered at the appointed time windows without battery level deficiency. We postulate that EVs can be recharged on route, and the charging amount can be adjusted depending on the circumstances. A column-and-constraint generation based heuristic algorithm, which is coupled with variable neighbourhood search and alternating direction algorithm, is proposed to solve the resulting model. The computational results show the economic efficiency and robustness of the proposed model, and that there is a tradeoff between the total required energy and the risk of failing to satisfy all customers’ demand.

  Link(s) to publication:

  http://dx.doi.org/10.1016/j.trc.2024.104529

• Ghaddar, B.; Gómez-Casares, I.; González-Díaz, J.; González-Rodríguez, B.; Pateiro-López, B.; Rodríguez-Ballesteros, S., 2023, "Learning for Spatial Branching: An Algorithm Selection Approach", INFORMS Journal on Computing, September 35(5): 1024 - 1043.
  Abstract: The use of machine learning techniques to improve the performance of branch-and-bound optimization algorithms is a very active area in the context of mixed integer linear problems, but little has been done for nonlinear optimization. To bridge this gap, we develop a learning framework for spatial branching and show its efficacy in the context of the Reformulation-Linearization Technique for polynomial optimization problems. The proposed learning is performed offline, based on instance-specific features and with no computational overhead when solving new instances. Novel graph-based features are introduced, which turn out to play an important role for the learning. Experiments on different benchmark instances from the literature show that the learning-based branching rule significantly outperforms the standard rules.History: Accepted by Andrea Lodi, Area Editor/Design FEDER [MTM2014-60191-JIN]; Spanish Ministry of Education [FPU Grant 17/02643, FPU Grant 20/01555]; Conselleria de Cultura, Educacion e Universidade [ED431C 2021/24]; Natural Sciences and Engineering Research Council of Canada [Discovery Grant 2017-04185]; Spanish Ministry of Science and Technology [MTM2017-87197-C3] and Spanish Ministry of Science and Innovation [PID2021-124030NB-C32].

  Link(s) to publication:

  https://doi.org/10.1287/ijoc.2022.0090

  http://dx.doi.org/10.1287/ijoc.2022.0090

• Kuryatnikova, O.; Ghaddar, B.; Molzahn, D. K., 2023, "Two-Stage Robust Quadratic Optimization with Equalities and Its Application to Optimal Power Flow", SIAM Journal on Optimization, May 33(4): 2830 - 2857.
  Abstract: Abstract. In this work, we consider two-stage quadratic optimization problems under ellipsoidal uncertainty. In the first stage, one needs to decide upon the values of a subset of optimization variables (control variables). In the second stage, the uncertainty is revealed, and the rest of the optimization variables (state variables) are set up as a solution to a known system of possibly nonlinear equations. This type of problem occurs, for instance, in optimization for dynamical systems, such as electric power systems as well as gas and water networks. We propose a convergent iterative algorithm to build a sequence of approximately robustly feasible solutions with an improving objective value. At each iteration, the algorithm optimizes over a subset of the feasible set and uses affine approximations of the second-stage equations while preserving the nonlinearity of other constraints. We implement our approach and demonstrate its performance on Matpower instances of AC optimal power flow. Although this paper focuses on quadratic problems, the approach is suitable for more general setups.

  Link(s) to publication:

  https://doi.org/10.1137/22M1469651

  http://dx.doi.org/10.1137/22M1469651

• Lin, B.; Ghaddar, B.; Nathwani, J., 2022, "Deep Reinforcement Learning for the Electric Vehicle Routing Problem With Time Windows", IEEE Transactions On Intelligent Transportation Systems, August 23(8): 11528 - 11538.
  Abstract: The past decade has seen a rapid penetration of electric vehicles (EVs) as more and more logistics and transportation companies start to deploy electric vehicles (EVs) for service provision. In order to model the operations of a commercial EV fleet, we utilize the EV routing problem with time windows (EVRPTW). In this paper, we propose an end-to-end deep reinforcement learning framework to solve the EVRPTW. In particular, we develop an attention model incorporating the pointer network and a graph embedding layer to parameterize a stochastic policy for solving the EVRPTW. The model is then trained using policy gradient with rollout baseline. Our numerical studies show that the proposed model is able to efficiently solve EVRPTW instances of large sizes that are not solvable with current existing approaches.

  Link(s) to publication:

  http://dx.doi.org/10.1109/TITS.2021.3105232

• Chang, H. C.; Ghaddar, B.; Nathwani, J., 2022, "Shared Community Energy Storage Allocation and Optimization", Applied Energy, July 318
  Abstract: Distributed Energy Resources have been playing an increasingly important role in smart grids. Distributed Energy Resources consist primarily of energy generation and storage systems utilized by individual households or shared among them as a community. In contrast to individual energy storage, the field of community energy storage is now gaining more attention in various countries. However, existing models are either tailored towards optimizing the operations of individual energy storage or do not consider the notion of sharing energy storage within a community. This paper proposes a framework to allocate shared energy storage within a community and to then optimize the operational cost of electricity using a mixed integer linear programming formulation. The allocation options of energy storage include private energy storage and three options of community energy storage: random, diverse, and homogeneous allocation. With various load options of appliances, photovoltaic generation and energy storage set-ups, the operational cost of electricity for the households is minimized to provide the optimal operation scheduling. Computational results are presented on two real use cases in the cities of Ennis, Ireland and Waterloo, Canada, to show the advantage of using community energy storage as opposed to private energy storage and to evaluate the cost savings which can facilitate future deployment of community energy storage. In addition to the electricity operational cost, energy storage utilization and operation fairness are used to compare different allocation options of storage systems.

  Link(s) to publication:

  http://dx.doi.org/10.1016/j.apenergy.2022.119160

• Lin, B.; Ghaddar, B.; Nathwani, J., 2021, "Electric vehicle routing with charging/discharging under time-variant electricity prices", Transportation Research Part C-Emerging Technologies, September 130: 103285 - 103285.
  Abstract: The integration of electric vehicles (EVs) with the energy grid has become an important area of research due to the increasing EV penetration in today’s transportation systems. Under appropriate management of EV charging and discharging, the grid can currently satisfy the energy requirements of a considerable number of EVs. Furthermore, EVs can help enhance the reliability and stability of the energy grid through ancillary services such as energy storage. This paper proposes the EV routing problem with time windows under time-variant electricity prices (EVRPTW-TP) which optimizes the routing of an EV fleet that are delivering products to customers, jointly with the scheduling of the charging and discharging of the EVs from/to the grid. The proposed model is a multiperiod vehicle routing problem where EVs can stop at charging stations to either recharge their batteries or inject stored energy to the grid. Given the energy costs that vary based on time-of-use, the charging and discharging schedules of the EVs are optimized to benefit from the capability of storing energy by shifting energy demands from peak hours to off-peak hours when the energy price is lower. The vehicles can recover the energy costs and potentially realize profits by injecting energy back to the grid at high price periods. EVRPTW-TP is formulated as an optimization problem. A Lagrangian relaxation approach and a hybrid variable neighborhood search/tabu search heuristic are proposed to obtain high quality lower bounds and feasible solutions, respectively. Numerical experiments on instances from the literature are provided. The proposed heuristic is also evaluated on a case study of an EV fleet providing grocery delivery at the region of Kitchener-Waterloo in Ontario, Canada. Insights on the impacts of energy pricing, service time slots, range reduction in winter as well as fleet size are presented.

  Link(s) to publication:

  http://dx.doi.org/10.1016/j.trc.2021.103285

• Premsankar, G.; Ghaddar, B.; Slabicki, M.; Francesco, M. D., 2020, "Optimal Configuration of LoRa Networks in Smart Cities", IEEE Transactions on Industrial Informatics, December 16(12): 7243 - 7254.
  Abstract: Long range (LoRa) is a wireless communication standard specifically targeted for resource-constrained Internet of Things (IoT) devices. LoRa is a promising solution for smart city applications as it can provide long-range connectivity with a low energy consumption. The number of LoRa-based networks is growing due to its operation in the unlicensed radio bands and the ease of network deployments. However, the scalability of such networks suffers as the number of deployed devices increases. In particular, the network performance drops due to increased contention and interference in the unlicensed LoRa radio bands. This results in an increased number of dropped messages and, therefore, unreliable network communications. Nevertheless, network performance can be improved by appropriately configuring the radio parameters of each node. To this end, in this article we formulate integer linear programming models to configure LoRa nodes with the optimal parameters that allow all devices to reliably send data with a low energy consumption. We evaluate the performance of our solutions through extensive network simulations considering different types of realistic deployments. We find that our solution consistently achieves a higher delivery ratio (up to 8% higher) than the state of the art with minimal energy consumption. Moreover, the higher delivery ratio is achieved by a large percentage of nodes in each network, thereby resulting in a fair allocation of radio resources. Finally, the optimal network configurations are obtained within a short time, usually much faster than the state of the art. Thus, our solution can be readily used by network operators to determine optimal configurations for their IoT deployments, resulting in improved network reliability.

  Link(s) to publication:

  http://dx.doi.org/10.1109/tii.2020.2967123

• Ustun, T. S.; Hussain, S. M. S.; Kirchhoff, H.; Ghaddar, B.; Strunz, K.; Lestas, I., 2019, "Data Standardization for Smart Infrastructure in First-Access Electricity Systems", Proceedings of the IEEE, September 107(9): 1790 - 1802.
  Abstract: Recent developments in renewable energy and information technology (IT) fields made it easier to set up power systems at a smaller scale. This proved to be a turning point for developing first-access electricity systems for the underserved locations around the world. However, there are planning and operation challenges due to lack of past data on such places. Deployment of Internet-of-Things (IoT) devices and proliferation of smart infrastructures with additional sensors will lead to tremendous opportunities for gathering very useful data. For different stakeholders to access and manage these data, trusted and standardized mechanisms need to be in place. Storing proper data in a well-structured common format allows for collaborative research across disciplines, large-scale analytics, and sharing of algorithms and methodologies, in addition to improved customer service. Data standardization plays a more vital role in the context of electricity access in the underdeveloped countries, where there is no past data on generation or consumption as in utility grids. Data collected in a standard structure, being it for a short period of time, facilitate learning from the past experiences, monitoring the current projects, and delivering better results in the future endeavors. It will result in ways to better assist consumers and help the industry operate more efficiently by sharing data with different stakeholders. It can also enhance competition, thus making electricity accessible faster and to more people. The focus of this article is data standardization for first-access electricity systems, in general, and renewable energy-based microgrids, in particular. Different data sources and ways that the corresponding data can be exploited, technological and capacity constraints for storage of data, political and governance implications, as well as data security and privacy issues, are examined. This article is relevant to different stakeholders, such as investors, public utilities, nongovernmental organizations (NGOs), and communities. Using the data standardization approach developed here, it is possible to create a much-needed first-access electricity system database. This will provide an important resource for project developers and energy companies to assess the potential of a certain unelectrified site, estimating its demand growth in time and establishing universal control systems that can seamlessly communicate with different components

  Link(s) to publication:

  http://dx.doi.org/10.1109/JPROC.2019.2929621

• Kuang, X.; Ghaddar, B.; Naoum-Sawaya, J.; Zuluaga, L. F., 2019, "Alternative SDP and SOCP approximations for polynomial optimization", EURO Journal on Computational Optimization, June 7(2): 153 - 175.
  Abstract: In theory, hierarchies of semidefinite programming (SDP) relaxations based on sum of squares (SOS) polynomials have been shown to provide arbitrarily close approximations for a general polynomial optimization problem (POP). However, due to the computational challenge of solving SDPs, it becomes difficult to use SDP hierarchies for large-scale problems. To address this, hierarchies of second-order cone programming (SOCP) relaxations resulting from a restriction of the SOS polynomial condition have been recently proposed to approximate POPs. Here, we consider alternative ways to use the SOCP restrictions of the SOS condition. In particular, we show that SOCP hierarchies can be effectively used to strengthen hierarchies of linear programming relaxations for POPs. Specifically, we show that this solution approach is substantially more effective in finding solutions of certain POPs for which the more common hierarchies of SDP relaxations are known to perform poorly. Furthermore, when the feasible set of the POP is compact, these SOCP hierarchies converge to the POP’s optimal value.

  Link(s) to publication:

  http://dx.doi.org/10.1007/s13675-018-0101-2

• Ghaddar, B.; Jabr, R. A., 2019, "Power transmission network expansion planning: A semidefinite programming branch-and-bound approach", European Journal of Operational Research, May 274(3): 837 - 844.
  Abstract: Transmission network expansion planning is a mixed-integer optimization problem, whose solution is used to guide future investment in transmission equipment. An approach is presented to find the global optimal solution of the transmission planning problem using an AC network model. The approach builds on the semidefinite relaxation of the AC optimal power flow problem (ACOPF); its computational engine is a specialized branch-and-bound algorithm for transmission expansion planning to deal with the underlying mixed-integer ACOPF problem. Valid inequalities that are based on specific knowledge of the expansion problem are employed to improve the solution quality at any node of the search tree, and thus significantly reduce the overall computational effort of the branch-and-bound algorithm. Additionally, sparsity of the semidefinite relaxation is exploited to further reduce the computation time at each node of the branch-and-bound tree. Despite the vast number of publications on transmission expansion planning, the proposed approach is the first to provide expansion plans that are globally optimal using a solution approach for the mixed-integer ACOPF problem. The results on standard networks serve as important benchmarks to assess the solution quality from existing techniques and simplified models.

  Link(s) to publication:

  http://dx.doi.org/10.1016/j.ejor.2018.10.035

• Gambella,, C.; Naoum-Sawaya, J.; Ghaddar, B., 2018, "The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches", INFORMS Journal on Computing, August 30(3): 554 - 569.
  Abstract: This paper addresses a generalization of the vehicle routing problem in which the pick-up locations of the targets are nonstationary. We refer to this problem as the vehicle routing problem with floating targets and the main characteristic is that targets are allowed to move from their initial home locations while waiting for a vehicle. This problem models new applications in drone routing, ridesharing, and logistics where a vehicle agrees to meet another vehicle or a customer at a location that is away from the designated home location. We propose a Mixed Integer Second Order Cone Program (MISOCP) formulation for the problem, along with valid inequalities for strengthening the continuous relaxation. We further exploit the problem structure using a Lagrangian decomposition and propose an exact branch-and-price algorithm. Computational results on instances with varying characteristics are presented and the results are compared to the solution of the full problem using CPLEX. The proposed valid inequalities reduce the computational time of CPLEX by up to 30% on average while the proposed branch and price is capable of solving instances where CPLEX fails in finding the optimal solution within the imposed time limit.

  Link(s) to publication:

  http://dx.doi.org/10.1287/ijoc.2017.0800

• Ghaddar, B.; Naoum-Sawaya, J., 2018, "High Dimensional Data Classification and Feature Selection using Support Vector Machines", European Journal of Operational Research, March 265(3): 993 - 1004.
  Abstract: In many big-data systems, large amounts of information are recorded and stored for analytics purposes. Often however, this vast amount of information does not offer additional benefits for optimal decision making, but may rather be complicating and too costly for collection, storage, and processing. For instance, tumor classification using high-throughput microarray data is challenging due to the presence of a large number of noisy features that do not contribute to the reduction of classification errors. For such problems, the general aim is to find a limited number of genes that highly differentiate among the classes. Thus in this paper, we address a specific class of machine learning, namely the problem of feature selection within support vector machine classification that deals with finding an accurate binary classifier that uses a minimal number of features. We introduce a new approach based on iteratively adjusting a bound on the l1-norm of the classifier vector in order to force the number of selected features to converge towards the desired maximum limit. We analyze two real-life classification problems with high dimensional features. The first case is the medical diagnosis of tumors based on microarray data where we present a generic approach for cancer classification based on gene expression. The second case deals with sentiment classification of on-line reviews from Amazon, Yelp, and IMDb. The results show that the proposed classification and feature selection approach is simple, computationally tractable, and achieves low error rates which are key for the construction of advanced decision-support systems.

  Link(s) to publication:

  https://doi.org/10.1016/j.ejor.2017.08.040

• Naoum-Sawaya, J.; Ghaddar, B., 2017, "Cutting plane approach for the maximum flow interdiction problem", Journal of the Operational Research Society, December 68(12): 1553 - 1569.
  Abstract: The maximum flow interdiction is a class of leaderfollower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.

  Link(s) to publication:

  http://dx.doi.org/10.1057/s41274-017-0185-8

For more publications please see our Research Database