the model runs into a bug in version 12.9, it has been fixed in version 12.10. Could you upgrade please?
In version 12.9 there is a workaround: set undocumented parameter PresolveTransformers to value 2146959359. It disables part of the presolve with the bug. However the disabled presolve could be quite helpful, so upgrading is a better option.
Original Message:
Sent: Wed April 29, 2020 10:27 AM
From: Sulivan Cheung
Subject: Problem in constraint programming: model has no feasible solution, but with some decision variables specified, feasible and optimal solutions can be found.
Here is my log:
! ---------------------------------------------------------------------------- ! Minimization problem - 128 variables, 3,325 constraints ! Presolve : 2 extractables eliminated ! TimeLimit = 3,600 ! Workers = 4 ! NoOverlapInferenceLevel = Medium ! Initial process time : 0.03s (0.03s extraction + 0.00s propagation) ! . Log search space : 632.1 (before), 632.1 (after) ! . Memory usage : 1.8 MB (before), 1.8 MB (after) ! Using parallel search with 4 workers. ! ---------------------------------------------------------------------------- ! Best Branches Non-fixed W Branch decision 0 128 - + New bound is 49 ! ---------------------------------------------------------------------------- ! Search completed, model has no solution. ! Best bound : 49 ! ---------------------------------------------------------------------------- ! Number of branches : 0 ! Number of fails : 0 ! Total memory usage : 10.3 MB (9.1 MB CP Optimizer + 1.2 MB Concert) ! Time spent in solve : 0.04s (0.00s engine + 0.03s extraction) ! Search speed (br. / s) : 0 ! ---------------------------------------------------------------------------- ! ---------------------------------------------------------------------------- ! Minimization problem - 128 variables, 3,325 constraints ! Presolve : 2 extractables eliminated ! TimeLimit = 3,600 ! Workers = 4 ! NoOverlapInferenceLevel = Medium ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation) ! . Log search space : 632.1 (before), 632.1 (after) ! . Memory usage : 1.8 MB (before), 1.8 MB (after) ! Using sequential search. ! ---------------------------------------------------------------------------- ! Best Branches Non-fixed Branch decision ! ---------------------------------------------------------------------------- ! Minimization problem - 128 variables, 3,325 constraints ! Presolve : 2 extractables eliminated ! TimeLimit = 3,600 ! Workers = 4 ! NoOverlapInferenceLevel = Medium ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation) ! . Log search space : 632.1 (before), 632.1 (after) ! . Memory usage : 1.8 MB (before), 1.8 MB (after) ! Using sequential search. ! ---------------------------------------------------------------------------- ! Best Branches Non-fixed Branch decision ! ---------------------------------------------------------------------------- ! Conflict refining - 3,325 constraints ! TimeLimit = 3,600 ! Workers = 4 ! NoOverlapInferenceLevel = Medium ! ---------------------------------------------------------------------------- ! Iteration Number of constraints * 1 3,313 * 2 3,313 * 3 1,657 * 4 829 * 5 829 * 6 829 * 7 829 * 8 778 * 9 778 * 10 778 * 11 778 * 12 775 * 13 774 * 14 773 * 15 1 * 16 1 ! Conflict refining terminated ! ---------------------------------------------------------------------------- ! Conflict status : Terminated normally, conflict found ! Conflict size : 1 constraint ! Number of iterations : 16 ! Total memory usage : 9.0 MB ! Conflict computation time : 0.19s ! ----------------------------------------------------------------------------
Seems that the number of constraints in my log is different from yours. I am not sure if the parameters of the solver are default or not. I am using CPLEX 12.9.
------------------------------
Sulivan Cheung
Original Message:
Sent: Wed April 29, 2020 05:58 AM
From: Xavier Nodet
Subject: Problem in constraint programming: model has no feasible solution, but with some decision variables specified, feasible and optimal solutions can be found.
When I comment out these constraints, I get slightly different results, but I do still get solutions:
! -------------------------------------------------- CP Optimizer 12.10.0.0 -- ! Minimization problem - 128 variables, 3305 constraints ! Presolve : 9 extractables eliminated ! TimeLimit = 3600 ! Workers = 4 ! NoOverlapInferenceLevel = Medium ! Initial process time : 0.10s (0.10s extraction + 0.00s propagation) ! . Log search space : 184.6 (before), 184.6 (after) ! . Memory usage : 3.0 MB (before), 3.0 MB (after) ! Using parallel search with 4 workers. ! ---------------------------------------------------------------------------- ! Best Branches Non-fixed W Branch decision 0 128 - + New bound is 49 * 237 195 0.20s 1 (gap is 79.32%) * 234 339 0.20s 1 (gap is 79.06%) * 223 761 0.20s 1 (gap is 78.03%) 223 1000 1 1 148 = startOf(a_itv({12,3}))[...] 183 602k 3 2 114 = startOf(a_itv({19,4})) 183 612k 3 3 58 != startOf(a_itv({16,2})) 183 631k 3 4 7 != startOf(a_itv({3,3})) 183 632k 3 4 7 = startOf(a_itv({1,1})) 183 426k 51 1 50 <= startOf(a_itv({9,1})) + New bound is 181 (gap is 1.09%) 183 426k 45 1 F !presenceOf(a_itv({13,3})) + New bound is 183 (gap is 0.00%) ! ---------------------------------------------------------------------------- ! Search completed, 13 solutions found. ! Best objective : 183 (optimal - effective tol. is 0) ! Best bound : 183 ! ---------------------------------------------------------------------------- ! Number of branches : 2277304 ! Number of fails : 1136254 ! Total memory usage : 27.9 MB (26.8 MB CP Optimizer + 1.2 MB Concert) ! Time spent in solve : 32.02s (31.92s engine + 0.10s extraction) ! Search speed (br. / s) : 71344.1 ! ----------------------------------------------------------------------------
Could you please post the log that you get from the solver? Are you using any non-default parameters?
------------------------------
Xavier Nodet
Program Manager, Development
CPLEX Optimization Studio
Original Message:
Sent: Wed April 29, 2020 05:31 AM
From: Sulivan Cheung
Subject: Problem in constraint programming: model has no feasible solution, but with some decision variables specified, feasible and optimal solutions can be found.
Dear Xavier,
Thanks very much for your reply. Indeed the model I posted has an optimal solution with objective value = 183.
However, if you remove the last four lines in the constraints by commenting them as follows:
//z[<1>][<5>]==1;//z[<2>][<6>]==1;//z[<3>][<5>]==1;//z[<4>][<6>]==1;
The model becomes infeasible. My original intension was to find these z values (as decision variables) automatically by the model itself from constraints ct8~ct11.
Without these specified values of z, the solver says that the model has no solution as ct11 is in conflict, which is apprently incorrect. The specied values are parts of a feasible solution, but the solver cannot find it.
------------------------------
Sulivan Cheung
Original Message:
Sent: Wed April 29, 2020 04:18 AM
From: Xavier Nodet
Subject: Problem in constraint programming: model has no feasible solution, but with some decision variables specified, feasible and optimal solutions can be found.
Hi Sulivan,
When I tried your model on my laptop, I got this. So I'm not sure what's going on. Posting the log of the solver may help pinpoint the issue...
! -------------------------------------------------- CP Optimizer 12.10.0.0 -- ! Minimization problem - 128 variables, 3309 constraints ! Presolve : 3 extractables eliminated ! TimeLimit = 3600 ! Workers = 4 ! NoOverlapInferenceLevel = Medium ! Initial process time : 0.07s (0.07s extraction + 0.00s propagation) ! . Log search space : 178.6 (before), 178.6 (after) ! . Memory usage : 2.6 MB (before), 2.6 MB (after) ! Using parallel search with 4 workers. ! ---------------------------------------------------------------------------- ! Best Branches Non-fixed W Branch decision 0 128 - + New bound is 49 * 331 89 0.15s 1 (gap is 85.20%) * 256 133 0.15s 1 (gap is 80.86%) * 238 208 0.15s 1 (gap is 79.41%) * 236 228 0.15s 1 (gap is 79.24%) * 229 332 0.15s 1 (gap is 78.60%) * 225 807 0.15s 1 (gap is 78.22%) 225 1000 1 1 119 = startOf(a_itv({14,3})) * 213 1228 0.15s 1 (gap is 77.00%) 213 1000 1 2 119 = startOf(a_itv({14,3})) 213 1000 1 3 !presenceOf(a_itv({14,2})) * 210 1192 0.15s 3 (gap is 76.67%) 210 2000 3 1 18 = startOf(a_itv({2,2})) 210 3000 18 1 114 = startOf(a_itv({11,3}))[...] 183 196k 33 1 F presenceOf(a_itv({11,2})) 183 196k 42 1 F presenceOf(a_itv({16,2})) + New bound is 174 (gap is 4.92%) 183 196k 42 1 F !presenceOf(a_itv({6,1})) + New bound is 183 (gap is 0.00%) ! ---------------------------------------------------------------------------- ! Search completed, 16 solutions found. ! Best objective : 183 (optimal - effective tol. is 0) ! Best bound : 183 ! ---------------------------------------------------------------------------- ! Number of branches : 968454 ! Number of fails : 493105 ! Total memory usage : 24.0 MB (22.7 MB CP Optimizer + 1.2 MB Concert) ! Time spent in solve : 13.21s (13.13s engine + 0.07s extraction) ! Search speed (br. / s) : 73702.7 ! ----------------------------------------------------------------------------
------------------------------
Xavier Nodet
Program Manager, Development
CPLEX Optimization Studio
Original Message:
Sent: Tue April 28, 2020 11:07 PM
From: Sulivan Cheung
Subject: Problem in constraint programming: model has no feasible solution, but with some decision variables specified, feasible and optimal solutions can be found.
Hello all! I'm studying an assembling scheduling problem. The CP model I am using is as follows (a simplified example):using CP;tuple Job{ key int ID; int L; int R;};tuple Operation{ key int ID; int jID;};tuple Assignment{ key int oID; key int mID; int jID; int pt;};tuple Precedence{ int prd; int suc;};tuple Triplet{ int i; int j; int t;};{Job} Jobs = {<1,1,0>,<2,2,0>,<3,2,0>,<4,4,0>,<5,0,3>,<6,0,6>};{Operation} Operations = {<1,1>,<2,1>,<3,1>,<4,1>,<5,2>,<6,2>,<7,2>,<8,2>,<9,3>,<10,3>,<11,3>,<12,3>,<13,4>,<14,4>,<15,4>,<16,4>,<17,5>,<18,5>,<19,6>,<20,6>};{Assignment} Assignments = {<1,1,1,8>,<1,2,1,11>,<1,3,1,15>,<2,1,1,20>,<2,2,1,13>,<2,3,1,11>,<3,1,1,19>,<3,2,1,27>,<3,3,1,24>,<4,1,1,21>,<4,2,1,18>,<4,3,1,27>,<5,1,2,23>,<5,2,2,29>,<5,3,2,20>,<6,1,2,13>,<6,2,2,16>,<6,3,2,22>,<7,1,2,30>,<7,2,2,19>,<7,3,2,24>,<8,1,2,20>,<8,2,2,25>,<8,3,2,16>,<9,1,3,23>,<9,2,3,29>,<9,3,3,20>,<10,1,3,13>,<10,2,3,16>,<10,3,3,22>,<11,1,3,30>,<11,2,3,19>,<11,3,3,24>,<12,1,3,20>,<12,2,3,25>,<12,3,3,16>,<13,1,4,17>,<13,2,4,24>,<13,3,4,19>,<14,1,4,23>,<14,2,4,15>,<14,3,4,14>,<15,1,4,28>,<15,2,4,27>,<15,3,4,24>,<16,1,4,20>,<16,2,4,18>,<16,3,4,22>,<17,4,5,14>,<18,1,5,17>,<18,2,5,10>,<18,3,5,18>,<19,4,6,16>,<20,1,6,20>,<20,2,6,31>,<20,3,6,23>};{Precedence} Precedences = {<1,2>,<2,4>,<3,4>,<5,6>,<5,7>,<9,10>,<9,11>,<13,14>,<13,16>,<15,16>,<17,18>,<19,20>};{Triplet} T = {<1,1,0>,<1,2,5>,<1,3,5>,<1,4,15>,<2,1,5>,<2,2,0>,<2,3,5>,<2,4,15>,<3,1,5>,<3,2,5>,<3,3,0>,<3,4,15>,<4,1,15>,<4,2,15>,<4,3,15>,<4,4,0>};{Triplet} S = {<0,1,7>,<0,2,7>,<0,3,7>,<0,4,7>,<0,5,7>,<0,6,7>,<1,1,0>,<1,2,10>,<1,3,10>,<1,4,10>,<1,5,10>,<1,6,10>,<2,1,10>,<2,2,0>,<2,3,3>,<2,4,10>,<2,5,10>,<2,6,10>,<3,1,10>,<3,2,3>,<3,3,0>,<3,4,10>,<3,5,10>,<3,6,10>,<4,1,10>,<4,2,10>,<4,3,10>,<4,4,0>,<4,5,10>,<4,6,10>,<5,1,10>,<5,2,10>,<5,3,10>,<5,4,10>,<5,5,0>,<5,6,10>,<6,1,10>,<6,2,10>,<6,3,10>,<6,4,10>,<6,5,10>,<6,6,0>};range Machs = 1..4;dvar interval a_itv [a in Assignments] optional size a.pt;dvar interval o_itv [o in Operations];dvar interval j_itv [j in Jobs];dvar boolean z[j1 in Jobs][j2 in Jobs];dvar sequence mAssignments[m in Machs] in // Machine associated assignments all(a in Assignments, j in Jobs: a.mID == m && a.jID == j.ID) a_itv[a] types all(a in Assignments, j in Jobs: a.mID == m && a.jID == j.ID) j.ID; dvar sequence jAssignments[j in Jobs] in // Job associated assignments all(a in Assignments, m in Machs: a.jID == j.ID && a.mID == m) a_itv[a] types all(a in Assignments, m in Machs: a.jID == j.ID && a.mID == m) m;dexpr int ms = max(j in Jobs) endOf(j_itv[j]);execute { cp.param.TimeLimit = 3600; cp.param.NoOverlapInferenceLevel="Medium"; cp.param.Workers = 4;}// Objectiveminimize ms;subject to{ct1: forall(j in Jobs) noOverlap(jAssignments[j], T);ct2: forall(m in Machs) noOverlap(mAssignments[m], S);ct3: forall(a in Assignments, s in S: s.i==0 && s.j==a.mID) startOf(a_itv[a], s.t) >= s.t; ct4: forall(p in Precedences, o1 in Operations: o1.ID == p.prd, o2 in Operations: o2.ID == p.suc) endBeforeStart(o_itv[o1], o_itv[o2]);ct5: forall(j in Jobs) span(j_itv[j], all(o in Operations: o.jID == j.ID) o_itv[o]);ct6: forall(o in Operations) alternative(o_itv[o], all(a in Assignments: a.oID == o.ID) a_itv[a]);ct7: forall(a1 in Assignments, a2 in Assignments, t in T: t.i==a1.mID && t.j == a2.mID) startOf(a_itv[a2],100000) + 100000*(1-z[<a1.jID>][<a2.jID>]) >= endOf(a_itv[a1], -t.t) + t.t;ct8: forall(j in Jobs) sum(j1 in Jobs) z[j][j1] <= 1;ct9: forall(j1 in Jobs, j2 in Jobs) z[j1][j2] + z[j2][j1] <= 1;ct10: forall(j in Jobs) z[j][j] ==0;ct11: forall(j in Jobs) j.R == sum(j1 in Jobs) z[j1][j]*j1.L;z[<1>][<5>]==1;z[<2>][<6>]==1;z[<3>][<5>]==1;z[<4>][<6>]==1;}The problem is, the model has no feasible solution (which is apparently no true) if I comment out the specified z values in the last four lines. With these values specified (other z values equal to 0), the model has feasible and optimal solutions.
Why is this happening? Are the settings of some parameters need reconfiguration?
------------------------------
Sulivan Cheung
------------------------------
#DecisionOptimization