A Novel Method to Analyze and Decompose the Weights in the Weighted Sum Method of a MOLP

Authors
Javad Vakili
Sahar Shahsavan Pour Ahl
University of Tabriz
Abstract
The present study presents a new and applicable method to analyze and decompose the weights set in the weighted sum method. To do this, a linear programming (LP) problem is first designed for each extreme point of the expanded outcome space. Then, it is shown that the extreme optimal solutions of the presented LPs are the gradient vectors of the defining (weak) non-dominated hyperplanes of the expanded outcome space. Then, the set of eligible weights in the weighted sum method is comprehensively studied. The polyhedral and structural soft engineering of the set of all weights yielding the same non-dominated solution is meticulously checked. As a consequence, some structural insights related to the properties of the set of (weak) non-dominated solutions are discussed. Finally, the advantage and validity of the method is presented by a numerical example.
Keywords
Multi-Objective Linear Programming (MOLP)
Weighted sum method
Weights
Decomposition
1. M. J. Alves and J. P. Costa, Graphical exploration of the weight space in three-objective mixed integer linear programs, Eur. J. Oper. Res. 248(2016), 72–83.

2. Y. Aneja and P. K. Nair, Bicriteria transportation problem, Management Scienc., 25(1979), 73-78.

3. M. S. Bazaraa, J. J. Jarvis and H. D. Sherali, Linear programming and network flows, John Wiely and Sons, Hoboken, New Jersey (2010).

4. H. P. Benson and E. Sun, A weight set decomposition algorithm for finding all efficient extreme points in the outcome set of a multiple objective linear program, Eur. J. Oper. Res., 139 (2002), 26-41.

5. H. P. Benson and E. Sun, Outcome space partition of the weight set in multiobjective linear programming, J. Optim. Theory Appl., 105(2000), 17–36.

6. F. Bökler and P. Mutzel, Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. In: N. Bansal, I. Finocchi (eds.) Algorithms – ESA 2015, 288–299. Springer, Berlin Heidelberg (2015).

7. M. Botte and S. Schabel, Dominance for multi-objective robust optimization concepts, Eur. J. Oper. Res., 273(2019), 430-440.

8. T. V. Brasch, K. H. Grini, M.B. Johnsen and T.C. Vigtel, An exact additive decomposition of the weighted arithmetic mean, Econ. Stor., 994(2021), 1-21.

9. T. C. Y. Chan, T. Craig, T. Lee and M. B. Sharpe, Generalized inverse multiobjective optimization with application to cancer therapy, Oper. Res., 62(2014), 680–695.

10. H. Charkhgard, M. Savelsbergh and M. Talebian, Nondominated nash points: application of biobjective mixed integer programming, Quart. J. Oper. Res. 16(2018), 151–171.

11. J.L. Cohon, Multiobjective programming and planning. Dover Books on Computer Science. Dover, Mineola (2004).

12. W.W. Cooper, L. M. Seiford and K. Tone, Introduction to data envelopment analysis and its uses: with DEA-solver software and references, Springer Science & Business Media, 2006.

13. C. Cotrutz, M. Lahanas, K. Kappas and D. Baltas, A multiobjective gradient-based dose optimization algorithm for external beam conformal radiotherapy, Phys. Med. Biol., 46(2001),2161–2175.



14. M. Ehrgott, Multicriteria optimization, Springer-Verlag, Berlin Heidelberg (2005).

15. G. R. Jahanshahloo, A. Shirzadi and S. M. Mirdehghan, Finding strong defining hyperplanes of PPS using multiplier form, Eur. J. Oper. Res., 194(2009), 933-938.



16. P. Halffmann, T. Dietz, A. Przybylski and S. Ruzika, An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem, J. Global Optim., 77(2020), 715-742.

17. H. Hamacher and K-H. Küfer, Inverse radiation therapy planing—A multiple objective optimization Approach, Discret Appl. Math., 118 (2002),145–161.

18. A. Holder, Designing radiotherapy plans with elastic constraints and interior point methods, Health Care Management Sci., 6 (2003), 5–16.



19. O. Özpeynirci and M. Köksalan, An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs, Manage. Sci., 56(2010),2302–2315 .

20. F. P. Preparata and M. I. Shamos, Computational geometry, Springer-Verlag New York, New York (1988).

21. K-H. Küfer, A. Scherrer, M. Monz , F. Alonso, H. Trinkaus, T. Bortfeld and C. Thieke, Intensity modulated radiotherapy—A large scale multi-criteria programming problem, OR Spectr., 25(2003), 223–249.

22. M. Lahanas, E. Schreibmann and D. Baltas, Multiobjective inverse planning for intensity modulated radiotherapy with constraint-free gradient-based optimization algorithms, Phys. Med. Biol., 48(2003),2843–2871.



23. H. Romeijn, J. Dempsey and J. Li, A unifying framework for multi-criteria fluence map optimization models, Phys. Med. Biol., 49(2004),1991–2013.



24. P. L. Yu and M. Zeleny, The set of all nondominated solutions in linear cases and a multicriteria simplex method, J. Math. Anal. Appl., 49(1975), 430–468.

25. L. Zadeh, Optimality and non-scalar-valued performance criteria, IEEE Trans. Autom. Control 8(1963), 59–60.