Joe Naoum-Sawaya

• Fukasawa, R.; Naoum-Sawaya, J.; Oliveira, D., 2024, "The Price-elastic Knapsack Problem", Omega (Oxford), April 124: 103003 - 103003.
  Abstract: This paper introduces the price-elastic knapsack problem (PEKP), an extension of the classic knapsack problem where instead of fixed item characteristics, the weight of each item and the profit from including an item in the knapsack are a function of a parameter, namely the price. PEKP is first formulated as a generic nonlinear optimization problem and three special cases are investigated. First, we show a polynomial-time solvable case. Next, we formulate the case where the item weights are affine-linear functions as a quadratic program. The computational results show that solving the quadratic program to optimality is computationally challenging, and thus, an approach that decomposes the problem into three mixed integer programs is proposed. Similarly, the case where the weights of the items are piecewise-linear functions is investigated and a quadratic formulation is proposed. A solution approach based on decomposing the problem into three mixed integer programs that are solved independently is also proposed. Using randomly generated instances of varying sizes, the computational results show that the proposed decomposition leads to significant computational advantages compared to solving the quadratic program in the cases of affine-linear and piecewise-linear functions.

  Link(s) to publication:

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

• Manias, D. M.; Shaer, I.; Naoum-Sawaya, J.; Shami, A., 2024, "Robust and Reliable SFC Placement in Resource-Constrained Multi-Tenant MEC-Enabled Networks", IEEE Transactions on Network and Service Management, February 21(1): 187 - 199.
  Abstract: With the rapid development and incoming implementation of 5G networks, many use cases, such as Intelligent Transportation Systems (ITS), are being realized. Utilizing networking technologies, including Network Function Virtualization and Mobile Edge Computing, along with 5G network slicing, the Next-Generation Service Placement Problem (NGSPP) is gaining significant attention due to the criticality of its services and its resource-constrained network nodes. The placement of services on Next-Generation (NG) networks has inherent challenges, mainly ultra-low latency requirements and the complexity of NG network management and orchestration. A candidate solution to the NGSPP should provide a placement that adheres to the strict Quality of Service (QoS) requirements. This work presents the formulation of a robust optimization problem that optimizes the high-availability placement of applications in resource-constrained and multi-tenant NG networks, which complies with QoS requirements and is capable of protecting the performance of the solution under adverse conditions. Finally, a set of hierarchical clustering-based heuristic algorithms, which reduce the time-complexity of the solution are proposed. Results demonstrate that formulating the robust solution is a proactive method of injecting resilience into the system and can preserve performance across various levels of system uncertainty.

  Link(s) to publication:

  http://dx.doi.org/10.1109/tnsm.2023.3293027

• Naoum-Sawaya, J.; Elhedhli, S.; De Carvalho, P., 2023, "Strategic Blockchain Adoption to Deter Deceptive Counterfeiters", European Journal of Operational Research, November 311(1): 373 - 386.
  Abstract: Counterfeiting is an ever growing problem worldwide which is exacerbated by the ease of access through e-commerce and online shopping. This calls for innovative technologies, such as blockchain, to identify, track, and prevent fake products from reaching consumers, especially for vital sectors such as the drug industry, which is the main motivation for this work. We investigate the strategic implications of using blockchain technology to deter counterfeiters. We particularly focus on the case of deceptive counterfeits that infiltrate legitimate distribution channels. Deceptive counterfeits lack the quality of genuine products and may pose immense health and safety risks to consumers who are unable to distinguish them from genuine products at the time of purchase. In contrast to prior literature that assumes that blockchain eliminates deceptive counterfeiting, we present a model that realistically considers blockchain as a technology that increases the capability of detecting counterfeits. This capability nonetheless comes at an increasing cost that may financially discourage genuine manufacturers from adopting the technology. The presented model shows that blockchain is not always financially beneficial and demonstrates that manufacturers can strategically balance between product quality and investment in blockchain to combat counterfeiting. Furthermore, our results demonstrate that, with the availability of blockchain, genuine manufacturers may be less interested to differentiate products based on quality, but rather rely on blockchain to block counterfeits.

  Link(s) to publication:

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

• Manias, D. M.; Naoum-Sawaya, J.; Shami, A.; Javadtalab, A.; Hemmati, M.; You, Y., 2023, "Robust Traffic Grooming and Infrastructure Placement in OTN-over-DWDM Networks", Journal of Optical Communications and Networking, August 15(8): 553 - 553.
  Abstract: The advent of next-generation networks has revolutionized modern networking practices through its improved service capability as well as its numerous emerging use cases. Coupled with the increasing number of connected devices, 5G and beyond (5G+) network traffic is expected to be increasingly diverse and high in volume. To address the large amount of data exchanged between the 5G+ core and external data networks, optical transport networks (OTNs) with dense wavelength-division multiplexing (DWDM) will be leveraged. In order to prepare for this increase in traffic, network operators (NOs) must develop and expand their existing backbone networks, requiring significant levels of capital expenditures. To this end, the traffic grooming and infrastructure placement problem is critical to supporting NO decisions. The work presented in this paper considers the traffic grooming and infrastructure placement problem for OTN-over-DWDM networks. The dynamicity and diversity of 5G+ network traffic are addressed through the use of robust optimization, allowing for increasing levels of solution conservativeness to protect against various levels of demand uncertainty. Furthermore, a robust traffic grooming and infrastructure placement heuristic (RGIP-H) solution capable of addressing the scalability concerns of the optimization problem formulation is presented. The results presented in this work demonstrate how the tuning of the robust parameters affects the cost of the objective function. Additionally, the ability of the robust solution to protect the solution under demand uncertainty is highlighted when the robust and deterministic solutions are compared during parameter deviation trials. Finally, the performance of the RGIP-H is compared to the optimization models when applied to larger network sizes.

  Link(s) to publication:

  http://dx.doi.org/10.1364/jocn.486838

• Manias, D. M.; Javadtalab, A.; Naoum-Sawaya, J.; Shami, A., 2023, "The Role of Optical Transport Networks in 6G and Beyond: A Vision and Call to Action", Journal of Sensor and Actuator Networks, May 12(3)
  Abstract: As next-generation networks begin to take shape, the necessity of Optical Transport Networks (OTNs) in helping achieve the performance requirements of future networks is evident. Future networks are characterized as being data-centric and are expected to have ubiquitous artificial intelligence integration and deployment. To this end, the efficient and timely transportation of fresh data from producer to consumer is critical. The work presented in this paper outlines the role of OTNs in future networking generations. Furthermore, key emerging OTN technologies are discussed. Additionally, the role intelligence will play in the Management and Orchestration (MANO) of next-generation OTNs is discussed. Moreover, a set of challenges and opportunities for innovation to guide the development of future OTNs is considered. Finally, a use case illustrating the impact of network dynamicity and demand uncertainty on OTN MANO decisions is presented.

  Link(s) to publication:

  http://dx.doi.org/10.3390/jsan12030043

• de Carvalho, P. R. V.; Naoum-Sawaya, J.; Elhedhli, S., 2022, "Blockchain-Enabled supply chains: An application in fresh-cut flowers", Applied Mathematical Modelling, October 110: 841 - 858.
  Abstract: Supply chains have often benefited from breakthroughs in information technology. Blockchain, in particular, is a recent technology that is promising to revolutionize the way supply chains are designed and operated. This paper proposes a framework to optimize the adoption of blockchain jointly with the design of the supply chain network. A new form of product differentiation is enabled through blockchain adoption where blockchain-certified products are sold at a premium price to a growing segment of customers. The proposed framework allows supply chain managers to monetize data which has traditionally been used to improve supply chain efficiency. The framework is evaluated using a realistic case study inspired by the global supply chain of fresh-cut flowers. The results show that by strategically using blockchain at certain locations in the supply chain network, significant cost savings are realized compared to fully deploying blockchain throughout the supply chain. These cost savings lead to increased demand, better consumer surplus, and higher supply chain profit. Furthermore, the proposed data-enabled product differentiation leads to fresher products in the market.

  Link(s) to publication:

  http://dx.doi.org/10.1016/j.apm.2022.06.011

• Shaheen, S.; Naoum-Sawaya, J.; Crisostomi, E., 2022, "Editorial: Smart Mobility", Frontiers in Sustainable Cities, April 4
  Abstract: Urban mobility is experiencing a number of disruptive forces that are changing how individuals interact with cities. Many younger travelers are seeking on-demand mobility strategies to avoid the hassles of car ownership, while older travelers want the freedoms guaranteed by long-term access to personal mobility. Regulators, driven by concerns about climate change, air quality, noise pollution, and the economic and societal cost of congestion, are placing more stringent requirements on mobility strategies to manage their integration into urban settings. In addition, advances in areas such as communication networks, the internet of things (IoT), distributed ledger technology (blockchain), smart cities, and cyber physics, are placing increased expectations on the performance of urban mobility strategies. This is happening at a time when the workhorse of urban mobility—the motor vehicle—is undergoing a technological transformation. Cars have basically retained the same form, with the same functionalities, since the invention of the diesel engine over 100 years ago. More recently innovation is coming in every direction. The future of mobility is no longer dominated by internal combustion engine automobiles but rather automated, electric, connected, shared, and deliverable mobility options ranging from bikes and scooters to cars, shuttles, and more.

  Link(s) to publication:

  http://dx.doi.org/10.3389/frsc.2022.880968

• 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

• Rostami, B.; Kammerling, N.; Naoum-Sawaya, J.; Buchheim, C.; Clausen, U., 2021, "Stochastic single-allocation hub location", EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, March 289(3): 1087 - 1106.
  Abstract: This paper considers the single allocation hub location problem under demand uncertainty where the allocation of the spokes to the hubs is optimized as second stage decision after the uncertainty in the demand is realized. We refer to this case as the variable allocation case, meaning that the allocation of the spokes to the hubs can be altered after the uncertainty is realized. This is in contrast to the fixed allocation case that is addressed in the literature, where the spokes are allocated to the chosen hubs before the uncertainty is realized. As shown in the paper, the fixed allocation case can be solved as a deterministic problem using the expected values of the random variables. However, the variable allocation model is a two-stage stochastic program that is challenging to solve. An alternative convex mixed-integer nonlinear formulation is presented for the variable allocation and a customized solution approach based on cutting planes is proposed to address the computational challenges. The proposed solution approach is implemented in a branch-and-cut framework where the cut-generating subproblems are solved combinatorially, i.e. without an optimization solver. Extensive computational results on the single allocation hub location problem and two of its variants, the capacitated case and the single allocation p-median problem are presented. The proposed cutting plane approach outperforms the direct solution of the problem using the state-of-the-art solver GUROBI as well the L-shaped decomposition, which is a common approach for addressing two-stage stochastic programs with recourse.

  Link(s) to publication:

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

• Sarhadi, H.; Naoum-Sawaya, J.; Verma, M., 2020, "A robust optimization approach to locating and stockpiling marine oil-spill response facilities", Transportation Research Part E: Logistics and Transportation Review, September 102005(141): 1 - 19.
  Abstract: In this research, a robust optimization approach is proposed to the problem of designing emergency response networks for marine oil-spills given uncertainty in the location, size and type of the spill. In this regard, we formulate two robust models (Gamma and Ellipsoidal) to optimize the allocation of response equipment while considering the underlying uncertainty in each oil-spill scenario. An efficient Branch-and-Cut algorithm is then designed to improve the computational performance. The benefits of applying the robust formulations are illustrated and compared to the non-robust model using a realistic case study from Newfoundland (Canada).

  Link(s) to publication:

  http://dx.doi.org/10.1016/j.tre.2020.102005

• 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

• Liu, M.; Naoum-Sawaya, J.; Gu, Y.; Leccue, F.; Shorten, R., 2019, "A Distributed Markovian Parking Assist System", IEEE Transactions on Intelligent Transportation Systems, June 20(6): 2230 - 2240.
  Abstract: This paper proposes a congestion balancing parking guidance system that suggests to a driver a sequence of streets to follow around the desired destination with the aim to reduce the total distance that is travelled while searching for a free parking spot. The system requires only limited infrastructure information, and neither requires parking spaces to be instrumented, nor vehicles to communicate with each other. Specifically, the system utilizes parking vacancy information on each street. The system also accounts for the added cost of not finding a free space, which is typically expressed as the additional distance that needs to be travelled to find an available parking spot. To avoid local congestion, different drivers respond to different suggestions based on a probability distribution that considers the total distance that needs to be travelled. A mobility simulator is used to model the searching behaviors of vehicles for parking spaces with and without the smart parking algorithm and experimental results are provided using the road network of the city of Dublin, Ireland.

  Link(s) to publication:

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

• 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

• Griggs, W. M.; Verago, R.; Naoum-Sawaya, J.; Ordonez-Hurtado, R. H.; Gilmore, R.; Shorten, R. N., 2018, "Localizing Missing Entities Using Parked Vehicles: An RFID-Based System", IEEE Internet of Things Journal, October 5(5): 4018 - 4030.
  Abstract: In this paper, we demonstrate a system for locating missing entities using radio-frequency identification (RFID)-based techniques. A key feature of our system is that we utilize the large, high-density networks of parked vehicles incident to urban areas for the detection and reporting process. RFID readers and antennas are placed within the vehicles, while RFID passive tags are carried on the entity of interest via some means, e.g., a wrist band. If an entity is reported as missing, then the application on board each of the parked vehicles is awoken by an administrative center. The technology on board the vehicles enables those participating in the service to attempt to locate the missing entity, sending useful information back to the administration center, which could be tied to an organization like the police. We demonstrate our system via a use case of a missing Alzheimer's patient in inner-city Dublin, Ireland. One of the key challenges in validating our system is being able to replicate a large-scale, real-world setting. Our technique for obtaining an early evaluation of our system thus employs the use of the microscopic traffic simulation package Simulation of Urban MObility (SUMO). SUMO permits multiple emulations of hundreds or thousands of parked vehicles participating in the service to be carried out, while simulated pedestrians walk random routes. Our results show that a simulated wandering person in need can be detected within a 30-min time frame, in the heart of Dublin city center, during a typical weekday, up to approximately 98% of the time, depending on how various parameters of the system are set.

  Link(s) to publication:

  http://dx.doi.org/10.1109/JIOT.2018.2864590

• 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

For more publications please see our Research Database