6
$\begingroup$

I am a student and I am studying the following problem during my spare time. Your comments and suggestions would be helpful.

Given the following primal program: (Decision variables are $\xi_{v}$, others are parameters)

(rewritten according to the valuable comments made by Mike Spivey)
max $\sum_{v\in A}\left(\sum_{i\in N}\sum_{j\in G_{i}}\alpha_{ijv}\cdot w_{i}\cdot d_{ij}\right)\cdot\xi_{v}$
s.t. $\sum_{v\in A}\left(\sum_{j\in G_{i}}\alpha_{ijv}\right)\cdot\xi_{v}\leq1,\,\,\,\,\forall i\in N,$
$\sum_{v\in A}\left(\sum_{k\in U_{ij}}\alpha_{ikv}\right)\cdot\xi_{v}\leq x_{j},\,\,\,\,\forall i\in N,j\in F_{i},$
$\xi_{v}\geq0,\,\,\,\,\forall v\in A.$

Then I try to write the dual of it. Suppose $\beta_{i}$ are the dual variable corresponding to the first set of constraints and $\mu_{ij}$ are the dual variable corresponding to the second set of constraints.

(modified according to the valuable comments made by Mike Spivey)
min $\sum_{i\in N}\sum_{j\in F_{i}}\left(x_{j}\cdot\mu_{ij}+\beta_{i}\right)$
s.t.
$\sum_{i \in N}\left(\sum_{j\in G_{i}}\alpha_{ijv}\right)\cdot\beta_{i}+\sum_{i \in N}\sum_{j\in F_{i}}\left(\sum_{k\in U_{ij}}\alpha_{ikv}\right)\cdot\mu_{ij}\geq \sum_{i\in N}\sum_{j\in G_{i}}\alpha_{ijv}\cdot w_{i}\cdot d_{ij},\,\,\,\,\forall v\in A,$
$\beta_{i}\geq0,\forall i\in N,$
$\mu_{ij}\geq0,\forall i\in N,j\in F_{i}.$

However, I am sure that I must have made some mistakes. It is because when I tried to implement the above two programs using IBM ILOG OPL, it gave me different solutions at optimality! Would you please guide me to the correct direction? I would be very grateful if you point out what's wrong in my conversion. It is because I have spent several days but I still have no idea. Thank you very much.

$\endgroup$
2
  • $\begingroup$ Are you getting the same answer for the primal and the dual problems now? Or is there still some mistake? $\endgroup$ Aug 23, 2011 at 5:19
  • $\begingroup$ Thank you very much for your valuable comments. Your revision to the primal program makes me understand my dual program was definitely incorrect. However, I still get different answers with the amendments. That is, they have different objective values at optimality. Actually, your dual program looks perfectly correct to me. I am really puzzled now. $\endgroup$
    – T W Lai
    Aug 23, 2011 at 5:36

1 Answer 1

5
$\begingroup$

I think the problem is with the constraints in the dual (added: there's also a problem with the objective in the dual, which I just corrected), and I think it would help spot the mistake if we rewrite the primal problem to emphasize the primal variables. Doing that, the primal looks like this:

max $\sum_{v\in A}\left(\sum_{i\in N}\sum_{j\in G_{i}}\alpha_{ijv}\cdot w_{i}\cdot d_{ij}\right)\cdot\xi_{v}$
s.t.
$\sum_{v\in A}\left(\sum_{j\in G_{i}}\alpha_{ijv}\right)\cdot\xi_{v}\leq1,\,\,\,\,\forall i\in N,$
$\sum_{v\in A}\left(\sum_{k\in U_{ij}}\alpha_{ikv}\right)\cdot\xi_{v}\leq x_{j},\,\,\,\,\forall i\in N,j\in F_{i},$
$\xi_{v}\geq0,\,\,\,\,\forall v\in A.$

Then, for the dual I get

min $\sum_{i\in N}\beta_{i} + \sum_{i\in N}\sum_{j\in F_{i}}x_{j}\cdot\mu_{ij}$
s.t.
$\sum_{i \in N}\left(\sum_{j\in G_{i}}\alpha_{ijv}\right)\cdot\beta_{i}+\sum_{i \in N}\sum_{j\in F_{i}}\left(\sum_{k\in U_{ij}}\alpha_{ikv}\right)\cdot\mu_{ij}\geq \sum_{i\in N}\sum_{j\in G_{i}}\alpha_{ijv}\cdot w_{i}\cdot d_{ij},\,\,\,\,\forall v\in A,$
$\beta_{i}\geq0,\forall i\in N,$
$\mu_{ij}\geq0,\forall i\in N,j\in F_{i}.$

Remember that there's a constraint in the dual for each variable in the primal, so in the dual the constraints should only be indexed by the values in $A$.

$\endgroup$
3
  • 1
    $\begingroup$ The second mistake I spotted - in the dual objective - was that $\beta_i$ was being summed over $F_i$ for each $i \in N$, which is much too often. You only want to sum $\beta_i$ over $N$. Does this new version work? $\endgroup$ Aug 23, 2011 at 5:51
  • 1
    $\begingroup$ Wonderful!! It now works!! Thank you very much!! Your comments are really helpful and I now have better understanding of the primal-dual relationship. Thank you!! $\endgroup$
    – T W Lai
    Aug 23, 2011 at 6:26
  • $\begingroup$ @T W Lai: You're welcome. I'm glad my comments were so helpful for you. :) $\endgroup$ Aug 23, 2011 at 14:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .