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&\quad c^\top x\\ \text{s.t. }&\quad Ax\geq b\\ &\quad x_i \in \{0,1\}, \end{alignat} $$ with $c$ depending linearly on the variables over which maximization happens.

To obtain a single maximization problem, I want to consider the dual of the inner problem. I am unable to verify if the inner program is total dual integral (all I know is that the matrix $A$ is not totally unimodular). So I start by considering the relaxation of the inner problem: $$ \begin{align*} \min\limits_x&\quad c^\top x\\ \text{s.t.}&\quad Ax \geq b\\ &\quad x_i \in [0,1], \end{align*} $$ which can be rewritten as $$ \begin{align*} \min\limits_x&\quad c^\top x\\ \text{s.t.}&\quad A'x \geq b'\\ &\quad x_i \geq 0, \end{align*} $$ where $A'$ is obtained by appending rows of negated identity matrix to $A$, and $b'$ by extending $b$ with a vector of $-1$'s.

Then, I take the dual of the relaxed problem, which is $$ \begin{align*} \max\limits_{\lambda}&\quad b'^\top \lambda\\ \text{s.t.}&\quad A'^\top\lambda \leq c\\ &\quad \lambda \geq 0. \end{align*} $$ Finally, I activate the maximization variables, say $\mathbf{z}$, and obtain the program $$ \begin{align*} \max\limits_{\mathbf{z}, \lambda}&\quad b'^\top \lambda\\ \text{s.t.}&\quad A'^\top\lambda \leq c(\mathbf{z})\\ &\quad B z \leq d\\ &\quad \lambda \geq 0, z_i \in \{0,1\}. \end{align*} $$

Question: Switching to relaxed program introduces integrality gap. How can I check the extent of/minimize its impact on the solution of the final problem?


1 Answer 1


If I understand correctly and you want a primal-dual formulation of the lower-level problem you may want to consider that: DG (duality gap)= cX-bλ (primal obj.- dual obj.). Given that, your problem can be equivalently written as: min DG s.t. primal constraints, dual(of the relaxed primal) constraints, z in {0,1}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.