Multi-Objective Linear Programming Revisited: Exact and Approximate Approaches

Most real world decision making problems involve more than one objective function and can be formulated as multiple objective linear programming (MOLP) problems. Some exact methods have proven to be effective on small and medium scale MOLP instances. The thesis considers prominent exact methods, implements and modifies some of them and compares them on existing test problems. Heuristics or approximate methods on the other hand, have been commonly applied to nonlinear and discrete multi-objective optimisation problems, and not so much to MOLP. Given the complexity of MOLP, it is worth investigating heuristics as a solution approach. This has also been considered here. The thesis presents an extensive state-of-the-art survey of MOLP algorithms developed over the past five decades and modifies/extends some of them to generate the set of all nondominated points of the problem. It then compares these extended variants with others such as Benson's algorithm, the affine scaling interior-point MOLP algorithm and the recently introduced parametric simplex algorithm. Furthermore, the thesis investigates heuristic approaches namely nondominated sorting genetic algorithm II and the plant propagation algorithm as alternative approximate methodologies for MOLP. It also presents a procedure to compute the most preferred nondominated point of the problem. All algorithms have been tested and compared on existing test instances.