The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the applicability of the strong duality theorem.
Let there be an acyclic network $G$ with source and target nodes ${s,t}\in A$. The capacity per arc is denoted by $u_e\in\mathcal{R}^+$. Some of the arcs are blocked, denoted by $\beta_e=1$ and otherwise $\beta_e=0$. We are interested in finding a maximum flow between $s$ and $t$ subject to linear budget constraints and the possibility to unblock arcs, denoted by $b_e=1$.
I formulate it as follows: $$ \max_{\bar{f},\bar{b}} \sum_{f_e\in I(t)}{f_e}$$ $$s.t.\sum_{f_e\in I(v)}{f_e} - \sum_{f_e\in O(v)}{f_e} = 0 \qquad \forall v\in A\setminus\{s,t\}$$ $$f_e - u_e \cdot (1-\beta_e+b_e) \leq 0 \qquad \forall e\in E$$ $$\sum{c^f_e \cdot f_e}+\sum{c^b_e \cdot b_e} - B \leq 0$$ $$f_e\geq 0, b_e\in\{0,1\} \qquad \forall e\in E$$
In order to examine the dual problem, I examine constraint qualification. For example, Slater's theorem does not hold due to the integral variables (non-convex hull). Is there another constraint qualification suitable for this mixed-integer problem and if so, how do I derive the dual of this problem, related to the min-cut formulation, from the Lagrangian dual?
