Episode
ompr: eine alternative Methode zum Modellieren gemischter ganzzahliger linearer Programme
durch Dirk Schumacher
useR!2017: ompr: eine alternative Möglichkeit zum Modellieren von Gemischten-...
Schlüsselwörter: Ganzzahlprogrammierung, lineare Programmierung, Modellierung, Optimierung
Webseiten:https://github.com/dirkschumacher/ompr
Viele Probleme bei der Optimierung der realen Welt, wie z. B. das beliebte Problem des Reisenden, können als gemischt-ganzzahliges lineares Programm (MILP) formuliert werden. Das Ziel von MILP ist es, eine lineare Zielfunktion zu optimieren, die einer Reihe linearer Einschränkungen unterliegt. In den letzten Jahrzehnten wurden spezialisierte Open-Source- und kommerzielle Solver entwickelt, z. B. das GNU Linear Programming Kit (GLPK), das diese Art von Problemen effizient lösen kann.
In R sind Schnittstellen zu diesen Solvern hauptsächlich matrixorientiert. Beim Lösen eines MILP in R müssen Sie daher zuerst Ihr tatsächliches Modell entwickeln und dann in Code übersetzen, der eine Matrix und Vektoren erstellt, bevor Sie es an einen Solver übergeben. Insbesondere für komplexere Modelle ist der R-Code möglicherweise eher schwer zu entwickeln und ohne zusätzliche Dokumentation zu begründen.
ompr ist eine domänenspezifische Sprache, mit der Sie MILPs deklarativ mithilfe von Funktionen wie set_objective, add_variable oder add_constraint modellieren können. Zusammen mit magrittr pipes können Sie ein Modell genau wie eine Dplyr-Anweisung inkrementell erstellen, ohne sich Gedanken darüber zu machen, wie die Matrix und die Vektoren erstellt werden. Darüber hinaus ist ein Ompr-Modell von spezifischen Solvern unabhängig und viele beliebte Solver können leicht über die ROI-Familie der Pakete (Hornik et al. 2016) verwendet werden.
Die Idee zum Modellieren gemischter ganzzahliger Programme ist im Allgemeinen nicht neu. Domänenspezifische Sprachen wie GNU MathProg oder das JuMP-Projekt (Dunning, Huchette und Lubin 2015) in Julia implementieren einen ähnlichen Ansatz wie ompr und inspirierten seine Entwicklung. Soweit ich weiß, gibt es ein weiteres verwandtes R-Paket , Roml (Vana, Schwendinger und Hochreiter 2016), das derzeit entwickelt wird und auf einem ähnlichen Weg folgt.
Das ompr-Paket wird entwickelt und auf GitHub verfügbar. Neben dem Paket selbst gibt es mehrere Vignetten und Beispiele, die beschreiben, wie man beliebte Optimierungsprobleme modellieren und lösen kann, wie z. B. das Problem des Reisenden, das Lagerstandortproblem oder das interaktive Lösen von Sudokus mit glänzenden.
In diesem Vortrag werde ich die Modellierungsfeatures von ompr präsentieren, wie das Paket verwendet werden kann, um praktische Optimierungsprobleme und einige Ideen für zukünftige Entwicklungen zu lösen.
Referenzen Dunning, Iain, Joey Huchette und Miles Lubin. 2015. "JuMP: Eine Modellierungssprache für mathematische Optimierung." arXiv:1508.01982 [Math.OC]. http://arxiv.org/abs/1508.01982.
GNU Linear Programming Kit. 2017. http://www.gnu.org/software/glpk/glpk.html.
Hornik, Kurt, David Meyer, Florian Schwendinger und Stefan Theussl. 2016. (Microsoft: „Inklusives Microsoft Design-Toolkit“, 2016) ROI: R Optimization Infrastructure. https://CRAN.R-project.org/package=ROI.
Vana, Laura, Florian Schwendinger und Ronald Hochreiter. 2016. (Microsoft: „Inklusives Microsoft Design-Toolkit“, 2016) R Optimization Modeling Language. https://r-forge.r-project.org/projects/roml/.
useR!2017: ompr: eine alternative Möglichkeit zum Modellieren von Gemischten-...
Schlüsselwörter: Ganzzahlprogrammierung, lineare Programmierung, Modellierung, Optimierung
Webseiten:https://github.com/dirkschumacher/ompr
Viele Probleme bei der Optimierung der realen Welt, wie z. B. das beliebte Problem des Reisenden, können als gemischt-ganzzahliges lineares Programm (MILP) formuliert werden. Das Ziel von MILP ist es, eine lineare Zielfunktion zu optimieren, die einer Reihe linearer Einschränkungen unterliegt. In den letzten Jahrzehnten wurden spezialisierte Open-Source- und kommerzielle Solver entwickelt, z. B. das GNU Linear Programming Kit (GLPK), das diese Art von Problemen effizient lösen kann.
In R sind Schnittstellen zu diesen Solvern hauptsächlich matrixorientiert. Beim Lösen eines MILP in R müssen Sie daher zuerst Ihr tatsächliches Modell entwickeln und dann in Code übersetzen, der eine Matrix und Vektoren erstellt, bevor Sie es an einen Solver übergeben. Insbesondere für komplexere Modelle ist der R-Code möglicherweise eher schwer zu entwickeln und ohne zusätzliche Dokumentation zu begründen.
ompr ist eine domänenspezifische Sprache, mit der Sie MILPs deklarativ mithilfe von Funktionen wie set_objective, add_variable oder add_constraint modellieren können. Zusammen mit magrittr pipes können Sie ein Modell genau wie eine Dplyr-Anweisung inkrementell erstellen, ohne sich Gedanken darüber zu machen, wie die Matrix und die Vektoren erstellt werden. Darüber hinaus ist ein Ompr-Modell von spezifischen Solvern unabhängig und viele beliebte Solver können leicht über die ROI-Familie der Pakete (Hornik et al. 2016) verwendet werden.
Die Idee zum Modellieren gemischter ganzzahliger Programme ist im Allgemeinen nicht neu. Domänenspezifische Sprachen wie GNU MathProg oder das JuMP-Projekt (Dunning, Huchette und Lubin 2015) in Julia implementieren einen ähnlichen Ansatz wie ompr und inspirierten seine Entwicklung. Soweit ich weiß, gibt es ein weiteres verwandtes R-Paket , Roml (Vana, Schwendinger und Hochreiter 2016), das derzeit entwickelt wird und auf einem ähnlichen Weg folgt.
Das ompr-Paket wird entwickelt und auf GitHub verfügbar. Neben dem Paket selbst gibt es mehrere Vignetten und Beispiele, die beschreiben, wie man beliebte Optimierungsprobleme modellieren und lösen kann, wie z. B. das Problem des Reisenden, das Lagerstandortproblem oder das interaktive Lösen von Sudokus mit glänzenden.
In diesem Vortrag werde ich die Modellierungsfeatures von ompr präsentieren, wie das Paket verwendet werden kann, um praktische Optimierungsprobleme und einige Ideen für zukünftige Entwicklungen zu lösen.
Referenzen Dunning, Iain, Joey Huchette und Miles Lubin. 2015. "JuMP: Eine Modellierungssprache für mathematische Optimierung." arXiv:1508.01982 [Math.OC]. http://arxiv.org/abs/1508.01982.
GNU Linear Programming Kit. 2017. http://www.gnu.org/software/glpk/glpk.html.
Hornik, Kurt, David Meyer, Florian Schwendinger und Stefan Theussl. 2016. (Microsoft: „Inklusives Microsoft Design-Toolkit“, 2016) ROI: R Optimization Infrastructure. https://CRAN.R-project.org/package=ROI.
Vana, Laura, Florian Schwendinger und Ronald Hochreiter. 2016. (Microsoft: „Inklusives Microsoft Design-Toolkit“, 2016) R Optimization Modeling Language. https://r-forge.r-project.org/projects/roml/.
Feedback? Melden Sie hier ein Problem.