Warm tip: This article is reproduced from serverfault.com, please click

Non-optimal result from MIP program in Google OR Tools

发布于 2020-12-11 01:49:11

I was working on a sample MIP program, a selection of a coed sports team starting lineup, and found a small example that comes up with a non-optimal result in Google OR-tools.

The basics: Choose 5 starters from a team of n>5 players. At least two starters must be female. Scratched players can not start. The objective function is a simple sum of the skill-level of the starters. The code is:

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

The objective function returns as 55 even though a solution of 56 exists. In fact, adding an additional constraint (commented out in the code above) will yield the optimal result. (Mike can start instead of Bill or Tom and not violate any constraints.)

So what gives? Am I going something wrong? Why is the original code not providing the optimal solution? Am I using the correct solver?? I would love to think this is a problem in my model specification but, if so, it is eluding me.

Questioner
Leonard Armstrong
Viewed
0
Stradivari 2020-12-11 10:20:43

It works well for CBC and SAT, looks like you have to set the PRIMAL_TOLERANCE for SCIP.

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