We study the inefficiency of pure Nash equilibria in symmetric network congestion games defined over series-parallel networks with affine edge delays. For arbitrary networks, Correa (2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, for extension-parallel networks, a subclass of series-parallel networks, Fotakis (2010) proved that the PoA is … Read more
We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have … Read more
This paper shows that there exists a Nash equilibrium of an n-player chance-constrained game for elliptically symmetric distributions. For a certain class of payoff functions, we suitably construct an equivalent mathematical program whose global maximizer is a Nash equilibrium. ArticleDownload View PDF
This work introduces the StoMADS-PB algorithm for constrained stochastic blackbox optimization, which is an extension of the mesh adaptive direct-search (MADS) method originally developed for deterministic blackbox optimization under general constraints. The values of the objective and constraint functions are provided by a noisy blackbox, i.e., they can only be computed with random noise whose … Read more
Drone delivery is drawing increasing attention in last-mile delivery. Effective solution methods to solve decision-making problems arising in drone delivery allow to run and assess drone delivery systems. In this paper, we focus on delivery systems with a single traditional vehicle and multiple drones working in tandem to fulfill customer requests. We address the Traveling … Read more
The running time for solving a mixed-integer linear optimization problem (MIP) strongly depends on the number of its integral variables. Bader et al. [Math. Progr. 169 (2018) 565–584] equivalently reformulate an integer program into an MIP that contains a reduced number of integrality constraints, when compared to the original model. Generalizing the concept of totally … Read more
In this paper we present the nonconvex exterior-point optimization solver (NExOS)—a novel first-order algorithm tailored to constrained nonconvex learning problems. We consider the problem of minimizing a convex function over nonconvex constraints, where the projection onto the constraint set is single-valued around local minima. A wide range of nonconvex learning problems have this structure including … Read more
Despite the success of branch-and-cut methods for solving mixed integer bilevel linear optimization problems (MIBLPs) in practice, there are still gaps in both the theory and practice surrounding these methods. In the first part of this paper, we lay out a basic theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing … Read more
Inverse optimization is the problem of determining the values of missing input parameters that are closest to given estimates and that will make a given solution optimal. This study is concerned with the relationship of a particular inverse mixed integer linear optimization problem (MILPs) to both the original problem and the separation problem associated with … Read more
This work proposes a partial optimization metaheuristic under special intensification conditions (POPMUSIC) for the classical capacitated vehicle routing problem (CVRP). The proposed approach uses a branch-cut-and-price algorithm as a powerful heuristic to solve subproblems whose dimensions are typically between 25 and 200 customers. The whole algorithm can be seen as the application of local search … Read more