Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Are you getting the same answer for the primal and the dual problems now? Or is there still some mistake? –  Mike Spivey Aug 23 '11 at 5:19
    
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. –  T W Lai Aug 23 '11 at 5:36
add comment

1 Answer 1

up vote 5 down vote accepted

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$.

share|improve this answer
1  
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? –  Mike Spivey Aug 23 '11 at 5:51
1  
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!! –  T W Lai Aug 23 '11 at 6:26
    
@T W Lai: You're welcome. I'm glad my comments were so helpful for you. :) –  Mike Spivey Aug 23 '11 at 14:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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