An Improved Method for Solving Multiobjective Integer Linear Fractional Programming Problem

We describe an improvement of Chergui and Moula？’s method (2008) that generates the whole efficient set of a multiobjective integer linear fractional program based on the branch and cut concept. The general step of this method consists in optimizing (maximizing without loss of generality) one of the fractional objective functions over a subset of the original continuous feasible set; then if necessary, a branching process is carried out until obtaining an integer feasible solution. At this stage, an efficient cut is built from the criteria’s growth directions in order to discard a part of the feasible domain containing only nonefficient solutions. Our contribution concerns firstly the optimization process where a linear program that we define later will be solved at each step rather than a fractional linear program. Secondly, local ideal and nadir points will be used as bounds to prune some branches leading to nonefficient solutions. The computational experiments show that the new method outperforms the old one in all the treated instances. 1. Introduction In this paper we focus our interest on multiobjective integer linear fractional programming (MOILFP) where several linear fractional objectives (i.e., ratio of two linear functions) are to be optimized simultaneously subject to a set of linear constraints and nonnegative integer variables. The motivation behind this choice comes in particular from the fact that in our knowledge a very few number of papers treating this type of problem were published in the literature [1–3] contrary to continuous case which has received much more attention from researchers (see, e.g., [4–13]). For the interested reader, Stancu-Minasian [14] has presented a comprehensive bibliography with 491 entries in addition to his book [15] containing the state of the art in the theory and practice of fractional programming. Abbas and Moula？ [1] and Gupta and Malhotra [3] have presented each a technique to generate the efficient set of a MOILFP based on the same principle: solving a sequence of integer linear fractional programs (ILFPs) until the stopping criterion they propose is met. The first ILFP solved is defined by optimizing one of the objective functions subject to the entire feasible set; then a cutting plane is recursively added to eliminate the current optimal solution and eventually the solutions lying on an adjacent edge. The choice of this latter makes the main difference between these two methods. Unfortunately, they have both the same inconvenience that is scanning almost the whole search space which is very