Zusammenfassung
Das Toolkit glpk enthält Methoden der gemischt-ganzzahligen linearen Program-
mierung (MILP). Diese Methoden lassen sich zur Lösung von Capital Budgeting
Problemen (CBP) nutzen. Da glpk weder multithreaded fähig ist noch eine Vertei-
lung auf mehrere Rechner implementiert ist, kann es sein Potential auf heutigen
Computern und in vernetzten IT-Systemen nicht voll entfalten. Um bei der Lösung
von CBP mit kommerziellen Too lkits wie CPLEX und Guro bi mithalten zu kön-
nen, haben wir mit dem Verteilungs-Framework Apache thrift und der C-API von
glpk eine Möglichkeit geschaffen, um CBP auf beliebig viele Kerne und Rechner zu
verteilen. Durch Last-Balancierung und Berücksichtigung der Methoden der MILP
bei der Verteilung war es uns sogar möglich, die Verarbeitung um mehr als das
Vielfache der genutzten Prozessor-Kerne zu beschleunigen. Der „Branch-and-Cut“-
Algorithmus von glpk, mit dem primär gearbeitet wird, liefert bei einer ausgewogenen
Unterteilung in Teilprobleme, paralleler Verarbeitung und regelmäßigem Austausch
der bisher besten Lösung unter den Teilproblemen deutlich schneller eine Lösung,
als eine sequenzielle Verarbeitung der Teilprobleme.
Abstract
The toolkit glpk supports methods for mixed integer linear programming (MILP).
These methods solve Capital Budgeting Problems (CBP). Unfortunately, glpk does
not support any multithreading and there is no feature to distribute problems via
network connections. Today, this is a pitiable sight, because modern computer
systems are coupled by networks and support multi threading. To solve CBP with
glpk like commercial toolkits (CPLEX or Gurobi) we create a distributed system
with Apache thrift and t he C-API of glpk. Now, it is possible to use as many cores
in a network as you want. With a focus o n the MILP methods we implement a
load balancing and speed up the solving process in a multiplicative way. Sometimes
we have super-linear speedup with a small set of hardware. glpk primary uses the
"Branch-and-Cut" algorithm. With an intelligent splitting of problems, parallel
computing and distributing the actual best solution to all running processes we
solve CBP much faster than a sequential processing can do.
