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?
