Bilevel optimization problems embed the optimality of a subproblem as a constraint of another optimization problem. We introduce the concept of near-optimality robustness for bilevel optimization, protecting the upper-level solution feasibility from limited deviations from the optimal solution at the lower level. General properties and necessary conditions for the existence of solutions are derived for near-optimal robust versions of general bilevel optimization problems. A duality-based solution method is defined when the lower level is convex, leveraging the methodology from the robust and bilevel literature. Numerical results assess the efficiency of exact and heuristic methods and the impact of valid inequalities on the solution time.

Abstract With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of user satisfaction with a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixed‐integer linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real‐world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.

We present a new model for finding the optimal placement of electric vehicle charging stations across a multiperiod time frame so as to maximise electric vehicle adoption. Via the use of stochastic discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. We adopt a simulation approach and precompute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Our major contribution is a reformulation into a maximum covering model, which uses the precomputed error terms to calculate the users covered by each charging station. This allows solutions to be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and greedy randomised adaptive search procedure heuristics to obtain good-quality solutions more efficiently. Extensive computational results are provided, and they compare the maximum covering formulation with the current state of the art for both exact solutions and the heuristic methods. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Hydro-Québec and the Natural Sciences and Engineering Research Council of Canada [Discovery Grant 2017-06054; Collaborative Research and Development Grant CRDPJ 536757–19]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0185 .

The Optimal Power Flow (OPF) problem is a central optimization problem in power systems. Its global resolution is a challenge since it is highly nonconvex and NP-hard. Semidefinite Programming (SDP) is a powerful tool to progress towards global optimality as semidefinite relaxations provide tight lower bounds for the OPF problem. However, solving semidefinite relaxations for large power networks is very costly, because it is required to exploit its sparsity for achieving this aim. One efficient way to exploit sparsity for the OPF problem is to use clique decomposition techniques along with state-of-the-art interior point algorithms. Yet many clique decompositions can be computed for the same sparse SDP problem, their performance can significantly varies in practice. In this context, it is crucial to identify a good decomposition, where by good we mean a decomposition that allows to solve the SDP relaxation of the OPF problem in a small amount of time. At the moment, it is not possible in the literature to find a systematic analysis that allows to characterize in detail the properties of a good decomposition, the works proposed so fare relies on the basic assumption that there is a trade-off between the size and the number of the cliques: a decomposition with only one large clique is problematic because of memory issues but a decomposition with many tiny cliques is not advisable either as it implies lots of linking constraints, which slows down the resolution. In this work, we propose to use machine learning techniques to understand what are the characteristics of a good clique decomposition. More precisely, we propose to identify the relevant features to describe a good clique decomposition, using both classification and regression approaches. The results show that the decomposition identified with the proposed techniques are comparable with the state of the art.

Abstract We present a solution approach for a multi‐trip vehicle routing problem with time windows in which the locations of a prescribed number of depots and the fleet sizes must also be optimized. Given the complexity of the task, we divide the problem into subproblems that are solved sequentially. First, we address strategic decisions, which are solved once and remain constant thereafter. Depots are allocated by solving a p‐median problem and fleet sizes are determined by identifying the vehicle requirements of several worst‐case demand instances. Then, we address the operational planning aspect: optimizing the vehicle routes on a daily basis to satisfy the fluctuating customer demand. We assign customers to depots based on distance and “routing effort,” and for the routing problem we combine a tailor‐made branch‐and‐cut algorithm with a heuristic consisting of a route construction phase and packing of routes into vehicle trips. Our strategic decision models are robust in the sense that when applied to unseen data, all customers could be visited with the allocated fleet sizes and depot locations. Our operational routing methods are both time and cost‐effective. The exact method yields acceptable optimality gaps in 20 min and the heuristic runs in less than 2 min, finding optimal or near‐optimal solutions for small instances. Finally, we explore the trade‐off between depot and fleet costs, and routing costs to make recommendations on the optimal number of depots. Our solution approach was entered into the 12th AIMMS‐MOPTA Optimization Modeling Competition and was awarded the first prize.

A two-stage optimization methodology is proposed to solve the fixed-outline floorplanning problem that is a global optimization problem for wirelength minimization. In the first stage, an attractor-repeller convex optimization model provides the relative positions of the modules on the floorplan. The second stage places and sizes the modules using second-order cone optimization. A Voronoi diagram is employed to obtain a planar graph and thus a relative position matrix to connect the two stages. Overlap-free and deadspace-free floorplans are achieved in a fixed outline and floorplans with any specified percentage of whitespace can be produced. Experimental results on GSRC benchmarks demonstrate that we obtain significant improvements on the best results known in the literature for these benchmarks. Most importantly, our methodology provides greater improvement over other floor-planners as the number of modules increases.

This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) interactions between them. We demonstrate that the combination of a semidefinite programming relaxation with cutting planes is able to compute globally optimal layouts for large SRFLPs with up to 30 facilities. In particular, we report the globally optimal solutions for two sets of SRFLPs previously studied in the literature, some of which have remained unsolved since 1988.

Telecommunication companies, such as Internet and cellular service providers, are seeing rapid and uncertain growth of amount of traffic routed through their networks. It has become a challenge for these companies to make optimal decisions for equipment purchase that simultaneously satisfy the uncertain future demand while minimizing investment cost. This paper presents a decision-making framework for installing the required equipment into the networks while in the uncertain environment. The framework is based on new multi-stage stochastic programming mathematical models that capture the complexity of the individual Central Office (CO) decision-making process. The models are solved using the online NEOS server. Two examples are presented to illustrate the procedure. The optimization model also addresses the equipment pricing problem, i.e., what premium is worth paying for shorter installation times.

We present a new framework for efficiently finding competitive solutions for the facility-layout problem. This framework is based on the combination of two new mathematical-programming models. The first model is a relaxation of the layout problem and is intended to find good starting points for the iterative algorithm used to solve the second model. The second model is an exact formulation of the facility-layout problem as a nonconvex mathematical program with equilibrium constraints (MPEC). Aspect ratio constraints, which are frequently used in facility-layout methods to restrict the occurrence of overly long and narrow departments in the computed layouts, are easily incorporated into this new framework. Finally, we present computational results showing that the complete framework can be solved efficiently using widely available optimization software, and the resulting layouts improve on those obtained using previous approaches in the literature. Moreover, the framework can be used to find different competitive layouts with relatively little computational effort, which is advantageous for a user who wishes to consider several competitive layouts rather than simply using a mathematically optimal layout.

Semidefinite programming (SDP) is currently one of the most active areas of research in optimization. SDP has attracted researchers from a wide variety of areas because of its theoretical and numerical elegance as well as its wide applicability. In this paper we present a survey of two major areas of application for SDP, namely discrete optimization and matrix completion problems. In the first part of this paper we present a recipe for finding SDP relaxations based on adding redundant constraints and using Lagrangian relaxation. We illustrate this with several examples. We first show that many relaxations for the max-cut problem (MC) are equivalent to both the Lagrangian and the well-known SDP relaxation. We then apply the recipe to obtain new strengthened SDP relaxations for MC as well as known SDP relaxations for several other hard discrete optimization problems. In the second part of this paper we discuss two completion problems, the positive semidefinite matrix completion problem and the Euclidean distance matrix completion problem. We present some theoretical results on the existence of such completions and then proceed to the application of SDP to find approximate completions. We conclude this paper with a new application of SDP to find approximate matrix completions for large and sparse instances of Euclidean distance matrices.