Richard Ivey Building 2349
- Operations Research
- Connected Vehicles
- Smart Cities
- Energy Networks
- Water Networks
- Big Data Analytics
- Internet of Things
- Read the Impact article featuring research from Professor Naoum-Sawaya
- To search for publications by a specific faculty member, select the database and then select the name from the Author drop down menu.
Joe Naoum-Sawaya is an Assistant Professor of Management Science at the Ivey Business School. He holds a Ph.D. in Management Science/Operations Research from the University of Waterloo. Prior to joining Ivey, Joe was a research scientist at IBM Research. Joe’s research focus is on machine learning and optimization with applications in smarter cities (energy, mobility, water, and telecommunication). His work has appeared in INFORMS Journal on Computing, European Journal of Operational Research, Transportation Research, and Naval Research Logistics among others.
- Decision Making with Analytics
- Prescriptive Analytics
- Ph.D. Management Sciences, University of Waterloo
Recent Refereed Articles
Ghaddar, B, Naoum-Sawaya, J,
2018, "High Dimensional Data Classification and Feature Selection using Support Vector Machines", European Journal of Operational Research 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.
Gu, Y, Liu, M, Naoum-Sawaya, J, Crisostomi, E, Russo, G, Shorten, R,
2018, "Pedestrian-Aware Engine Management Strategies for Plug-In Hybrid Electric Vehicles", IEEE Transactions on Intelligent Transportation Systems 19(1): 92 - 101.
Abstract: Electric vehicles (EVs) and plug-in hybrid EVs (PHEVs) are increasingly being seen as a means of mitigating the pressing concerns of traffic-related pollution. While hybrid vehicles are usually designed with the objective of minimizing fuel consumption, in this paper we propose a engine management strategies that also consider environmental effects of the vehicles to pedestrians outside of the vehicles. Specifically, we present the optimisation-based engine energy management strategies for PHEVs that attempt to minimize the environmental impact of pedestrians along the route of the vehicle, while taking account of route-dependent uncertainties. We implement the proposed approach in a real PHEV and evaluate the performance in a hardware-in-the-loop platform. A variety of simulation results are given to illustrate the efficacy of our proposed approach.
Naoum-Sawaya, J, Ghaddar, B,
2017, "Cutting plane approach for the maximum flow interdiction problem", Journal of the Operational Research Society 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:
Naoum-Sawaya, J, Yu, JY,
2017, "Ridesharing for emergency evacuation", INFOR 55(4): 339 - 358.
Abstract: In this paper, we consider the evacuation problem that consists of grouping and routing evacuees to safe zones. Grouping evacuees reduces congestion on roads, addresses fuel shortage and supports individuals with limited access to transportation means. We propose a mixed integer programming model where individuals with vehicles are instructed to pick up others along their route in order to evacuate the maximum number of individuals within a limited time. Since evacuation decisions and plans must be made as quickly as possible, we propose two heuristics that provide comparable solutions within a short computational time. The first heuristic is inspired from the Clarke-Wright savings heuristic for the vehicle routing problem, while the second heuristic is based on maximum bipartite matching. Computational results show that the proposed heuristics find solutions in less than a second for instances with up to 40 evacuee locations. We also present extensions of the evacuation problem that include vehicles with different capacities, that minimize the time to evacuate everyone, and that find the optimal vehicle placement.
Link(s) to publication:
Kuang, X, Ghaddar, B, Naoum-Sawaya, J, Zuluaga, L,
2017, "Alternative LP and SOCP hierarchies for ACOPF problems", IEEE Transactions on Power Systems 32(4): 2828 - 2836.
Abstract: Semidefinite programming (SDP) relaxations for the Alternating Current Optimal Power Flow (ACOPF) problem have been shown to be tight for well studied problem instances. However, due to the computational demands of SDP, it becomes difficult to use SDP relaxations to approximate large-scale instances of the ACOPF problem. Recently, computationally cheaper second-order cone relaxations have been proposed for the ACOPF problem that are tight for networks with a simple topology. In this paper, we exploit recent results in polynomial optimization to construct a hierarchy of second-order cone relaxations that provide increasingly better approximations for ACOPF problems. We show that in comparison with proposed related SDP hierarchies, the second-order cone hierarchies provide good approximations to the ACOPF problems for larger scale networks. We illustrate this with numerical examples on well studied instances of the ACOPF problem.
Naoum-Sawaya, J, Crisostomi, E, Liu, M,
2017, "Smart Procurement of Naturally Generated Energy (SPONGE) for Plug-In Hybrid Electric Buses", IEEE Transactions on Automation Science and Engineering 14(2): 598 - 607.
Abstract: We discuss a recently introduced ECO-driving concept known as smart procurement of naturally generated energy (SPONGE) in the context of plug-in hybrid electric buses. Examples are given to illustrate the benefits of this approach to ECO-driving. Finally, distributed algorithms to realize SPONGE are discussed, paying attention to the privacy implications of the underlying optimization problems.
Link(s) to publication:
Yassine, A, Naoum-Sawaya, J,
2017, "Architecture, Performance, and Investment in Product Development Networks", Journal of Mechanical Design 139(1).
Abstract: Firms engaging in product development (PD) face the imperative problem of allocating scarce development resources to a multitude of opportunities. In this paper, we propose a mathematical formulation to optimize PD investment or resource allocation decisions. The model maximizes the performance of a product under development, based on its architecture and the firm's available resource, by choosing the optimal resource allocation across product modules and design rules that govern the relationships between these modules. Results based on a comprehensive experiment (with various architectural patterns, escalating number of dependencies, and different problem sizes) shed light on three important hypotheses. First, product architecture affects resource allocation decisions and ultimately product performance. The second hypothesis tests whether modular or integral architectures can attain higher performance levels based on our formulation. A third hypothesis states that there is a shift in the temporal allocation of resources from design rules to individual modules, thus supporting the move from integral to modular architectures as the product evolves across multiple generations. Finally, the model and the experimental results provide design and managerial insights to both development engineers and managers. Specifically, for development engineers, the model and its analysis provide guidance for selecting the product architecture which leads to maximum performance. For development managers, the model and its analysis assist in deciding the optimal budget proportions to be allocated to modules and to design rules, given a fixed architecture and budget.
Link(s) to publication:
Villumsen, JC, Naoum-Sawaya, J,
2016, "Column Generation for Stochastic Green Telecommunication Network Planning with Switchable Base Stations", Naval Research Logistics 63(5): 351 - 366.
Abstract: We present the green telecommunication network planning problem with switchable base stations, where the location and configuration of the base stations are optimized, while taking into account uncertainty and variability of demand. The problem is formulated as a two-stage stochastic program under demand uncertainty with integers in both stages. Since solving the presented problem is computationally challenging, we develop the corresponding Dantzig-Wolfe reformulation and propose a solution approach based on column generation. Comprehensive computational results are provided for instances of varying characteristics. The results show that the joint location and dynamic switching of base stations leads to significant savings in terms of energy cost. Up to 30% reduction in power consumption cost is achieved while still serving all users. In certain cases, allowing dynamic configurations leads to more installed base stations and higher user coverage, while having lower total energy consumption. The Dantzig-Wolfe reformulation provides solutions with a tight LP-gap eliminating the need for a full branch-and-price scheme. Furthermore, the proposed column generation solution approach is computationally efficient and outperforms CPLEX on the majority of the tested instances.
Link(s) to publication:
Naoum-Sawaya, J, Buchheim, C,
2016, "Robust Critical Node Selection by Benders Decomposition", INFORMS Journal on Computing 28(1): 162 - 174.
Abstract: The critical node selection problem (CNP) has important applications in telecommunication, supply chain design, and disease propagation prevention. In practice, the weights on the connections are often uncertain or hard to estimate. For this reason, robust optimization approaches have been considered recently for CNP. In this article, we address very general uncertainty sets, only requiring a linear optimization oracle for the set of potential scenarios. In particular, we can deal with discrete scenario based uncertainty, gamma uncertainty, and ellipsoidal uncertainty. For this general class of robust critical node selection problems, we propose an exact solution method based on Benders decomposition. The Benders subproblem, which in our approach is a robust optimization problem, is efficiently solved by applying the Floyd-Warshall algorithm. The presented approach is tested on 384 instances based on Forest-Fire, Barabási-Albert, Erdos-Rényi, and Watts-Strogatz graphs with different number of nodes and edges, where running times are compared to CPLEX being directly applied to the robust problem formulation. The computational results show the advantage of the proposed approach in handling the uncertainty thus outperforming CPLEX most notably for the ellipsoidal uncertainty cases.
Link(s) to publication:
Challita, U, Dawy, Z, Turkiyyah, G, Naoum-Sawaya, J,
2016, "A Chance Constrained Approach for LTE Cellular Network Planning under Uncertainty", Computer Communications 73: 34 - 45.
Abstract: With the evolution towards 4G cellular networks, there is a need to develop new approaches for radio network planning (RNP) that can capture the technology enhancements to determine optimized locations and configurations of base station sites. Conventional RNP approaches are normally based on a deterministic link budget analysis that compensates for signal statistical variation via pre-determined power margins this is normally followed by Monte-Carlo simulations to fine tune the planning outcome. In this work, we present a novel approach for cellular RNP that captures the uncertainty in signals and interference as part of the problem formulation leading directly to an optimized planning solution the approach is generic and can capture signal uncertainty due to fading and dynamic resource allocation with possible extension to other adaptive system features. The approach is divided into two parts that are addressed separately using chance constrained optimization and then combined within a common framework. The first part, denoted as site selection problem, aims at selecting the minimum cardinality set of eNodeBs from a given large set, that satisfies target performance requirements. The second part, denoted as site placement problem, aims at refining the locations of the selected eNodeBs in order to further enhance the planning quality. Finally, both parts are combined within a common framework to determine the optimized number and locations of eNodeBs over a given geographical area based on a wide range of system and user parameters. A divide and conquer approach is also proposed to deal with the complexity of planning large network scenarios. Performance results are presented to highlight the effectiveness of the proposed framework with detailed analysis and verification via Monte-Carlo simulations.
Link(s) to publication:
Elhedhli, S, Naoum-Sawaya, J,
2015, "Improved Branching Disjunctions for Branch-and-Bound: An Analytic Center Approach", European Journal of Operational Research 247(1): 37 - 45.
Abstract: In classical branch-and-bound algorithms, the branching disjunction is often based on a single variable, which is a special case of the more general approach that involves multiple variables. In this paper, we present a new approach to generate good general branching disjunctions based on the shape of the polyhedron and interior-point concepts. The approach is based on approximating the feasible polyhedron using Dikin’s inscribed ellipsoid, calculated using the analytic center from interior-point methods. We use the fact that the width of the ellipsoid in a given direction has a closed form expression to formulate a quadratic problem whose optimal solution is a thin direction of the ellipsoid. While solving a quadratic problem at each node of the branch-and-bound tree is impractical, we use an efficient neighborhood search heuristic for its solution. We report computational results on hard mixed integer problems from the literature showing that the proposed approach leads to smaller branch-and-bound trees and a reduction in the computational time as compared with classical branching and strong branching. As the computation of the analytic center is a bottleneck, we finally test the approach within a general interior-point based Benders decomposition where the analytic center is readily available, and show clear dominance of the approach over classical branching.
Link(s) to publication:
Eck, B, Arandia, E, Naoum-Sawaya, J, Wirth, F,
2015, "Decomposition Approach for Background Leakage Assessment: BBLAWN Instance", Journal of Water Resources Planning and Management 142(5).
Abstract: This paper summarizes an approach for the assessment and control of background leakage on water distribution networks. The methodology was developed for the battle of background leakage assessment for water networks (BBLAWN) held at the Water Distribution System Analysis Conference 2014 in Bari, Italy. The problem instance posed for the conference considers an aging water network with high levels of background leakage. A range of operational and design changes including new valves, pipes, pumps, tanks, and controls are available to reduce the expenditure needed to operate the system. Constraints are imposed on nodal pressures and tank levels to meet service level requirements. The solution methodology proposed in this paper decomposes the problem according to the type of intervention, considering each type separately. An initial diagnosis of the network informs the manner and order of evaluating the various interventions. Custom implementations of network simulation, heuristic algorithms, and optimization models are used to identify improvements. The recommended program of network modifications reduced the annual cost of running the system from 4 million to 1.5 million and had a return on investment in network infrastructure of 430%. Read More: http:ascelibrary.orgdoi10.1061%28ASCE%29WR.1943-5452.0000602
Naoum-Sawaya, J, Ghaddar, B, Arandia, E, Eck, B,
2015, "Simulation-Optimization Approaches for Water Pump Scheduling and Pipe Replacement Problems", European Journal of Operational Research 246(1): 293 - 306.
Abstract: Network operation and rehabilitation are major concerns for water utilities due to their impact on providing a reliable and efficient service. Solving the optimization problems that arise in water networks is challenging mainly due to the nonlinearities inherent in the physics and the often binary nature of decisions. In this paper, we consider the operational problem of pump scheduling and the design problem of leaky pipe replacement. New approaches for these problems based on simulation-optimization are proposed as solution methodologies. For the pump scheduling problem, a novel decomposition technique uses solutions from a simulation-based sub-problem to guide the search. For the leaky pipe replacement problem a knapsack-based heuristic is applied. The proposed solution algorithms are tested and detailed results for two networks from the literature are provided.
Link(s) to publication:
Naoum-Sawaya, J, Cogill, R, Ghaddar, B, Sajja, S, Shorten, R, Taheri, N, Tommasi, P, Verago, R, Wirth, F,
2015, "Stochastic optimization approach for the car placement problem in ridesharing systems", Transportation Research - Part B Methodological 80: 173 - 184.
Abstract: With the increasing fuel prices and the pressure towards greener modes of transportation, ridesharing has emerged as an alternative to private car ownership and public transportation. In this paper, we focus on a common destination ridesharing system which is of interest in large organizations such as companies and government offices. Particularly, such organizations are looking at using company owned vehicles to offer a ridesharing service by which employees carpool to work thus leading to several benefits that include decreasing pressure on on-campus parking spaces, lowering localized on-campus congestion, in addition to offering a greener transportation mode while lowering transportation costs for employees. Based on discussions with our industry partners, optimizing the distribution of limited number of company vehicles while insuring robustness against unlikely vehicle unavailability is of critical importance. Thus in this paper, we present a stochastic mixed integer programming model to optimize the allocation of shared vehicles to employees while taking into account the unforeseen event of vehicle unavailability which would require some participants to take own vehicles or rerouting of existing vehicles. Since solving the proposed model to optimality is computationally challenging for problems of large sizes, we also propose a heuristic that is capable of finding good quality solutions in limited computational time. The proposed model and heuristic are tested on several instances of varying sizes showing the computational performance. Finally, a test case based on the city of Rome, Italy is presented and insights related to vehicle distribution and travel time savings are discussed.
Link(s) to publication:
Ghaddar, B, Naoum-Sawaya, J, Kishimoto, A,
2015, "A Lagrangian Decomposition Approach for the Pump Scheduling Problem in Water Networks", European Journal of Operational Research 241(2): 490 - 501.
Abstract: Dynamic pricing has become a common form of electricity tariff, where the price of electricity varies in real time based on the realized electricity supply and demand. Hence, optimizing industrial operations to benefit from periods with low electricity prices is vital to maximizing the benefits of dynamic pricing. In the case of water networks, energy consumed by pumping is a substantial cost for water utilities, and optimizing pump schedules to accommodate for the changing price of energy while ensuring a continuous supply of water is essential. In this paper, a Mixed-Integer Non-linear Programming (MINLP) formulation of the optimal pump scheduling problem is presented. Due to the non-linearities, the typical size of water networks, and the discretization of the planning horizon, the problem is not solvable within reasonable time using standard optimization software. We present a Lagrangian decomposition approach that exploits the structure of the problem leading to smaller problems that are solved independently. The Lagrangian decomposition is coupled with a simulation-based, improved limited discrepancy search algorithm that is capable of finding high quality feasible solutions. The proposed approach finds solutions with guaranteed upper and lower bounds. These solutions are compared to those found by a mixed-integer linear programming approach, which uses a piecewise-linearization of the non-linear constraints to find a global optimal solution of the relaxation. Numerical testing is conducted on two real water networks and the results illustrate the significant costs savings due to optimizing pump schedules.
Link(s) to publication:
- Research Scientist, IBM Research