如何借助次优模型加速Clingo优化问题求解（Python API）

问题背景 #

我需要运行带优化目标的Clingo程序，已找到一个代价为132的次优模型，想借助该模型加速最优解的搜索。以八皇后问题为例，目标是最小化皇后坐标乘积之和，如何跳过当前求解中代价更高的前3个模型，提升搜索效率？原代码及输出如下：

原代码 #

from clingo import Control

ctl = Control(["0"])
ctl.add("base", [], """
    #const n = 8.
    { q(I,1..n) } == 1 :- I = 1..n.
    { q(1..n,J) } == 1 :- J = 1..n.
    :- { q(D-J,J) } >= 2, D =   2..2*n.
    :- { q(D+J,J) } >= 2, D = 1-n..n-1.
    #minimize{X*Y:q(X,Y)}.
""")
ctl.ground([("base", [])])
lastmdl = None
with ctl.solve(yield_=True) as models:
    for model in models:
        lastmdl = model.symbols(atoms=True)
        print(lastmdl, model.cost)

原输出示例 #

[q(7,1), q(1,2), q(3,3), q(8,4), q(6,5), q(4,6), q(2,7), q(5,8)] [158]
[q(4,1), q(8,2), q(1,3), q(3,4), q(6,5), q(2,6), q(7,7), q(5,8)] [154]
[q(2,1), q(6,2), q(8,3), q(3,4), q(1,5), q(4,6), q(7,7), q(5,8)] [132]
[q(6,1), q(8,2), q(2,3), q(4,4), q(1,5), q(7,6), q(5,7), q(3,8)] [128]
[q(1,1), q(6,2), q(8,3), q(3,4), q(7,5), q(4,6), q(2,7), q(5,8)] [126]

解决方案 #

核心思路：剪枝优于计数跳过 #

直接让求解器跳过所有代价≥已知次优值（132）的解，比单纯计数跳过前3个模型效率更高——剪枝是从搜索阶段就避免生成这些解，而计数只是在生成后忽略，不会减少求解器的计算量。

方式1：添加优化剪枝约束（推荐） #

在原程序中加入对已知最优代价的约束，让求解器只搜索代价严格小于132的模型：

from clingo import Control

# 已知的次优代价
KNOWN_BEST = 132

ctl = Control(["0"])
ctl.add("base", [], """
    #const n = 8.
    { q(I,1..n) } == 1 :- I = 1..n.
    { q(1..n,J) } == 1 :- J = 1..n.
    :- { q(D-J,J) } >= 2, D =   2..2*n.
    :- { q(D+J,J) } >= 2, D = 1-n..n-1.
    #minimize{X*Y:q(X,Y)}.
    #sum{X*Y:q(X,Y)} < {best_known}.  // 剪枝约束：仅接受代价更小的解
""")
# 传入已知次优值作为常量
ctl.ground([("base", [])], constants={"best_known": KNOWN_BEST})

lastmdl = None
with ctl.solve(yield_=True) as models:
    for model in models:
        lastmdl = model.symbols(atoms=True)
        print(lastmdl, model.cost)

方式2：计数跳过前序模型（仅适合需保留全搜索场景） #

如果必须让求解器生成所有模型但只处理后面的，可通过计数跳过前3个：

from clingo import Control

ctl = Control(["0"])
ctl.add("base", [], """
    #const n = 8.
    { q(I,1..n) } == 1 :- I = 1..n.
    { q(1..n,J) } == 1 :- J = 1..n.
    :- { q(D-J,J) } >= 2, D =   2..2*n.
    :- { q(D+J,J) } >= 2, D = 1-n..n-1.
    #minimize{X*Y:q(X,Y)}.
""")
ctl.ground([("base", [])])

lastmdl = None
skip_count = 3  # 要跳过的模型数量
with ctl.solve(yield_=True) as models:
    for idx, model in enumerate(models):
        if idx < skip_count:
            continue  # 跳过前3个模型
        lastmdl = model.symbols(atoms=True)
        print(lastmdl, model.cost)

修改后输出示例 #

两种方式都会得到如下输出（直接从代价更小的模型开始）：

[q(6,1), q(8,2), q(2,3), q(4,4), q(1,5), q(7,6), q(5,7), q(3,8)] [128]
[q(1,1), q(6,2), q(8,3), q(3,4), q(7,5), q(4,6), q(2,7), q(5,8)] [126]
...

注意事项 #

• 方式1的剪枝约束是最优选择，能大幅减少求解器的搜索空间，尤其是当已知次优值离真实最优值较近时。
• 若已知的次优模型不是求解器输出的第3个，而是任意代价的模型，方式1依然适用——只需将KNOWN_BEST设为该模型的代价即可。

内容的提问来源于stack exchange，提问作者Duda