You are not logged in. Please login at to post your questions!


CHEFBOOK - Editorial



Author: Shiplu Hawlader
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Minako Kojima




Linear Programming, Dual of Mincost Max Flow


Given M integers $L_{xy}$ ($1 \le x \le N$ and $1 \le y \le N$) we want to find $N$ integers $P_x$ ($1 \le x \le N$) and $N$ integers $Q_y$ ($1 \le y \le N$) such that for each of the $M$ given integers, $W_{xy} = L_{xy} + P_x - Q_y$ is within the range $(S_{xy}, T_{xy})$ inclusive. If there are several solutions possible, output the one with the least sum of all $W_{xy}$.


Thanks to the author for the explanation.

The problem can be reduced to a similar problem as below:

Given a 2D array. Some cells are empty and some cells contain number $L_{ij}$. We can make two kinds of operation: 1. Increase all the non-empty numbers in some row $i$ by $P_i$ ($P_i \ge 0$) 2. Decrease all the non-empty numbers in some column $j$ by $Q_j$ ($Q_j \ge 0$)

So for each cell $(i,j)$ the new value will be

$W_{ij} = L_{ij} + P_i - Q_j$

You also have two more 2D arrays $S$ and $T$ as the upper and lower bound of the new array $W$. Such that $S_{ij} \le W_{ij} \le T_{ij}$.

Your target is to maximize sum of $W_{ij}$, i.e, Maximize $L_{ij} + P_i - Q_j$

You also need to print $P_i$, $Q_j$.

Solution: Let's formulate primal-simplex.

Let, $sizeRow(i)$ = number of non-empty cells in row $i$. Also $sizeCol(j)$ is defined similarly. So our objective function is: Maximize: $sum(P_i * sizeRow(i)) - sum(Q_j * sizeCol(j))$ [we are omitting constant: $sum(L_{ij})$]

Constraints: $S_{ij} \le L_{ij} + P_i - Q_j \le T_{ij}$

Or both of them boil down to: $P_i - Q_j \le Constant$ or $Q_j - P_i \le Constant$.

So our constraint inequality: $Ax \le B$ will have one special properties: *Every row of $A$ has one $+1$, and one $-1$. Other than that every thing is normal.

Now dual time. Objective function: minimize $B*y$ [you will see in a moment that $B$ is acting as cost of a flow network and $y$ is the flow variables of the arcs]

Constraints: $A' * y \ge column\_matrix[sizeRow(1), ...., -sizeCol(1), ...]$

In $A'$ now we have one $+1$ and one $-1$ in each column. So if you sum all the in-equalities you will get 0 in left side. Right side it's also $0$. So all the $\ge$ are actually $=$.

Now consider, all the columns of $A'$ as directed edge (from say $-1$ to $+1$) and all the rows as vertex. Then you will find: sum(in flow) - sum(out flow) = const. Which is flow-conservative-equation. If the right side is say negative we have demand (arc to sink) and if positive then we have supply (arc from source). We have the cost of those flow in objective function.

So finally we are to solve min-cost maxflow problem.

One thing, One might wonder, why suddenly constraints changed from $\ge$ to $=$ in dual. What is the effect of such change in primal? Primal-dual conversion table says, it means the variable in primal is unconstrained.

Why its so? Our operation was: increase in row, decrease in column. But it gives the liberty to decrease row / increase column too. Suppose you want to decrease a row with only original operations: you can decrease all the columns and then increase other rows.


Author's solution
Tester's solution

This question is marked "community wiki".

asked 14 Jun '15, 00:01

balajiganapath's gravatar image

6★balajiganapath ♦♦
accept rate: 77%

edited 27 Jan '16, 14:00

admin's gravatar image

0★admin ♦♦

This Editorial is only for those who already know how to solve the problem so, please give some more detailed editorial or otherwise remove it too..


answered 15 Jun '15, 20:47

shubham011's gravatar image

accept rate: 0%

please explain in detailed please so learner(beginner)like me ):P also can try to understand too


answered 20 Jun '15, 22:19

rcsldav2017's gravatar image

accept rate: 6%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 14 Jun '15, 00:01

question was seen: 2,358 times

last updated: 27 Jan '16, 14:00