最大割问题¶

类别： 选址

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

在最大割问题中，我们考虑一个图 G = (V, E)。我们希望找到该图的一个最大割，即将图的顶点划分为两个互补集合 S 和 T，使得 S 和 T 之间的边数尽可能大。等价地，该问题在于找到该图的一个尽可能多边的二部子图。这里，我们考虑该问题的一个更通用的版本：加权最大割问题。每条边都与一个数（其权重）相关联，问题的目标是找到一个顶点的子集 S，使得 S 与其补集之间的边权重之和尽可能大。

学习要点¶

了解 OptAgent 的建模方式：区分决策变量与中间表达式
使用 非线性算子 来确定图中每条边是否在割集中

数据¶

我们提供的最大割问题实例来自 Biq Mac Library。最优解和每个数据集的描述可在此处找到此处。数据文件的格式如下：

顶点数
边数
带边权重的邻接表

建模思路¶

最大割问题的 OptAgent 模型使用布尔决策变量表示每个顶点是否属于子集 S。

由其起点和终点顶点描述的一条边位于割集中，当且仅当恰好有一个顶点属于 S。使用非线性 neq 算子，我们确定每条边是否在割集中。然后我们可以计算目标函数的值，即割集中所有边的权重之和。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve

def read_integers(filename):
    return [int(elem) for elem in Path(filename).read_text(encoding="utf-8").split()]

#
# Read instance data
#
def read_instance(filename):
    file_it = iter(read_integers(filename))
    # Number of vertices
    n = next(file_it)
    # Number of edges
    m = next(file_it)

    # Origin of each edge
    origin = [None] * m
    # Destination of each edge
    dest = [None] * m
    # Weight of each edge
    w = [None] * m

    for e in range(m):
        origin[e] = next(file_it)
        dest[e] = next(file_it)
        w[e] = next(file_it)
    
    return n, m, origin, dest, w

def main(instance_file, output_file=None, time_limit=10):
    n, m, origin, dest, w = read_instance(instance_file)

    model = OptModel()

    # x[i] is true when vertex i belongs to one side of the cut.
    x = [model.bool() for i in range(n)]

    # An edge is cut exactly when its endpoints are in different subsets.
    incut = [
        model.neq(x[origin[e] - 1], x[dest[e] - 1]) for e in range(m)
    ]
    cut_weight = model.sum(w[e] * incut[e] for e in range(m))
    model.maximize(cut_weight)

    solution = solve(model, time_limit_s=float(time_limit))
    side = [int(bool(variable.value)) for variable in x]
    print(
        f"Vertices = {n}; Edges = {m}; Cut weight = {cut_weight.value}; "
        f"Status = {solution.feasible}"
    )
    print("Side assignments:", side)

    if output_file is not None:
        lines = [str(cut_weight.value)]
        lines.extend(f"{i + 1} {side[i]}" for i in range(n))
        Path(output_file).write_text("\n".join(lines) + "\n", encoding="utf-8")
    return solution

本地运行¶

以下代码格演示如何调用 OptAgent 的 Max-Cut 模型。

INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)

solution_g05_60 = main(INSTANCE_DIR / "g05_60.0", time_limit=1)

solution_t2g10 = main(INSTANCE_DIR / "t2g10_5555", time_limit=1)