Comment utiliser la programmation par contraintes pour optimiser paniers?

Question

J'ai une liste des articles que je veux acheter. Les articles sont offerts par différents magasins et des prix différents. Les magasins ont des coûts de livraison individuels. Je suis à la recherche d'une stratégie de shopping optimale (et une bibliothèque java supportant) pour acheter tous les articles avec un prix total minimal.

Exemple:

• Item1 est offert à Shop1 pour 100 $, à 111 $ pour Shop2.
• Item2 est offert à Shop1 pour 90 $, à Shop2 pour 85 $.
• coût de Shop1 de livraison: 10 $ si la commande totale <150 $; $ 0 sinon
• coût de Shop2 de livraison: 5 $ si la commande totale <50 $; $ 0 sinon

• Si j'achète Item1 et Item2 à Shop1 le coût total est de 100 $ + $ 90 + $ 0 = 190 $.
• Si j'achète Item1 et Item2 à Shop2 le coût total est de 111 $ + 85+ $ 0 = 196 $.
• Si j'achète Item1 à Shop1 et Item2 à Shop2 le coût total est de 100 $ + 10 $ + 85+ $ 0 = 195.

je reçois le prix minimal si je commande Item1 et Item2 à Shop1: 190 $

Qu'est-ce que j'ai essayé jusqu'à présent

Je demande une autre question avant qui me conduit à le domaine de la programmation par contraintes. J'ai regardé crème et xy " est défini dans le domaine (0, c) où c est le prix de l'article dans cette boutique

un seul prix en ligne devrait être non nul

si un ou plusieurs articles sont achetés d'un magasin et la somme des prix est inférieure à la limite, puis ajouter les frais de port au coût total

Boutique coût total est la somme des prix de tous les articles dans un magasin

coût total est la somme de tous les totaux de magasin

L'objectif est le "coût total". Je veux minimiser cela.

Dans la crème je n'étais pas en mesure d'exprimer la contrainte « si alors » pour les frais d'expédition conditionnels.

En Choco ces contraintes existent, mais même pour 5 articles et 10 boutiques le programme est en cours d'exécution pendant 10 minutes sans trouver une solution.

Question

Comment dois-je exprimer mes contraintes pour faire de ce problème résoluble pour un solveur de programmation de contrainte?

Answer 1

Je l'ai mis en œuvre ce problème dans MiniZinc (une contrainte de haut niveau langage de programmation): shopping_basket.mzn . Il est tout à fait en avant et pourrait peut-être servir de modèle pour votre modèle Java.

Pour le modèle Choco, avez-vous essayé différentes stratégies de recherche? Une autre stratégie peut être plus rapide.

Par ailleurs, un autre solveur de programmation de contraintes Java, vous pouvez consulter est JACOP .

Answer 2

Ce que vous demandez est sur le point essentiellement problème k- havresac. La page wikipedia J'ai aimé a une foule de ressources sur des solutions. Le problème est cependant NP-complet pour résoudre en entier, donc ce que vous pouvez faire est de chercher une meilleure solution proche par recuit simulé ou d'autres formes de recherche dans l'espace de problème.

La première chose à retenir est que les problèmes de contrainte, vous finirez probablement prendre une bonne partie de temps pour générer une solution. Dans votre exemple précédent, bien que cinq articles et dix magasins semble petite, elle, en réalité, génère un grand espace de problème (de l'ordre de 1e5 ne comprenant pas la complication supplémentaire de la tarification conditionnelle qui accapare en outre le problème).

Les contraintes qui pèsent sur le problème sont que vous achetez un de chaque article. L'objectif est le prix minimal. Je pense que ce que vous avez est assez bonne, même si je ne suis pas trop sûr de points de balle un et deux.

  

chaque prix "p xy" est défini dans le domaine (0, c) où c est le prix de l'article dans cette boutique

   

un seul prix en ligne devrait être non nul

J'envisagerait amortissant l'expédition sur le coût des articles achetés plutôt que de l'ajouter en tant que valeur totale en faisant les calculs.

Answer 3

Je ne suis pas sûr que ce soit un problème k-havresac. La question a mentionné les mots « paniers » mais ne précise pas une capacité à tout envoi donné. Si vous avez spécifié une taille de transport maximale, le problème commence à chercher plus comme un problème de havresac.

Le problème est vraiment juste un problème de flux de réseau de base avec des coûts de transporation sur les arcs et les coûts à l'origine. Parce que vous avez une fonction objectif clair - réduire au minimum le transport + coût du produit et parce qu'il est susceptible d'être une seule solution, CP peut ne pas être la meilleure approche.

Considérer la résolution comme un problème de programmation linéaire:

Min: Transport + Coût Produit

ST: produit total livré> = la demande (pour chaque produit)

Vous pourriez avoir besoin de développer une équation linéaire par morceaux pour le coût du transport, mais cela ne devrait pas être un problème.