Solving eine Art Tornister prob mit mehreren Rucksäcken und Zwängen

Question

Ich habe folgendes Problem, das ich mit den Excel-Solver oder jedem anderen Werkzeug lösen möchte (jeder Vorschlag ist willkommen), aber ich mochte nicht, Code zu schreiben.

Ich habe mehrere Artikel (ca. 40) in mehrere Rucksack setzen (etwa 5). Jeder Artikel hat ein anderes Gewicht, aber jeder Rucksack hat den gleichen Platz.

Die Summe des Gewichts der Gegenstände ist viel geringer als die Kapazität der Rucksäcke.

Was ich tun müssen, um die Elemente im Rucksack zuzuteilen alle mit mehr oder weniger dem gleichen Gewicht zu füllen. Mit anderen Worten, die Varianz zu reduzieren.

Es gibt eine Einschränkung: einige Elemente können nicht zusammen gehen. Ich habe eine Liste (oder Adjazenzmatrix) der Elemente, die zusammenpassen können oder nicht.

Natürlich einmal ein Artikel ist in einem Rucksack nicht in einem zweiten gehen kann (nur ein Punkt für jeden König von Elementen ist).

Ich versuche, dies mit dem Excel-Löser zu lösen, aber alle 3 der Algorithmen sagen, dass sie keine Lösungen finden können, aber manuell kann ich sie finden, also denke ich, dass ich nicht richtig konfiguriere.

Auf jeden Fall in Excel configurate nur einen Teil des Problems in Bezug auf Gewichte, ich könnte, aber ich kann nicht Teil des Problems in Bezug auf die Unvereinbarkeit zwischen dem einzelnen Posten eingerichtet.

Vielen Dank für Ihre Hilfe

Answer 1

Das ist mehr multiprocessor scheduling mit Nebenbedingungen als Tornister.

Sie können eine naive Formulierung so versuchen. Für jeden Gegenstand gibt es [Anzahl der Rucksäcke] 0-1 Variablen, die anzeigen, in welchem ​​Rucksack sich der Gegenstand befindet, und eine Einschränkung, die diese Variablen auf 1 summieren. Das Ziel ist es, das maximale Gesamtgewicht in einem Rucksack zu minimieren. Für jedes Paar von Artikeln, die nicht zusammenpassen können, gibt es [Anzahl der Rucksäcke], die Summe der entsprechenden Indikatorvariablen ist kleiner oder gleich 1.

Hier ist ein Beispiel mit zwei Rucksäcken (A und B), drei Elemente (x, Gewicht 3; y, Gewicht 1; und z, Gewicht 4), und ein Konflikt (x kann nicht mit y sein).

minimize C 
over 0-1 variables Ax, Ay, Az, Bx, By, Bz and real variable C 
subject to 
C >= 3*Ax + 1*Ay + 4*Az # load in A 
C >= 3*Bx + 1*By + 4*Bz # load in B 
Ax + Bx = 1 # one placement of x 
Ay + By = 1 # one placement of y 
Az + Bz = 1 # one placement of z 
Ax + Ay <= 1 # conflict between x and y in A 
Bx + By <= 1 # conflict between x and y in B 

Diese Formulierung ist nicht optimal, weil es keine Symmetrie bricht - im Wesentlichen vor, der Suchbaum des LP-Löser um einen Faktor gleich die Anzahl von Permutationen von Rucksäcken dupliziert. Dies ist nur 5! = 120 im schlimmsten Fall, also könnte es in Ordnung sein. Der Weg zu gehen ist wahrscheinlich column generation mit einem Master-Problem, das sich auf genau die Gegenstände mit der richtigen Anzahl von Rucksäcken und ein Teilproblem, das auf die Verpackung eines Rucksacks vorbehaltlich Beschränkungen, aber das ist außerhalb des Umfangs für Excel.