Google 或工具中 MIP 程序的非最佳结果

Question

我正在研究一个示例 MIP 程序，一个男女混合运动队首发阵容的选择，并发现了一个在 Google OR 工具中得出非最佳结果的小例子。

基础知识：从 n>5 名球员中选择 5 名首发球员。至少有两名先发球员必须是女性。划伤玩家无法启动。 objective 函数是初学者技能水平的简单求和。代码是：

import pandas as pd
from ortools.linear_solver import pywraplp

# %% Read the data from an external file
pname   = ["Tom", "Joe", "Bill", "Mike", "Frank", "Mary", "Sue", "JoAnn"]
skill   = [ 11.0,  13.0,   11.0,   12.0,    14.0,   10.0,  10.0,     7.0]
female  = [    0,     0,      0,      0,       0,      1,     1,       1]
scratch = [    0,     0,      0,      0,       1,      0,     0,       0]

# %% Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')

# %% Add the variables
starters = pd.Series([ solver.BoolVar(name = f'dv_{n}') for n in pname ])

# %% Add the objective function
solver.Maximize(solver.Sum(skill * starters))

# %% Add the constraints
solver.Add(solver.Sum(starters) == 5)
solver.Add(solver.Sum(starters * female) >= 2)
solver.Add(solver.Sum(starters * scratch) == 0)
#solver.Add(starters[3] == 1)

# %% Invoke the solver
status = solver.Solve()

# %% Report results
print("  START?   NAME PVAL     SEX SCRATCHED")
for i in (1,0) :
    for n in range(starters.count()) :
        if starters[n].SolutionValue() == i :
            print(
                f'{n} {"YES   " if i == 1 else "NO    "} {pname[n]:>6} {skill[n]:4.0f} ',
                f'{"female" if female[n] else "  male"} ',
                f'{"scratched" if scratch[n] else " - "}')
    print("---------------")
print(f'OBJECTIVE VALUE: {solver.Objective().Value()}')
# %%

objective 函数 returns 为 55，即使存在 56 的解。事实上，添加一个额外的约束（在上面的代码中注释掉）将产生最佳结果。（Mike 可以代替 Bill 或 Tom 开始并且不违反任何约束。）

那么是什么原因呢？我做错了什么吗？为什么原始代码没有提供最优解？我使用的是正确的求解器吗？？我很乐意认为这是我的模型规范中的一个问题，但如果是这样，我就无法理解它。

Answer 1

它适用于 CBC 和 SAT，看来您必须为 SCIP 设置 PRIMAL_TOLERANCE。

solver_parameters = pywraplp.MPSolverParameters()
solver_parameters.SetDoubleParam(pywraplp.MPSolverParameters.PRIMAL_TOLERANCE, 0.001)
status = solver.Solve(solver_parameters)

Google 或工具中 MIP 程序的非最佳结果

Non-optimal result from MIP program in Google OR Tools

python

linear-programming

python-3.x

or-tools

mixed-integer-programming