Fdtxjr

What items from the Roman-age tech-level could be used to deter all creatures from entering a small area?

3 doors, three guards, one stone

Why is there no army of Iron-Mans in the MCU?

Unexpected result with right shift after bitwise negation

When is phishing education going too far?

Cauchy Sequence Characterized only By Directly Neighbouring Sequence Members

What's the difference between (size_t)-1 and ~0?

Why don't the Weasley twins use magic outside of school if the Trace can only find the location of spells cast?

Should you tell Jews they are breaking a commandment?

I'm thinking of a number

Is above average number of years spent on PhD considered a red flag in future academia or industry positions?

How can players take actions together that are impossible otherwise?

Notation for two qubit composite product state

Was credit for the black hole image misattributed?

How does modal jazz use chord progressions?

Is it possible to ask for a hotel room without minibar/extra services?

Mortgage adviser recommends a longer term than necessary combined with overpayments

Who can trigger ship-wide alerts in Star Trek?

Is there a service that would inform me whenever a new direct route is scheduled from a given airport?

Unable to start mainnet node docker container

Can a monk deflect thrown melee weapons?

Single author papers against my advisor's will?

Jazz greats knew nothing of modes. Why are they used to improvise on standards?

Direct Experience of Meditation

How to find the dual of max flow using bounding?

0

$begingroup$

I am learning about dual programs in a grad class, but the lectures are lacking. I had to teach myself the bounding method and I understand it, but I'm not sure how to apply it to the Max-flow problem. We did not go over how we obtained the dual in much detail during lecture.

Here is the concept I am trying to use:

To find the dual of
$$max_x c^Tx\
texts.t. Axleq b\
-Ixleq 0
$$
where $I$ is the identity matrix, note that for any $y,z geq 0$ and feasible solution the following must hold:
$$y^T(Ax-b)+z^T(-Ix)leq 0.$$
After some manipulation,
$$(A^Ty-Iz)x leq b^Ty$$
which yields the dual
$$min_y b^Ty\
texts.t. A^Ty-Iz = c\
ygeq 0.$$
We can then eliminate $z$ and get the constraint $A^Txgeq c$.

From my understanding, this works because we can relate $c$ to the coefficient on $x$ in the linear combination of constraints. However, the objective function in Max-flow only deals with flow out of the source and the flow conservation and capacity constraints deal with all flows in the network. Can this method still be applied to find the dual, or is there another method I need to learn?

Here is the Max-flow problem as a LP:
$$max sum_v:(s,v)in E f(s,v)\
texts.t. sum_u:(u,v)in E f(u,v) - sum_w:(v,w)in E f(v,w) = 0, forall vin V - s,t\
f(u,v)leq c(u,v), forall (u,v)in E\
f(u,v)geq 0, forall (u,v)in E.$$

linear-programming duality-theorems

share|cite|improve this question

asked Mar 25 at 19:32

PareodPareod

949

$endgroup$

add a comment | 

0

$begingroup$

I am learning about dual programs in a grad class, but the lectures are lacking. I had to teach myself the bounding method and I understand it, but I'm not sure how to apply it to the Max-flow problem. We did not go over how we obtained the dual in much detail during lecture.

Here is the concept I am trying to use:

To find the dual of
$$max_x c^Tx\
texts.t. Axleq b\
-Ixleq 0
$$
where $I$ is the identity matrix, note that for any $y,z geq 0$ and feasible solution the following must hold:
$$y^T(Ax-b)+z^T(-Ix)leq 0.$$
After some manipulation,
$$(A^Ty-Iz)x leq b^Ty$$
which yields the dual
$$min_y b^Ty\
texts.t. A^Ty-Iz = c\
ygeq 0.$$
We can then eliminate $z$ and get the constraint $A^Txgeq c$.

From my understanding, this works because we can relate $c$ to the coefficient on $x$ in the linear combination of constraints. However, the objective function in Max-flow only deals with flow out of the source and the flow conservation and capacity constraints deal with all flows in the network. Can this method still be applied to find the dual, or is there another method I need to learn?

Here is the Max-flow problem as a LP:
$$max sum_v:(s,v)in E f(s,v)\
texts.t. sum_u:(u,v)in E f(u,v) - sum_w:(v,w)in E f(v,w) = 0, forall vin V - s,t\
f(u,v)leq c(u,v), forall (u,v)in E\
f(u,v)geq 0, forall (u,v)in E.$$

linear-programming duality-theorems

share|cite|improve this question

asked Mar 25 at 19:32

PareodPareod

949

$endgroup$

add a comment | 

$begingroup$

I am learning about dual programs in a grad class, but the lectures are lacking. I had to teach myself the bounding method and I understand it, but I'm not sure how to apply it to the Max-flow problem. We did not go over how we obtained the dual in much detail during lecture.

Here is the concept I am trying to use:

To find the dual of
$$max_x c^Tx\
texts.t. Axleq b\
-Ixleq 0
$$
where $I$ is the identity matrix, note that for any $y,z geq 0$ and feasible solution the following must hold:
$$y^T(Ax-b)+z^T(-Ix)leq 0.$$
After some manipulation,
$$(A^Ty-Iz)x leq b^Ty$$
which yields the dual
$$min_y b^Ty\
texts.t. A^Ty-Iz = c\
ygeq 0.$$
We can then eliminate $z$ and get the constraint $A^Txgeq c$.

From my understanding, this works because we can relate $c$ to the coefficient on $x$ in the linear combination of constraints. However, the objective function in Max-flow only deals with flow out of the source and the flow conservation and capacity constraints deal with all flows in the network. Can this method still be applied to find the dual, or is there another method I need to learn?

Here is the Max-flow problem as a LP:
$$max sum_v:(s,v)in E f(s,v)\
texts.t. sum_u:(u,v)in E f(u,v) - sum_w:(v,w)in E f(v,w) = 0, forall vin V - s,t\
f(u,v)leq c(u,v), forall (u,v)in E\
f(u,v)geq 0, forall (u,v)in E.$$

linear-programming duality-theorems

share|cite|improve this question

asked Mar 25 at 19:32

PareodPareod

949

$endgroup$

share|cite|improve this question

asked Mar 25 at 19:32

PareodPareod

949

share|cite|improve this question

asked Mar 25 at 19:32

PareodPareod

949

asked Mar 25 at 19:32

PareodPareod

949

asked Mar 25 at 19:32

PareodPareod

949