Ich schreibe etwas Code in C++, und es stellt sich heraus, dass ich ein Optimierungsproblem lösen muss, das mit mVariablen und nlinearen Einschränkungen formuliert werden kann (dh Einschränkung ihat die Form \sum_j a_{i,j} x_j >= b_i; obwohl Sie nicht wissen, was lineare Programmierung ist, können Sie diese Frage wahrscheinlich nicht beantworten).
Es kommt vor, dass die Anzahl der Variablen ziemlich klein ist - normalerweise weniger als 10; aber die Anzahl der Einschränkungen ist viel höher.
Ich brauche die Lösung, um schnell zu sein - zumindest in Erwartung (hoffentlich nicht mehr als ein Durchgang über die meisten Einschränkungen) - und ich bin bereit, dafür den Abstand zum Optimum zu bezahlen.
Gibt es eine Bibliothek für diese „Nische“ der linearen Programmierung? Wenn nicht, was wären im Allgemeinen schnelle lineare Programmierbibliotheken?
Anforderungen:
Gewünschte Eigenschaften:
Ich schaue mir den CLP von COIN-OR an . Es ist ein C++ FOSS LP-Solver; darüber hinaus kann ich jetzt noch nicht viel sagen.
Hier sind zwei Aspekte zu diskutieren:
Der Algorithmus bestimmt die Laufzeit und Genauigkeit der Methode. Wenn Sie bereit sind, Genauigkeit zu opfern, würden Sie eine Methode wie IP über Simplex wählen (dies ist ein Beispiel zur Veranschaulichung).
Was die Implementierung betrifft - da diese Art von Problemen normalerweise durch Matrixoperationen gelöst werden, können Sie die klassische Go-to-Bibliothek für diese Dinge verwenden - BLAS . Eine weitere Möglichkeit ist das GLPK -Paket. Wenn Sie eine Demonstration der Verwendung des letzteren wünschen, werfen Sie einen Blick auf den Quellcode von Octave . Vielleicht ist auch die Dokumentation von Octave zu diesem Thema hilfreich.
Übrigens, eine andere Möglichkeit, den Kompromiss einzugehen, besteht unabhängig von der spezifischen Technik darin, die Berechnung in einem Datentyp mit reduzierter Genauigkeit durchzuführen, z . B. float32und nicht float64.
Geoffrey de Smet