如何为这个问题写出 milp 方程?
How to write milp equation for this problem?
考虑经典的网络流问题,其中的约束是从一个顶点流出的流量等于流入它的总和。考虑有一个更具体的约束,其中流可以在边之间拆分。
我有两个问题:
如何使用决策变量来识别节点 j 正在从多个边接收项目?
如何创建另一个方程来确定在汇聚节点中加入来自不同边缘的 x 个项目的成本(每个项目 2 个时间单位)?
这是一个棘手的建模问题。让我们分部分来。
Consider having a more specific constraint where the flow can be split between edges
我在这里假设您有一个建模为实变量集的经典流约束 y_ij。因此,流可以在两个或多个弧之间拆分。
How can I use a decision variable to identify that node j is receiving items from multiple edges?
您需要创建一个额外的二进制变量 z_ij 来表示您的流程。您还必须创建以下约束:
接下来,您将需要另一个额外的整数变量集,比方说 p_i 和一个额外的约束
然后,p_i会在节点j中存储传入弧的数量,用于发送流。由于您将尝试最小化连接弧的成本(我认为),因此您需要使用 <=.
How to create another equation to determine the cost(2 unit of time per item) of joining x number of items from different edges in the sink node?
为此,您可以使用 p_i 的值并乘以加入流程的预定义成本。
考虑经典的网络流问题,其中的约束是从一个顶点流出的流量等于流入它的总和。考虑有一个更具体的约束,其中流可以在边之间拆分。
我有两个问题:
如何使用决策变量来识别节点 j 正在从多个边接收项目?
如何创建另一个方程来确定在汇聚节点中加入来自不同边缘的 x 个项目的成本(每个项目 2 个时间单位)?
这是一个棘手的建模问题。让我们分部分来。
Consider having a more specific constraint where the flow can be split between edges
我在这里假设您有一个建模为实变量集的经典流约束 y_ij。因此,流可以在两个或多个弧之间拆分。
How can I use a decision variable to identify that node j is receiving items from multiple edges?
您需要创建一个额外的二进制变量 z_ij 来表示您的流程。您还必须创建以下约束:
接下来,您将需要另一个额外的整数变量集,比方说 p_i 和一个额外的约束
然后,p_i会在节点j中存储传入弧的数量,用于发送流。由于您将尝试最小化连接弧的成本(我认为),因此您需要使用 <=.
How to create another equation to determine the cost(2 unit of time per item) of joining x number of items from different edges in the sink node?
为此,您可以使用 p_i 的值并乘以加入流程的预定义成本。