HAVING DIFFERENT SOLUTIONS FOR THE SAME PROBLEM

[vizcayal]

Details for the issue

What did you do? Trying to solve a large LP problem, with 8k variables

What did you expect to see?

the same solution for the same problem,

What did you see instead?

different solutions for the same problem

Useful extra information

The info below often helps, please fill it out if you're able to. :)

What operating system are you using?

• [ X] Windows: ( _version:11 )
• [ ] Linux: ( distro: ___ )
• [ ] Mac OS: ( version: ___ )
• [ ] Other: ___

I'm using python version:

• [ ] 2.7
• [ ] 3.4
• [ ] 3.5
• [ ] 3.6
• [X ] Other: 3.7

I installed PuLP via:

• [ X] pypi (python -m pip install pulp)
• [ ] github (python -m pip install -U git+https://github.com/coin-or/pulp)
• [ ] Other: ___ (conda?)

Did you also

• [ X] Tried out the latest github version: https://github.com/coin-or/pulp
• [ ] Searched for an existing similar issue: https://github.com/coin-or/pulp/issues?utf8=%E2%9C%93&q=is%3Aissue%20

[stumitchell]

Hi this is an underlying problem with the CBC library on which pulp is based. It can be quite difficult to make an LpSolver return the same solution.

However, it should return the same objective function if run in the same manner. i.e. the solutions should be as good as each other even if the solutions are different.

To verify there is nothing wrong with pulp (python dictionaries did have a few issues before we moved to ordered dicts) please verify the the .lp or .mps files produced are identical.

[guifcoelho]

Many solvers have underlying (random) heuristics that try to accelerate solution time. Have you tried fixing the solver's random seed value? If you are using CBC or CLP (PuLP's default solvers), you should check on this

[chriswasser]

While it is certainly possible that the different solutions occur due to randomness in the underlying CBC solver, I noticed that the (intermediate) MPS files produced by PuLP can also differ between different executions of the same code. Due to this behaviour, CBC receives different input files which could lead to different column / row orders during the solution process potentially resulting in alternative solutions being found. To produce the same intermediate MPS files, you can set the PYTHONHASHSEED prior to invoking python3 like this:

# on windows cmd
> set PYTHONHASHSEED=123456
# on windows powershell
> $env:PYTHONHASHSEED=123456
# on linux / macos shell
$ export PYTHONHASHSEED=123456
$ python3 script.py ...

The value for this environment variable does not matter, just that it is the set to the same value for all of your python3 instances. As a side note: The feature of hash randomization was introduced in Python 3.2.3 to prevent DOS attacks which exploit the worst case performance of dict construction. Setting PYTHONHASHSEED disables this hash randomizations. Read more about the implications of this here and here.

[bsaunders23]

Hi there, have you tried setting an explicit RandomSeed for the solver? Often you'll get different results since there's some randomization involved in splitting between ties which impacts the cutting planes/heuristic solution (and maybe the Branch-and-Bound strategy?). Explanation of variable below from running cbc executable plus example of how to set in solver:

Welcome to the CBC MILP Solver 
Version: 2.10.3
Build Date: Dec 15 2019

CoinSolver takes input from arguments ( - switches to stdin)
Enter ? for list of commands or help
Coin:RandomS??
randomS(eed) : Random seed for Clp
Initialization of the random seed for pseudo-random numbers used to
break ties in degenerate problems. This may yield a different continuous
optimum and, in the context of Cbc, different cuts and heuristic solutions.
The special value of 0 lets CLP use the time of the day for the initial
seed.
<Range of values is 0 to 2147483647;
        current 1234567>

Example

import pulp
seed=20
cbc_solver = pulp.PULP_CBC_CMD(keepFiles=False,
             msg=True,
             threads=8,
             #Set random seed to ensure reproducability, passes as command-line arg to solver
             options= [f"RandomS {seed}"]
             )
model = pulp.LpProblem(...)
...
model.solve(cbc_solver)