mardi 8 mars 2011

Bob's Sale Problem

This is a very nice and interesting problem for CP posted recently on stackoverflow :

" Bob has a store, and wants to do a sale. His store carries a number of products, and he has a certain integer quantity of units of each product in stock. He also has a number of shelf-mounted price labels (as many as the number of products), with the prices already printed on them. He can place any price label on any product (unitary price for one item for his entire stock of that product), however some products have an additional restriction - any such product may not be cheaper than a certain other product. "

You must find how to arrange the price labels, such that the total cost of all of Bob's wares is as low as possible. The total cost is the sum of each product's assigned price label multiplied by the quantity of that product in stock. "

This can be modeled easily with some precedence constraints and an global alldiff constraint with costs (see Filippo Focacci, Andrea Lodi, Michela Milano: Cost-Based Domain Filtering. CP 1999 for the filtering algorithm) .

As soon is I find the time to do it, I'll generate some instances to test it....

Aucun commentaire:

Enregistrer un commentaire