Playing with job shop problem ft10 (4)

We could not solve my job shop formulations in http://yetanothermathprogrammingconsultant.blogspot.com/2014/04/playing-with-job-shop-problem-ft10-2.html but actually Or-tools has a pretty good C++ based implementation: https://code.google.com/p/or-tools/source/browse/trunk/examples/cpp/jobshop.cc. This can solve the ft10 problem in reasonable time:

c:\Users\erwin\tmp>jobshop --data_file=ft10 [19:25:55] examples\cpp/jobshop.h:131: Reading jssp instance ft10 [19:25:55] examples\cpp/jobshop.h:148: 10 machines and 10 jobs [19:25:55] src/constraint_solver/search.cc:243: Start search (memory used = 4.66 MB) [19:25:55] src/constraint_solver/search.cc:243: Root node processed (time = 1 ms, constraints = 351, memory used = 4.98 MB) [19:25:55] src/constraint_solver/search.cc:243: Solution #0 (objective value = 1740, time = 67 ms, branches = 91, failures = 0, depth = 91, memory used = 5.04 MB) [19:25:55] src/constraint_solver/search.cc:243: Solution #1 (objective value = 1734, objective maximum = 1740, time = 96 ms, branches = 96, failures = 7, depth = 89, memory used = 5.11 MB) [19:25:55] src/constraint_solver/search.cc:243: Solution #2 (objective value = 1729, objective maximum = 1740, time = 128 ms, branches = 101, failures = 13, depth = 87, memory used = 5.11 MB) [19:25:55] src/constraint_solver/search.cc:243: Solution #3 (objective value = 1723, objective maximum = 1740, time = 148 ms, branches = 106, failures = 17, depth = 88, memory used = 5.11 MB) [19:25:55] src/constraint_solver/search.cc:243: Solution #4 (objective value = 1717, objective maximum = 1740, time = 205 ms, branches = 125, failures = 46, depth = 76, memory used = 5.13 MB) [19:25:55] src/constraint_solver/search.cc:243: Solution #5 (objective value = 1685, objective maximum = 1740, time = 233 ms, branches = 136, failures = 55, depth = 78, memory used = 5.13 MB) [19:25:55] src/constraint_solver/search.cc:243: Solution #6 (objective value = 1664, objective maximum = 1740, time = 280 ms, branches = 154, failures = 75, depth = 74, memory used = 5.13 MB) .. [19:28:41] src/constraint_solver/search.cc:243: Solution #151 (objective value = 938, objective maximum = 1740, time = 165613 ms, branches = 534773, failures = 268520, depth = 36, memory used = 5.16 MB) [19:29:36] src/constraint_solver/search.cc:243: Solution #152 (objective value = 935, objective maximum = 1740, time = 221354 ms, branches = 709290, failures = 355782, depth = 40, memory used = 5.16 MB) [19:29:38] src/constraint_solver/search.cc:243: Solution #153 (objective value = 934, objective maximum = 1740, time = 222810 ms, branches = 709292, failures = 355784, depth = 40, memory used = 5.16 MB) [19:29:38] src/constraint_solver/search.cc:243: Solution #154 (objective value = 930, objective maximum = 1740, time = 222951 ms, branches = 709544, failures = 355918, depth = 34, memory used = 5.16 MB) [19:30:13] src/constraint_solver/search.cc:243: Finished search tree (time = 258350 ms, branches = 809795, failures = 406060, memory used = 5.16 MB) [19:30:13] src/constraint_solver/search.cc:243: End search (time = 258361 ms, branches = 809795, failures = 406060, memory used = 5.17 MB, speed = 3134 branches/s) [19:30:13] examples\cpp/jobshop.cc:165: Machine_0: 0, 1, 8, 6, 3, 4, 7, 9, 5, 2 [19:30:13] examples\cpp/jobshop.cc:165: Machine_1: 3, 5, 6, 9, 8, 4, 2, 7, 0, 1 [19:30:13] examples\cpp/jobshop.cc:165: Machine_2: 5, 3, 4, 7, 1, 6, 9, 8, 0, 2 [19:30:13] examples\cpp/jobshop.cc:165: Machine_3: 5, 6, 8, 4, 2, 0, 1, 9, 3, 7 [19:30:13] examples\cpp/jobshop.cc:165: Machine_4: 3, 1, 4, 5, 7, 0, 8, 9, 6, 2 [19:30:13] examples\cpp/jobshop.cc:165: Machine_5: 5, 4, 8, 6, 7, 9, 0, 2, 1, 3 [19:30:13] examples\cpp/jobshop.cc:165: Machine_6: 6, 3, 9, 5, 8, 7, 0, 1, 2, 4 [19:30:13] examples\cpp/jobshop.cc:165: Machine_7: 3, 5, 4, 8, 6, 2, 0, 7, 1, 9 [19:30:13] examples\cpp/jobshop.cc:165: Machine_8: 5, 3, 9, 4, 6, 2, 7, 8, 0, 1 [19:30:13] examples\cpp/jobshop.cc:165: Machine_9: 5, 1, 6, 8, 9, 4, 7, 3, 2, 0 c:\Users\erwin\tmp>

The problem is solved to a proven optimal solution in less than 5 minutes.

Some obvious questions arise:

1. So how is this implementation different from the Minizinc models I did before? One difference is that it is using interval variables. These variables have a start and a duration, and are often used in scheduling models. I am not sure how to use these variable in a Minizinc model.
2. Can we create a Minizinc model with similar performance?
3. The optimization is probably done by:
   1. Find solution
   2. If infeasible stop
   3. Else add the constraint obj < obj_found to the model and go to step 1
   This leads to many solutions being found: 154 to be precise. Would it not be better to use some binary search? This may be a stupid suggestion; but I would guess this could reduce the number of sub-problems to be solved. One could use an LP relaxation to find an initial lower bound. I assume my suggestion is not that good (otherwise it would have been implemented already), but I don’t see immediately why. May be tightening the problem is relatively easy compared to relaxing it.
4. When invoked without a data file name, the program crashes:
   
   Looks like this is caused by an abort() statement (replace by exit(-1) to stop more gracefully).
5. The performance over time looks vey much like a MIP solver:
   
   i.e. quick progress at the beginning and slowing down later on.