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.

  • 0
    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.2011-08-23

1 Answers 1

5

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

  • 0
    @T W Lai: You're welcome. I'm glad my comments were so helpful for you. :)2011-08-23