An official website of the United States government
Abstract We study a class of bilevel spanning tree (BST) problems that involve two independent decision‐makers (DMs), the leader and the follower with different objectives, who jointly construct a spanning tree in a graph. The leader, who acts first, selects an initial subset of edges that do not contain a cycle, from the set under her control. The follower then selects the remaining edges to complete the construction of a spanning tree, but optimizes his own objective function. If there exist multiple optimal solutions for the follower that result in different objective function values for the leader, then the follower may choose either the one that is the most (optimistic version) or least (pessimistic version) favorable to the leader. We study BST problems with the sum‐ and bottleneck‐type objective functions for the DMs under both the optimistic and pessimistic settings. The polynomial‐time algorithms are then proposed in both optimistic and pessimistic settings for BST problems in which at least one of the DMs has the bottleneck‐type objective function. For BST problem with the sum‐type objective functions for both the leader and the follower, we provide an equivalent single‐level linear mixed‐integer programming formulation. A computational study is then presented to explore the efficacy of our reformulation.
more »
« less
On Bilevel Optimization with Inexact Follower
Traditionally, in the bilevel optimization framework, a leader chooses her actions by solving an upper-level problem, assuming that a follower chooses an optimal reaction by solving a lower-level problem. However, in many settings, the lower-level problems might be nontrivial, thus requiring the use of tailored algorithms for their solution. More importantly, in practice, such problems might be inexactly solved by heuristics and approximation algorithms. Motivated by this consideration, we study a broad class of bilevel optimization problems where the follower might not optimally react to the leader’s actions. In particular, we present a modeling framework in which the leader considers that the follower might use one of a number of known algorithms to solve the lower-level problem, either approximately or heuristically. Thus, the leader can hedge against the follower’s use of suboptimal solutions. We provide algorithmic implementations of the framework for a class of nonlinear bilevel knapsack problem (BKP), and we illustrate the potential impact of incorporating this realistic feature through numerical experiments in the context of defender-attacker problems.
more »
« less
- Award ID(s):
- 1634835
- PAR ID:
- 10206044
- Date Published:
- Journal Name:
- Decision Analysis
- Volume:
- 17
- Issue:
- 1
- ISSN:
- 1545-8490
- Page Range / eLocation ID:
- 74 to 95
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This work develops analysis and algorithms for solving a class of bilevel optimization problems where the lower-level (LL) problems have linear constraints. Most of the existing approaches for constrained bilevel problems rely on value function-based approximate reformulations, which suffer from issues such as non-convex and non-differentiable constraints. In contrast, in this work, we develop an implicit gradient-based approach, which is easy to implement, and is suitable for machine learning applications. We first provide an in-depth understanding of the problem, by showing that the implicit objective for such problems is in general non-differentiable. However, if we add some small (linear) perturbation to the LL objective, the resulting implicit objective becomes differentiable almost surely. This key observation opens the door for developing (deterministic and stochastic) gradient-based algorithms similar to the state-of-the-art ones for unconstrained bi-level problems. We show that when the implicit function is assumed to be stronglyconvex, convex, and weakly-convex, the resulting algorithms converge with guaranteed rate. Finally, we experimentally corroborate the theoretical findings and evaluate the performance of the proposed framework on numerical and adversarial learning problems.more » « less
-
We consider a bilevel network interdiction problem where the follower aims to maximize the amount of flow from the source node to the sink node, and the leader aims to minimize the number of arcs from a critical set that have positive flow on them, that is, active arcs, in the maximum flow solution obtained by the follower. This problem is motivated by an application in human trafficking disruption. We consider both the optimistic and pessimistic variants of this bilevel optimization problem and develop their respective single-level reformulations. We present a tailored solution method to the pessimistic problem, which solves the problem to optimality for one practically important class of networks. Through computational experiments on randomly generated layered network instances, we show the effectiveness of the proposed methods and demonstrate that the tailored method is orders of magnitude faster than existing approaches in the literature. We also conduct computational experiments on randomly generated test instances inspired by domestic human trafficking networks and draw domain-specific insights.more » « less
-
This paper studies how to integrate rider mode preferences into the design of on-demand multimodal transit systems (ODMTSs). It is motivated by a common worry in transit agencies that an ODMTS may be poorly designed if the latent demand, that is, new riders adopting the system, is not captured. This paper proposes a bilevel optimization model to address this challenge, in which the leader problem determines the ODMTS design, and the follower problems identify the most cost efficient and convenient route for riders under the chosen design. The leader model contains a choice model for every potential rider that determines whether the rider adopts the ODMTS given her proposed route. To solve the bilevel optimization model, the paper proposes an exact decomposition method that includes Benders optimal cuts and no-good cuts to ensure the consistency of the rider choices in the leader and follower problems. Moreover, to improve computational efficiency, the paper proposes upper and lower bounds on trip durations for the follower problems, valid inequalities that strengthen the no-good cuts, and approaches to reduce the problem size with problem-specific preprocessing techniques. The proposed method is validated using an extensive computational study on a real data set from the Ann Arbor Area Transportation Authority, the transit agency for the broader Ann Arbor and Ypsilanti region in Michigan. The study considers the impact of a number of factors, including the price of on-demand shuttles, the number of hubs, and access to transit systems criteria. The designed ODMTSs feature high adoption rates and significantly shorter trip durations compared with the existing transit system and highlight the benefits of ensuring access for low-income riders. Finally, the computational study demonstrates the efficiency of the decomposition method for the case study and the benefits of computational enhancements that improve the baseline method by several orders of magnitude. Funding: This research was partly supported by National Science Foundation [Leap HI Proposal NSF-1854684] and the Department of Energy [Research Award 7F-30154].more » « less
-
Hebrard E., Musliu N. (Ed.)This study explores the design of an On-Demand Multimodal Transit System (ODMTS) that includes segmented mode switching models that decide whether potential riders adopt the new ODMTS or stay with their personal vehicles. It is motivated by the desire of transit agencies to design their network by taking into account both existing and latent demand, as quality of service improves. The paper presents a bilevel optimization where the leader problem designs the network and each rider has a follower problem to decide her best route through the ODMTS. The bilevel model is solved by a decomposition algorithm that combines traditional Benders cuts with combinatorial cuts to ensure the consistency of mode choices by the leader and follower problems. The approach is evaluated on a case study using historical data from Ann Arbor, Michigan, and a user choice model based on the income levels of the potential transit riders.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/deca.2019.0392
