Title: Efficient cuts for generating the non-dominated vectors for Multiple Objective Integer Linear Programming

Authors: Moncef Abbas; Mohamed El-Amine Chergui; Meriem Ait Mehdi

Addresses: Laboratory LAID3, University of Sciences and Technologie Houari Boumediene, USTHB, El-Alia, BP 32, 16111, Algiers, Algeria. ' Laboratory LAID3, University of Sciences and Technologie Houari Boumediene, USTHB, El-Alia, BP 32, 16111, Algiers, Algeria. ' Laboratory LAID3, University of Sciences and Technologie Houari Boumediene, USTHB, El-Alia, BP 32, 16111, Algiers, Algeria

Abstract: In this paper, a branch and bound multi-objective based method is proposed for reaching the non-dominated set. Two types of nodes are considered in the tree-search. The first type characterises the non-integer solutions found which are transformed to integer solutions by applying a branching procedure. The second type of nodes contains an integer solution and in this case efficient cuts are established in order either to remove dominated integer vectors or to fathom them. The method is compared advantageously with two exact methods of the literature tailored for the general case and also analysed computationally on benchmarks of MCDM library.

Keywords: branch and bound algorithms; multi-objective programming; non-dominated solutions; integer linear programming; non-dominated sets; tree search.

DOI: 10.1504/IJMOR.2012.046690

International Journal of Mathematics in Operational Research, 2012 Vol.4 No.3, pp.302 - 316

Published online: 23 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article