Premium
Using aspiration levels in an interior primal‐dual multiobjective linear programming algorithm
Author(s) -
Arbel Ami,
Korhonen Pekka
Publication year - 1996
Publication title -
journal of multi‐criteria decision analysis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.462
H-Index - 47
eISSN - 1099-1360
pISSN - 1057-9214
DOI - 10.1002/(sici)1099-1360(199603)5:1<61::aid-mcda84>3.0.co;2-c
Subject(s) - interior point method , simplex algorithm , linear programming , algorithm , mathematical optimization , path (computing) , computer science , duality (order theory) , process (computing) , function (biology) , criss cross algorithm , trace (psycholinguistics) , dual (grammatical number) , mathematics , linear fractional programming , art , linguistics , philosophy , literature , discrete mathematics , evolutionary biology , biology , programming language , operating system
We introduce in this paper a new multiple‐objective linear programming (MOLP) algorithm. The algorithm is based on the single‐objective path‐following primal—dual linear programming algorithm and combines it with aspiration levels and the use of achievement scalarizing functions. The resulting algorithm falls in the class of interactive MOLP algorithms, as it requires interaction with the decision maker (DM) during the iterative process to obtain statements of aspirations for levels of objectives of the MOLP problem. The interior point algorithm is then used to trace a path of interates from a current (interior) solution and approach as closely as desired a non‐dominated solution corresponding to the optimum of the achievement scalarizing function. The timing of the interaction with the DM is dependent on the progress of the interior algorithm. It can take place every few, pre‐specified, iterations or after the duality gap achieved for the stated aspirations has fallen below a certain threshold. It is expected that an interior algorithm will speed up the overall process of searching and finding the most preferred MOLP solution—especially in large‐scale problems—by avoiding the need for numerous pivot operations and their corresponding interactive sessions inherent in simplex‐based algorithms.