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?


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.