Solver of multiobjective linear optimization problems
vOptSolver is an ecosystem for modeling and solving multiobjective linear optimization problems (MOCO, MOIP, MOMIP, MOLP). It has been supported by the ANR/DFG14CE35003401 research project (link).
It integrates several exact algorithms for computing a complete set of nondominated points for structured and nonstructured optimization problems with at least two objectives.
This repository (1) gives a description of the solver and (2) hosts documents covering all parts of the solver.
Content
News
22Apr2019: Preparing an update of the documentation
31Oct2018: vOptSpecific and vOptGeneric are compliant with Julia v1.x
01Jul2018: Preparing the switch to Julia 0.7 and to the new version of JuMP
01Sep2017: Algorithms added to vOptGeneric and vOptSpecific, documentation and examples are coming.
20Jul2017: Examples presented in conferences (MCDM'2017; IFORS'2017) are online (folder examples)
26Jun2017: Source codes of vOptGeneric and vOptSpecific for v0.0.2 are online
17Jun2017: Moved from GitLab to GitHub
03Jun2017: The next release (v0.0.2) is scheduled for June 2017
Feedback
All bugs, feature requests, pull requests, feedback, etc., are welcome.
Coordinator
Prof. Dr. Xavier Gandibleux, University of Nantes  France (contact)
Developers
By chronological order:
 Current contributors: Xavier Gandibleux, Anthony Przybylski, Gauthier Soleilhac.
 Past contributors: Quentin Delmée, Dorian Dumez, Pauline Chatelier, Flavien Lucas, Clément Turcat.
How To Contribute
 in adding your examples (code JuMP + data) solved with vOptGeneric to the collection;
 in plugging your own C/C++/Julia algorithms into vOptSpecific or vOptGeneric;
 in adapting vOptSpecific for windows;
 in sending us your suggestions to improve/extend vOptSolver;
 in telling us when you have completed a work (exercices for students; research; paper; etc.) using vOptSolver;
 in joining the adventure with us as maintainer of the solver, repositories, documents, etc.
In brief, every contributions aiming to share our efforts, our algorithms, our productions around this open source software are welcome.
License
vOptSolver is distributed under the MIT License.
How To Cite
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 1014, 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 1721, 2017. Quebec City (Canada).
Cooperation
The development of vOptSolver started in the ANR/DFG14CE35003401 research project vOpt (link) involving Université de Nantes (France) and University of KoblenzLandau/University of Kaiserslautern (Germany).
Overview
Aims
 Solver of multiobjective linear optimization problems for scientifics and practionners
 Easy to formulate a problem, to provide data, to solve a problem, to collect the outputs, to analyze the solutions
 Natural and intuitive use for mathematicians, informaticians, engineers
Purposes
 Solving needs: methods and algorithms for performing numerical experiments
 Research needs: support and primitives for the development of new algorithms
 Pedagogic needs: environment for practicing of theories and algorithms
Characteristics
 Efficient, flexible, evolutive solver
 Free, open source, multiplatform, reusing existing specifications
 Easy installation, no need of being expert in computer science
Background
 Julia programming language (link)
 JuMP algebraic language (link)
 Usual free (GLPK, Clp/Cbc) and commercial (CPLEX, GUROBI) MILP solvers
Features
Problems managed
 vOptGeneric: Multiobjective nonstructured problems / algebraic language (JuMP),
 pLP: Linear Program
 pMILP: Mixed Integer Linear Program
 pILP: Integer Linear Program
 vOptSpecific: Multiobjective structured problems / Application Programming Interface (API),
 2LAP: Linear Assignment Problem
 2OSP: One machine Scheduling Problem
 2UKP: binary Unidimensional knapsack problem
 2UMFLP: Uncapacitated Mixed variables Facility Location Problem
 Forthcoming: [pPATHS, 2UDFLP]. Projects : [MKP, SSCFLP, CFLP]
Algorithms integrated
The solving algorithms included compute exact solution(s) corresponding to Y_{lex}, Y_{SN}, or Y_{N}.
 vOptGeneric: generic algorithms for structured or nonstructured discrete problems,
 Lexico: compute Y_{lex}, the lexicographic optimal solutions for pILP (Julia+JuMP)
 Aneja1979: compute Y_{SN} with Aneja & Nair method (also named the dichotomic method) for 2ILP (Julia+JuMP)
 Haimes1971: compute Y_{N} with epsilonconstraint method for 2ILP (Julia+JuMP)
 Chalmet1986: compute Y_N with Chalmet et al. method for 2ILP (Julia+JuMP)
 Forthcoming: algorithms for [{2,3}LP]. Projects: algorithms for [3ILP, {2,3}MILP]
 vOptSpecific: specific algorithms for structured (MOCO/MOMILP) problem,
 Przybylski2008: 2LAP2008 (C)
 Wassenhove1980: 2OSP1980 (implemented in 2017 in Julia)
 Jorge2010: 2UKP2010 (reimplemented in 2017 in Julia)
 Delmee2017: 2UMFLP2016 (C++)
 Forthcoming:[Gandibleux2006: PATHS (reimplemented in 2018 in Julia); Gandibleux2012: 2UDFLP2012 (reimplemented in 2018 in C)]
 vOptTools: collection of primitives for multiobjective linear optimization problems,
 Forthcoming: Dumez2017: algorithm for maintaining nondominated points/2ILP (Julia)
 Nonstructured problems:
 direct with the provided languages (Julia, JuMP)
 standard MOP format (ILP, MILP, LP)
 specific problem format (MILP)
 Structured problems:
 direct with the language (Julia),
 specific problem format (2LAP, 2UKP, 2UFLP)
Outputs
 Nonstructured problems:
 standard 2MOP format (ILP, MILP, LP)
 Structured problems:
 specific problem format (2LAP, 2UKP, 2UFLP)
Instructions
 Julia is available on macOS, linux, windows for a local use or online on JuliaBox for a distant use
 vOptSolver (composed of vOptGeneric, vOptSpecific, and vOptTools) is free, open source under MIT licence.
 vOptSolver has been tested with Julia 1.0 on macOS 10.13.6 and linuxUbuntu 14.04 LTS.
 vOptGeneric has been tested with Julia 1.0 on windows 10 64 bits.
Installation and usage Instructions
Refer to the instructions provided for
Documentation (working on it)
The documentation has been written for Julia v0.6.4. New versions compliant with v1.x are for soon. We apologize if some examples raise an error.
References

[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 SMC1, Issue 3, Pages 296297, July 1971.

[Aneja1979] Y. P. Aneja and K. P. K. Nair:
Bicriteria Transportation Problem.
Management Science, 25:1, 7378 1979.

[Wassenhove1980] L. N. Van Wassenhove, L. F. Gelders:
Solving a bicriterion scheduling problem.
European Journal of Operational Research, Volume 4, Issue 1, Pages 4248, 1980.

[Chalmet1986] L.G. Chalmet, L. Lemonidis, D.J. Elzinga:
An algorithm for the bicriterion integer programming problem.
European Journal of Operational Research, Volume 25, Issue 2, Pages 292300, 1986.

[Gandibleux2006] X. Gandibleux, F. Beugnies, S. Randriamasy:
Martins’ algorithm revisited for multiobjective shortest path problems with a MaxMin cost function.
4OR: A Quarterly Journal of Operations Research, Springer Verlag, 4 (1), pp.4759, 2006.

[Przybylski2008] A. Przybylski, X. Gandibleux, M. Ehrgott:
Two phase algorithms for the biobjective assignment problem.
European Journal of Operational Research, Volume 185, Issue 2, Pages 509533, 2008.

[Jorge2010] J. Jorge:
Nouvelles propositions pour la résolution exacte du sac à dos multiobjectif 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 1113, 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 biobjectif 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). 2224 février 2017, Metz, France.

[Dumez2017] D. Dumez, X. Gandibleux, I. Rusu. Datastructures for Filtering and Storing NonDominated Points.
MOPGP’2017: 12th International Conference on Multiple Objective Programming and Goal Programming. 3031 October 2017, Metz, France.
Terms and acronyms used
 LP: Linear Program
 MILP: Mixed Integer Linear Program
 IP: Integer linear program
 CO: Combinatorial Optimization
 MOLP: MultiObjective linear program
 MOIP: MultiObjective Integer linear program
 MOMILP: MultiObjective Mixed Integer Linear Program
 MOCO: MultiObjective Combinatorial Optimization
 OSP: One machine Scheduling Problem
 LAP: Linear Assignment Problem
 UKP: Unidimensional 01 Knapsack Problem
 MKP: Multidimensional 01 Knapsack Problem
 UFLP: Uncapacitated Facility Location Problem
 UDFLP: Discrete Uncapacitated Facility Location Problem
 SSCFLP: Single Source Capacitated Facility Location Problem
 UMFLP: Uncapacitated Mixed variables Facility Location Problem
 CFLP: Capacitated Facility Location Problem
 PATHS: shortest paths problem
 Julia: name of the programming language
 JuMP: stands for Julia for Mathematical Optimization, a modeling language for mathematical optimization embedded in Julia
 AVL tree is a selfbalancing binary search tree
 API: stands for Application Programming Interface
 GPL: stands for GNU General Public License
 GLPK: stands for GNU Linear Programming Kit, an open source solver
 Clp/Cbc : an open source solver (for LP and MILP respectively) from the COINOR project
 CPLEX: a commercial solver
 GUROBI: a commercial solver
 MOP: MultiObjective extension of MPS format