Occasionally reports it has found optimal solution when solution is not optimal

[tmtenbrink]

I was running a comparison of ORTools and this solver. However, for some instances ORTools found better solutions than aries, even though aries had reported them as being optimal.

An instance I was able to reproduce this quite easily was with orb05.jsp. The optimal value should be 887, which Aries does usually find. However, when I did a small sample of running it 20 times, 3 of those reported an optimal value of 889, one an optimal value of 890.

Is this expected, do you maybe know the reason for this?

Thank you.

Reproduce

Run

cargo run --release --bin  scheduler jobshop ./examples/scheduling/instances/jobshop/orb05.jsp

a few times.

Other instances

Other instances where I found a similar problem, but here I did not really extensively test it:

orb05.jsp:{"ortools": {"best": 887.0, "optimal": true}, "aries": {"best": 889.0, "optimal": true}}
ta03.jsp:{"ortools": {"best": 1218.0, "optimal": true}, "aries": {"best": 1222.0, "optimal": true}}
ta01.jsp:{"ortools": {"best": 1231.0, "optimal": true}, "aries": {"best": 1241.0, "optimal": true}}
ta05.jsp:{"ortools": {"best": 1224.0, "optimal": false}, "aries": {"best": 1235.0, "optimal": true}}
ta07.jsp:{"ortools": {"best": 1227.0, "optimal": false}, "aries": {"best": 1236.0, "optimal": true}}
la38.jsp:{"ortools": {"best": 1196.0, "optimal": true}, "aries": {"best": 1202.0, "optimal": true}}
ta04.jsp:{"ortools": {"best": 1175.0, "optimal": true}, "aries": {"best": 1181.0, "optimal": true}}
la40.jsp:{"ortools": {"best": 1222.0, "optimal": true}, "aries": {"best": 1224.0, "optimal": true}}
abz6.jsp:{"ortools": {"best": 943.0, "optimal": true}, "aries": {"best": 945.0, "optimal": true}}
orb02.jsp:{"ortools": {"best": 888.0, "optimal": true}, "aries": {"best": 889.0, "optimal": true}}
ta08.jsp:{"ortools": {"best": 1217.0, "optimal": true}, "aries": {"best": 1223.0, "optimal": true}}
abz5.jsp:{"ortools": {"best": 1234.0, "optimal": true}, "aries": {"best": 1238.0, "optimal": true}}
la19.jsp:{"ortools": {"best": 842.0, "optimal": true}, "aries": {"best": 846.0, "optimal": true}}
la21.jsp:{"ortools": {"best": 1046.0, "optimal": true}, "aries": {"best": 1049.0, "optimal": true}}
la24.jsp:{"ortools": {"best": 935.0, "optimal": true}, "aries": {"best": 940.0, "optimal": true}}
orb06.jsp:{"ortools": {"best": 1010.0, "optimal": true}, "aries": {"best": 1013.0, "optimal": true}}
ft10.jsp:{"ortools": {"best": 930.0, "optimal": true}, "aries": {"best": 936.0, "optimal": true}}

[arbimo]

Thanks for the report, it is indeed a bug if aries incorrectly reports optimality.

I was able to reproduce it (thank you for the details!). I only did a very shallow exploration but it seems that the bug was introduced very recently between v0.3.2 and v0.3.3. At least for orb05.jsp, version 0.3.2 appears to always return the valid solution.

Maybe you can use this version while I investigate the source of the problem (which may take some time depending on my availability).

Note that to automate testing you can use the ./ci/scheduling.py script that will run the solver on a number of problems with a know makespan and exit with error code 1 in case of a failure.

For instance, to find the problematic version, I extended the instances tested as follow:

instances = [
    ("jobshop", "examples/scheduling/instances/jobshop/ft06.jsp", 55),
    ("jobshop", "examples/scheduling/instances/jobshop/la01.jsp", 666),
    ("openshop", "examples/scheduling/instances/openshop/taillard/tai04_04_01.osp", 193),
] + [
    ("jobshop", "examples/scheduling/instances/jobshop/orb05.jsp", 887),
] * 100

[arbimo]

@tmtenbrink I have fixed a bug in #136 that seemed to be the cause of the problem you faced. Could you check that your problem has indeed disappeared with the latest master version?

[tmtenbrink]

Thank you for the swift resolution. Unfortunately we were not able to do the final runs for our project with the master version, we used 0.3.2 instead, so I cannot check that indeed it's resolved for all the instances I mentioned earlier. Those I tried seem good though.