Application of the ellipsoid method in an interactive procedure for multicriteria linear programming

The research reported in this paper is concerned with an application of the ellipsoid algorithm in the interactive multicriteria linear programming step method (STEM) byBenayoun et al. [1971]. Due to this application we eliminate some drawbacks of the original version of STEM and, moreover, we avoid extra computations connected with sensitivity analysis in every iteration. Specifically, we use the ellipsoid algorithm to minimize the Euclidean norm in the criterion space instead of the Chebyshev norm, which ensures that every solution submitted to the decision maker is efficient. As follows from a computational experiment, in comparison with the application of the simplex method, the proposed modification of STEM shows a smaller increase of the computational effort when the number of criteria increases. However, the absolute computation time becomes worse for problems of larger size.

---

Zusammenfassung In dieser Arbeit wird über eine Anwendungsmöglichkeit der Khachiyan-Shor-Algorithmus (Ellipsoid-Algorithmus) im Rahmen des STEM-Verfahrens zur interaktiven Lösung linearer Vektoroptimierungsmodelle berichtet. Auf diese Weise können einige spezifische Nachteile des STEM-Verfahrens in seiner Originalversion vermieden werden. Durch die Verwendung der Euklidischen Norm anstelle der beim STEM-Verfahren üblichen Tschebyscheff-Norm wird garantiert, daß dem Entscheidungsträger nur effiziente Lösungen vorgeschlagen werden. Die numerischen Erfahrungen zeigen, daß der Lösungsaufwand der hier vorgeschlagenen Modifikation des STEM-Verfahrens mit steigender Anzahl von Zielfunktionen weniger stark zunimmt als bei der üblichen Version. Dies gilt jedoch nicht hinsichtlich der allgemeinen Problemgröße.