The primal assignment problem that I have is: max ∑ i = i N ∑ j = 1 N c i j x i j subject to ∑ i = 1 N x i j = 1 , j = 1 , … , N ∑ j = 1 N x i j = 1 , i = 1 , … , N x i , j ∈ { 0 , 1 } and I would like to obtain its dual, which should be min p j { ∑ i = 1 N p j + ∑ i = 1 N max { a i j − p j } } Can you give me any hints on how to approach this derivation? I have tried with Lagrange multipliers but I have not been able to reach this expression.

Question

The primal assignment problem that I have is:                                  max                  ∑                      i            =            i                    N                          ∑                      j            =            1                    N                          c                      i            j                                    x                      i            j                                                    subject to                                                    ∑                      i            =            1                    N                          x                      i            j                          =        1        ,                          j        =        1        ,        …        ,        N                                                    ∑                      j            =            1                    N                          x                      i            j                          =        1        ,                          i        =        1        ,        …        ,        N                                            x                      i            ,            j                                   ∈        {        0        ,        1        }            and I would like to obtain its dual, which should be      min                  p        j                        {            ∑          i      =      1        N        p    j    +      ∑          i      =      1        N    max  {      a          i      j        −      p    j    }            }      Can you give me any hints on how to approach this derivation? I have tried with Lagrange multipliers but I have not been able to reach this expression.

morssiden5g · Accepted Answer

I don&#039;t know why you want to transform a standard LP problem, as the dual of the AP is, into a min-max problem.Anyway the transformation should be as follows.Let       α    j    ,     j  =  1  ,  …  ,  N be the dual multipliers associated to the first set of constraints and       β    i    ,     i  =  1  ,  …  ,  N those associated to the second set of constraints. Then, the ordinary dual is                              min                      α            ,            β                                                                 ∑                      j            =            1                    N                          α          j                +                  ∑                      i            =            1                    N                          β          i                                                    α          j                +                  β          i                ≥                  c                      i            j                                                     ∀        i        ,        j        =        1        ,        …        ,        N            Observe now that      β    i    ≥      c          i      j        −      α    j          ∀  i  ,  j  =  1  ,  …  ,  N  ⟹            β    i    =      max          1      ≤      j      ≤      N        {      c          i      j        −      α    j    }        ∀  i  =  1  ,  …  ,  NHence we get                              min                      α                                             ∑                      j            =            1                    N                          α          j                +                  ∑                      i            =            1                    N                          max                      1            ≤            j            ≤            N                          {                  c                      i            j                          −                  α          j                }

The primal assignment problem that I have is: <mtable columnalign="right left right left righ

Answered question

Answer & Explanation

New Questions in High school geometry