一个网络问题，如何建立其网络LP模型？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EE - 电子工程

一个网络问题，如何建立其网络LP模型？

一个网络问题，如何建立其网络LP模型？# EE - 电子工程

w*h2008-04-03 07:04

1 楼

假如一个网络中，每条链路对应一个effort to eliminate that link from the
network.现在的问题是如何寻找最小的effort to block all links from a source
node to a sink node。
如何建立关于这个问题的数学模型？用线性问题LP方程求解？

m*i2008-04-03 07:04

2 楼

Do you mean that you want to find the minimum cut set between the source and
the destination?

w*h2008-04-03 07:04

3 楼

差不多，但不完全是。
我需要屏蔽所有可能的 from source node to sink node之间的communication。
屏蔽每条链路有一个相应cost,现在需要寻找最小cost,用于屏蔽所有可能的从s到t的链
路。

and

【在 m***i 的大作中提到】

: Do you mean that you want to find the minimum cut set between the source and
: the destination?

m*i2008-04-03 07:04

4 楼

What do you mean by 链路? do you mean link or path?
If you block any cut between the source and the sink, you block all the
possible communication paths between them.

【在 w****h 的大作中提到】

: 差不多，但不完全是。
: 我需要屏蔽所有可能的 from source node to sink node之间的communication。
: 屏蔽每条链路有一个相应cost,现在需要寻找最小cost,用于屏蔽所有可能的从s到t的链
: 路。
:
: and

w*h2008-04-03 07:04

5 楼

链路指的是link,不是path
所以我要找any cut between s & t；但是有多种any cut，我要找最小的一个。
这个和最大流问题不一样。那是找最大，这是找最小。

【在 m***i 的大作中提到】

: What do you mean by 链路? do you mean link or path?
: If you block any cut between the source and the sink, you block all the
: possible communication paths between them.

m*i2008-04-03 07:04

6 楼

Let us assume that each link has weight of c_{i}. Let C^{*}=\max{c_{i}}+1.
Next, we can change the weight of link i to c'_{i}=C^{*}=c_{i}.
Under the new set of weights, we solve for the maximum flow problem.
It is equivalent to solving the minimum flow problem in the original problem.

【在 w****h 的大作中提到】

: 链路指的是link,不是path
: 所以我要找any cut between s & t；但是有多种any cut，我要找最小的一个。
: 这个和最大流问题不一样。那是找最大，这是找最小。

w*h2008-04-03 07:04

7 楼

多谢。那么这个weight c_{i}和cost_{i}有什么关系呢？
开始仅定义了每条链路的cost,也就是从网络中去掉这个链路的代价。
另外，你的c'_{i}=C^{*}=c_{i}应该写错了吧，觉得是c'_{i}=C^{*}－c_{i}

problem.

【在 m***i 的大作中提到】

: Let us assume that each link has weight of c_{i}. Let C^{*}=\max{c_{i}}+1.
: Next, we can change the weight of link i to c'_{i}=C^{*}=c_{i}.
: Under the new set of weights, we solve for the maximum flow problem.
: It is equivalent to solving the minimum flow problem in the original problem.

m*i2008-04-03 07:04

8 楼

c_{i} seems to me as the effort to block that link. I donot know what is
cost_{i}.
confused about this statement.
Yes, you are right. It is a typo.

【在 w****h 的大作中提到】

: 多谢。那么这个weight c_{i}和cost_{i}有什么关系呢？
: 开始仅定义了每条链路的cost,也就是从网络中去掉这个链路的代价。
: 另外，你的c'_{i}=C^{*}=c_{i}应该写错了吧，觉得是c'_{i}=C^{*}－c_{i}
:
: problem.

w*h2008-04-03 07:04

9 楼

C^{*}=\max{c_{i}}+1,为什么要加1？
总结，你的意思是，对于这个网络，首先寻找所有链路最大的effort of blocking,记
为c^{*},用这个最大c^{*}减去所有c_{i}得到各自链路的标记c，再用最大流方法求解
，所得的答案也就是本题要求的屏蔽从源到目标所有通信的最小代价问题。

【在 m***i 的大作中提到】

:
: c_{i} seems to me as the effort to block that link. I donot know what is
: cost_{i}.
: confused about this statement.
: Yes, you are right. It is a typo.

m*i2008-04-03 07:04

10 楼

To avoid the possibility that some link might have zero cost. In fact, you
can use a very large number to do so.
you are right.

【在 w****h 的大作中提到】

: C^{*}=\max{c_{i}}+1,为什么要加1？
: 总结，你的意思是，对于这个网络，首先寻找所有链路最大的effort of blocking,记
: 为c^{*},用这个最大c^{*}减去所有c_{i}得到各自链路的标记c，再用最大流方法求解
: ，所得的答案也就是本题要求的屏蔽从源到目标所有通信的最小代价问题。