3
$\begingroup$

Lately, I have been working on a CP-SAT model for solving multi-resource flexible job shop problems.

I used the code (1) as an inspiration for building code (2) in Python which works well. Then I had to recode (2) in C# which gave me code (3).

When I feed same data set in 2 and 3 I get different results and I have very hard time explaining it to me. It could definitely be my code but I spend the whole afternoon without finding the mistake.

(1) https://github.com/google/or-tools/blob/stable/examples/python/flexible_job_shop_sat.py

(2) https://github.com/ozizi1/MultiResourceFJSP/blob/master/Python_MR-FJSP

(3) https://github.com/ozizi1/MultiResourceFJSP/blob/master/Cs_MR-FJSP

Case : enter image description here enter image description here

EDIT:

Following Laurent Perron's recommandation bellow I kept on looking and to me both models seem correct. They both try to minimize makespan and they both respect no overlap and precedence constraints in the results displayed.

Once again this could be my model but I really don't see the issue.

Another weird phenomena is that code 2 and 3 can choose same alternatives but give different objective values : enter image description here

If you want to replicate this behaviour just change second's alternative lead time on github's code by 9 so that jobs start like : [[[[3, (0,1)],[9, (1,2)]...

Also please notice the difference in wall times. If I didn't had to use WPF - MVVM design pattern I would have stuck to Python.

If you have any idea where this is coming from please let me know.

$\endgroup$
11
  • $\begingroup$ The sum expression uses a hash map than is language dependant. $\endgroup$ – Laurent Perron Dec 6 '20 at 5:17
  • $\begingroup$ Thank you for the tip @LaurentPerron. I could have kept on looking for a long time. Any idea on how to improve C#’s result ? So far Python has always provided better results. $\endgroup$ – OtmaneZ Dec 6 '20 at 8:54
  • $\begingroup$ The only place where I use Sum in my C# is for setting the number of présences allowed (model.Add(LinearExpr.Sum(AltPresenceList) == 1). And that part seems to work well. $\endgroup$ – OtmaneZ Dec 6 '20 at 9:13
  • $\begingroup$ Which version of or-tools ? $\endgroup$ – Laurent Perron Dec 6 '20 at 9:49
  • $\begingroup$ Or tools C# version : 8.0.8283 ; Or tools Python version : 7.8.7959 Now I’m feeding larger data sets and C# fails to return any result in a very long time while python returns optimal solution on a reasonable 160 sec. $\endgroup$ – OtmaneZ Dec 6 '20 at 9:58
2
$\begingroup$

Running the C# version with or-tools master

"/usr/local/share/dotnet/dotnet" run --no-build  --project examples/tests/wrong_solution_flex_sat.csproj
[[[[3, (0, 1)],[1, (1, 2)],[5, (2, 3)]],[[2, (3, 4)], [4, (1, 2)], [6, (2, 3)]], [[2, (0, 1)], [3, (1, 2)], [1, (2, 3)]]],[[[2, (0, 1)], [3, (1, 2)], [4, (2, 3)]], [[1, (0, 1)], [5, (1, 2)], [4, (2, 3)]], [[2, (0, 1)], [1, (1, 2)], [4, (2, 3)]]],[[[2, (0, 1)], [1, (1, 2)], [4, (2, 3)]], [[2, (0, 1)], [3, (1, 2)], [4, (2)]], [[3, (0, 1)]]]]
38
Objective value: { "status": "OPTIMAL", "solution": [ "0", "1", "1", "0", "0", "1", "3", "1", "0", "1", "1", "0", "0", "1", "5", "1", "2", "3", "1", "1", "3", "2", "0", "1", "3", "4", "0", "1", "3", "6", "7", "1", "8", "0", "3", "4", "0", "3", "4", "1", "7", "8", "3", "4", "7", "0", "0", "2", "0", "0", "3", "1", "3", "7", "7", "1", "8", "1", "7", "8", "0", "2", "3", "0", "3", "4", "8", "1", "9", "0", "4", "5", "1", "8", "9", "0", "4", "5", "1", "1", "2", "0", "0", "1", "1", "1", "2", "0", "0", "1", "2", "2", "4", "1", "2", "4", "0", "1", "3", "0", "1", "3", "4", "3", "7", "1", "4", "7", "1", "9" ], "objectiveValue": 9, "bestObjectiveBound": 9, "numBooleans": "64", "numConflicts": "25", "numBranches": "176", "numBinaryPropagations": "1045", "numIntegerPropagations": "2769", "wallTime": 0.007670000000000001, "userTime": 0.007671000000000001, "deterministicTime": 0.00020175300000000072, "numRestarts": "103" }
Solution: Optimal
Objective value: 9
Job1-task1-Alt2
Job1-task2-Alt1
Job1-task3-Alt3
Job2-task1-Alt3
Job2-task2-Alt1
Job2-task3-Alt2
Job3-task1-Alt2
Job3-task2-Alt1

Running the python version

Horizon = 42
Solution 0, time = 0.004693 s, objective = 22
Solution 1, time = 0.005145 s, objective = 19
Solution 2, time = 0.005526 s, objective = 12
Solution 3, time = 0.006028 s, objective = 11
Solution 4, time = 0.006320 s, objective = 10
Solution 5, time = 0.006531 s, objective = 9
Job 1:
  task_1_1 starts at 1 - ends at 6 (alt 3, resources : 2,3, duration 5)
  task_1_2 starts at 6 - ends at 8 (alt 1, resources : 3,4, duration 2)
  task_1_3 starts at 8 - ends at 9 (alt 3, resources : 2,3, duration 1)
Job 2:
  task_2_1 starts at 1 - ends at 3 (alt 1, resources : 0,1, duration 2)
  task_2_2 starts at 3 - ends at 4 (alt 1, resources : 0,1, duration 1)
  task_2_3 starts at 6 - ends at 7 (alt 2, resources : 1,2, duration 1)
Job 3:
  task_3_1 starts at 0 - ends at 1 (alt 2, resources : 1,2, duration 1)
  task_3_2 starts at 4 - ends at 6 (alt 1, resources : 0,1, duration 2)
  task_3_3 starts at 6 - ends at 9 (alt 1, resources : 0,1, duration 3)
Solve status: OPTIMAL
Objective value: 9
Statistics
  - conflicts : 8
  - branches  : 214

I get the same objective value.

$\endgroup$
1
  • $\begingroup$ Those are not the same models since your C# horizon is 38 and your Python horizon is 42. $\endgroup$ – OtmaneZ Dec 6 '20 at 13:10
1
$\begingroup$

1 constraint on 1 job wasn't applied on code 2 because sketchy implementation of a if statement.

Fixed it and updated the code on GitHub for people who need smtg similar.

$\endgroup$
1
  • $\begingroup$ And now, they both find 27. $\endgroup$ – Laurent Perron Dec 7 '20 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.