Joe Naoum-Sawaya

• 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

• 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

• 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, January 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.

  Link(s) to publication:

  https://doi.org/10.1109/TITS.2017.2697044

• Naoum-Sawaya, J.; Yu, J. Y., 2017, "Ridesharing for emergency evacuation", INFOR, December 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:

  http://dx.doi.org/10.1080/03155986.2017.1302773

• 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

• Kuang, X.; Ghaddar, B.; Naoum-Sawaya, J.; Zuluaga, L., 2017, "Alternative LP and SOCP hierarchies for ACOPF problems", IEEE Transactions on Power Systems, July 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.

  Link(s) to publication:

  https://doi.org/10.1109/TPWRS.2016.2615688

• 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, April 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:

  http://dx.doi.org/10.1109/TASE.2016.2633001

• Yassine, A.; Naoum-Sawaya, J., 2017, "Architecture, Performance, and Investment in Product Development Networks", Journal of Mechanical Design, January 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:

  http://mechanicaldesign.asmedigitalcollection.asme.org/article.aspx?articleid=2552978

  http://dx.doi.org/10.1115/1.4034673

For more publications please see our Research Database