Constrained shift assignment problem using ilogcp solver can´t find an optimal solution

Question

I´ve been trying to solve a contrained assignation problem given a set of constraints based in a real-world problem. I modeled the problem in AMPL as follows:

    set Personnel;
    
    set Shifts;
    
    param costHora{i in Personnel}; 
    
    param necesidad{j in Shifts}; 
    
    param t_max{i in Personnel}; 
    
    param t_min{i in Personnel}; 
    
    param Eqn_horas{j in Shifts}; 
    
    param cost{i in Personnel, j in Shifts}= costHora[i]*Eqn_horas[j]; 
    
    var x{i in Personnel, j in Shifts} binary;
    
    minimize z: 
        sum{i in Personnel, j in Shifts} cost[i,j]*x[i,j];
    
    subject to N{j in Shifts}: sum{i in Personnel} x[i,j] >= necesidad[j];
    subject to MH{i in Personnel}: sum{j in Shifts} x[i,j]*Eqn_horas[j] <= t_max[i]; 
    subject to Mh{i in Personnel}: sum{j in Shifts} x[i,j]*Eqn_horas[j] >= t_min[i];
    subject to CVS{i in Personnel}: x[i,"I54"]+x[i,"I61"] <= 1;
    subject to CSD{i in Personnel}: x[i,"I64"]+x[i,"I71"] <= 1; 
    
    subject to DL{i in Personnel}: (if x[i,"I21"]+x[i,"I22"]=0 then 1 else 0) + (if x[i,"I31"]+x[i,"I32"]=0 then 1 else 0) + (if x[i,"I41"]+x[i,"I42"]=0 then 1 else 0) + (if x[i,"I51"]+x[i,"I52"]+x[i,"I53"]+x[i,"I54"]=0 then 1 else 0)  + (if x[i,"I61"]+x[i,"I62"]+x[i,"I63"]+x[i,"I64"]=0 then 1 else 0) + (if x[i,"I71"]+x[i,"I72"]=0 then 1 else 0) + (if x[i,"B11"]+x[i,"B12"]=0 then 1 else 0) + (if x[i,"B21"]+x[i,"B22"]=0 then 1 else 0) + (if x[i,"B31"]+x[i,"B32"]=0 then 1 else 0) + (if x[i,"B41"]+x[i,"B42"]=0 then 1 else 0) + (if x[i,"B51"]+x[i,"B52"]+x[i,"B53"]=0 then 1 else 0)  + (if x[i,"B61"]+x[i,"B62"]+x[i,"B63"]=0 then 1 else 0) + (if x[i,"B71"]=0 then 1 else 0)  >= 1;
     
    
    #subject to CT{i in Personnel}: if x[i,"I51"]=1 then x[i,"I52"]=1;

I´m using the Ilogcp solver included by default on the AMPL IDE as is the only solver (included by default) that is able to handle my second to last constraint due to it having logical operators (I´m not really sure if I could use any other solver, tips are always welcome!).

My problem comes when I include the last constraint (the one commented). I´m trying to make people work continuos shifts, since some shifts are less than the required working hours per day. For example, I´m trying to make workers assigned shift I51 to also be assigned shift I52. But, the solver can´t seem to hanlde the constraint as it keeps processing without reaching an optimal answer.

Without said constraint, for example, I get this answer:

ilogcp 12.10.0: interrupted
16327848 choice points, 7499498 fails, objective 2726.29
z = 2726.29

x [*,*] (tr)
# $1 = ADiego
# $2 = BDiego
# $3 = CEugenia
# $4 = CMerwin
# $5 = CMileidy
# $6 = CYolanda
# $7 = EJonathan
# $8 = FVanessa
# $9 = FlVanessa
# $10 = GAlejandro
# $11 = GBernardo
# $12 = LAnderson
# $13 = MEdwar
# $14 = PFrancisco
# $16 = QAdrian
# $17 = QCarolina
# $18 = RDanny
:     $1  $2  $3  $4  $5  $6  $7  $8  $9 $10 $11 $12 $13 $14 PJean $16 $17 $18 :=
B11    1   0   0   1   0   0   0   0   0   0   1   0   0   0    0    0   1   0
B12    1   0   1   0   0   0   0   0   0   1   0   0   0   0    0    0   1   0
B21    0   0   1   0   1   0   0   0   0   0   1   0   1   0    0    0   0   0
B22    0   0   0   0   0   0   0   0   0   1   0   1   1   0    1    1   0   0
B31    0   0   0   0   1   0   0   0   0   0   0   0   0   0    1    0   0   0
B32    0   1   0   0   0   0   1   0   1   1   0   0   0   0    0    0   0   0
B41    0   0   0   0   0   0   0   1   1   0   0   1   0   0    0    0   0   0
B42    1   0   0   0   1   1   1   0   0   0   0   1   0   0    0    1   0   0
B43    0   0   0   0   0   0   0   1   1   1   1   0   0   0    0    0   0   0
B51    1   0   0   1   0   1   0   0   0   0   0   0   0   0    0    0   0   1
B52    0   0   1   0   0   1   1   0   0   0   0   0   1   1    0    0   0   1
B53    0   1   0   1   0   0   0   0   0   0   0   0   0   1    1    0   0   0
B61    1   0   0   0   0   1   0   0   0   1   1   0   0   1    0    1   0   1
B62    0   1   1   1   0   0   0   1   1   0   1   1   0   0    0    0   1   0
B63    0   0   1   0   1   1   0   0   0   0   0   1   0   0    1    0   0   0
B71    0   1   0   1   0   0   0   0   0   0   1   0   1   1    0    0   0   0
BL21   0   0   0   1   0   0   0   0   0   0   0   0   0   0    0    0   0   1
BL31   0   0   0   0   0   0   1   0   1   0   0   0   0   0    0    0   0   0
BL41   0   0   0   0   0   0   0   0   0   1   0   0   0   0    0    1   0   0
BL51   0   0   0   1   0   0   0   0   0   0   0   0   0   0    0    1   0   0
BL52   0   0   0   0   0   1   0   1   1   0   0   0   0   0    0    0   0   0
BL61   0   0   1   0   0   0   0   0   0   0   0   0   0   0    1    0   0   0
BL62   1   0   0   0   0   0   0   0   0   0   0   0   0   0    1    0   0   1
BL71   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    1   0   0
I21    0   1   0   0   0   0   0   0   0   0   0   0   0   0    0    1   1   1
I22    1   0   0   0   1   1   0   0   1   0   0   0   0   0    0    0   0   0
I31    0   0   0   0   0   0   0   0   0   1   1   0   1   1    0    0   1   0
I32    0   0   0   0   0   1   1   0   0   0   0   0   0   0    0    0   1   0
I41    0   0   1   0   0   0   0   1   0   0   0   0   0   1    0    1   1   0
I42    1   1   0   0   0   0   0   0   0   0   0   1   1   1    1    0   0   0
I51    0   1   0   0   0   0   0   1   0   0   0   1   0   0    0    0   0   0
I52    1   0   1   0   0   0   1   0   0   0   0   0   0   0    1    0   0   0
I53    0   0   0   0   1   1   1   1   0   0   1   1   1   1    1    0   0   0
I54    0   0   0   0   1   0   0   1   0   1   0   0   0   1    0    0   0   1
I61    0   1   1   0   0   0   0   0   0   0   1   0   0   0    0    0   0   0
I62    1   1   1   0   1   1   0   1   1   1   0   0   0   0    0    0   0   0
I63    0   1   1   1   1   0   0   0   0   1   1   1   0   0    0    0   0   1
I64    0   0   0   0   1   0   0   0   0   0   1   0   0   0    1    0   1   0
I65    1   1   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   1
I71    0   1   0   1   0   0   1   0   0   0   0   1   0   0    0    0   0   1
I72    0   0   1   1   0   0   1   1   0   0   0   1   1   1    1    0   0   0

:    SDennis TTania VGabriela    :=
B11      0      0        0
B12      0      0        1
B21      0      0        0
B22      0      0        0
B31      1      0        1
B32      0      0        0
B41      0      1        0
B42      0      0        0
B43      0      0        0
B51      0      0        1
B52      1      1        0
B53      0      1        1
B61      1      0        0
B62      1      0        0
B63      0      0        1
B71      0      1        1
BL21     0      0        0
BL31     0      0        0
BL41     0      0        0
BL51     0      0        0
BL52     0      0        0
BL61     0      0        0
BL62     0      0        0
BL71     1      0        0
I21      0      0        1
I22      0      0        0
I31      0      0        0
I32      0      1        0
I41      0      0        0
I42      0      1        0
I51      0      0        1
I52      0      1        1
I53      0      0        1
I54      0      0        1
I61      0      1        0
I62      1      1        0
I63      1      0        1
I64      1      1        0
I65      0      1        0
I71      0      0        1
I72      1      1        0
;

With my last constraint uncommented I get this:

ilogcp 12.10.0: interrupted
15451615 choice points, 8621693 fails
z = 0

x [*,*] (tr)
# $1 = ADiego
# $2 = BDiego
# $3 = CEugenia
# $4 = CMerwin
# $5 = CMileidy
# $6 = CYolanda
# $7 = EJonathan
# $8 = FVanessa
# $9 = FlVanessa
# $10 = GAlejandro
# $11 = GBernardo
# $12 = LAnderson
# $13 = MEdwar
# $14 = PFrancisco
# $16 = QAdrian
# $17 = QCarolina
# $18 = RDanny
:     $1  $2  $3  $4  $5  $6  $7  $8  $9 $10 $11 $12 $13 $14 PJean $16 $17 $18 :=
B11    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B12    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B21    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B22    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B31    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B32    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B41    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B42    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B43    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B51    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B52    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B53    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B61    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B62    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B63    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
B71    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
BL21   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
BL31   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
BL41   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
BL51   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
BL52   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
BL61   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
BL62   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
BL71   0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I21    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I22    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I31    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I32    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I41    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I42    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I51    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I52    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I53    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I54    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I61    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I62    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I63    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I64    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I65    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I71    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0
I72    0   0   0   0   0   0   0   0   0   0   0   0   0   0    0    0   0   0

:    SDennis TTania VGabriela    :=
B11      0      0        0
B12      0      0        0
B21      0      0        0
B22      0      0        0
B31      0      0        0
B32      0      0        0
B41      0      0        0
B42      0      0        0
B43      0      0        0
B51      0      0        0
B52      0      0        0
B53      0      0        0
B61      0      0        0
B62      0      0        0
B63      0      0        0
B71      0      0        0
BL21     0      0        0
BL31     0      0        0
BL41     0      0        0
BL51     0      0        0
BL52     0      0        0
BL61     0      0        0
BL62     0      0        0
BL71     0      0        0
I21      0      0        0
I22      0      0        0
I31      0      0        0
I32      0      0        0
I41      0      0        0
I42      0      0        0
I51      0      0        0
I52      0      0        0
I53      0      0        0
I54      0      0        0
I61      0      0        0
I62      0      0        0
I63      0      0        0
I64      0      0        0
I65      0      0        0
I71      0      0        0
I72      0      0        0
;

I can´t seem to grasp why would that constraint make the problem unsolvable, even if I remove the second to last constraint the solver won´t find an optimal answer.

Is there any way I could reformulate my constraints to make the problem solvable? Is it due to the solver?

Answer 1

There's an experimental version of "Gurobi for AMPL" that should accept your constraint DL just as you have written it. It uses AMPL's new "MP" solver interface that converts many kinds of logical constraints to forms that MIP solvers can recognize. (You can find it as "x-gurobi" in AMPL distributions and download listings.) I haven't been able to test the new interface on your example, because I do not have the data, but I verified that "x-gurobi" worked on a simplified version of the condition that you are enforcing.

Concerning constraint CT, AMPL interprets what follows "then" (and optionally "else") as an expression, not as a constraint, so the ILOG CP solver may not be interpreting it as you intend. To say that one constraint implies another constraint, use the ==> ("implies") operator:

subject to CT {i in Personnel}: x[i,"I51"] = 1 ==> x[i,"I52"] = 1;

Because x is a binary variable, this is in fact an "indicator constraint" that's widely accepted by MIP solvers. (Constraint DL is also easily converted to indicator constraints.)

Answer 2

Regarding the possibility of switching to a MIP model, the last constraint is easy to convert. The implication $x_{i,j}=1 \implies x_{i,k}=1$ just becomes $x_{i,k}\ge x_{i,j}.$ The penultimate constraint is a disjunction saying that at least one of a gaggle of clauses must hold. To handle that, you introduce new binary variables $z_1,z_2,\dots$ (one for each clause) with the constraint $z_1+z_2+\dots \ge 1.$ I'll show by example how to connect each $z$ to its clause. The fourth clause in the code reads if x[i,"I51"]+x[i,"I52"]+x[i,"I53"]+x[i,"I54"]=0 then 1 else 0. The corresponding added constraints would be $$z_4\le 1 - x_{i,\textrm{I51}}$$ $$\cdots$$ $$z_4\le 1 - x_{i,\textrm{I54}}.$$ So for this clause to be satisfied ($z_4=1$), all four $x$ variables would have to be 0. Another approach would use the single constraint $$x_{i,\textrm{I51}}+\dots+x_{i,\textrm{I54}}+4z_4 \le 4,$$ (so if $z_4=1$ then all the $x$ variables must be 0), but the first approach makes for a tighter model.