Joint UAV and Truck Routing Under Uncertain Disruptions: Measuring the Value of Information

\(\) We consider a joint UAV and truck routing problem in which the operation of the UAV is subject to uncertain disruptions. The planner initially does not know in which locations a disruption will occur but can refine his/her knowledge by spending additional resources to probe locations for additional information, removing the uncertainty for the … Read more

An Extension of the Bertsimas & Sim Result for Discrete, Linear, and Γ-Robust Min-Max Problems

Due to their nested structure, bilevel problems are intrinsically hard to solve – even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. We provide an extension of the … Read more

Connections and Reformulations between Robust and Bilevel Optimization

Robust and bilevel optimization share the common feature that they involve a certain multilevel structure. Hence, although they model something rather different when used in practice, they seem to have a similar mathematical structure. In this paper, we analyze the connections between different types of robust problems (strictly robust problems with and without decision-dependence of … Read more

Markov Decision Process Design: A Framework for Integrating Strategic and Operational Decisions

We consider the problem of optimally designing a system for repeated use under uncertainty. We develop a modeling framework that integrates design and operational phases, which are represented by a mixed-integer program and discounted-cost infinite-horizon Markov decision processes, respectively. We seek to simultaneously minimize the design costs and the subsequent expected operational costs. This problem … Read more

Bilevel optimization with a multi-objective lower-level problem: Risk-neutral and risk-averse formulations

In this work, we propose different formulations and gradient-based algorithms for deterministic and stochastic bilevel problems with conflicting objectives in the lower level. Such problems have received little attention in the deterministic case and have never been studied from a stochastic approximation viewpoint despite the recent advances in stochastic methods for single-level, bilevel, and multi-objective … Read more

Analyzing Inexact Hypergradients for Bilevel Learning

Estimating hyperparameters has been a long-standing problem in machine learning. We consider the case where the task at hand is modeled as the solution to an optimization problem. Here the exact gradient with respect to the hyperparameters cannot be feasibly computed and approximate strategies are required. We introduce a unified framework for computing hypergradients that … Read more

First-order penalty methods for bilevel optimization

\(\) In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower-level part is a convex optimization problem, while the upper-level part is possibly a nonconvex optimization problem. In particular, we propose penalty methods for solving them, whose subproblems turn out to be a structured minimax problem and … Read more

A Brief Introduction to Robust Bilevel Optimization

Bilevel optimization is a powerful tool for modeling hierarchical decision making processes. However, the resulting problems are challenging to solve – both in theory and practice. Fortunately, there have been significant algorithmic advances in the field so that we can solve much larger and also more complicated problems today compared to what was possible to … Read more

An Exact Method for Nonlinear Network Flow Interdiction Problems

We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower’s problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing … Read more

A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints

\(\) We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and \(n\) items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of … Read more