1
$\begingroup$

Could anyone confirm me if I write the correct dual for my problem? The different sets confuse me a lot.

enter image description here $s$ is the source node and $t$ the sink node. enter image description here

I'm uncertain if the last dual constraint in necessary.

$\endgroup$
3
  • 1
    $\begingroup$ Please use MathJax. You have a typo ($A3$ instead of $A^3$). Also, your primal problem doesn't mention $A^4$ anywhere. And do you have lower bounds $X_a \ge 0$? $\endgroup$
    – RobPratt
    May 16 at 20:48
  • $\begingroup$ Sorry that I missed the $A3$. $A^4$ is part of $A$, but is not in the objective function. It's in the "Notice that". $\endgroup$
    – orpanter
    May 16 at 20:51
  • 1
    $\begingroup$ OK, thank you for the clarification. Two more typos: $x$ should be $X$, and $X_e$ should be $X_a$. $\endgroup$
    – RobPratt
    May 16 at 21:03

1 Answer 1

3
$\begingroup$

Looks almost correct to me. Two issues:

  • Your $ \le$ dual constraints suggest that you omitted $X_a \ge 0$ in the primal. If instead $X_a$ is free, then your dual constraints should be $=$.
  • Your Tail and Head are reversed in the dual.
$\endgroup$
2
  • $\begingroup$ Thank you so much! I spend two whole week fighting with this! My first time with a model like this with so many subsets. $\endgroup$
    – orpanter
    May 16 at 21:06
  • $\begingroup$ Glad to help. Please mark my answer as accepted. Also, you might find Arthur Benjamin's S-O-B Method useful. $\endgroup$
    – RobPratt
    May 16 at 22:28

Your Answer

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

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