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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.