最小圆问题¶

类别： 选址

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

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

问题描述¶

Smallest Circle Problem（也称为 Minimum Covering Circle Problem 或 Smallest Enclosing Circle Problem）是一个计算几何问题，其目的是在欧几里得平面上计算包含给定点集的最小圆。

该问题是一个 Facility Location Problem（1-Center Problem）的实例，其中需要为新设施选择一个位置，以便为多个客户提供服务，并最小化任何客户到达该新设施所需的最远距离。

学习要点¶

使用 OptAgent 的 float 决策变量建模圆心坐标
使用非线性算子 sqrt 和幂运算计算圆的半径
区分圆心决策变量与由圆心推导出的半径表达式

数据¶

数据文件的格式如下：

第一行：点的数量
接下来几行：对于每个点，其 x 和 y 坐标

建模思路¶

Smallest Circle Problem 的 OptAgent 模型使用两个 float 决策变量分别表示圆心的横坐标和纵坐标。通过 sqrt、max 和幂运算，将半径计算为圆心到所有给定点距离的最大值。半径可由圆心坐标推导，因此只是中间表达式，不需要额外的决策变量。

目标函数是最小化圆的半径。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve


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


def read_instance(instance_file):
    values = iter(read_integers(instance_file))
    nb_points = next(values)
    return [(next(values), next(values)) for _ in range(nb_points)]


def main(input_file, output_file=None, time_limit=6):
    points = read_instance(input_file)
    coord_x = [point[0] for point in points]
    coord_y = [point[1] for point in points]

    model = OptModel()

    # The circle center lies within the points' coordinate bounds.
    x = model.float(min(coord_x), max(coord_x))
    y = model.float(min(coord_y), max(coord_y))

    # The radius is the maximum Euclidean distance from the center.
    squared_distances = [(x - point_x) ** 2 + (y - point_y) ** 2 for point_x, point_y in points]
    radius = model.sqrt(model.max(squared_distances))
    model.minimize(radius)

    solution = solve(model, time_limit_s=float(time_limit))
    if not solution.feasible:
        print(f"No feasible circle found; Status = {solution.status}")
        return solution

    result_text = f"x={x.value:.6f}\ny={y.value:.6f}\nr={radius.value:.6f}"
    print(f"Status = {solution.status}\n{result_text}")
    if output_file is not None:
        Path(output_file).write_text(result_text + "\n", encoding="utf-8")
    return solution

本地运行¶

Notebook 直接调用 main 并显式传入点集实例路径。以下代码格相互独立，可以按需要单独运行；调整 time_limit 可以控制每个实例的求解时间。

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

solution_10points = main(
    INSTANCE_DIR / "10points.txt",
    time_limit=1,
)

solution_20points = main(
    INSTANCE_DIR / "20points.txt",
    time_limit=1,
)

solution_30points = main(
    INSTANCE_DIR / "30points.txt",
    time_limit=1,
)