NP komplett oder NP schwer Probleme im wirklichen Leben

17

Hat jemand Beispiele aus der Praxis, bei denen er regelmäßig NP-vollständige oder NP-schwierige Probleme (durch Heuristik oder Jagd nach einer suboptimalen Lösung oder was auch immer) in seinem Job löst? Ich weiß, dass sie beim Planen, Planen, VLSI-Design usw. auftreten, aber ich versuche, mir einen Eindruck von den wichtigsten Branchen zu verschaffen, in denen heute Programmierer oder Ingenieure beschäftigt sind, die dies regelmäßig tun. Wenn man zum Beispiel Fachwissen oder eine Bibliothek entwickeln würde, wo könnte man dies als Teil eines Programmierjobs verwenden, um eine kombinatorische Optimierung durchzuführen?

Irgendwelche persönlichen Accounts?

grosse Bandbreite
quelle
Was meinst du mit "regelmäßig"
Conrad Frix
@Conrad, nun, ich denke, es ist eine subjektive Idee. Ich würde sagen, dass mehr als 5-10% der Anstrengungen auf die Lösung von np-vollständigen oder np-harten Problemen gerichtet sind.
HighBandWidth
Ich glaube, dass KI-Programmierung in Spielen das Potenzial hat, NP-vollständig zu sein.
Michael K
Es gibt viele NP-schwierige Probleme (Planung und Planung mit begrenzten Ressourcen sind normalerweise NP-schwierig). Kombinatorische Optimierung ist jedoch der falsche Weg. 100 generieren können! Möglichst schnelle Kombinationen sind weitaus weniger sinnvoll, als domänenspezifische Heuristiken anwenden zu können.
David Thornley
@ David, ich wollte keine Kombinationen durch kombinatorische Optimierung generieren. Ich bezog mich auf eine Klasse von Problemen, wie k-SAT oder Traveling Salesman Problem usw.
HighBandWidth

Antworten:

8

Einige der Dinge, an die ich denken kann (die meisten davon habe ich mehr oder weniger mitgemacht):

  • Entwicklungsumgebungen für Sprachen und Compiler. Fragen wie: Erzeugt diese Grammatik eine mehrdeutige Sprache? (Dieses Problem ist tatsächlich unentscheidbar!)
  • Datenwiederherstellung. Wiederaufbau von teilweise verlorenen Datenpaketen oder Wiederherstellung fragmentierter Dateien. (Faktorielle Komplexität)
  • Software-Sicherheit. Bewertung aller möglichen Ausführungspfade durch eine Software, um festzustellen, ob ein beobachtetes Verhalten darauf zurückzuführen ist. (Halteproblem?)
  • Logistik. Optimieren der Verwendung von Transporten basierend auf den zu transportierenden Paketen, ihrer Größe und dem Ort, an dem sie abgelegt werden müssen. (Zumindest exponentiell)

Es gibt viele Standardbeispiele wie die Suche nach der kürzesten Route, die Planung von Krankenschwestern usw. Aber wenn Sie sich für die kombinatorische Optimierung interessieren, wissen Sie alles darüber :)

Deckard
quelle
Gibt es also Programmierer bei Logistikunternehmen, die sich tatsächlich mit der Lösung dieser Optimierungsprobleme befassen, oder werden die meisten dieser Vorgänge in der Regel einmal ausgeführt und nur für die meisten Unternehmen wiederholt? +1 für eine Reihe von Beispielen. Bist du / warst du an einem von diesen beteiligt?
HighBandWidth
Die ersten beiden Tools habe ich geschrieben, das dritte ist etwas, woran Kollegen arbeiten. Ich würde erwarten, dass große Logistikunternehmen aktiv in diesem Bereich forschen, da sie dadurch Millionen von Dollar einsparen können, wenn sie durch einen neuen Algorithmus ein paar Prozent mehr Leistung erzielen :)
Deckard
Ich habe für eine Handelsreiserolle interviewt. Die große Muttergesellschaft hatte einen Raum voller Doktoranden in der Hoffnung, ihre Streckenführung um ein paar Zehntel Prozent zu verbessern. Das wäre ihnen ein paar Millionen Dollar wert ... jeden Tag. Diese Orte existieren also. Routing und Terminplanung sind die zwei großen Dinge - stellen Sie sich vor, Sie haben 1000 Mitarbeiter und eine Fabrik, die zwei- oder dreischichtig arbeitet. Planen Sie jetzt, dass alle für den nächsten Monat arbeiten. Beachten Sie dabei diese 200 Regeln und die Vorlieben aller ...
9

Ich habe ein zeitlich begrenztes simuliertes Tempern verwendet, um ein Problem zu lösen, das einem reisenden Verkäufer bei der Herstellung von Touchpanels ähnelt. Jede Millisekunde, die wir von der Zykluszeit des Laserätzens jedes Panels an einsparen könnten, würde den Durchsatz, die Auslastung und damit die Rentabilität der Maschine erhöhen. Deshalb habe ich viel Mühe darauf verwendet, die Totzeit (nicht schreibende Pfade) zwischen schreibenden Pfaden (welche) zu minimieren offensichtlich nicht wegoptimierbar).

Ich habe einen zeitlich begrenzten Algorithmus verwendet, um die NP-Härte des Problems zu umgehen, da wir uns das Risiko nicht leisten konnten, dass die Optimierungsberechnung länger dauert als die Zeit, die durch den optimaleren Pfad eingespart wird. Während die Maschine das Panel von der Ladeposition in die Position bewegte, in der sich der Laserkopf über der nächsten Ecke befand, hatte ich die Zeit, einige Simulationen durchzuführen. Der Algorithmus lief fast nie innerhalb von ein paar hundert Millisekunden ab, lieferte jedoch fast immer einen besseren Schreibpfad als jedes der einfachen, nicht adaptiven Modelle, die wir zuvor verwendet hatten (z. B. Spiral- oder Schlangenpfade).

Mark Booth
quelle
2
Das ist cool. Aber ich dachte, jedes Panel würde das gleiche Muster haben, und Sie würden das Problem nur einmal lösen und nicht immer wieder für jedes Widget. Warum mussten Sie es jedes Mal lösen?
HighBandWidth
2
Das ideale Muster war für jedes Paneel das gleiche, aber die mechanische Ausrichtung des Paneels, die Position der vorherigen Schichten im Prozess und die Kachelnatur des Laserritzkopfs ergaben, dass für jedes Paneel ein dynamischer Satz von Untermustern berechnet werden musste individuell und dann optimiert. Es war ein interessantes Problem, daran zu arbeiten, insbesondere angesichts der zeitlichen Einschränkungen.
Mark Booth
7

Ich arbeite (gerade) an dem bioinformatischen Problem der Ausrichtung mehrerer lokaler DNA-Sequenzen. Der Punkt dabei ist, dass, wenn viele Sequenzen von Genen mit einer gemeinsamen Eigenschaft (ähnliches Expressionsprofil oder gleiche Transkriptionsfaktorbindung in einem ChIP-Chip-Experiment) an einem bestimmten Punkt stark übereinstimmen, Sie wahrscheinlich den Grund für ihre Gemeinsamkeit gefunden haben Eigentum. Andererseits interessieren mich eher die statistischen Aspekte des Problems. Obwohl es NP-schwer ist, verlieren Sie nicht viel, wenn Sie Heuristiken in der Praxis anwenden. Der interessante Teil des Problems, IMHO, ist das Problem des Signal-Rausch-Verhältnisses.

dsimcha
quelle
1
Verwenden Sie klassische kombinatorische / ai-Ansätze oder statistische. In gewisser Weise befasst sich das gesamte moderne maschinelle Lernen mit nlp, Clustering und np-vollständigen Problemen, wird jedoch in der Regel aus statistischer Sicht angegriffen. Es ist trotzdem interessant und relevant. Ist das in der Wissenschaft oder in der Industrie?
HighBandWidth
@highBandWidth: Mein Ansatz ist statistisch. Ich bin in der Wissenschaft. Der springende Punkt meiner Forschung ist, dass, wenn Sie die statistischen Probleme ignorieren und sich nur auf das kombinatorische Problem konzentrieren, Bad Things Happen.
Dsimcha
3

Ich weiß nicht genau, was NP complete / hard bedeutet, aber ich denke, Supply Autoplanning ist so etwas.

Sie haben einen Bedarfsplan von 90 Tagen für 100 Produkt-SKUs: Bier! Die 100-Produkt-SKU stammt von:

  • Es gibt 10-15 Arten von roh gebrautem Grundstoff der Stufe 1, sie werden in Tausend-Liter-Großdosen gebraut und es dauert einen Tag.
  • Nach dem Brauen müssen einige Materialien hinzugefügt werden (Sauerteig?) und es muss eine Pause von 10 bis 15 Tagen eingelegt werden. Dann erhalten Sie 15 bis 20 Arten von Level-2-Material.
  • Schließlich, wenn es fertig ist, sollten einige Materialien hinzugefügt werden, es ist das Level-3-Zeug, genannt trinkbares Bier, es gibt CC. 30 Biersorten;
  • Das Bier kann in 3 dl, 5 dl Flaschen abgefüllt werden, manchmal wird es mit einem speziellen Halsschmuck versehen (Stufe 4), dann kann es als 5x4-Box im 6er-Pack (Stufe 5) verpackt werden.

Es gibt Maschinenlinien für jeden Vorgang: vom Brauen bis zur Verpackung. Die Maschinen können mehr Operationen ausführen, beispielsweise können einige Verpackungsmaschinen 6er- und 3er-Packungen herstellen, andere dagegen nur 6er-Packungen. Es gibt Einschränkungen, z. B. Geschwindigkeit, oder der große Brühkessel ist für das Brühen von min. 6000, max. 8000 l Bier (aber wenn die Biersorte leicht ist, dann sind die min. 5000 l und die max. 7000 l). Und so weiter, auf jeder Ebene.

Die Aufgabe: Wie ich bereits erwähnt habe, gibt es einen Nachfrageplan für die 100 Arten von Level-5 (abgefülltes, verpacktes Zeug). Erstellen Sie einen optimalen Fertigungsplan für alle 5 Ebenen, alle Maschinen. Maschinenschalter minimieren (z. B. Abfüllen von .5, .5, .5, .3, .3 ist besser als .3, .5, .3, .5, .3, .5, .5, es gibt weniger swithc, weniger Totzeit für Abfüllmaschinen). Priorisierung durch den Kunden: Einige Kunden müssen das Bier nur versenden, wenn mehr als 50% der Verfallszeit verbleiben. Usw.

Entdecken Sie Engpässe (eh), machen Sie alternative Pläne, indem Sie nicht vorhandene Maschinen zu diesen Punkten hinzufügen. Dann kann das beste virtuelle Szenario verwendet werden, um den Kauf einer neuen Maschine vorzuschlagen.

Ist es schwer genug, oder soll ich dir sagen, wie eine Textilfabrik funktioniert?

(Persönliche Bemerkung: Das Internet, die Bank und die Logistik sind herausfordernde Bereiche, aber sie sind Babyspielzeug im Vergleich zu Herstellungsproblemen.)

Haftungsausschluss: Zahlen sind aus Sicherheitsgründen verzerrt, Größenordnung ist real.

ern0
quelle
Arbeiten Sie an so etwas oder an einem Tool, um solche Probleme für Ihren Arbeitgeber zu lösen?
HighBandWidth
1
Nun, die Fertigung wird logistisch groß geschrieben. Auf jeden Fall schwieriger als diesbezüglich zu finanzieren. Zumindest geht es aber um definierte Probleme, nicht um Zufallsgleichungen und lose definierte Operationsreihenfolgen!
Michael K
1
Jede Art von Planungsalgorithmus mit bestmöglicher Ressourcenanpassung entspricht wahrscheinlich dem Rucksackproblem , das NP-vollständig ist.
Scott Whitlock
Ein Freund von mir hat vor Jahren ein DP / SP-System in Excel + VB erstellt. Es enthält keine automatische Planung, die App ist zu fett für Excel. Also haben wir gerade ein auf MySQL / PHP / AJAX basierendes kollaboratives erweiterbares Spreadsheet-Framework (siehe: dataflow - aka. Flow-based programming - approach) (ich) erstellt und die Biz-Logik aus der XLS-Version übernommen (Freund) . Wir haben auch Autoplaning implementiert (Freund). Es war eine verrückte Idee, eine Tabelle zu schreiben, aber es funktioniert. Das Beste daran: XLS-> SQL-Switch ist etwas wundervoll! Wir können alles mit den Daten machen (zB Autoplan), mit jedem Werkzeug / jeder Plattform (PHP, Java, was wir wollen).
ern0
@ ern0, NP-complete / NP-hard bezieht sich im Grunde genommen darauf, wie wenig Abkürzungen Sie annehmen können, um in der Lage zu sein, alle Möglichkeiten einzeln auszuprobieren . Theoretiker geben sich viel Mühe, um Abkürzungen zu finden. Wenn wir beispielsweise wissen, dass der Pfad ABC immer länger als AC ist, können wir ihn schneller machen und nachweisen , dass er innerhalb von 50% des optimalen Werts liegt. Etc.