Sac à dos 0/1 avec poids d'article dépendant ?

Question

Le sac à dos standard 0/1 exige que le poids de chaque élément soit indépendant des autres. Alors DP est un algorithme efficace vers la solution. Mais maintenant j'ai rencontré un problème similaire mais avec des extensions de ce problème, à savoir

le poids des nouveaux éléments dépend des éléments précédents déjà présents dans le système. le sac à dos.

Par exemple nous avons 5 articles a , b , c , d y e avec poids w_a , ..., w_e . point b y c ont une dépendance de poids.

Lorsque b est déjà dans le sac à dos, le poids de l'élément c sera plus petit que w_c car il peut partager un espace avec b c'est-à-dire weight(b&c) < w_b + w_c . Symétriquement, lorsque c est déjà dans le sac à dos, le poids de b sera plus petit que w_b .

Cette incertitude entraîne l'échec de l'algorithme DP original, puisqu'il dépend de l'exactitude des itérations précédentes qui peuvent ne pas être correctes maintenant. J'ai lu quelques articles sur le knapsack mais ils ont soit des dépendances soumises à profit ( problème de sac à dos quadratique ), ou ont un poids variable qui suit une distribution aléatoire ( problème de sac à dos stochastique ). J'ai également pris connaissance de la question précédente Variation de Knapsack 1/0 avec bords pondérés mais il n'y a qu'une réponse très générique disponible, et aucune réponse sur le nom de ce sac à dos.

Une solution existante :

J'ai également lu une solution approximative dans un document sur les optimisations des SGBD, où elles group the related items as one combined item for knapsack . Si l'on utilise cette technique dans notre exemple, les articles du sac à dos seront les suivants a , bc , d , e Il n'y a donc plus de dépendance entre deux de ces quatre éléments. Cependant, il est facile de construire un exemple qui n'obtient pas un résultat optimal, comme dans le cas où an item with "small weight and benefit" is grouped with another item with "large weight and benefit" . Dans cet exemple, le "petit" élément ne devrait pas être sélectionné en solution, mais est sélectionné avec le "grand" élément.

Question :

Existe-t-il des techniques de résolution efficaces permettant d'obtenir un résultat optimal, ou au moins une certaine garantie d'erreur ? Ou est-ce que je prends la mauvaise direction pour modéliser ce problème ?

Answer 1

Ne pourriez-vous pas avoir des articles a , b , c , bc , d y e ? Peut-être avec une contrainte selon laquelle b y bc ne peut pas être à la fois dans le sac à dos et de même avec c y bc ? D'après ce que j'ai compris, ce serait une solution correcte puisque toute solution qui a b y c peut être amélioré en substituant les deux par bc (par définition). Les contraintes d'appartenance devraient permettre de régler tous les autres cas.

Answer 2

Il s'agit d'un problème très intéressant sur lequel je travaille depuis un certain temps. La première chose à considérer est que le problème du sac à dos binaire avec des poids/valeurs d'éléments dépendants n'est pas du tout trivial. Vous pouvez envisager d'utiliser des réseaux bayésiens, des modèles de Markov et d'autres techniques similaires pour résoudre ce problème. Néanmoins, toute approche pratique de ce problème doit faire certaines hypothèses, soit sur le modèle d'optimisation, soit sur son entrée. Voici un exemple de formulation du problème du sac à dos binaire avec des éléments dépendant de la valeur. https://arxiv.org/pdf/1702.06662.pdf

Dans ce travail, les auteurs ont proposé de modéliser l'entrée (dépendances liées aux valeurs) à l'aide de graphes flous, puis d'utiliser le modèle de programmation linéaire en nombres entiers proposé pour résoudre le problème d'optimisation. Une version étendue de ce travail a été acceptée pour publication et sera bientôt disponible en ligne.

N'hésitez pas à me contacter si vous avez besoin de plus d'informations. Je peux également vous fournir le code source du modèle si nécessaire.

Answer 3

Finalement, j'ai réussi à résoudre le problème avec la méthode B&B proposée par @Holt. Voici les principaux paramètres :

(0) Avant d'exécuter l'algorithme B&B, regrouper tous les éléments en fonction de leur dépendance. Tous les éléments d'une partition ont une dépendance de poids avec tous les autres éléments du même groupe, mais pas avec les éléments des autres groupes.

Paramètres pour le B&B :

(1) Limite supérieure : supposer que l'élément actuel a la valeur minimum poids, c'est-à-dire supposer que toutes les dépendances existent.

(2) Limite inférieure : supposer que l'élément actuel a la valeur maximum poids, c'est-à-dire supposer que toutes les dépendances n'existent pas.

(3) Poids actuel : Calculer le poids actuel réel.

Tous les calculs ci-dessus peuvent être effectués en un temps linéaire en jouant avec les groupes que nous obtenons à l'étape 0. Spécifiquement, lors de l'obtention de ces poids, il suffit d'analyser uniquement les éléments du groupe actuel (le groupe dans lequel se trouve l'élément actuel) - les éléments des autres groupes n'ont aucune dépendance avec l'élément actuel, donc cela ne changera pas le poids réel de l'élément actuel.