Questions tagged [bilevel-optimization]
For questions related to optimization problems in which one decision maker (the "leader") chooses decision variables, then a second decision maker (the "follower") chooses decision variables in response. The optimization problem is formulated from the leader's point of view and takes into account the follower's best response. Bilevel optimization is closely related to Stackelberg games.
16 questions
0
votes
0
answers
73
views
+50
Binary search to tune LP constraints
I have a sort of reverse question; I have a technique that finds a close approximate solution to my problem but I'm not sure what this technique is named, if at all.
My problem started as a network ...
- 521
6
votes
1
answer
195
views
How to find costs to an integer program that maximize integrality gap
Let $A \in \mathbb{Z}^{m \times n}$ and $b \in \mathbb{Z}^m$. For $c \in \mathbb{R}^n$, let
\begin{align} \text{ILP}(c) = \max \quad & c^\top x \\ \text{s.t.} \quad & x \in \mathbb{Z}^n \\ &...
- 161
0
votes
1
answer
142
views
Removing min operator from max objective
I am reading a paper where the authors made the following statement on page 16:
I wonder why dropping the 'min' operator inside a 'max' objective function is a valid operation here. Any explanation ...
3
votes
1
answer
181
views
How to solve a min max problem?
The optimization model is defined as,
$$
\begin{aligned}
\min_{\bf x}\max_{\bf y}f_{0}(y)\\
s.t.\bf f_1(y)=0\\
\bf f_2(y)\leq0\\
\bf f_{3}(x,y)\leq0\\
\bf f_{4}(x)\leq0
\end{aligned}
$$
where $f_0(y)$ ...
- 115
2
votes
1
answer
133
views
Finding a maximum violated infeasible subset
Given a binary optimization problem of the following form:
\begin{align}
min\; &cx&\\
&Dx \leq e&\\
&\sum_{i\in S} x_i \leq r(S) &\forall S\in \mathbb{S}\\
&x_i binary &...
- 3,563
2
votes
1
answer
123
views
Dualization of the subproblem in bilevel programs
Let's say we have the following problem
$$\max_{x∈X}(cx - \min_{y∈Y}dxy)$$
where $x$ and $y$ are decision variables and $c$ and $d$ are parameters. Then, we take the dual of the inner maximization ...
user5245
1
vote
1
answer
95
views
Connected optimization problems
I'm working on a set of interconnected problems and I'm not sure how I can solve across the connection. First, a set of variables, $x$, is solved using the following:
$$\max_{x}f(x)$$
Subject to:
$$w^...
- 45
2
votes
1
answer
112
views
How do we call this optimization problem?
Let $f_k\colon\Bbb R^n\to\Bbb R$, $k=1,\dots,K$, be differentiable (possibly nonconvex) functions and $X\subset\Bbb R^n$ be a convex set.
Consider the following optimization problem:
$$
\min_{x\in X}\...
- 155
2
votes
1
answer
129
views
Decision Variables becoming Constraints
Consider a convex optimization problem with decision variable x. Though I'm interested in answers for any kind of convex optimization problem, let's say it's an LP, so we have something like:
\begin{...
- 121
5
votes
2
answers
765
views
Minimizing under argmin constraint
I have a problem in the form
$$\begin{aligned}
\min_a f(a,b)\\
\text{s.t.}\ b =\ & \arg\min_c g(a,c)\\
& \text{s.t.}\ H(a,c) \leq \vec{0}
\end{aligned}$$
where $f, g, H$ are all ...
- 51
2
votes
1
answer
117
views
Interchange upper- and lower-level decision variables in bi-level programming
Consider a general bi-level programming as follows:
\begin{align*}
\min_{x\in X,y\in Y}&~F(x,y) \\
s.t.&~ G(x,y) \leq 0, \\
&~ y\in \arg\min_{z\in Y}\{f(x,z): ...
- 37
-3
votes
1
answer
202
views
Ask for suggestions on bilevel optimization question [closed]
Here is a bilevel question:
the master problem is $\max_y \sum_{n \in 1,...,N} x[n] * y[n];$
subject to $$\min_x \sum_{n \in 1,...,N} x[n] * y[n]$$
$$yy^T = I$$
and some other linear constraints.
So ...
- 7
3
votes
1
answer
231
views
A tricky Bi-Level Location Problem using VISUM
I'm writing my thesis on the optimal location of Air-Taxi Stations. I'm using PTV VISUM for the transport model where I'll inherit the Origin-Destination demand matrix. I come from transportation ...
- 31
2
votes
0
answers
253
views
How to linearize a max min objective function?
Let us suppose that I have a $\max \min$ objective function that only depends on one set of variables:
$\underset{x}\max \underset{y}\min dy$
Associated with the linear set of constraints and right ...
- 875
15
votes
1
answer
372
views
Integrality gap in bilevel binary linear programming problem
I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is
$$
\begin{alignat}2
\min\limits_x&\...
- 309