Bissan Ghaddar

• 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, December 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

• 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

• 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: 1 - 11.
  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

• Gambella, G.; Ghaddar, B.; Naoum-Sawaya, J., 2021, "Optimization Problems for Machine Learning: A Survey", European Journal of Operational Research, May 290(3): 807 - 828.
  Abstract: This paper surveys the machine learning literature and presents in an optimization framework several commonly used machine learning approaches. Particularly, mathematical optimization models are presented for regression, classification, clustering, deep learning, and adversarial learning, as well as new emerging applications in machine teaching, empirical model learning, and Bayesian network structure learning. Such models can benefit from the advancement of numerical optimization techniques which have already played a distinctive role in several machine learning settings. The strengths and the shortcomings of these models are discussed and potential research directions and open problems are highlighted.

  Link(s) to publication:

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

• 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

• Kuang, X.; Ghaddar, B.; Naoum-Sawaya, J.; Zuluaga, K., 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 to general polynomial optimization problems (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 these SOCP restriction of the SOS condition. In particular, we show that SOCP hierarchies can be effectively used to strengthen hierarchies of linear programming (LP) 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. Also, we use hierarchies of LP relaxations for POPs that allows us to show that the SOCP approach can be used to obtain hierarchies of SOCPs that converge to the optimal value of the POP when its feasible set is compact. Additionally, we show that the SOCP approach can be used to address the solution of the fundamental alternating current optimal power flow (ACOPF) problem. In particular, we show that the first-order SOCP hierarchy obtained by weakening the more common hierarchy of SDP relaxations for this problem is equivalent to solving the conic dual of the SOCP approximations recently proposed to address the ACOPF problem. Through out the article, we illustrate our findings with relevant experimental results. In the case of the ACOPF problem, we use well-known instances of the problem that appear in the related literature.

  Link(s) to publication:

  https://www.researchgate.net/publication/283247186_Alternative_Linear_and_Second-order_Cone_Approximation_Approaches_for_Polynomial_Optimization

  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

• Ghaddar, B.; Claeys, M.; Mevissen, M.; Eck, B., 2017, "Polynomial optimization for water networks: Global solutions for the valve setting problem", European Journal of Operational Research, September 261(2): 450 - 459.
  Abstract: This paper explores polynomial optimization techniques for two formulations of the energy conservation constraint for the valve setting problem in water networks. The sparse hierarchy of semidefinite programing relaxations is used to derive globally optimal bounds for an existing cubic and a new quadratic problem formulation. Both formulations use an approximation for friction loss that has an accuracy consistent with the experimental error of the classical equations. Solutions using the proposed approach are reported on four water networks ranging in size from 4 to 2000 nodes and are compared against a local solver, Ipopt and a global solver, Couenne. Computational results found global solutions using both formulations with the quadratic formulation having better time efficiency due to the reduced degree of the polynomial optimization problem and the sparsity of the constraint matrix. The approaches presented in this paper may also allow global solutions to other water network steady-state optimization problems formulated with continuous variables.

  Link(s) to publication:

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

For more publications please see our Research Database