×

PolySCIP. (English) Zbl 1434.90004

Greuel, Gert-Martin (ed.) et al., Mathematical software – ICMS 2016. 5th international conference, Berlin, Germany, July 11–14, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9725, 259-264 (2016).
Summary: PolySCIP [http://polyscip.zib.de] is a new solver for multi-criteria integer and multi-criteria linear programs handling an arbitrary number of objectives. It is available as an official part of the non-commercial constraint integer programming framework SCIP. It utilizes a lifted weight space approach to compute the set of supported extreme non-dominated points and unbounded non-dominated rays, respectively. The algorithmic approach can be summarized as follows: at the beginning an arbitrary non-dominated point is computed (or it is determined that there is none) and a weight space polyhedron created. In every next iteration a vertex of the weight space polyhedron is selected whose entries give rise to a single-objective optimization problem via a combination of the original objectives. If the optimization of this single-objective problem yields a new non-dominated point, the weight space polyhedron is updated. Otherwise another vertex of the weight space polyhedron is investigated. The algorithm finishes when all vertices of the weight space polyhedron have been investigated. The file format of PolySCIP is based on the widely used MPS format and allows a simple generation of multi-criteria models via an algebraic modelling language.
For the entire collection see [Zbl 1342.68017].

MSC:

90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] PolySCIP website: http://polyscip.zib.de
[2] PolySCIP user guide: http://polyscip.zib.de/download/userguide.pdf
[3] Ralphs, T., Guzelsoy, M., Mahajan, A.: SYMPHONY Version 5.5 User’s Manual. Lehigh University (2013). https://projects.coin-or.org/SYMPHONY
[4] Löhne, A.: Vector Optimization with Infimum and Supremum. Springer, Heidelberg (2011). www.bensolve.org · Zbl 1230.90002 · doi:10.1007/978-3-642-18351-5
[5] Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1
[6] Gamrath, G., Fischer, T., Gally, T., et al.: The SCIP Optimization Suite 3.2. ZIB-Report 15–60 (2016)
[7] SCIP Optimization Suite. http://scip.zib.de
[8] Gurobi Optimization. www.gurobi.com
[9] FICO Xpress Optimization Suite. www.fico.com/en/products/fico-xpress-optimization-suite
[10] ILOG Cplex Optimization Studio. www-03.ibm.com/software/products/en/ibmilogcpleoptistud
[11] CRC (2011) Observation of strains: Sustainable Manufacturing. www.sustainable-manufacturing.net
[12] Isermann, H.: Proper efficiency and the linear vector maximum problem. Oper. Res. 22(1), 189–191 (1974) · Zbl 0274.90024 · doi:10.1287/opre.22.1.189
[13] Ehrgott, M.: Multicriteria Optimization. Springer, Heidelberg (2005) · Zbl 1132.90001
[14] Benson, H.P., Sun, E.: Outcome space partition of the weight set in multiobjective linear programming. J. Optim. Theory Appl. 105(1), 17–36 (2000) · Zbl 1028.90051 · doi:10.1023/A:1004605810296
[15] Przybylski, A., Gandibleux, X., Ehrgott, M.: A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme. INFORMS J. Comput. 22(3), 371–386 (2010) · Zbl 1243.90203 · doi:10.1287/ijoc.1090.0342
[16] Özpeynirci, Ö., Köksalan, M.: An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Manage. Sci. 56(12), 2302–2315 (2010) · Zbl 1232.90329 · doi:10.1287/mnsc.1100.1248
[17] Benson, H.P.: An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J. Global Optim. 13(1), 1–24 (1998) · Zbl 0908.90223 · doi:10.1023/A:1008215702611
[18] Ehrgott, M., Löhne, A., Shao, L.: A dual variant of Benson’s ”outer approximation algorithm” for multiple objective linear programming. J. Global Optim. 52(4), 757–778 (2012) · Zbl 1245.90115 · doi:10.1007/s10898-011-9709-y
[19] LEMON Graph Library. https://lemon.cs.elte.hu/trac/lemon
[20] MPS format: http://lpsolve.sourceforge.net/5.5/mps-format.htm · Zbl 1307.76031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.