[gecode-users] BAB and pruning

[aqwzsxaqwzsx at orange.fr]

 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" <cschulte at 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, cschulte at kth.se
Expert Researcher, RISE SICS, christian.schulte at ri.se

-----Original Message-----
From: users-bounces at gecode.org <users-bounces at gecode.org> On Behalf Of aqwzsxaqwzsx at orange.fr
Sent: 20 March 2018 17:20
To: users at 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 at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users