Problèmes NP complets ou NP difficiles dans la vie réelle

17

Quelqu'un a-t-il des exemples concrets où il résout régulièrement des problèmes NP complets ou NP difficiles (par heuristique, ou à la recherche d'une solution sous-optimale ou autre) dans son travail? Je sais qu'ils se produisent dans la planification, la planification, la conception VLSI, etc., mais j'essaie de me faire une idée des principales industries qui emploient aujourd'hui des programmeurs ou des ingénieurs qui le font régulièrement. Si l'on devait développer une expertise ou une bibliothèque, par exemple, l'optimisation combinatoire, où pourrait-on l'utiliser dans le cadre d'un travail de programmation?

Des comptes personnels?

algorithms optimization bande passante élevée
la source
Qu'entendez-vous par "régulièrement"
Conrad Frix
@Conrad, eh bien, je suppose que c'est une idée subjective. Je dirais que plus de 5 à 10% de l'effort est axé sur la résolution de problèmes np-complets ou np-difficiles.
highBandWidth le
La programmation de l'IA dans les jeux a le potentiel d'être NP-complète, je crois.
Michael K
Il y a beaucoup de problèmes NP-difficiles (la planification et la planification avec des ressources limitées sont généralement NP-difficiles). Cependant, l'optimisation combinatoire n'est pas la bonne solution. Pouvoir en générer 100! des combinaisons aussi rapides que possible est beaucoup moins utile que de pouvoir appliquer des heuristiques spécifiques à un domaine.
David Thornley
@ David, je ne voulais pas générer des combinaisons par optimisation combinatoire. Je faisais allusion à une classe de problèmes, comme k-SAT ou Travelling Salesman Problem etc.
highBandWidth

Réponses:

8

Certaines des choses auxquelles je peux penser (la plupart de celles-ci auxquelles j'ai participé plus ou moins):

  • Environnements de développement pour les langages et les compilateurs. Des questions telles que: cette grammaire génère-t-elle un langage ambigu? (Ce problème est en fait indécidable!)
  • Récupération de données. Réassemblage de paquets de données partiellement perdus ou récupération de fichiers fragmentés. (Complexité factorielle)
  • Sécurité des logiciels. Évaluation de tous les chemins d'exécution possibles à travers un logiciel pour déterminer si un comportement observé peut lui être attribué. (Arrêter le problème?)
  • Logistique. Optimiser l'utilisation des transports basés sur les paquets à transporter, leur taille et leur destination. (Au moins exponentiel)

Il existe de nombreux exemples standard tels que la recherche de l'itinéraire le plus court, la planification des infirmières, etc. mais si vous êtes dans l'optimisation combinatoire, vous en savez tout :)

Deckard
la source
Y a-t-il donc des programmeurs employés par des sociétés de logistique qui se consacrent réellement à résoudre ces problèmes d'optimisation, ou la plupart de ces opérations sont-elles généralement résolues une fois et sont simplement répétées pour la plupart des entreprises? +1 pour un certain nombre d'exemples. Êtes-vous / avez-vous participé à l'une de ces activités?
highBandWidth le
Les deux premiers outils pour lesquels j'ai écrit, le troisième est quelque chose sur lequel les collègues travaillent. Je m'attendrais à ce que les grandes entreprises de logistique fassent activement des recherches dans ce domaine car cela peut leur faire économiser des millions de dollars si elles atteignent quelques pour cent de performances supplémentaires grâce à un nouvel algorithme :)
Deckard
J'ai interviewé pour un rôle de vendeur itinérant. La grande société mère disposait d'une salle remplie de docteurs dans l'esclavage dans l'espoir d'obtenir quelques dixièmes de pour cent d'amélioration de leur routage. Ce qui leur rapporterait quelques millions de dollars ... chaque jour. Ces endroits existent donc. Le routage et la planification sont les deux gros problèmes - imaginez que vous avez 1000 personnes et une usine qui gère deux ou trois équipes. Maintenant, programmez tout le monde à travailler pour le mois prochain en gardant à l'esprit ces 200 règles et préférences de tous ...
9

J'ai utilisé un recuit simulé à contrainte de temps pour résoudre un problème de type saleman itinérant dans la fabrication d'écrans tactiles. Chaque milliseconde que nous pourrions raser du temps de cycle de la gravure au laser de chaque panneau augmenterait le débit, l'utilisation et donc la rentabilité de la machine, donc j'ai mis beaucoup d'efforts pour minimiser le temps mort (chemins non marquants) entre les chemins marquants (qui ne pouvait évidemment pas être optimisé).

J'ai utilisé un algorithme limité dans le temps pour contourner la dureté NP du problème, car nous ne pouvions pas nous permettre que le calcul d'optimisation prenne plus de temps que le temps économisé par le chemin le plus optimal. Pendant que la machine déplaçait le panneau de la position de chargement à la position où la tête laser se trouvait dans le coin le plus proche, j'ai eu le temps d'effectuer quelques simulations. L'algorithme n'a presque jamais fonctionné dans les quelques centaines de millisecondes du mouvement, mais il a presque toujours renvoyé un meilleur chemin de scribe que n'importe lequel des modèles simples et non adaptatifs que nous avions toujours utilisés auparavant (tels que les chemins en spirale ou en serpent).

Mark Booth
la source
2
C'est super. Mais je pensais que chaque panneau aurait le même modèle, et vous ne feriez que résoudre le problème une fois plutôt que plusieurs fois pour chaque widget. Pourquoi avez-vous dû le résoudre à chaque fois?
highBandWidth
2
Le motif idéal était le même pour chaque panneau, mais l'alignement mécanique du panneau, la position des couches précédentes dans le processus et la nature carrelée de la tête de traçage laser signifiaient qu'un ensemble dynamique de sous-motifs devait être calculé pour chaque panneau. individuellement puis optmised. C'était un problème intéressant sur lequel travailler, surtout compte tenu des contraintes de temps.
Mark Booth
7

Je travaille (en ce moment, en fait) sur le problème bioinformatique de l'alignement de plusieurs séquences d'ADN local. Le point de cela est que si beaucoup de séquences de gènes ayant une propriété commune (profil d'expression similaire ou même liaison de facteur de transcription dans une expérience sur puce ChIP) s'alignent fortement à un moment donné, alors vous avez probablement trouvé la raison de leur commune propriété. Là encore, je suis plus intéressé par les aspects statistiques du problème. Même si c'est NP-difficile, vous ne perdez pas grand-chose en utilisant l'heuristique dans la pratique. La partie intéressante du problème, à mon humble avis, est un problème de rapport signal / bruit.

dsimcha
la source
1
utilisez-vous des approches combinatoires / ai classiques ou statistiques? D'une certaine manière, tout le nlp moderne, le clustering, l'apprentissage automatique traitent de problèmes np-complets, mais sont généralement attaqués d'un point de vue statistique. C'est intéressant et pertinent quand même. Est-ce dans le milieu universitaire ou industriel?
highBandWidth
@highBandWidth: Mon approche est statistique. Je suis dans le milieu universitaire. L'intérêt de la recherche que je fais est que si vous ignorez les problèmes statistiques et que vous vous concentrez uniquement sur le problème combinatoire, Bad Things Happen.
dsimcha
3

Je ne sais pas vraiment ce que signifie NP complete / hard, mais je pense que la planification automatique de l'offre est une sorte de cela.

Vous avez un plan de demande de 90 jours pour 100 références de produit: bière! La référence 100 produits provient de:

  • il y a 10 à 15 sortes de matières brutes de base de niveau 1, elles sont brassées dans de grandes boîtes de mille litres, et cela prend une journée;
  • après le brassage, certains matériaux doivent être ajoutés (levain?), et il doit être au repos pendant 10-15 jours, puis vous avez 15-20 sortes de trucs de niveau 2;
  • enfin, quand c'est prêt, il faut ajouter du matériel, c'est le truc de niveau 3, appelé bière buvable, il y a cc. 30 sortes de bières;
  • la bière peut être mise en bouteille en 3 dl, 5 dl, parfois elle reçoit un collier spécial (niveau 4), puis elle peut être emballée en boîte de 5x4, pack de 6 (niveau 5).

Il existe des "lignes" de machines pour chaque opération: du brassage à l'emballage. Les machines peuvent effectuer plus d'opérations, par exemple, certaines machines d'emballage peuvent fabriquer des paquets de 6 et 3, mais d'autres ne peuvent en faire que 6. Il y a des contraintes, par exemple la vitesse, ou la grande bouilloire de brassage est pour le brassage min. 6000, max, 8000 l de bière (mais si le type de bière est léger, le minimum est de 5000 l et le maximum est de 7000 l). Et ainsi de suite, à tous les niveaux.

La tâche: comme je l'ai mentionné, il existe un plan de demande pour les 100 types de niveau 5 (les trucs en bouteille et emballés). Faites un plan de fabrication optimal pour tous les 5 niveaux, toutes les machines. Minimiser les commutateurs de la machine (par exemple, la mise en bouteille 0,5, 0,5, 0,5, 0,3, 0,3, 0,3 est meilleure que 0,3, 0,5, 0,3, 0,5, 0,5, 0,5, il y a moins de swithc, moins de temps mort pour les machines d'embouteillage). Prioriser par client: certains clients exigent d'expédier la bière uniquement avec plus de 50% de délai d'expiration. Etc.

Découvrez les goulots d'étranglement (hein), faites des plans alternatifs en ajoutant des machines inexistantes à ces points, puis le meilleur scénario virtuel peut être utilisé pour suggérer d'acheter de nouvelles machines.

Est-ce assez difficile, ou devrais-je vous dire comment fonctionne une usine textile ?

(Remarque personnelle: le Web, la banque et la logistique sont des domaines difficiles, mais ce sont des jouets pour bébés par rapport aux problèmes de fabrication.)

Avertissement: les chiffres sont déformés pour des raisons de sécurité, l'ordre de grandeur est réel.

ern0
la source
Travaillez-vous sur quelque chose comme ça ou un outil pour résoudre des trucs comme ça pour votre employeur?
highBandWidth
1
Eh bien, la fabrication est la logistique dans son ensemble. Certainement plus difficile que la finance à cet égard. Mais au moins, il traite de problèmes définis, pas d'équations aléatoires et d'ordres de fonctionnement définis de manière lâche!
Michael K
1
Tout type d'algorithme de planification avec le meilleur ajustement des ressources est probablement équivalent au problème du sac à dos , qui est NP-complet.
Scott Whitlock
Il y a quelques années, un de mes amis a créé un système DP / SP dans Excel + VB. Il ne contient pas de planification automatique, l'application est trop grasse pour Excel. Donc, nous venons de créer un cadre de feuille de calcul collaboratif extensible basé sur MySQL / PHP / AJAX (voir: flux de données - alias. Programmation basée sur les flux - approche) (moi), et adopté la logique biz de la version XLS (ami) . Nous avons également implémenté la planification automatique (ami). C'était une idée folle d'écrire une feuille de calcul, mais ça marche. La meilleure partie: XLS-> le commutateur SQL est quelque peu merveilleux! Nous pouvons tout faire avec les données (par exemple, autoplan), en utilisant n'importe quel outil / plateforme (PHP, Java, ce que nous souhaitons).
ern0
@ ern0, NP-complete / NP-hard fait référence au peu de raccourcis que vous pouvez même supposer pouvoir prendre au lieu d'essayer toutes les possibilités une par une. Les théoriciens passent beaucoup d'efforts à trouver des raccourcis qui, par exemple, disent que si nous savons que le chemin ABC sera toujours plus long que AC directement, nous pouvons le rendre plus rapide et prouver qu'il se trouve à moins de 50% de la valeur optimale. Etc.