For any feasible assignment, the unit row and column sums give

i, j \sum \overset{c}{ˉ}_{ij} x_{ij} = i, j \sum c_{ij} x_{ij} - i \sum u_{i} j \sum x_{ij} - j \sum v_{j} i \sum x_{ij} = i, j \sum c_{ij} x_{ij} - i \sum u_{i} - j \sum v_{j} .

Thus the transformed objective differs by the fixed constant

- i \sum u_{i} - j \sum v_{j} .

(2)

Every feasible assignment shifts by that same amount, so all objective comparisons and all optimal assignments remain unchanged. The calculation also holds for fractional feasible points of the assignment LP relaxation. The numbers

u_{i}, v_{j}

are assignment dual potentials.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

Past exam of the integer programming course of the University of Oxford / 2011 / 3 / b

Solution

 Ancestors (11)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the integer programming course of the University of Oxford / 2011 / 3 / b

Solution

 Ancestors (11)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

 Discussion (0) New discussion