3
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ With the last constraint included, did you allow CPO to run to completion (i.e., until it either found an "optimal" solution or proved infeasibility) or did you stop it at some point. The output says "interrupted". If you aborted the run, it may be that CPO would have found a feasible solution given more time. $\endgroup$
    – prubin
    Aug 8 at 18:02
  • $\begingroup$ I interrupted it after 25 min, I'm running the program in a low to mid tier pc and I´m not really sure how much time I should leave it running. I will try running it overnight just in case you are right and it just need some more time to find a solution. $\endgroup$ Aug 8 at 20:16
  • $\begingroup$ FYI, if you want to try another approach, the problem can be expressed as a mixed integer linear program (in which case you can try running it with CPLEX). $\endgroup$
    – prubin
    Aug 8 at 20:27
  • $\begingroup$ How could I turn my last two constraints to fit a MILP? My only idea would be assigning them manually to avoid using logical constraints, but I would rather avoid having to manually assign someone as it may not be "most" optimal assignation. Thanks for your help btw. $\endgroup$ Aug 8 at 21:14

2 Answers 2

3
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.