示例 11：最大流问题

问题描述

定义有向连通图 $G=(V,E)$，$V$ 为图中的节点集合，$E$ 为图中的弧集合，其中 $r$ 起点，$e$ 为终点，弧边的权表示该弧所能经过的最大流量：

	0	1	2	3	4	5	6	7	8
0	-	15	10	40	-	-	-	-	-
1	-	-	-	-	15	-	-	-	-
2	-	-	-	-	-	10	35	-	-
3	-	-	-	-	-	-	30	20	-
4	-	-	-	-	-	-	10	-	-
5	-	-	-	-	-	-	-	-	10
6	-	-	-	-	-	-	-	10	-
7	-	-	-	-	-	-	-	-	45
8	-	-	-	-	-	-	-	-	-

数学模型

变量

$x_{ij}\in Z^{+}$：在节点 $i$ 到 $j$ 流通的流量单位。

$f\in Z^{+}f$：流量。

中间值

1. 流入总流量

$$I{n}_i=\sum _{j\in V}{x}_{ji},\mathrm{\forall }i\in V$$

2. 流出总流量

$$Ou{t}_i=\sum _{j\in V}{x}_{ij},\mathrm{\forall }i\in V$$

目标函数

1. 最大化通过流量

$$maxf$$

约束条件

1. 起点 $r$ 流出的流量

$$Ou{t}_r-I{n}_r=f$$

2. 终点 $e$ 流入的流量

$$I{n}_e-Ou{t}_e=f$$

3. 通过图中非起点终点的流量平衡约束

$$Ou{t}_i-I{n}_i=0,\mathrm{\forall }i\in (V-\{r,e\})$$

4. 弧容量约束

$$x_{ij}\le c_{ij},\mathrm{\forall }i\in V,\mathrm{\forall }j\in V$$

期望结果

	0	1	2	3	4	5	6	7	8
0	-	10	10	30	-	-	-	-	-
1	-	-	-	-	10	-	-	-	-
2	-	-	-	-	-	10	0	-	-
3	-	-	-	-	-	-	0	20	-
4	-	-	-	-	-	-	10	-	-
5	-	-	-	-	-	-	-	-	10
6	-	-	-	-	-	-	-	10	-
7	-	-	-	-	-	-	-	-	30
8	-	-	-	-	-	-	-	-	-

代码实现

kotlin

import fuookami.ospf.kotlin.utils.math.*
import fuookami.ospf.kotlin.utils.concept.*
import fuookami.ospf.kotlin.utils.functional.*
import fuookami.ospf.kotlin.utils.multi_array.*
import fuookami.ospf.kotlin.core.frontend.variable.*
import fuookami.ospf.kotlin.core.frontend.expression.polynomial.*
import fuookami.ospf.kotlin.core.frontend.expression.symbol.*
import fuookami.ospf.kotlin.core.frontend.inequality.*
import fuookami.ospf.kotlin.core.frontend.model.mechanism.*
import fuookami.ospf.kotlin.core.backend.plugins.scip.*

sealed class Node : AutoIndexed(Node::class)
class RootNode : Node()
class EndNode : Node()
class NormalNode : Node()

val nodes: List<Node> = ... // 节点列表
val capacities: Map<Node, Map<Node, Flt64>> = ... // 容量矩阵

// 创建模型实例
val metaModel = LinearMetaModel("demo11")

// 创建变量
val x = UIntVariable2("x", Shape2(nodes.size, nodes.size))
for (node1 in nodes) {
    for (node2 in nodes) {
        if (node1 == node2) {
            continue
        }
        capacities[node1]?.get(node2)?.let {
            val xi = x[node1, node2]
            xi.range.leq(it)
            metaModel.add(xi)
        }
    }
}

val flow = UIntVar("flow")
metaModel.add(flow)

// 定义中间值
val flowIn = LinearIntermediateSymbols1("flow_in", Shape1(nodes.size)) { i, _ ->
    LinearExpressionSymbol(sum(x[_a, i]), "flow_in_$i")
}
metaModel.add(flowIn)

val flowOut = LinearIntermediateSymbols1("flow_out", Shape1(nodes.size)) { i, _ ->
    LinearExpressionSymbol(sum(x[i, _a]), "flow_out_$i")
}
metaModel.add(flowOut)

// 定义目标函数
metaModel.maximize(flow, "flow")

// 定义约束条件
val rootNode = nodes.first { it is RootNode }
metaModel.addConstraint(
    flowOut[rootNode] - flowIn[rootNode] eq flow,
    "flow_${rootNode.index}"
)

val endNode = nodes.first { it is EndNode }
metaModel.addConstraint(
    flowIn[endNode] - flowOut[endNode] eq flow,
    "flow_${endNode.index}"
)

 for (node in nodes.filterIsInstance<NormalNode>()) {
    metaModel.addConstraint(
        flowOut[node] eq flowIn[node],
        "flow_${node.index}"
    )
}

// 调用求解器求解
val solver = ScipLinearSolver()
when (val ret = solver(metaModel)) {
    is Ok -> {
        metaModel.tokens.setSolution(ret.value.solution)
    }

    is Failed -> {}
}

// 解析结果
val solution: MutableMap<Node, MutableMap<Node, UInt64>> = HashMap()
for (token in metaModel.tokens.tokens) {
    if (token.result!! geq Flt64.one && token.variable belongsTo x) {
        val vector = token.variable.vectorView
        val node1 = nodes[vector[0]]
        val node2 = nodes[vector[1]]
        solution.getOrPut(node1) { mutableMapOf() }[node2] = token.result!!.round().toUInt64()
    }
}

完整实现请参考：

• Kotlin