Premium
Adjacency‐based local top‐down search method for finding maximal efficient faces in multiple objective linear programming
Author(s) -
Tohidi G.,
Hassasi H.
Publication year - 2018
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21805
Subject(s) - adjacency list , linear programming , affine transformation , adjacency matrix , vertex (graph theory) , computer science , set (abstract data type) , convexity , mathematical optimization , code (set theory) , extreme point , mathematics , graph , algorithm , theoretical computer science , combinatorics , financial economics , pure mathematics , economics , programming language
Abstract It is well‐known that the efficient set of a multiobjective linear programming (MOLP) problem can be represented as a union of the maximal efficient faces of the feasible region. In this paper, we propose a method for finding all maximal efficient faces for an MOLP. The new method is based on a condition that all efficient vertices (short for the efficient extreme points and rays) for the MOLP have been found and it relies on the adjacency, affine independence and convexity results of efficient sets. The method uses a local top‐down search strategy to determine maximal efficient faces incident to every efficient vertex for finding maximal efficient faces of an MOLP problem. To our knowledge, the proposed method is the first top‐down search method that uses the adjacency property of the efficient set to find all maximal efficient faces. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several MOLP problems with the code.