Hi, Thank you for your reply. I thought my question was directly related to Gecode (and how the propagation were handled) and not to constraint programming in general. Do I understand that such a propagation can not to be generically integrated into the Gecode engine ? Anayway, thanks for your advices Philippe
---------------- Le 20/03/2018, à 21:26, "Christian Schulte" <cschu...@kth.se> a écrit : BAB only uses what propagation provides it with. If you want to have better bounds you have to make sure that you have stronger propagation.additional (a Try to turn your reasoning into additional (known as redundant) constraints, for example. But ultimately, this mailing list is for questions specific to Gecode not constraint programming in general. So you might want to find a different forum. Best Christian -- Christian Schulte, https://chschulte.github.io/ Professor of Computer Science, KTH, cschu...@kth.se Expert Researcher, RISE SICS, christian.schu...@ri.se -----Original Message----- From: users-boun...@gecode.org <users-boun...@gecode.org> On Behalf Of aqwzsxaqw...@orange.fr Sent: 20 March 2018 17:20 To: users@gecode.org Subject: [gecode-users] BAB and pruning Hi, I have a general question on BAB engine in Gecode. Suppose I have to affect 4 jobs to 4 persons and i want to minimize the cost of this affectation (using a MinimizeScript) : cost_matrix : J1 J2 J3 J4 --|---------------- A | 9, 2, 7, 8 B | 6, 4, 3, 7 C | 5, 8, 1, 8 D | 7, 6, 9, 4 Suppose also that I post these constraints : (e.g., exactly one person to exactly one job) x(*this, cols*rows, 0, 1) // array of assignments (as rows x cols) for(int r = 0; r < rows; r++) { linear(*this, x_m.row(r), IRT_EQ, 1); } for(int c = 0; c < cols; c++) { linear(*this, x_m.col(c), IRT_EQ, 1); } linear(*this, cost, x, IRT_EQ, total_cost); branch(*this, x, INT_VAR_NONE(), INT_VAL_MAX()); with x an array of assignments (and x_m its matrix representation) Now, let's make some reasoning : - if I affect J1 to person A, the minimum cost that we can expect is 17 (9 + 3 + 1 + 4) = 9 + (J3/B) + (J3/C) + (J4/D) - if I affect J2 to person A, the minimum cost that we can expect is 10 (2 + 3 + 1 + 4) = 2 + (J3/B) + (J3/C) + (J4/D) - if I affect J3 to person A, the minimum cost that we can expect is 20 (7 + 4 + 5 + 4) = 7 + (J2/B) + (J1/C) + (J4/D) - if I affect J4 to person A, the minimum cost that we can expect is 18 (8 + 3 + 1 + 6) = 8 + (J3/B) + (J3/C) + (J2/D) However, i see under Gist that for instance, the total cost when exploring the J1/A alternative is [9..59](lower bound could be 17) Is it normal that B&B cannot estimate more precisely the lower bound ? Can we expect that the pruning will be more efficient ? Thank you. _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
