Download

Dokumentation

Dieses Programm ist eine Weiterentwicklung meines Codes aus der Bachelorarbeit. Die OR-Instanzen von Chu-And-Beasley sind damit weiterhin lösbar - mal schneller und mal auch leider langsamer. Primär tut dieser Code bei binären Rucksack Problemen die dem Capital Budgeting Problemen entsprechen (BIP).

Das Logging ist sehr umfangreich und stellt immer nur eine Momentaufnahme dar.

Die Config Datei

So könnte eine farmer.cfg Datei aussehen:

2 
5000 
6 
1.05 
20.6 
50.0 
500 
3000 
127.0.0.1 61001 
127.0.0.1 61002 
127.0.0.1 61003 
127.0.0.1 61004 

Die erste Zeile gibt an, wie viele Worker, die am Dateiende aufgelistet sind, genommen werden sollen. In diesem Beispiel sind es zwei: der Worker mit Port 61001 und der mit 61002.

Die zweite Zeile gibt in ms an, wie lange jeder Job auf einem Worker laufen darf. Die Zeit für das Lösen des vorangestellten Simplex-Verfahrens ist hier nicht enthalten.

Die dritte Zeile gibt an, bis zu wie viele Variablen bzw. Projekte vorbelegt werden sollen, sollte das Zeitlimit auf dem Worker überschritten werden.

Die vierte Zeile sollte man besser auf 1.0 stellen. Dieser Wert ist ein Faktor, mit dem bei jeder Überschreitung des Zeitlimits das Zeitlimit verändert wird. Streng genommen kann man so das Limit mit einem Wert kleiner 1 auch herunter setzten.

Die beiden nächsten Werte sind Prozentangaben, ab welcher Vorbelegung die Jobs via Tiefensuche abgearbeitet werden sollen bzw. ab wann die Zeitbeschränkung aufgehoben wird und ein Presolver eingesetzt werden darf.

Die Zeile mit der 500 bedeutet, dass im 500ms Tackt der Farmer die Worker nach neuen, bisher besten Lösungen abfragt und seine bekannte bisher beste Lösung dem Worker mitteilt. Dieser Update- oder Sync-Intervall erfagt auch die Speichernutzung des Workers, um dies mit loggen zu können.

Die 3000 bedeutet, dass alle 3 Sekunden eine Logginginfo auf stderr ausgegeben wird. Erst am ende gibt der Farmer das Ergebnis auf stdout aus. Dieser Intervall wird auch für das Informieren des HTML-Client genommen. In dem HTML-Client ist via Polling 1000ms eingestellt, um die Logging-Infos ab zu fragen. Auch hier werden dann trotzdem nur die Infos, die alle 3s aufgezeichnet werden, übertragen.

GANZ WICHTIG: hinter jeder Zeile sollte ein LEERFELD sein! Manche Editoren neigen dazu, dieses Leerfeld zu entfernen. Ohne dieses Leerfeld hatte ich Probleme.

Beispiel: Aufruf der Worker

Starten von 8 Workern, mit je 800MB, die diese zum allokieren von Speicher nutzen dürfen:

./worker 61001 800 &
./worker 61002 800 &
./worker 61003 800 &
./worker 61004 800 &

Beispiel: Aufruf des Farmers

./farmer Instances/OR10x100-0.50_4.dat.cplex farmer.cfg

Kompilieren

make idl
make

Aufräumen

make clean-idl
make clean

Veränderungen gegenüber Bachelorarbeit

• die Dateien der Problem-Instanzen werden nur noch im cplex oder den beiden MIPLIB-Dateiformaten eingelesen
• Die Worker, und nicht mehr der Farmer, erzeugen die neuen Jobs
• Das retten einer bisher besten Schranke nach einer Zeitüberschreitung bei einem Worker wurde entfernt. Es war so langsam, dass es keine Geschwindigkeitsvorteile hatte.
• Es werden je Vorbelegung die Jobs mit höherer Simplexlösung bevorzugt
• Code vereinfacht
  • Bounded Buffer durch etwas schlankeres ersetzt
  • Worker nicht mehr als Daemon startbar
  • kein Wrapper für Windows und Mac mehr drin (prinzipiell ist Code aber weiterhin leicht portierbar)
  • kein static linking mehr drin
• bei Workern ist beim Starten in MB ein limit an zu geben, wann dieser abbrechen soll/darf
• Logging des Speicherverbrauchs der Worker (in %)
• Config-Datei für Farmer
• es kann in Prozent angegeben werden, ab wie viel Vorbelegung keine Breitensuche, sondern eine Tiefensuche gestartet werden soll
• mit einer Prozentangabe bzgl. der Vorbelegung kann man das Zeitlimit der worker auf unendlich stellen. In dem Fall setzt auch erst der Presolver ein.
• Alles wurde von INT und BOOL auf DOUBLE gestellt, um möglichst nahe an die Funktionen von glpk zu kommen, die Double Werte erwarten.
• Optimierung der Daten bzgl. dünn besetzter Matrizen
• Vorbelegung geschieht nicht mehr durch Binäres Array, sondern es werden nicht-ganzzahlen Werte der Simplex-Lösung auf- bzw. abgerundet
• Projekte werden nicht mehr nach Profitdichte sortiert
• Datenstruktur bei thrift-Übertragung für glpk verallgemeinert
• farmer ist mit einem thrift-Server bestückt, der Logging-Infos an einen html-Client sendet

Issues

• IP und MIP scheint noch nicht korrekt verarbeitet zu werden
• Mit Minimierungsproblemen noch nicht hinreichend getestet
• zu langsam bzw. nicht für alle MIPLIB Probleme brauchbar
• kein dynamisches bzw. inteligentes Job Balancing

Licence

Copyright (c) 2016, Jochen Peters (Krefeld)
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.