Dienstag, 2. September 2014

(Lineare) Optimierung mit C# und Gurobi

Den heutigen Post möchte ich dem Optimierungsprogramm Gurobi widmen, mit welchem Optimierungsprobleme gelöst werden können, speziell lineare und quadratische Programme.
Gurobi ist an sich kostenpflichtig, Angehörige einer akademischen Einrichtung (wie Studenten einer Universität) können sich allerdings eine kostenlose Lizenz besorgen, für alle anderen gibt es Trial Lizenzen. Für viele verschiedenen Programmiersprachen, wie auch die .Net Sprachen, werden Schnittstellen angeboten.
Zuerst muss Gurobi heruntergeladen werden, welches hier gemacht werden kann. Achtung: Für .Net scheint wohl die 64 Bit Version nicht zu funktionieren, die 32 Bit Version läuft aber auf allen Systemen - siehe nächster Post.
Danach ist eine Gurobi Lizenz zu erwerben. Hierfür muss man auf der Gurobi Website unter Downloads - Licenses die entsprechende Lizenz auswählen und auf "Request License" klicken. Auf der sich öffnenden Seite befindet ein Befehl in der Form "grbgetkey e7300a11-...", welcher mittels Start - Ausführen ausgeführt werden muss. Daraufhin wird der Gurobi Server kontaktiert, die Lizenz erworben und auf dem Computer gespeichert. Nun ist der Solver einsatzbereit.
Ich möchte nun ein Beispiel zur Benutzung dieses geben und werde hierfür das gleiche Beispiel wie im Gurobi Quickstart Guide verwenden.
Ziel ist die Optimierung des folgenden Modells:

Maximiere x + y + 2z
s.t. x + 2y + 3z <= 4
x + y >= 1
x, y ∈ {0, 1}

Um Gurobi in .Net benutzen zu können, müssen wir zuerst einen Verweis auf die Bibliothek Gurobi56.NET.dll zu unserem Projekt hinzufügen. Bei mir befindet sich diese Datei im Verzeichnis C:\gurobi563\win32\bin.
Der C# Code für eine Konsolenanwendung, welcher obiges Beispiel modelliert, lautet dann:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

using Gurobi;

namespace GurobiConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                GRBEnv env = new GRBEnv("mip1.log");
                GRBModel model = new GRBModel(env);

                // Create variables

                GRBVar x = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "x");
                GRBVar y = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "y");
                GRBVar z = model.AddVar(0.0, 1.0, 0.0, GRB.BINARY, "z");

                // Integrate new variables

                model.Update();

                // Set objective: maximize x + y + 2 z

                model.SetObjective(x + y + 2 * z, GRB.MAXIMIZE);

                // Add constraint: x + 2 y + 3 z <= 4

                model.AddConstr(x + 2 * y + 3 * z <= 4.0, "c0");

                // Add constraint: x + y >= 1

                model.AddConstr(x + y >= 1.0, "c1");

                // Optimize model

                model.Optimize();

                Console.WriteLine(x.Get(GRB.StringAttr.VarName)
                                   + " " + x.Get(GRB.DoubleAttr.X));
                Console.WriteLine(y.Get(GRB.StringAttr.VarName)
                                   + " " + y.Get(GRB.DoubleAttr.X));
                Console.WriteLine(z.Get(GRB.StringAttr.VarName)
                                   + " " + z.Get(GRB.DoubleAttr.X));

                Console.WriteLine("Obj: " + model.Get(GRB.DoubleAttr.ObjVal));

                // Dispose of model and env

                model.Dispose();
                env.Dispose();

                string Dummy = Console.ReadLine();

            }
            catch (GRBException ex)
            {
                Console.WriteLine("Error code: " + ex.ErrorCode + ". " + ex.Message);
            }
        }
    }
}

Gehen wir diesen Schritt für Schritt durch. Anfangs erstellen wir eine Gurobi Umgebung und ein Modell, als Parameter geben wir die Log Datei, in welche Meldungen des Programms geschrieben werden. Dann legen wir die 3 benötigten Variablen x, y und z an. Die ersten beiden Parameter sind Unter- und Obergrenze für diese, der dritte Wert gibt den Koeffizient in der Zielfunktion an. Dieser ist hier 0, da wir diese später definieren. GRB.BINARY gibt an, dass die Variable binär ist. Andere mögliche Werte sind GRB.INTEGER (ganzzahlig) und GRB.CONTINOUS (reell). Die darauf folgenden Befehle sollten selbsterklärend sein, mittels SetObjective() setzen wir die Zielfunktion, mittels AddConstr() definieren wir Nebenbedingungen. Die ermittelte Lösung wird schließlich in der Konsole ausgegeben.
Hat das LP keine Lösung oder ist unbeschränkt, wird ein Fehler beim Abfragen der Variablenwerte geworfen, nämlich "Error at GRBVar.Get".

Keine Kommentare:

Kommentar veröffentlichen