Google OR Tools 中 MIP 程序的非最佳结果

Question

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

基础知识：从 n>5 名玩家组成的团队中选择 5 名首发。至少两名首发必须是女性。被划伤的玩家无法启动。目标函数是初学者技能水平的简单总和。代码是：

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()}')
# %%

即使存在解 56，目标函数仍返回 55。事实上，添加额外的约束（在上面的代码中注释掉）将产生最佳结果。（迈克可以代替比尔或汤姆开始，并且不违反任何限制。）

那么什么给出呢？我是不是出了什么问题？为什么原来的代码没有给出最优解？我使用了正确的解算器吗？我很想认为这是我的模型规范中的一个问题，但如果是这样，我就无法理解。

Answer 1

它适用于CBCand SAT，看起来您必须设置PRIMAL_TOLERANCEfor SCIP。

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