Solver of multiobjective linear optimization problems: description and documents
vOptSolver is an ecosystem for modeling and solving multiobjective linear optimization problems (MOMIP, MOLP, MOIP, MOCO). It integrates several exact algorithms for computing the set of non-dominated points $Y_N$, and the corresponding complete set of efficient solutions $X_E$, for structured and non-structured optimization problems with at least two objectives.
It is composed of the two julia packages MultiObjectiveAlgorithms (previously vOptGeneric) and vOptSpecific, and hosts vOPtLib, a library of numerical instances:
IMPORTANT (Feb-2023): vOptGeneric.jl has been fully redesigned, and reimplemented. It becomes MultiObjectiveAlgorithms.jl (MOA), a collection of algorithms for multi-objective optimization integrated to JuMP and MathOptInterface. MOA comes with an enriched list of multi-objective algorithms, especially for solving problems with 3 objectives. Consequently vOptGeneric.jl is no longer under active development. It will remain available on Github at https://github.com/vOptSolver/vOptGeneric.jl. From February 2023, the JuMP-dev organization will continue to maintain the MOA package and transition development over the long term.
15-Feb-2023: Simple examples from vOptGeneric have been adapted for MOA
15-Feb-2023: vOptGeneric.jl is no longer under active development
15-Feb-2023: vOptGeneric.jl has been redesigned and reimplemented, it becomes MultiObjectiveAlgorithms.jl
03-Sep-2022: Instances and parser for uncapacitated facility location problems added
12-Mar-2022: vOptGeneric is compliant with JuMP 0.23.0 and MOI 1.1.0
25-Jan-2022: Parser for set partitionning problems added
24-Jul-2021: vOptSpecific updated, and new examples added
21-Jul-2021: Examples for vOptGeneric updated and new examples added
15-Jun-2019: Testing the version of vOptGeneric compliant with JuMP 0.19
22-Apr-2019: Preparing an update of the documentation
31-Oct-2018: vOptSpecific and vOptGeneric are compliant with Julia v1.x
01-Jul-2018: Preparing the switch to Julia 0.7 and to the new version of JuMP
01-Sep-2017: Algorithms added to vOptGeneric and vOptSpecific, documentation and examples are coming.
20-Jul-2017: Examples presented in conferences (MCDM'2017; IFORS'2017) are online (folder examples)
26-Jun-2017: Source codes of vOptGeneric and vOptSpecific for v0.0.2 are online
17-Jun-2017: Moved from GitLab to GitHub
03-Jun-2017: The next release (v0.0.2) is scheduled for June 2017
All bugs, feature requests, pull requests, feedback, etc., are welcome.
Prof. Dr. Xavier Gandibleux, University of Nantes - France (contact)
By alphabetical order (concerning vOptGeneric and vOptSpecific):
In brief, every contributions aiming to share our efforts, our algorithms, our productions around this open source software are welcome.
vOptSolver is distributed under the MIT License.
Xavier Gandibleux. Multi-objective optimization with JuMP. JuliaCon 2023. Massachusetts Institute of Technology. Cambridge, USA. July 25-29, 2023.
Xavier Gandibleux, Gauthier Soleilhac, Anthony Przybylski. vOptSolver: an ecosystem for multi-objective linear optimization. JuliaCon 2021. Online and everywhere. July 28-30, 2021. Abstract. Reference to use for citing vOptSolver
Anthony Przybylski. Optimisation combinatoire multi-objectif : méthodes de résolution exacte et solveur vOpt. JuliaDay’2019 : Journée « Julia et Optimisation ». 17 Juin 2019. Université de Nantes, France. https://julialang.univ-nantes.fr/journee-julia-et-optimisation
Xavier Gandibleux et Anthony Przybylski, Algorithmes de branch-and-bound multiobjectif et vOptSolver. Tutoriel du GDR CNRS RO, ROADEF’2018 : 19e édition du congrès annuel de la Société Française de Recherche Opérationnelle et d’Aide à la Décision. 22 février 2018, Lorient. Video.
Xavier Gandibleux et Anthony Przybylski, Optimisation combinatoire multiobjectif : deux contributions issues du projet de recherche ANR-DFG vOpt. SPOC16 : 16e journée “Polyèdres et optimisation combinatoire”. LAMSADE/Université Paris-Dauphine. 15 décembre 2017.
Xavier Gandibleux, Pascal Halffmann. Designing and Experimenting with vOptSolver an Algorithm for Computing the Weight Set Decomposition. RAMOO’2017 : 4th International workshop “Recent Advances in Multi-Objective Optimization”, TU-Kaiserslautern, Germany. 2017.
Xavier Gandibleux, Gauthier Soleilhac, Anthony Przybylski, Flavien Lucas, Stefan Ruzika, Pascal Halffmann. vOptSolver, a “get and run” solver of multiobjective linear optimization problems built on Julia and JuMP. MCDM2017: 24th International Conference on Multiple Criteria Decision Making. July 10-14, 2017. Ottawa (Canada).
Xavier Gandibleux, Gauthier Soleilhac, Anthony Przybylski, Stefan Ruzika. vOptSolver: an open source software environment for multiobjective mathematical optimization. IFORS2017: 21st Conference of the International Federation of Operational Research Societies. July 17-21, 2017. Quebec City (Canada).
The development of vOptSolver started in the ANR/DFG-14-CE35-0034-01 research project vOpt (2015-2019) (link) involving Université de Nantes (France) and University of Koblenz-Landau/University of Kaiserslautern (Germany).
The solving algorithms included compute exact solution(s) corresponding to Y_{lex}, Y_{SN}, or Y_{N}.
Refer to the instructions provided for
NB: the available documentation is obsolete (written for Julia v0.6.4; new documentation compliant with v1.x is coming).
Old documentation:
Examples of problems ready to be solved:
[Haimes1971] Y.V. Haimes, L.S. Lasdon, D.A. Wismer: On a bicriterion formation of the problems of integrated system identification and system optimization. IEEE Transactions on Systems, Man and Cybernetics, Volume SMC-1, Issue 3, Pages 296-297, July 1971.
[Aneja1979] Y. P. Aneja and K. P. K. Nair: Bicriteria Transportation Problem. Management Science, 25:1, 73-78 1979.
[Wassenhove1980] L. N. Van Wassenhove, L. F. Gelders: Solving a bicriterion scheduling problem. European Journal of Operational Research, Volume 4, Issue 1, Pages 42-48, 1980.
[Chalmet1986] L.G. Chalmet, L. Lemonidis, D.J. Elzinga: An algorithm for the bi-criterion integer programming problem. European Journal of Operational Research, Volume 25, Issue 2, Pages 292-300, 1986.
[Gandibleux2006] X. Gandibleux, F. Beugnies, S. Randriamasy:
Martins’ algorithm revisited for multi-objective shortest path problems with a MaxMin cost function.
4OR: A Quarterly Journal of Operations Research, Springer Verlag, 4 (1), pp.47-59, 2006.
[Przybylski2008] A. Przybylski, X. Gandibleux, M. Ehrgott: Two phase algorithms for the bi-objective assignment problem. European Journal of Operational Research, Volume 185, Issue 2, Pages 509-533, 2008.
[Jorge2010] J. Jorge: Nouvelles propositions pour la résolution exacte du sac à dos multi-objectif unidimensionnel en variables binaires. PhD Thesis (in French), Université de Nantes - France, 2010.
[Gandibleux2012] X. Gandibleux, A. Przybylski , S. Bourougaa, A. Derrien, A. Grimault: Computing the Efficient Frontier for the 0/1 Biobjective Uncapacitated Facility Location Problem CORS/MOPGP’2012 (10th international conference on Multiple Objective Programming and Goal Programming). June 11-13, 2012, Niagara Falls, Canada.
[Vincent2013] Th. Vincent: Caractérisation des solutions efficaces et algorithmes d’énumération exacts pour l’optimisation multiobjectif en variables mixtes binaires. PhD Thesis (in French), Université de Nantes - France, 2013.
[Delmee2017] Q. Delmée, X. Gandibleux, A. Przybylski: Résolution exacte du problème de localisation de services bi-objectif sans contrainte de capacité en variables mixtes. ROADEF2017 (18ème édition du congrès annuel de la Société Française de Recherche Opérationnelle et d’Aide à la Décision). 22-24 février 2017, Metz, France.
[Dumez2017] D. Dumez, X. Gandibleux, I. Rusu. Datastructures for Filtering and Storing Non-Dominated Points. MOPGP’2017: 12th International Conference on Multiple Objective Programming and Goal Programming. 30-31 October 2017, Metz, France.
Terms and acronyms used