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.

Improve this question
$\endgroup$
11
  • $\begingroup$ The sum expression uses a hash map than is language dependant. $\endgroup$
    – Laurent Perron
    Dec 6, 2020 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$
    – ooo
    Dec 6, 2020 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$
    – ooo
    Dec 6, 2020 at 9:13
  • $\begingroup$ Which version of or-tools ? $\endgroup$
    – Laurent Perron
    Dec 6, 2020 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$
    – ooo
    Dec 6, 2020 at 9:58

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Those are not the same models since your C# horizon is 38 and your Python horizon is 42. $\endgroup$
    – ooo
    Dec 6, 2020 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ And now, they both find 27. $\endgroup$
    – Laurent Perron
    Dec 7, 2020 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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