Competition: shift design and assignment problem

Help
2013-08-20
2015-10-02
1 2 > >> (Page 1 of 2)
  • Thomas B. Léauté

    Hello,

    My company is organizing an internal competition to solve a real-life-inspired problem that involves optimally designing and assigning shifts for a number of employees. I know that most of my competitors in the challenge are going to go for a Mixed Integer-Linear Programming approach using CPLEX. I would like to see whether JaCoP can compete, and I am welcoming suggestions on how to model the problem and what search to use.

    The problem is as follows (without going into too much detail). On the one hand, you have a number of employees (100), who are the resources. On the other hand, you have a demand curve, which gives the desired number of employees/resources for each 15-min time interval over a whole week. The goal is to design and assign shifts to the employees so as to cover the demand. There are labor law constraints on the shifts (min and max duration, min rest period between two shifts, necessity of a break in the middle of long shifts, maximum number of consecutive work days, maximum number of consecutive work days with a night shift...). The objective function is a weighted sum of multiple factors, including a measure of fairness, and the total amount of under- or over-coverage of the demand (so, the demand is a soft constraint).

    I assume that the only way JaCoP could win over CPLEX is if I formulate the problem using global constraints. So I went through the catalog of global constraints supported by JaCoP, and one I thought could help might be the Geost constraint, where the objects would be the shifts (whose durations would be decision variables), to be laid out over the schedule (the matrix of time x employees). I could have a master search that tries to find the optimal number of shifts, and a slave search that would use the Geost constraint (and many others) to optimally size and schedule the shifts.

    What do you think of my idea? Would you have suggestions on how to do it better?

    Thanks a lot in advance.

     
  • kris

    kris - 2013-08-21

    Hi!

    Yes, you are right. The only way to compete with ILP solutions is by using global constraints. You problem seems to be a kind of rostering problem that is very much dependent on involved constraints. However, I guess you can look at constraints such as Diff2, Binpacking and Cumulative. Geost is a good constraint but it addresses much more general problem of packing non-convex shapes build of n-dimensional rectangles. In your problems, you probably can use Diff2 constraint that has more pruning power and can be more efficient for your purpose. Cumulative is specially developed for scheduling while Binpacking can be useful for constraining, for example that "the desired number of employees/resources for each 15-min time interval over a whole week".

    You can also combine several constraints even they do not define new logical conditions. In such a way you get possibly more pruning power.

    Search is an art and it would be good to try different search alternatives.

    Best regards and good luck,
    /Kris

     
  • Thomas B. Léauté

    Hi Kris,

    Thanks a lot for your suggestions. I have been making significant progress on my problem formulation. So far I am using Diff2 to impose that no two shifts may overlap, GCC to count the number of shifts that start on each day, and Among to compute the number of shifts that overlap a particular time step (as part of the objective function).

    However I have encountered problems, for which I wanted to create a ticket in the bug tracker, but it appears I don't have the proper access rights to create tickets.

    Here is what I have encountered:
    - XmulCeqZ is not a PrimitiveConstraint, so I can't use it as Then or Else in an IfThenElse.
    - The code in XmodYeqZ.satisfied() doesn't look right. Same in XdivYeqZ.
    - I am encountering the following error inside the Among constraint. I will investigate a bit to check whether the bug is in my code rather than in the Among constraint, but here is last part of the trace:

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
    at JaCoP.constraints.Among.consistency(Among.java:179)
    at JaCoP.core.Store.consistency(Store.java:640)
    at JaCoP.search.DepthFirstSearch.label(DepthFirstSearch.java:524)

    Thanks again,

    Thomas

     
  • kris

    kris - 2013-08-26

    Hi Thomas,

    Thanks for the bug report. We will look at this. Fortunately, a bug in satisfied in XmodYeqZ and XdivYeqZ does not effect the solver in any way it is currently configured ;)

    Another suggestion. You can rather easily use result of XmodYeqZ and XdivYeqZ constraints in conditional or reified constraints. The trick is to define constraints in the following way, assuming that you want to use x mod y = z in conditional constraint.

    Define constraints

    x mod y = temp
    temp = z

    Then you can use temp = z in conditional constraint or reified since XeqY is PrimitiveConstraint. Obviously temp variable must have a domain that does not exclude values needed for both constraint to work properly. It is usually larger than domain of z.

    Can you send us an example that generates out-of-bound exception in Among constraint? it will help to find a bug.

    Best regards,
    /Kris

     
  • Thomas B. Léauté

    Hi Kris,

    I had already come up with a workaround similar to yours, but both involve creating one additional auxiliary variable per IfThenElse constraint, and I already have a lot of variables (and many IfThenElse constraints), so this is not ideal from the point of view of performance.

    Attached is a piece of code that demonstrates the NullPointerException in the Among constraint (and my workaround to the IfThenElse).

    It also demonstrates how I have been trying to use the Sequence constraint, but I got very disappointing results: it gets decomposed into a very large regular constraint, which does not give the correct result in the end (compared to the other approach using multiple Min constraints). I am wondering whether this is a bug in the Sequence constraint or in the way I am using it.

    Finally, I need a global constraint that is sort of a conditional sum constraint: it sums up a number of FDM terms, but each term is only taken into account if a certain condition is satisfied. More precisely, I want to compute sum_i {x[i] such that y[i] = C}. I have not found any global constraint in the JaCoP catalog to achieve this, so I have implemented my own as a generalization of the Count constraint (also attached). Do you know of any better way to achieve this?

    Thanks a lot again,

    Thomas

     
  • kris

    kris - 2013-08-27

    Hi Thomas,

    Good that you found a workaround.

    In connection to IfThenElse. I would suggest that you look at reified constraint. IfThenElse is "directional" constraint, that means that nothing happen to "then" and "else" constraint before we now whether "if" condition is true or false. The condition is also only checked. Reified works in both directions from constraint to variable and vice versa. This gives more propagation. Of course, the constraints are not interchangeable and you need to look at your problem.

    When it comes to conditional sum, it is a non-linear constraint and we do not plan to make it as global currently. Of course, you can extend JaCoP for your purpose ;) It might be useful to combine it with reified constraint, as mentioned before.

    Thanks for the code. We will check the bug in Among.

    Good luck with your problem.
    /Kris

     
  • Thomas B. Léauté

    Hi Kris,

    Thanks for your suggestion about reified constraints instead of IfThenElse. I will look into this.

    In the mean time, I can confirm that there is definitely a bug in the Among constraint; just look at the following debug message, which proves that Among detected an inconsistency even though the constraint is clearly satisfied:

    *** Constraint failed :Counting the breaks ending <= 117 Among(
    variableBreak_end_0 : {8, 12..16}
    variableBreak_end_10 : {8, 12..16}
    variableBreak_end_20 : {8, 12..16}
    variableBreak_end_30 : {8, 12..16}
    variableBreak_end_40 : {8, 12..16}
    variableBreak_end_1 : {104, 108..112}
    variableBreak_end_11 : {104, 108..112}
    variableBreak_end_21 : {104, 108..112}
    variableBreak_end_31 : {104, 108..112}
    variableBreak_end_39 : {1067, 1071..1072}
    variableBreak_end_41 : 116
    variableBreak_end_38 : {971, 975..976}
    variableBreak_end_37 : {872, 876..880}
    variableBreak_end_36 : {776, 780..784}
    variableBreak_end_35 : {680, 684..688}
    variableBreak_end_34 : {392, 396..400}
    variableBreak_end_33 : {296, 300..304}
    variableBreak_end_32 : {200, 204..208}
    variableBreak_end_29 : {1064, 1068..1072}
    variableBreak_end_28 : {968, 972..976}
    variableBreak_end_27 : {872, 876..880}
    variableBreak_end_26 : {776, 780..784}
    variableBreak_end_25 : {680, 684..688}
    variableBreak_end_24 : {392, 396..400}
    variableBreak_end_23 : {296, 300..304}
    variableBreak_end_22 : {200, 204..208}
    variableBreak_end_19 : {1064, 1068..1072}
    variableBreak_end_18 : {968, 972..976}
    variableBreak_end_17 : {872, 876..880}
    variableBreak_end_16 : {776, 780..784}
    variableBreak_end_15 : {680, 684..688}
    variableBreak_end_14 : {392, 396..400}
    variableBreak_end_13 : {296, 300..304}
    variableBreak_end_12 : {200, 204..208}
    variableBreak_end_9 : {1064, 1068..1072}
    variableBreak_end_8 : {968, 972..976}
    variableBreak_end_7 : {872, 876..880}
    variableBreak_end_6 : {776, 780..784}
    variableBreak_end_5 : {680, 684..688}
    variableBreak_end_4 : {392, 396..400}
    variableBreak_end_3 : {296, 300..304}
    variableBreak_end_2 : {200, 204..208} )
    Kset : {0..117}
    variable Nbr_breaks_ending_before_117 : 10)

    It would greatly help me if you could isolate the bug and propose a fix. I am going to look into the code myself as well to try to find it.

    Thanks a lot,

    Thomas

     
    Last edit: Thomas B. Léauté 2013-08-27
  • kris

    kris - 2013-08-27

    Hi Thomas,

    Among constraint has been developed by my colleague and I asked him to look at the problem you indicated.

    Best,
    /Kris

     
  • Radoslaw Szymanek

    Hi,

    I was running the test provided in your previous message.

    I see one usage pattern for Among that we have not tried before. Namely, you impose Among constraint for situation where all variables provided in the list are already within the kSet.

    I would avoid posting this type of Among constraints as n can be set to 5 (list length) immediately and no need to impose Among constraint. For a moment, the optimization employed within Among constraint (dynamic removal of constraint from variable is failing when constraint is already satisfied at imposition).

    Example of Among constraint.

    Counting the breaks ending <= 335 Among(
    variableBreak_end_0 : {2..335}
    variableBreak_end_1 : {2..335}
    variableBreak_end_2 : {2..335}
    variableBreak_end_3 : {2..335}
    variableBreak_end_4 : {2..335} )
    Kset : {0..335}
    variable Nbr_breaks_ending_before_335 : 5)

    We never tried this type of Among constraint. Can you change your code so it uses XeqC(variable Nbr_breaks_ending_before_335, list_length) instead of Among where all variables are already within the kSet and see if the problem with Among remains?

    I am not sure yet how to fix it. The constraint was built with the assumption that it is not satisfied already the first time the consistency method is executed.

    best,
    Radek

     
  • Radoslaw Szymanek

    Hi,

    I am not sure I fully understand your problem, so my suggestion may not be fully relevant.

    I have an impression that you use Among to obtain information how many variables have value lower than x. This is why your kSet is so large (e.g. 0..335). However, you seem to do it for all x within a given interval (0 to horizon). Thus, I think it would be more efficient to compute how many variables are equal to each x (0, 1, ..., horizon). Having this cardinality variable for 0, 1, 2, 3, ..., you could add cardinality variable 0 and 1 to have value how many variables end before 2. You could use the sum of cardinality variables 0 and 1 add to it cardinality for value 2 and have number of variables that end before 3. You use those simple partial sums as you need them to know the cardinality for sets (0, 0..1, 0..2, 0..3, 0..4, 0..horizon).

    You could use Count constraint to count how many variables are equal to given value x.
    I would try this model because it may perform significantly better as Among must to do a lot of set inclusion checks while Count does only membership checks.

    best,
    Radek

     
  • Radoslaw Szymanek

    Hi,

    Concerning your bug report with Among failing for unknown reasons. I created a simplified test with Among with 11 variables, set n to 10 and my Among was consistent. It would suggest that state of Among somehow gets corrupted while it is being used during the search and then based on this corrupted state incorrectly fails. I need to have your example in order to replicate the bug. If possible, send it to me by email.

    If it is not possible to send the complete example then could you re-run your example that has this failing Among in the following setup. Change the debugAll switch within Among code to non static public attribute. Set it to true only to this constraint that fails and then send me by email the printout generated by this constraint. It may help me to isolate the bug even If I can not run your example exhibiting the bug in Among.

    Isolating this bug may take a while as it is the nastiest bug possible when due to some boundary conditions the state of the constraint is being corrupted and then it causes wrong calculations. It may require looking at search consisting of millions of nodes and figuring out in which search node then the state was corrupted that it showed later on. Hopefully, in this constraint the state corruption occurs relatively closely to the incorrectly failed search node making it somehow easier to debug. If my previous comment concerning your model (possible use of Count instead of Among for your model) is correct then I would experiment with this model variation so you are not dependent on this bug resolution.

    best,
    Radek

     
  • Radoslaw Szymanek

    Hi,

    What is very suspicious about Among in this printout that those two lines are in this order and not reversed.

    variableBreak_end_39 : {1067, 1071..1072}
    variableBreak_end_41 : 116

    The state invariant in Among (variables that can not contribute to n are to the right of the variables that can contribute to n) is violated.

    best,
    Radek

     
  • Thomas B. Léauté

    Hi Radek,

    Thanks a lot for your support.

    By adding asserts in the Among constraint (see attachments) to check that the variable list order and the bounds remain consistent whenever the bounds are modified, I have been able to isolate the bug. I haven't figured out how to properly fix it, though.

    The problem is when the search reaches a case where Variable X notifies Among of a change in its domain, X.domain is already contained in kSet, and the position of X in the list is already BEFORE currentLB = currentUB. Then I assume the code should not do anything, but instead currently it will swap the position of X with another variable's position, introducing an inconsistency in the list order.

    When I run the attached (revised) Test.java with asserts enabled I get the following, which indicates that Among is being notified of a change in the domain of the variable Break_end_41, which is at position 9 in the list, and currentLB = currentUB = 10. After the incorrect swap, Break_end_41 ends up at position 10, Break_end_39 has been introduced at position 9 (introducing an inconsistency in the list order), and currentLB = 11 > currentUB.

    Before Break_end_41 = 116: n = Nbr_breaks_ending_before_117 = 10 currentLB = 10 currentUB =10
    [Break_end_0::{8, 12..16}, Break_end_10::{8, 12..16}, Break_end_20::{8, 12..16}, Break_end_30::{8, 12..16}, Break_end_40::{8, 12..16}, Break_end_1::{104, 108..112}, Break_end_11::{104, 108..112}, Break_end_21::{104, 108..112}, Break_end_31::{104, 108..112}, Break_end_41 = 116, Break_end_39::{1064, 1068..1072}, Break_end_38::{968, 972..976}, Break_end_37::{872, 876..880}, Break_end_36::{776, 780..784}, Break_end_35::{680, 684..688}, Break_end_34::{392, 396..400}, Break_end_33::{296, 300..304}, Break_end_32::{200, 204..208}, Break_end_29::{1064, 1068..1072}, Break_end_28::{968, 972..976}, Break_end_27::{872, 876..880}, Break_end_26::{776, 780..784}, Break_end_25::{680, 684..688}, Break_end_24::{392, 396..400}, Break_end_23::{296, 300..304}, Break_end_22::{200, 204..208}, Break_end_19::{1064, 1068..1072}, Break_end_18::{968, 972..976}, Break_end_17::{872, 876..880}, Break_end_16::{776, 780..784}, Break_end_15::{680, 684..688}, Break_end_14::{392, 396..400}, Break_end_13::{296, 300..304}, Break_end_12::{200, 204..208}, Break_end_9::{1064, 1068..1072}, Break_end_8::{968, 972..976}, Break_end_7::{872, 876..880}, Break_end_6::{776, 780..784}, Break_end_5::{680, 684..688}, Break_end_4::{392, 396..400}, Break_end_3::{296, 300..304}, Break_end_2::{200, 204..208}]
    Exception in thread "main" java.lang.AssertionError:
    After Break_end_41 = 116: n = Nbr_breaks_ending_before_117 = 10 currentLB = 11 currentUB=10
    [Break_end_0::{8, 12..16}, Break_end_10::{8, 12..16}, Break_end_20::{8, 12..16}, Break_end_30::{8, 12..16}, Break_end_40::{8, 12..16}, Break_end_1::{104, 108..112}, Break_end_11::{104, 108..112}, Break_end_21::{104, 108..112}, Break_end_31::{104, 108..112}, Break_end_39::{1064, 1068..1072}, Break_end_41 = 116, Break_end_38::{968, 972..976}, Break_end_37::{872, 876..880}, Break_end_36::{776, 780..784}, Break_end_35::{680, 684..688}, Break_end_34::{392, 396..400}, Break_end_33::{296, 300..304}, Break_end_32::{200, 204..208}, Break_end_29::{1064, 1068..1072}, Break_end_28::{968, 972..976}, Break_end_27::{872, 876..880}, Break_end_26::{776, 780..784}, Break_end_25::{680, 684..688}, Break_end_24::{392, 396..400}, Break_end_23::{296, 300..304}, Break_end_22::{200, 204..208}, Break_end_19::{1064, 1068..1072}, Break_end_18::{968, 972..976}, Break_end_17::{872, 876..880}, Break_end_16::{776, 780..784}, Break_end_15::{680, 684..688}, Break_end_14::{392, 396..400}, Break_end_13::{296, 300..304}, Break_end_12::{200, 204..208}, Break_end_9::{1064, 1068..1072}, Break_end_8::{968, 972..976}, Break_end_7::{872, 876..880}, Break_end_6::{776, 780..784}, Break_end_5::{680, 684..688}, Break_end_4::{392, 396..400}, Break_end_3::{296, 300..304}, Break_end_2::{200, 204..208}]

    Thanks for your suggestion about using Count instead of Among; I will look into it. What about using one GCC to count the number of variables that take on each possible value, instead of using a large number of Count constraints to count each value?

    Best,

    Thomas

     
    Last edit: Thomas B. Léauté 2013-08-28
  • Radoslaw Szymanek

    Hi,

    I have a suspicion what is the problem and may have a solution but I did not have time to try it yet.

    I think we need to add the following if statement at the beginning of loop for (IntVar var : variableQueue) { ... }

    if (posVar < currentLB || posVar >> currentUB)
    continue;

    It will make sure that the variable that has been already classified as one or the other type is not being treated again.

    Of course, posVar computation has to be taken out of if statements before the if to make it work.

    best,
    Radek

     
  • Thomas B. Léauté

    Hi Radek and Kris,

    I strongly suspect a similar bug exists in the implementation of GCC. When I enable the tracing of failing constraints, I get messages that a GCC constraint has failed the consistency check, but not all grounded variables appear at the end of the list (see example below).

    Also, at one point I got a NullPointerException inside of GCC, but I was not able to reproduce it (and I haven't saved the trace, unfortunately).

    Do you think you will be able to find the bug (based on where you found it in Among) or do you need code that demonstrates it?

    Thanks a lot in advance,

    Thomas

    *** Constraint failed :Counting the number of shifts ending at each timestep : GCC ([assignement variables : Shift_end_63::{816, 818, 820, 822}, Shift_end_62::{720, 722, 724, 726, 728, 730, 732, 734}, Shift_end_64::{904, 906, 908, 910}, Shift_end_53::{904, 906, 908, 910}, Shift_end_52::{816, 818, 820, 822}, Shift_end_51::{720, 722, 724, 726, 728, 730, 732, 734}, Shift_end_50::{328, 330, 332, 334}, Shift_end_49::{240, 242, 244, 246}, Shift_end_48::{144, 146, 148, 150, 152, 154, 156, 158}, Shift_end_47::{912, 914, 916, 918, 920, 922, 924, 926, 928, 930, 932, 934, 936, 938, 940, 942, 944, 946, 948, 950, 952, 954, 956, 958}, Shift_end_46::{720, 722, 724, 726, 728, 730, 732, 734, 736, 738, 740, 742, 744, 746, 748, 750, 752, 754, 756, 758, 760, 762, 764, 766}, Shift_end_45::{432, 434, 436, 438, 440, 442, 444, 446, 448, 450, 452, 454, 456, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478}, Shift_end_44::{336, 338, 340, 342, 344, 346, 348, 350, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 382}, Shift_end_43::{240, 242, 244, 246, 248, 250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, 278, 280, 282, 284, 286}, Shift_end_42::{144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190}, Shift_end_41::{1096, 1098, 1100, 1102}, Shift_end_40::{1008, 1010, 1012, 1014}, Shift_end_39::{912, 914, 916, 918, 920, 922, 924, 926}, Shift_end_38::{816, 818, 820, 822, 824, 826, 828, 830, 832, 834, 836, 838}, Shift_end_19::{336, 338, 340, 342, 344, 346, 348, 350, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 382}, Shift_end_20::{720, 722, 724, 726, 728, 730, 732, 734, 736, 738, 740, 742, 744, 746, 748, 750, 752, 754, 756, 758, 760, 762, 764, 766}, Shift_end_21::{912, 914, 916, 918, 920, 922, 924, 926}, Shift_end_22::{1008, 1010, 1012, 1014}, Shift_end_23::{1096, 1098, 1100, 1102}, Shift_end_24::{48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94}, Shift_end_25::{144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190}, Shift_end_26::{336, 338, 340, 342, 344, 346, 348, 350, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 382}, Shift_end_27::{432, 434, 436, 438, 440, 442, 444, 446, 448, 450, 452, 454, 456, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478}, Shift_end_28::{816, 818, 820, 822, 824, 826, 828, 830, 832, 834, 836, 838, 840, 842, 844, 846, 848, 850, 852, 854, 856, 858, 860, 862}, Shift_end_29::{912, 914, 916, 918, 920, 922, 924, 926, 928, 930, 932, 934, 936, 938, 940, 942, 944, 946, 948, 950, 952, 954, 956, 958}, Shift_end_30::{48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94}, Shift_end_31::{144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190}, Shift_end_32::{336, 338, 340, 342, 344, 346, 348, 350, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 382}, Shift_end_33::{432, 434, 436, 438, 440, 442, 444, 446, 448, 450, 452, 454, 456, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478}, Shift_end_34::{720, 722, 724, 726, 728, 730, 732, 734, 736, 738, 740, 742, 744, 746, 748, 750, 752, 754, 756, 758, 760, 762, 764, 766}, Shift_end_35::{912, 914, 916, 918, 920, 922, 924, 926, 928, 930, 932, 934, 936, 938, 940, 942, 944, 946, 948, 950, 952, 954, 956, 958}, Shift_end_36::{240, 242, 244, 246, 248, 250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, 278, 280, 282, 284, 286}, Shift_end_37::{432, 434, 436, 438, 440, 442, 444, 446, 448, 450, 452, 454, 456, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478}, Shift_end_18 = 72, Shift_end_17 = 1096, Shift_end_16 = 1008, Shift_end_15 = 912, Shift_end_14 = 432, Shift_end_13 = 336, Shift_end_12 = 144, Shift_end_11 = 1104, Shift_end_10 = 1008, Shift_end_9 = 720, Shift_end_8 = 240, Shift_end_7 = 144, Shift_end_6 = 48, Shift_end_5 = 1104, Shift_end_4 = 912, Shift_end_3 = 816, Shift_end_2 = 720, Shift_end_1 = 336, Shift_end_0 = 48, Shift_end_60 = 438, Shift_end_58 = 310, Shift_end_57 = 246, Shift_end_55 = 118, Shift_end_61 = 526, Shift_end_59 = 374, Shift_end_56 = 182, Shift_end_54 = 48 count variables : Nbr_shifts_ending_at_1390 = 0, Nbr_shifts_ending_at_1388 = 0, Nbr_shifts_ending_at_1386 = 0, Nbr_shifts_ending_at_1384 = 0, Nbr_shifts_ending_at_1382 = 0, Nbr_shifts_ending_at_1380 = 0, Nbr_shifts_ending_at_1378 = 0, Nbr_shifts_ending_at_1376 = 0, Nbr_shifts_ending_at_1374 = 0, Nbr_shifts_ending_at_1372 = 0, Nbr_shifts_ending_at_1370 = 0, Nbr_shifts_ending_at_1368 = 0, Nbr_shifts_ending_at_1366 = 0, Nbr_shifts_ending_at_1364 = 0, Nbr_shifts_ending_at_1362 = 0, Nbr_shifts_ending_at_1360 = 0, Nbr_shifts_ending_at_1358 = 0, Nbr_shifts_ending_at_1356 = 0, Nbr_shifts_ending_at_1354 = 0, Nbr_shifts_ending_at_1352 = 0, Nbr_shifts_ending_at_1350 = 0, Nbr_shifts_ending_at_1348 = 0, Nbr_shifts_ending_at_1346 = 0, Nbr_shifts_ending_at_1344 = 0, Nbr_shifts_ending_at_1342::{3..4}, Nbr_shifts_ending_at_1340 = 0, Nbr_shifts_ending_at_1338 = 0, Nbr_shifts_ending_at_1336 = 0, Nbr_shifts_ending_at_1334 = 0, Nbr_shifts_ending_at_1332 = 0, Nbr_shifts_ending_at_1330 = 0, Nbr_shifts_ending_at_1328 = 0, Nbr_shifts_ending_at_1326 = 0, Nbr_shifts_ending_at_1324 = 0, Nbr_shifts_ending_at_1322 = 0, Nbr_shifts_ending_at_1320 = 0, Nbr_shifts_ending_at_1318 = 1, Nbr_shifts_ending_at_1316 = 0, Nbr_shifts_ending_at_1314 = 0, Nbr_shifts_ending_at_1312 = 0, Nbr_shifts_ending_at_1310 = 0, Nbr_shifts_ending_at_1308 = 0, Nbr_shifts_ending_at_1306 = 0, Nbr_shifts_ending_at_1304 = 0, Nbr_shifts_ending_at_1302 = 0, Nbr_shifts_ending_at_1300 = 0, Nbr_shifts_ending_at_1298 = 0, Nbr_shifts_ending_at_1296 = 0, Nbr_shifts_ending_at_1294 = 0, Nbr_shifts_ending_at_1292 = 0, Nbr_shifts_ending_at_1290 = 0, Nbr_shifts_ending_at_1288 = 0, Nbr_shifts_ending_at_1286 = 0, Nbr_shifts_ending_at_1284 = 0, Nbr_shifts_ending_at_1282 = 0, Nbr_shifts_ending_at_1280 = 0, Nbr_shifts_ending_at_1278 = 0, Nbr_shifts_ending_at_1276 = 0, Nbr_shifts_ending_at_1274 = 0, Nbr_shifts_ending_at_1272 = 1, Nbr_shifts_ending_at_1270 = 0, Nbr_shifts_ending_at_1268 = 0, Nbr_shifts_ending_at_1266 = 0, Nbr_shifts_ending_at_1264 = 0, Nbr_shifts_ending_at_1262 = 0, Nbr_shifts_ending_at_1260 = 0, Nbr_shifts_ending_at_1258 = 0, Nbr_shifts_ending_at_1256 = 0, Nbr_shifts_ending_at_1254 = 0, Nbr_shifts_ending_at_1252 = 0, Nbr_shifts_ending_at_1250 = 0, Nbr_shifts_ending_at_1248 = 0, Nbr_shifts_ending_at_1246::{2..3}, Nbr_shifts_ending_at_1244::{0..1}, Nbr_shifts_ending_at_1242::{0..1}, Nbr_shifts_ending_at_1240::{0..1}, Nbr_shifts_ending_at_1238::{0..1}, Nbr_shifts_ending_at_1236::{0..1}, Nbr_shifts_ending_at_1234::{0..1}, Nbr_shifts_ending_at_1232::{0..1}, Nbr_shifts_ending_at_1230::{0..1}, Nbr_shifts_ending_at_1228::{0..1}, Nbr_shifts_ending_at_1226::{0..1}, Nbr_shifts_ending_at_1224::{0..1}, Nbr_shifts_ending_at_1222::{0..1}, Nbr_shifts_ending_at_1220::{0..1}, Nbr_shifts_ending_at_1218::{0..1}, Nbr_shifts_ending_at_1216::{0..1}, Nbr_shifts_ending_at_1214::{0..1}, Nbr_shifts_ending_at_1212::{0..1}, Nbr_shifts_ending_at_1210::{0..1}, Nbr_shifts_ending_at_1208::{1..2}, Nbr_shifts_ending_at_1206::{0..1}, Nbr_shifts_ending_at_1204::{0..1}, Nbr_shifts_ending_at_1202::{0..1}, Nbr_shifts_ending_at_1200::{0..1}, Nbr_shifts_ending_at_1198 = 0, Nbr_shifts_ending_at_1196 = 0, Nbr_shifts_ending_at_1194 = 0, Nbr_shifts_ending_at_1192 = 0, Nbr_shifts_ending_at_1190 = 0, Nbr_shifts_ending_at_1188 = 0, Nbr_shifts_ending_at_1186 = 0, Nbr_shifts_ending_at_1184 = 0, Nbr_shifts_ending_at_1182 = 0, Nbr_shifts_ending_at_1180 = 0, Nbr_shifts_ending_at_1178 = 0, Nbr_shifts_ending_at_1176 = 0, Nbr_shifts_ending_at_1174 = 0, Nbr_shifts_ending_at_1172 = 0, Nbr_shifts_ending_at_1170 = 0, Nbr_shifts_ending_at_1168 = 0, Nbr_shifts_ending_at_1166 = 0, Nbr_shifts_ending_at_1164 = 0, Nbr_shifts_ending_at_1162 = 0, Nbr_shifts_ending_at_1160 = 0, Nbr_shifts_ending_at_1158 = 0, Nbr_shifts_ending_at_1156 = 0, Nbr_shifts_ending_at_1154 = 0, Nbr_shifts_ending_at_1152 = 0, Nbr_shifts_ending_at_1150::{1..2}, Nbr_shifts_ending_at_1148::{0..1}, Nbr_shifts_ending_at_1146::{0..1}, Nbr_shifts_ending_at_1144::{1..2}, Nbr_shifts_ending_at_1142::{0..1}, Nbr_shifts_ending_at_1140::{0..1}, Nbr_shifts_ending_at_1138::{0..1}, Nbr_shifts_ending_at_1136::{0..1}, Nbr_shifts_ending_at_1134::{0..1}, Nbr_shifts_ending_at_1132::{0..1}, Nbr_shifts_ending_at_1130::{0..1}, Nbr_shifts_ending_at_1128::{0..1}, Nbr_shifts_ending_at_1126::{0..1}, Nbr_shifts_ending_at_1124::{0..1}, Nbr_shifts_ending_at_1122::{0..1}, Nbr_shifts_ending_at_1120::{0..1}, Nbr_shifts_ending_at_1118::{0..1}, Nbr_shifts_ending_at_1116::{0..1}, Nbr_shifts_ending_at_1114::{0..1}, Nbr_shifts_ending_at_1112::{0..1}, Nbr_shifts_ending_at_1110::{0..1}, Nbr_shifts_ending_at_1108::{0..1}, Nbr_shifts_ending_at_1106::{0..1}, Nbr_shifts_ending_at_1104::{0..1}, Nbr_shifts_ending_at_1102 = 0, Nbr_shifts_ending_at_1100 = 0, Nbr_shifts_ending_at_1098 = 0, Nbr_shifts_ending_at_1096 = 0, Nbr_shifts_ending_at_1094 = 0, Nbr_shifts_ending_at_1092 = 0, Nbr_shifts_ending_at_1090 = 0, Nbr_shifts_ending_at_1088 = 0, Nbr_shifts_ending_at_1086 = 0, Nbr_shifts_ending_at_1084 = 0, Nbr_shifts_ending_at_1082 = 0, Nbr_shifts_ending_at_1080 = 1, Nbr_shifts_ending_at_1078 = 0, Nbr_shifts_ending_at_1076 = 0, Nbr_shifts_ending_at_1074 = 0, Nbr_shifts_ending_at_1072 = 0, Nbr_shifts_ending_at_1070 = 0, Nbr_shifts_ending_at_1068 = 0, Nbr_shifts_ending_at_1066 = 0, Nbr_shifts_ending_at_1064 = 0, Nbr_shifts_ending_at_1062::{0..1}, Nbr_shifts_ending_at_1060::{0..1}, Nbr_shifts_ending_at_1058::{0..1}, Nbr_shifts_ending_at_1056::{0..1}, Nbr_shifts_ending_at_1054::{2..6}, Nbr_shifts_ending_at_1052::{0..4}, Nbr_shifts_ending_at_1050::{0..4}, Nbr_shifts_ending_at_1048::{0..4}, Nbr_shifts_ending_at_1046::{0..4}, Nbr_shifts_ending_at_1044::{0..4}, Nbr_shifts_ending_at_1042::{0..4}, Nbr_shifts_ending_at_1040::{0..4}, Nbr_shifts_ending_at_1038::{0..4}, Nbr_shifts_ending_at_1036::{0..4}, Nbr_shifts_ending_at_1034::{0..4}, Nbr_shifts_ending_at_1032::{0..4}, Nbr_shifts_ending_at_1030::{0..4}, Nbr_shifts_ending_at_1028::{0..4}, Nbr_shifts_ending_at_1026::{0..4}, Nbr_shifts_ending_at_1024::{0..4}, Nbr_shifts_ending_at_1022::{0..4}, Nbr_shifts_ending_at_1020::{0..4}, Nbr_shifts_ending_at_1018::{0..4}, Nbr_shifts_ending_at_1016::{1..5}, Nbr_shifts_ending_at_1014::{0..4}, Nbr_shifts_ending_at_1012::{0..4}, Nbr_shifts_ending_at_1010::{0..4}, Nbr_shifts_ending_at_1008::{0..4}, Nbr_shifts_ending_at_1006 = 0, Nbr_shifts_ending_at_1004 = 0, Nbr_shifts_ending_at_1002 = 0, Nbr_shifts_ending_at_1000 = 0, Nbr_shifts_ending_at_998 = 0, Nbr_shifts_ending_at_996 = 0, Nbr_shifts_ending_at_994 = 0, Nbr_shifts_ending_at_992 = 0, Nbr_shifts_ending_at_990 = 0, Nbr_shifts_ending_at_988 = 0, Nbr_shifts_ending_at_986 = 0, Nbr_shifts_ending_at_984 = 0, Nbr_shifts_ending_at_982 = 0, Nbr_shifts_ending_at_980 = 0, Nbr_shifts_ending_at_978 = 0, Nbr_shifts_ending_at_976 = 0, Nbr_shifts_ending_at_974 = 0, Nbr_shifts_ending_at_972 = 0, Nbr_shifts_ending_at_970 = 0, Nbr_shifts_ending_at_968 = 0, Nbr_shifts_ending_at_966 = 0, Nbr_shifts_ending_at_964 = 0, Nbr_shifts_ending_at_962 = 0, Nbr_shifts_ending_at_960 = 0, Nbr_shifts_ending_at_958::{1..5}, Nbr_shifts_ending_at_956::{0..4}, Nbr_shifts_ending_at_954::{0..4}, Nbr_shifts_ending_at_952::{1..5}, Nbr_shifts_ending_at_950::{0..4}, Nbr_shifts_ending_at_948::{0..4}, Nbr_shifts_ending_at_946::{0..4}, Nbr_shifts_ending_at_944::{0..4}, Nbr_shifts_ending_at_942::{0..4}, Nbr_shifts_ending_at_940::{0..4}, Nbr_shifts_ending_at_938::{0..4}, Nbr_shifts_ending_at_936::{0..4}, Nbr_shifts_ending_at_934::{0..4}, Nbr_shifts_ending_at_932::{0..4}, Nbr_shifts_ending_at_930::{0..4}, Nbr_shifts_ending_at_928::{0..4}, Nbr_shifts_ending_at_926::{0..4}, Nbr_shifts_ending_at_924::{0..4}, Nbr_shifts_ending_at_922::{0..4}, Nbr_shifts_ending_at_920::{0..4}, Nbr_shifts_ending_at_918::{0..4}, Nbr_shifts_ending_at_916::{0..4}, Nbr_shifts_ending_at_914::{0..4}, Nbr_shifts_ending_at_912::{0..4}, Nbr_shifts_ending_at_910 = 0, Nbr_shifts_ending_at_908 = 0, Nbr_shifts_ending_at_906 = 0, Nbr_shifts_ending_at_904 = 0, Nbr_shifts_ending_at_902 = 0, Nbr_shifts_ending_at_900 = 0, Nbr_shifts_ending_at_898 = 0, Nbr_shifts_ending_at_896 = 0, Nbr_shifts_ending_at_894 = 0, Nbr_shifts_ending_at_892 = 0, Nbr_shifts_ending_at_890 = 0, Nbr_shifts_ending_at_888 = 0, Nbr_shifts_ending_at_886 = 0, Nbr_shifts_ending_at_884 = 0, Nbr_shifts_ending_at_882 = 0, Nbr_shifts_ending_at_880 = 0, Nbr_shifts_ending_at_878 = 0, Nbr_shifts_ending_at_876 = 0, Nbr_shifts_ending_at_874 = 0, Nbr_shifts_ending_at_872 = 0, Nbr_shifts_ending_at_870 = 0, Nbr_shifts_ending_at_868 = 0, Nbr_shifts_ending_at_866 = 0, Nbr_shifts_ending_at_864 = 1, Nbr_shifts_ending_at_862 = 0, Nbr_shifts_ending_at_860 = 0, Nbr_shifts_ending_at_858 = 0, Nbr_shifts_ending_at_856 = 0, Nbr_shifts_ending_at_854 = 0, Nbr_shifts_ending_at_852 = 0, Nbr_shifts_ending_at_850 = 0, Nbr_shifts_ending_at_848 = 0, Nbr_shifts_ending_at_846 = 0, Nbr_shifts_ending_at_844 = 0, Nbr_shifts_ending_at_842 = 0, Nbr_shifts_ending_at_840 = 0, Nbr_shifts_ending_at_838 = 0, Nbr_shifts_ending_at_836 = 0, Nbr_shifts_ending_at_834 = 0, Nbr_shifts_ending_at_832 = 0, Nbr_shifts_ending_at_830 = 0, Nbr_shifts_ending_at_828 = 0, Nbr_shifts_ending_at_826 = 0, Nbr_shifts_ending_at_824 = 0, Nbr_shifts_ending_at_822 = 0, Nbr_shifts_ending_at_820 = 0, Nbr_shifts_ending_at_818 = 0, Nbr_shifts_ending_at_816 = 0, Nbr_shifts_ending_at_814 = 0, Nbr_shifts_ending_at_812 = 0, Nbr_shifts_ending_at_810 = 0, Nbr_shifts_ending_at_808 = 0, Nbr_shifts_ending_at_806 = 0, Nbr_shifts_ending_at_804 = 0, Nbr_shifts_ending_at_802 = 0, Nbr_shifts_ending_at_800 = 0, Nbr_shifts_ending_at_798 = 0, Nbr_shifts_ending_at_796 = 0, Nbr_shifts_ending_at_794 = 0, Nbr_shifts_ending_at_792 = 0, Nbr_shifts_ending_at_790 = 0, Nbr_shifts_ending_at_788 = 0, Nbr_shifts_ending_at_786 = 0, Nbr_shifts_ending_at_784 = 0, Nbr_shifts_ending_at_782 = 0, Nbr_shifts_ending_at_780 = 0, Nbr_shifts_ending_at_778 = 0, Nbr_shifts_ending_at_776 = 0, Nbr_shifts_ending_at_774 = 0, Nbr_shifts_ending_at_772 = 0, Nbr_shifts_ending_at_770 = 0, Nbr_shifts_ending_at_768 = 0, Nbr_shifts_ending_at_766 = 0, Nbr_shifts_ending_at_764 = 0, Nbr_shifts_ending_at_762 = 0, Nbr_shifts_ending_at_760 = 0, Nbr_shifts_ending_at_758 = 0, Nbr_shifts_ending_at_756 = 0, Nbr_shifts_ending_at_754 = 0, Nbr_shifts_ending_at_752 = 0, Nbr_shifts_ending_at_750 = 0, Nbr_shifts_ending_at_748 = 0, Nbr_shifts_ending_at_746 = 0, Nbr_shifts_ending_at_744 = 0, Nbr_shifts_ending_at_742 = 0, Nbr_shifts_ending_at_740 = 0, Nbr_shifts_ending_at_738 = 0, Nbr_shifts_ending_at_736 = 0, Nbr_shifts_ending_at_734 = 0, Nbr_shifts_ending_at_732 = 0, Nbr_shifts_ending_at_730 = 0, Nbr_shifts_ending_at_728 = 0, Nbr_shifts_ending_at_726 = 0, Nbr_shifts_ending_at_724 = 0, Nbr_shifts_ending_at_722 = 0, Nbr_shifts_ending_at_720 = 0, Nbr_shifts_ending_at_718 = 0, Nbr_shifts_ending_at_716 = 0, Nbr_shifts_ending_at_714 = 0, Nbr_shifts_ending_at_712 = 0, Nbr_shifts_ending_at_710 = 0, Nbr_shifts_ending_at_708 = 0, Nbr_shifts_ending_at_706 = 0, Nbr_shifts_ending_at_704 = 0, Nbr_shifts_ending_at_702 = 0, Nbr_shifts_ending_at_700 = 0, Nbr_shifts_ending_at_698 = 0, Nbr_shifts_ending_at_696 = 0, Nbr_shifts_ending_at_694 = 0, Nbr_shifts_ending_at_692 = 0, Nbr_shifts_ending_at_690 = 0, Nbr_shifts_ending_at_688 = 0, Nbr_shifts_ending_at_686 = 0, Nbr_shifts_ending_at_684 = 0, Nbr_shifts_ending_at_682 = 0, Nbr_shifts_ending_at_680 = 0, Nbr_shifts_ending_at_678 = 0, Nbr_shifts_ending_at_676 = 0, Nbr_shifts_ending_at_674 = 0, Nbr_shifts_ending_at_672 = 0, Nbr_shifts_ending_at_670::{2..7}, Nbr_shifts_ending_at_668::{0..5}, Nbr_shifts_ending_at_666::{0..5}, Nbr_shifts_ending_at_664::{0..5}, Nbr_shifts_ending_at_662::{0..5}, Nbr_shifts_ending_at_660::{0..5}, Nbr_shifts_ending_at_658::{0..5}, Nbr_shifts_ending_at_656::{0..5}, Nbr_shifts_ending_at_654::{0..3}, Nbr_shifts_ending_at_652::{0..3}, Nbr_shifts_ending_at_650::{0..3}, Nbr_shifts_ending_at_648::{0..3}, Nbr_shifts_ending_at_646::{0..3}, Nbr_shifts_ending_at_644::{0..3}, Nbr_shifts_ending_at_642::{0..3}, Nbr_shifts_ending_at_640::{0..3}, Nbr_shifts_ending_at_638::{0..3}, Nbr_shifts_ending_at_636::{0..3}, Nbr_shifts_ending_at_634::{0..3}, Nbr_shifts_ending_at_632::{0..3}, Nbr_shifts_ending_at_630::{0..3}, Nbr_shifts_ending_at_628::{0..3}, Nbr_shifts_ending_at_626::{0..3}, Nbr_shifts_ending_at_624::{0..3}, Nbr_shifts_ending_at_622 = 0, Nbr_shifts_ending_at_620 = 0, Nbr_shifts_ending_at_618 = 0, Nbr_shifts_ending_at_616 = 0, Nbr_shifts_ending_at_614 = 0, Nbr_shifts_ending_at_612 = 0, Nbr_shifts_ending_at_610 = 0, Nbr_shifts_ending_at_608 = 0, Nbr_shifts_ending_at_606 = 0, Nbr_shifts_ending_at_604 = 0, Nbr_shifts_ending_at_602 = 0, Nbr_shifts_ending_at_600 = 0, Nbr_shifts_ending_at_598 = 0, Nbr_shifts_ending_at_596 = 0, Nbr_shifts_ending_at_594 = 0, Nbr_shifts_ending_at_592 = 0, Nbr_shifts_ending_at_590 = 0, Nbr_shifts_ending_at_588 = 0, Nbr_shifts_ending_at_586 = 0, Nbr_shifts_ending_at_584 = 0, Nbr_shifts_ending_at_582 = 0, Nbr_shifts_ending_at_580 = 0, Nbr_shifts_ending_at_578 = 0, Nbr_shifts_ending_at_576 = 0, Nbr_shifts_ending_at_574::{1..5}, Nbr_shifts_ending_at_572::{0..4}, Nbr_shifts_ending_at_570::{0..4}, Nbr_shifts_ending_at_568::{0..4}, Nbr_shifts_ending_at_566::{0..2}, Nbr_shifts_ending_at_564::{0..2}, Nbr_shifts_ending_at_562::{0..2}, Nbr_shifts_ending_at_560::{0..2}, Nbr_shifts_ending_at_558::{0..2}, Nbr_shifts_ending_at_556::{0..2}, Nbr_shifts_ending_at_554::{0..2}, Nbr_shifts_ending_at_552::{0..2}, Nbr_shifts_ending_at_550::{0..1}, Nbr_shifts_ending_at_548::{0..1}, Nbr_shifts_ending_at_546::{0..1}, Nbr_shifts_ending_at_544::{0..1}, Nbr_shifts_ending_at_542::{0..1}, Nbr_shifts_ending_at_540::{0..1}, Nbr_shifts_ending_at_538::{0..1}, Nbr_shifts_ending_at_536::{0..1}, Nbr_shifts_ending_at_534::{0..1}, Nbr_shifts_ending_at_532::{0..1}, Nbr_shifts_ending_at_530::{0..1}, Nbr_shifts_ending_at_528::{0..1}, Nbr_shifts_ending_at_526 = 0, Nbr_shifts_ending_at_524 = 0, Nbr_shifts_ending_at_522 = 0, Nbr_shifts_ending_at_520 = 0, Nbr_shifts_ending_at_518 = 0, Nbr_shifts_ending_at_516 = 0, Nbr_shifts_ending_at_514 = 0, Nbr_shifts_ending_at_512 = 0, Nbr_shifts_ending_at_510 = 0, Nbr_shifts_ending_at_508 = 0, Nbr_shifts_ending_at_506 = 0, Nbr_shifts_ending_at_504 = 0, Nbr_shifts_ending_at_502 = 0, Nbr_shifts_ending_at_500 = 0, Nbr_shifts_ending_at_498 = 0, Nbr_shifts_ending_at_496 = 0, Nbr_shifts_ending_at_494 = 0, Nbr_shifts_ending_at_492 = 0, Nbr_shifts_ending_at_490 = 0, Nbr_shifts_ending_at_488 = 0, Nbr_shifts_ending_at_486::{0..2}, Nbr_shifts_ending_at_484::{0..2}, Nbr_shifts_ending_at_482::{0..2}, Nbr_shifts_ending_at_480::{0..2}, Nbr_shifts_ending_at_478::{2..7}, Nbr_shifts_ending_at_476::{0..5}, Nbr_shifts_ending_at_474::{0..5}, Nbr_shifts_ending_at_472::{0..5}, Nbr_shifts_ending_at_470::{0..5}, Nbr_shifts_ending_at_468::{0..5}, Nbr_shifts_ending_at_466::{0..5}, Nbr_shifts_ending_at_464::{0..5}, Nbr_shifts_ending_at_462::{0..3}, Nbr_shifts_ending_at_460::{0..3}, Nbr_shifts_ending_at_458::{0..3}, Nbr_shifts_ending_at_456::{0..3}, Nbr_shifts_ending_at_454::{0..3}, Nbr_shifts_ending_at_452::{0..3}, Nbr_shifts_ending_at_450::{0..3}, Nbr_shifts_ending_at_448::{0..3}, Nbr_shifts_ending_at_446::{0..3}, Nbr_shifts_ending_at_444::{0..3}, Nbr_shifts_ending_at_442::{0..3}, Nbr_shifts_ending_at_440::{0..3}, Nbr_shifts_ending_at_438::{0..3}, Nbr_shifts_ending_at_436::{0..3}, Nbr_shifts_ending_at_434::{0..3}, Nbr_shifts_ending_at_432::{0..3}, Nbr_shifts_ending_at_430 = 0, Nbr_shifts_ending_at_428 = 0, Nbr_shifts_ending_at_426 = 0, Nbr_shifts_ending_at_424 = 0, Nbr_shifts_ending_at_422 = 0, Nbr_shifts_ending_at_420 = 0, Nbr_shifts_ending_at_418 = 0, Nbr_shifts_ending_at_416 = 0, Nbr_shifts_ending_at_414 = 0, Nbr_shifts_ending_at_412 = 0, Nbr_shifts_ending_at_410 = 0, Nbr_shifts_ending_at_408 = 0, Nbr_shifts_ending_at_406 = 0, Nbr_shifts_ending_at_404 = 0, Nbr_shifts_ending_at_402 = 0, Nbr_shifts_ending_at_400 = 0, Nbr_shifts_ending_at_398 = 0, Nbr_shifts_ending_at_396 = 0, Nbr_shifts_ending_at_394 = 0, Nbr_shifts_ending_at_392 = 0, Nbr_shifts_ending_at_390 = 0, Nbr_shifts_ending_at_388 = 0, Nbr_shifts_ending_at_386 = 0, Nbr_shifts_ending_at_384 = 0, Nbr_shifts_ending_at_382::{2..4}, Nbr_shifts_ending_at_380::{0..2}, Nbr_shifts_ending_at_378::{0..2}, Nbr_shifts_ending_at_376::{0..2}, Nbr_shifts_ending_at_374 = 0, Nbr_shifts_ending_at_372 = 0, Nbr_shifts_ending_at_370 = 0, Nbr_shifts_ending_at_368 = 0, Nbr_shifts_ending_at_366 = 0, Nbr_shifts_ending_at_364 = 0, Nbr_shifts_ending_at_362 = 0, Nbr_shifts_ending_at_360 = 0, Nbr_shifts_ending_at_358 = 0, Nbr_shifts_ending_at_356 = 0, Nbr_shifts_ending_at_354 = 0, Nbr_shifts_ending_at_352 = 0, Nbr_shifts_ending_at_350 = 0, Nbr_shifts_ending_at_348 = 0, Nbr_shifts_ending_at_346 = 0, Nbr_shifts_ending_at_344 = 0, Nbr_shifts_ending_at_342 = 0, Nbr_shifts_ending_at_340 = 0, Nbr_shifts_ending_at_338 = 0, Nbr_shifts_ending_at_336 = 0, Nbr_shifts_ending_at_334 = 0, Nbr_shifts_ending_at_332 = 0, Nbr_shifts_ending_at_330 = 0, Nbr_shifts_ending_at_328 = 0, Nbr_shifts_ending_at_326 = 0, Nbr_shifts_ending_at_324 = 0, Nbr_shifts_ending_at_322 = 0, Nbr_shifts_ending_at_320 = 0, Nbr_shifts_ending_at_318 = 0, Nbr_shifts_ending_at_316 = 0, Nbr_shifts_ending_at_314 = 0, Nbr_shifts_ending_at_312 = 0, Nbr_shifts_ending_at_310 = 0, Nbr_shifts_ending_at_308 = 0, Nbr_shifts_ending_at_306 = 0, Nbr_shifts_ending_at_304 = 0, Nbr_shifts_ending_at_302 = 0, Nbr_shifts_ending_at_300 = 0, Nbr_shifts_ending_at_298 = 0, Nbr_shifts_ending_at_296 = 0, Nbr_shifts_ending_at_294::{1..3}, Nbr_shifts_ending_at_292::{0..2}, Nbr_shifts_ending_at_290::{0..2}, Nbr_shifts_ending_at_288::{0..2}, Nbr_shifts_ending_at_286 = 2, Nbr_shifts_ending_at_284 = 0, Nbr_shifts_ending_at_282 = 0, Nbr_shifts_ending_at_280 = 0, Nbr_shifts_ending_at_278 = 0, Nbr_shifts_ending_at_276 = 0, Nbr_shifts_ending_at_274 = 0, Nbr_shifts_ending_at_272 = 0, Nbr_shifts_ending_at_270 = 0, Nbr_shifts_ending_at_268 = 0, Nbr_shifts_ending_at_266 = 0, Nbr_shifts_ending_at_264 = 0, Nbr_shifts_ending_at_262 = 0, Nbr_shifts_ending_at_260 = 0, Nbr_shifts_ending_at_258 = 0, Nbr_shifts_ending_at_256 = 0, Nbr_shifts_ending_at_254 = 0, Nbr_shifts_ending_at_252 = 0, Nbr_shifts_ending_at_250 = 0, Nbr_shifts_ending_at_248 = 0, Nbr_shifts_ending_at_246 = 0, Nbr_shifts_ending_at_244 = 0, Nbr_shifts_ending_at_242 = 0, Nbr_shifts_ending_at_240 = 0, Nbr_shifts_ending_at_238 = 0, Nbr_shifts_ending_at_236 = 0, Nbr_shifts_ending_at_234 = 0, Nbr_shifts_ending_at_232 = 0, Nbr_shifts_ending_at_230 = 0, Nbr_shifts_ending_at_228 = 0, Nbr_shifts_ending_at_226 = 0, Nbr_shifts_ending_at_224 = 0, Nbr_shifts_ending_at_222 = 0, Nbr_shifts_ending_at_220 = 0, Nbr_shifts_ending_at_218 = 0, Nbr_shifts_ending_at_216 = 0, Nbr_shifts_ending_at_214 = 0, Nbr_shifts_ending_at_212 = 0, Nbr_shifts_ending_at_210 = 0, Nbr_shifts_ending_at_208 = 0, Nbr_shifts_ending_at_206 = 0, Nbr_shifts_ending_at_204 = 0, Nbr_shifts_ending_at_202 = 0, Nbr_shifts_ending_at_200 = 0, Nbr_shifts_ending_at_198 = 0, Nbr_shifts_ending_at_196 = 0, Nbr_shifts_ending_at_194 = 0, Nbr_shifts_ending_at_192 = 0, Nbr_shifts_ending_at_190 = 0, Nbr_shifts_ending_at_188 = 0, Nbr_shifts_ending_at_186 = 0, Nbr_shifts_ending_at_184 = 0, Nbr_shifts_ending_at_182 = 0, Nbr_shifts_ending_at_180 = 0, Nbr_shifts_ending_at_178 = 0, Nbr_shifts_ending_at_176 = 0, Nbr_shifts_ending_at_174 = 0, Nbr_shifts_ending_at_172 = 0, Nbr_shifts_ending_at_170 = 0, Nbr_shifts_ending_at_168 = 0, Nbr_shifts_ending_at_166 = 0, Nbr_shifts_ending_at_164 = 0, Nbr_shifts_ending_at_162 = 0, Nbr_shifts_ending_at_160 = 0, Nbr_shifts_ending_at_158 = 0, Nbr_shifts_ending_at_156 = 0, Nbr_shifts_ending_at_154 = 0, Nbr_shifts_ending_at_152 = 0, Nbr_shifts_ending_at_150 = 0, Nbr_shifts_ending_at_148 = 0, Nbr_shifts_ending_at_146 = 0, Nbr_shifts_ending_at_144 = 0, Nbr_shifts_ending_at_142 = 0, Nbr_shifts_ending_at_140 = 0, Nbr_shifts_ending_at_138 = 0, Nbr_shifts_ending_at_136 = 0, Nbr_shifts_ending_at_134 = 0, Nbr_shifts_ending_at_132 = 0, Nbr_shifts_ending_at_130 = 0, Nbr_shifts_ending_at_128 = 0, Nbr_shifts_ending_at_126 = 0, Nbr_shifts_ending_at_124 = 0, Nbr_shifts_ending_at_122 = 0, Nbr_shifts_ending_at_120 = 0, Nbr_shifts_ending_at_118 = 0, Nbr_shifts_ending_at_116 = 0, Nbr_shifts_ending_at_114 = 0, Nbr_shifts_ending_at_112 = 0, Nbr_shifts_ending_at_110 = 0, Nbr_shifts_ending_at_108 = 0, Nbr_shifts_ending_at_106 = 0, Nbr_shifts_ending_at_104 = 0, Nbr_shifts_ending_at_102 = 0, Nbr_shifts_ending_at_100 = 0, Nbr_shifts_ending_at_98 = 0, Nbr_shifts_ending_at_96 = 0, Nbr_shifts_ending_at_94 = 0, Nbr_shifts_ending_at_92 = 0, Nbr_shifts_ending_at_90 = 0, Nbr_shifts_ending_at_88 = 0, Nbr_shifts_ending_at_86 = 0, Nbr_shifts_ending_at_84 = 0, Nbr_shifts_ending_at_82 = 0, Nbr_shifts_ending_at_80 = 0, Nbr_shifts_ending_at_78 = 0, Nbr_shifts_ending_at_76 = 0, Nbr_shifts_ending_at_74 = 0, Nbr_shifts_ending_at_72 = 0, Nbr_shifts_ending_at_70 = 0, Nbr_shifts_ending_at_68 = 0, Nbr_shifts_ending_at_66 = 0, Nbr_shifts_ending_at_64 = 0, Nbr_shifts_ending_at_62 = 0, Nbr_shifts_ending_at_60 = 0, Nbr_shifts_ending_at_58 = 0, Nbr_shifts_ending_at_56 = 0, Nbr_shifts_ending_at_54 = 0, Nbr_shifts_ending_at_52 = 0, Nbr_shifts_ending_at_50 = 0, Nbr_shifts_ending_at_48 = 0, Nbr_shifts_ending_at_46 = 0, Nbr_shifts_ending_at_44 = 0, Nbr_shifts_ending_at_42 = 0, Nbr_shifts_ending_at_40 = 0, Nbr_shifts_ending_at_38 = 0, Nbr_shifts_ending_at_36 = 0, Nbr_shifts_ending_at_34 = 0, Nbr_shifts_ending_at_32 = 0, Nbr_shifts_ending_at_30 = 0, Nbr_shifts_ending_at_28 = 0, Nbr_shifts_ending_at_26 = 0, Nbr_shifts_ending_at_24 = 0, Nbr_shifts_ending_at_22 = 0, Nbr_shifts_ending_at_20 = 0, Nbr_shifts_ending_at_18 = 0, Nbr_shifts_ending_at_16 = 0, Nbr_shifts_ending_at_14 = 0, Nbr_shifts_ending_at_12 = 0, Nbr_shifts_ending_at_10 = 0, Nbr_shifts_ending_at_8 = 0, Nbr_shifts_ending_at_6 = 0, Nbr_shifts_ending_at_4 = 0, Nbr_shifts_ending_at_2 = 0, Nbr_shifts_ending_at_0 = 0])

     
  • Thomas B. Léauté

    Actually, now that I look at it in more detail, I realize that the X variables ARE ordered as expected (grounded variables last); it is the list of counter variables that is not sorted (but I guess this is the expected behavior?...).

    Let me investigate further what is going on here, by adding asserts to GCC to check that the invariants are never violated. (Can I suggest you make more often use of asserts in JaCoP to catch bugs like the one in Among and possibly this one - if I can confirm this is a bug?)

     
  • Thomas B. Léauté

    I can confirm the existence of a similar bug in GCC; this can be demonstrated by adding asserts. I have attached my "asserted" version of GCC and my code.

    Thanks in advance for looking into this.

    Exception in thread "main" java.lang.AssertionError: Inconsistent X variable order: [Break_end_0::{204..278},
    Break_end_1::{684..758},
    Break_end_2::{780..854},
    Break_end_3::{876..950},
    Break_end_4::{1068..1102},
    Break_end_5::{1156..1190},
    Break_end_6::{108..182},
    Break_end_7::{204..278},
    Break_end_8::{300..374},
    Break_end_9::{396..470},
    Break_end_10::{684..758},
    Break_end_11::{780..854},
    Break_end_12::{108..182},
    Break_end_13::{204..278},
    Break_end_14::{300..374},
    Break_end_15::{780..854},
    Break_end_16::{876..950},
    Break_end_17::{972..1046},
    Break_end_18::{300..374},
    Break_end_19::{396..470},
    Break_end_20::{780..830},
    Break_end_21::{876..918},
    Break_end_22::{972..1006},
    Break_end_23::{1060..1094},
    Break_end_24::{12..86},
    Break_end_25::{108..182},
    Break_end_26::{204..278},
    Break_end_27::{684..758},
    Break_end_28::{780..854},
    Break_end_29::{876..950},
    Break_end_30::{108..182},
    Break_end_31::{204..278},
    Break_end_32::{300..374},
    Break_end_33::{780..854},
    Break_end_34::{876..950},
    Break_end_35::{972..1046},
    Break_end_36::{12..86},
    Break_end_37::{204..278},
    Break_end_38::{300..374},
    Break_end_39::{876..918},
    Break_end_40::{972..1006},
    Break_end_41::{1060..1094},
    Break_end_42::{12..86},
    Break_end_43::{108..182},
    Break_end_44::{396..470},
    Break_end_45::{684..718},
    Break_end_46::{772..806},
    Break_end_47::{876..950},
    Break_end_48::{12..40},
    Break_end_49::{100..122},
    Break_end_64::{968..1046},
    Break_end_51::{296..374},
    Break_end_52::{392..454},
    Break_end_53::{456..518},
    Break_end_54::{8..70},
    Break_end_55::{72..134},
    Break_end_56::{136..182},
    Break_end_57::{200..278},
    Break_end_58::{296..374},
    Break_end_59::{392..454},
    Break_end_60::{456..518},
    Break_end_61::{680..742},
    Break_end_62::{744..806},
    Break_end_50 = 182,
    Break_end_63::{808..854}]

     
  • Thomas B. Léauté

    Hi,

    I have tried to implement the fix suggested (briefly by email) by Radek (see attached patched version of GCC.java), but now the invariant becomes violated immediately after the first time the consistency method is called, after one of the variables involved has just been grounded:

    1. level: 22, Variable: Employee_for_shift_0 = 0<--0
      Exception in thread "main" java.lang.AssertionError: Inconsistent X variable order: [Employee_for_shift_0 = 0,
      Employee_for_shift_1::{0..9},
      ...]

      at JaCoP.constraints.GCC.consistency(GCC.java:311)

    Did I misunderstand the fix suggestion?...

    Thanks,

    Thomas

     
  • Radoslaw Szymanek

    Hi,

    I looked at your implementation of the fix attempt. You understood me correctly. It looks proper.

    However, your first assert is just incorrect. The added code to consistency function is to repair the invariant required by the remaining part of the consistency function. You can not check this invariant before the added code. It is expected that this assert is violated at this moment. Before, this invariant was maintained outside of the consistency function which is dangerous and can cause problems.

    I tried to run your Test. I encountered two problems.

    First, it seems you have implemented a constraint called ConditionalSum. I do not have this constraint. I commented out this constraint, but this may cause difficulty in bug replication.

    Second, I do not know how to run your Test. If I execute it without any parameters then the following condition in the main function will cause an error message being displayed and Test program exit.

    if (args.length != horizon) {
    System.err.println("Incorrect number of arguments; expected " + horizon + " but got " + args.length);
    return;
    }

    Thus for a moment, I can not replicate your bug to continue bug investigation.

    If the problem persists (after removal of the wrong assert) feel free to call me by Skype and we can sit down together and see if we can resolve this matter quickly.

    best,
    Radek

     
  • Thomas B. Léauté

    Hi Radek,

    Thanks a lot for your help! Indeed, I meant to put my first assert inside the if ( firstConsistencyCheck ), but I mistakenly put it outside. Attached is the revised version of GCC.java that seems to work (at least, I am not getting assertion errors anymore).

    The code for my ConditionalSum constraint has already been uploaded as attachment to an earlier post:
    https://sourceforge.net/p/jacop-solver/discussion/1220992/thread/ca76946a/#0464

    Here is what I need this constraint for. I have shifts, and two variables per shift:
    - the work time of the shift
    - the employee to which the shift is assigned
    and I want to compute the work time of each employee by adding the work times of the shifts she has been assigned. If you can think of another way to compute this that does not involve introducing too many auxiliary variables, I warmly welcome your suggestions.

    Finally, sorry for forgetting the input parameters to my main() method. This is supposed to be the demand curve (for each interval of 15 min, how many employees should be on duty). Here is the demand curve:

    2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1

    Best,

    Thomas

     
  • Thomas B. Léauté

    Hi again,

    After some effort put into introducing lots of auxiliary, redundant constraints to speed up my search, I am now stuck, unable to speed it further, and still very dissatisfied with the weakness of the propagation. Here is what I am seeing.

    For each shift i, I have 4 variables:
    - shiftStartTime[i]
    - breakStartTime[i]
    - breakEndTime[i]
    - shiftEndTime[i]

    Remember that the goal is to match the demand curve, so I need to compute the coverage at each time step (i.e. how many employees are working at each time step) to compare it with the demand curve. The way I compute the coverage at time step t is by first computing 4 counters:
    - nbrShiftsStartingAt[t], computed using a GCC on the shiftStartTime array
    - nbrBreaksStartingAt[t], computed using a GCC on the breakStartTime array
    - nbrBreaksEndingAt[t], computed using a GCC on the breakEndTime array
    - nbrShiftsEndingAt[t], computed using a GCC on the shiftEndTime array
    Then I compute the coverage at time step t by inference on t (using a SumWeight):
    coverage[t] = coverage[t-1] + nbrShiftsStartingAt[t] - nbrBreaksStartingAt[t] + nbrBreaksEndingAt[t] - nbrShiftsEndingAt[t].

    My current search strategy first fixes the shiftStartTimes and shiftEndTimes, fixes the duration of each break, and then searches for the optimal assignments to the breakStartTime variables. At some point during my search, I have two shifts starting at t_s = 0 and ending at t_e = 48 (= 12 hours later, with 4 timesteps per hour). The search chooses to have the break of the first shift start at its earliest start time of breakStartTime[0] = 8 (i.e. 2 hours after the beginning of the shift, according to the labor law). The propagation mechanism correctly infers that the coverage between timesteps 0 and 8 (excluded) is 2 (because the break of the second shift is also not allowed to start earlier than 2 hours after the beginning of the shift).

    With a break duration of 4 (= 1 hour), the propagation also correctly infers that the coverage between timesteps 8 and 12 (excluded) must be either 0 or 1. 0 would correspond to the case when the break of the second shift is also scheduled to start at timestep 8, and the coverage is 1 if it starts later.

    So far, so good. But the disappointing behavior I am now seeing is that starting at timestep 12 (after the break of the first shift has ended), the propagator thinks that the coverage beyond timestep 12 can be between 0 and 2, failing to realize that it cannot be 0, since the second part of the first shift (after its break) guarantees a coverage of at least 1. The problem is that the SumWeight sees that coverage[11] has domain {0..1}, it knows that nbrBreaksEndingAt[12] must be at least 1, but it thinks that nbrBreaksStartingAt[12] can be at most 1, so the lower bound on coverage[12] remains 0 + 1 - 1 = 0. What it fails to see is that the only way coverage[11] can be 0, is if the break of the second shift has started before timestep 12, and therefore nbrBreaksStartingAt[12] cannot be higher than 0.

    Do you have suggestions on how to improve the propagation in this case?

    Thanks a lot in advance,

    Thomas

     
  • Robin

    Robin - 2013-10-05

    Hello Thomas,

    Your problem can be modeled quite nicely as a network flow.

    The graph has a source node, a sink node and a node[t] for each instant in time (0 <= t <= 48).
    Then, you will have 3 types of arcs ("arc = directed edge"):
    - Arcs from source to node[t] with a flow of (nbrShiftsStartingAt[t] + nbrBreaksEndingAt[t])
    - Arcs from node[t] to node[t+1] with a flow of coverage[t]
    - Arcs from node[t] to sink with a flow of (nbrShiftsEndingAt[t] + nbrBreaksStartingAt[t])

    The unit of flow is a shift.
    Initially, there we configure an excess flow of 2 * N_SHIFTS at the source
    which then must flow through the network until it reaches the sink.

    For illustration, let's look at the flow for the first shift. (start=0, end=48)
    This shift corresponds to 1 unit of flow that takes the following path through the network:
    - source -> node[0] -> node[1] -> ... -> node[48] -> sink
    The break for the first shift (breakStart=8, breakEnd=12) takes this path:
    - source -> node[12] -> node[11] -> ... -> node[8] -> sink
    Hence breaks will flow 'backwards' through the network and will cancel existing flow.

    I attached a program that compares the propagation power of 3 different models.
    Model 'SIMPLE':
    - coverage[t] is computed using SumWeight as you described above
    - totalCoverageCost is computed as a simple sum
    Model 'NFC_FOR_COVERAGE':
    - coverage[t] is computed using the NetworkFlow constraint
    - totalCoverageCost is computed as a simple sum
    Model 'NFC_FOR_COST':
    - totalCoverageCost is computed directly using the NetworkFlow constraint

    The third model is particularly nice for your problem.
    Here you get a global constraint that optimizes the totalCoverageCost.
    The NetworkFlow constraint uses a simplex algorithm which is specialized in cost optimization.
    Note how powerful the domain reduction is in this case.

    Best wishes,
    Robin

     
  • Radoslaw Szymanek

    Hi Thomas and Robin,

    Thomas, is the improvement proposed by Robin helping sufficiently in your efficiency problem? If you need more help, just give me a call on Skype and we will discuss your problem in detail (both modeling and search).

    Robin, thanks for your suggestion and time preparing the example. It is great to see that you are using JaCoP in your work and publishing articles. You should keep us up to date so we know better what is JaCoP used for. ;).

    all the best,
    Radek

     
  • Thomas B. Léauté

    Hi Robin,
    Hi Radek,

    Thanks a lot for your suggestion!
    I implemented it but did not get the results I expected, for three reasons:

    1) JaCoP is now super slow at finding a first feasible solution. While it used to take it about 3 seconds, now it is more on the order of 1-2 min. This is because the NetworkFlow constraint has an extreme overhead: after each decision, JaCoP needs on the order of 1 second to propagate the constraint.

    2) I don't get the correct result in the end. In particular, once the search has finished assigning values to all decision variables (not counting the auxiliary variables), some of the auxiliary variables I have introduced to compute the under- and over-coverage at each timestep still remain undecided. This doesn't look right to me. I don't know if there is a bug in my code, or if I am making a mistake in the way I use the NetworkFlow constraint, or if this is a bug in the NetworkFlow constraint.

    3) Finally, soon after a first feasible solution has been found, the search crashes with and ArrayIndexOutOfBoundsException in GCC:
    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at JaCoP.constraints.GCC.putToTheEnd(GCC.java:1115)
    at JaCoP.constraints.GCC.consistency(GCC.java:334)
    at JaCoP.core.Store.consistency(Store.java:640)
    at JaCoP.search.DepthFirstSearch.label(DepthFirstSearch.java:524)

    I am attaching the latest version of my code that demonstrates the behavior above. This is now really looking like bad spaghetti code, sorry about that.

    The competition has officially ended this morning. My efforts to use JaCoP have been a pretty pathetic failure: I have been unable to produce good-quality solutions to a toy problem, while many other teams participating in the challenge have found provably optimal solution to much larger problems.
    I believe this failure is mainly due to two reasons:

    1) I have lost too much time debugging JaCoP itself. Looks like it has not been sufficiently tested yet and still contains too many bugs.

    2) It appears that the key to the success in the challenge was not in using the right solver, but really in using the right search strategy. My search strategy has probably been too poor to compete. The choice if JaCoP vs. another solver then becomes irrelevant.

    Best,

    Thomas

     
    Last edit: Thomas B. Léauté 2013-10-14
  • Radoslaw Szymanek

    Hi Thomas,

    Sorry about the bugs in GCC. Each constraint is a complex piece of code and sometimes some bugs go unnoticed for longer just because they require a particular search and activation sequence to trigger the bug. We will look into the recent bug in GCC, for a moment what seems to be weird that the exception does not happen with disabled asserts so looks like asserts may have some side effects. Thank you for your time.

    Concerning your search comment. Unfortunately, CP technology still requires getting the model and search right. There is no free lunch yet, even if many people are focusing on automatic search. Getting the search right often requires understanding how constraints are propagating to avoid thrashing (wrong decisions that take a lot of time to discover).
    Thus the search depends heavily not only on the problem type but also on the model used.

    I will appreciate if you send me the original problem description with some examples of instances by email. We may want to add it as an example to JaCoP library of examples, so next time somebody stumbles upon this type of problem has some clues how this problem can be addressed. I would like to have a shot at this problem, but I need to have all details.

    best,
    Radek

    P.S. What JVM are you using? Some JVMs are still too experimental and were not working properly. We check JaCoP only against JVM from Oracle.

     
1 2 > >> (Page 1 of 2)

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks