# An Improved Method for Solving Multiobjective Integer Linear Fractional Programming Problem

Authors: Meriem Ait Mehdi; Mohamed El-Amine Chergui; Moncef Abbas
Journal: Advances in Decision Sciences
 (2014)

---

## Abstract

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.


---

## Body

## 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 expensive in time and memory space.In [2], Chergui and Moulaï proposed a branch and cut approach to solve MOILFP problems. At each step, a new node is added to the search tree and the corresponding problem defined by optimizing one of the fractional objective functions over a subset of the original continuous feasible set is solved. Two types of nodes are distinguished: those relative to the branching process and are created for the search of integer feasible solutions and those relative to the addition of what the authors called an efficient cut. The purpose of adding such a cut to a given problem is to remove from its feasible domain the optimal solution and eventually a set of nonefficient solutions. A node is fathomed if the corresponding problem is infeasible or if the set of the criteria's growth directions determined to construct the efficient cut is empty. The procedure terminates when all the created nodes have been examined. The major drawback of this method lies in the fact that the integer feasible solutions found during the resolution are not all efficient (the efficiency of a solution is guaranteed only at the end of the procedure; otherwise, it is only potentially efficient). The larger the size of the problem, the greater the number of nonefficient solutions generated and thus the slower the convergence of the algorithm. To overcome this, we will introduce two new node fathoming rules based on the calculation of local ideal and nadir points that will avoid exploring other branches leading to unnecessary solutions. Also, we will give the formulation of the linear program that we propose to solve as subproblem at each node rather than a fractional linear program.The rest of the paper is organized as follows: in Section2, we give some definitions and some theoretical results related to our work. In Section 3, we describe in detail the improved method. We present a numerical example in Section 4 followed by a discussion of the results obtained from the computational experiments in Section 5. We conclude in Section 6.


## 2. Definitions and Previous Results

A multiobjective integer linear fractional program(MOILFP) can be written as follows:
(1)(MOILFP){max⁡⁡Z1(x)=c1x+α1d1x+β1⋮max⁡Zk(x)=ckx+αkdkx+βks.t.x∈X={x∈Rn∣Ax=b,x≥0},xinteger,
where ci, di are (1×n) vectors and αi, βi are scalars for i=1,k¯; A is a (m×n) real matrix and b∈Rm.We assume thatX is a nonempty compact polyhedron and all denominators are positive everywhere in X.The solution to the problem(MOILFP) is to find all solutions that areefficient in the sense of the following definition.An integer solutionx¯∈X is calledefficient if there does not exist another integer solution x∈X such that Zi(x)≥Zi(x¯) for all i=1,k¯ with at least one strict inequality. The resulting criterion vector (Z1(x¯),…,Zk(x¯))T is said to benondominated. The set of efficient solutions of (MOILFP) will be denoted by Eff throughout the paper.The vectorsId=(Id1,…,Idk)T with Idi=max⁡x∈X,xintegerZi(x) and Nd=(Nd1,…,Ndk)T with Ndi=min⁡x∈EffZi(x) are called, respectively,ideal andnadir points of the problem (MOILFP).Apayoff table (suggested by Benayoun et al. [16]) is a square matrix of order k where itsith row represents values of all objective functions calculated at a point where theith objective obtained its maximum value. An estimate of the nadir point is obtained by finding the worst objective values in each column. This method gives accurate information only in the biobjective case; otherwise, it may be an over or an underestimation.We give in the following the results that justify the method described in [2]. We first need to introduce some notations:xl
: the optimal integer solution of the linear fractional program(Pl):max⁡{Z1(x)∣x∈Xl,Xl⊆X}; note that instead of Z1, one can similarly consider the problem (Pl) with any of the remaining objectives Zi, i∈{2,…,k}. Moreover, in the new method that we will state later, the fractional objective function of (Pl) will be replaced by a linear one;Bl (resp., Nl): the set of indices of basic variables (resp., nonbasic variables) of xl;γ¯i: the reduced gradient vector of theith objective. It is defined by
(2)γ¯i=β¯ic¯i-α¯id¯i,where β¯i, α¯i, c¯i, and d¯i are updated values obtained from the optimal simplex tableau of (Pl);H
l: the set defined by {j∈Nl∣∃i∈{1,2,…,k};γ¯ji>0}∪{j∈Nl∣γ¯ji=0,∀i∈{1,2,…,k}};X
l
+
1: the set defined by {x∈Xl∣∑j∈Hlxj≥1}.Theorem 1.
Suppose thatHl≠∅ at the current integer solution xl. If x is an integer efficient solution in domain Xl∖{xl} then x∈Xl+1.For proof, see [2].Definition 2.
Anefficient cut is a constraint added to the model and does not eliminate any feasible efficient integer solutions.Corollary 3.
Suppose thatHl≠∅ at the current integer solution xl; then the following constraint is an efficient cut:
(3)∑j∈Hlxj≥1.See [2] for proof.Proposition 4.
IfHl=∅ at the current integer solution xl then Xl∖{xl} is an explored domain.The proof is also in [2].


## 3. Description of the Method

In this section, we describe some improvements that we will bring to Chergui and Moulaï’s method [2] but first we recall briefly its principle and its limitations.Let us consider a multiobjective integer linear fractional program in the form of(MOILFP). The method of Chergui and Moulaï manages a search tree consisting of nodes. At each node (say l) the following linear fractional program is solved using Cambini and Martein's method [17] or the dual simplex method:
(4)(Pl):max⁡{Z1(x)∣x∈Xl},whereXl⊆X and X0=X.(i)
If this problem is infeasible, then the nodel is fathomed.(ii)
On the contrary case, if the obtained optimal solution is not integer, a branching process is performed. Otherwise, the setHl defined above is determined. If it is empty then the node l is fathomed; else a new node is created and the corresponding problem is obtained by adding to (Pl) the efficient cut constructed from Hl.The procedure ends when all the created nodes have been examined.As it can be seen, the node fathoming rules are reduced to the two following cases: the problem(Pl) is infeasible and Hl is empty which happens very rarely (see Table 7) during the search process. Since the performance of this method depends, among other things, on its ability to avoid exploring nodes of the search tree leading to nonefficient solutions, we propose to add at each node l the two new fathoming conditions given below.(i)
The ideal point, sayIdl, of the multiobjective linear fractional program (MOFPl):max⁡{Z1(x),…,Zk(x)∣x∈Xl} is dominated by at least one of the potentially nondominated points already found.(ii)
There existsi∈{1,…,k} such that Idil<Ndi, where Ndi is theith component of the original problem's nadir point.Note that the use of the last rule is more appropriate in the biobjective case since the nadir point can be easily computed using the payoff table.On the other hand, as we need to generate a feasible solution at each step of the method and not necessarily the solution which optimizes one of the fractional objective functions, we suggest to replace for each nodel the linear fractional program by the following linear program (we keep the same notation for the new problem):(5)(Pl):max⁡{c1x-λd1x∣x∈Xl},
where λ is the parameter of Seshan and Tikekar’s method [18] taken at the optimum when the first fractional objective is optimized under the integer feasible set. The idea behind this choice is to start with a solution close to an efficient one (in our case, that with the maximum value of Z1). However, any linear objective function can be used in (Pl) since the purpose is to obtain a feasible solution; the only disadvantage is that the starting solution will be any vertex of the feasible set which may increase the iteration number.Handling linear programs will not only reduce the number of simplex iterations performed but also facilitate the use of the dual simplex algorithm whenever a constraint is added to a node problem.By taking into account the suggested changes and by adopting the same notations as above, we obtain the following algorithm that generates the entire efficient setEff of (MOILFP).The AlgorithmStep  0 (initialization). Denote by L the list of untreated problems. Set Eff to the empty set and L to the linear program (P0). Compute the nadir point Nd of (MOILFP) (for the biobjective case, the payoff table is used and the individual optimization of both fractional objectives is performed by Seshan and Tikekar’s method [18]).Step  1 (problem selection and resolution). If L is empty, return the efficient set Eff and terminate. Otherwise, select the linear program with the greatest index l in L. Solve the problem (Pl) using the simplex or the dual simplex method; remove (Pl) from L and go to Step 2.Step  2 (Fathoming). If (Pl) is infeasible, go to Step 1.If not, letxl be its optimal solution, Bl (resp., Nl) the set of indices of basic variables (resp., nonbasic variables) of xl and Zl the corresponding criterion vector.IfZl is not dominated, go to Step 3. Else, compute the ideal point Idl of (MOFPl) as follows.The individual optimization of each fractional objectivei under Xl is done by adding three rows to the optimal tableau of (Pl); the first and second rows correspond, respectively, to the numerator and denominator of the fractional function i written in the basis Bl and the last one to the reduced gradient vector of theith objective γ¯i (see (2)). The ordinary simplex pivot operations are then applied to the new table's rows except the last one which is modified using (2) until the optimal condition is met; that is, γ¯ji≤0,  ∀j∈Nl.IfIdl is dominated by the criterion vector of at least one solution of Eff or if there exists i∈{1,…,k} such that Idil<Ndi then fathom the corresponding node and go to Step 1. On the contrary case, go to Step 3.Step  3 (branching). If xl is integer, go to Step 4; else select the most fractional variable xjl=αj. Create and add to L two problems identical to (Pl) with the additional constraint xj≥⌊αj⌋+1 in the first one and xj≤⌊αj⌋ in the second; go to Step 1.Step  4 (cut generating). Update Eff: If there does not exist x∈Eff such that the corresponding criterion vector dominates Zl then add xl to Eff and remove all solutions for which the criterion vector is dominated by Zl.Determine the setHl. If Hl is empty, go to Step 1. In case that Hl=Nl, generate the incident edge Ep with the greatest number of integer solutions and update Eff; set Hl=Nl∖{p}. Add to L the problem obtained by extending (Pl) with the efficient cut of (3) and go to Step 1.


## 4. Numerical Example

Consider the following MOILFP problem:(6)(MOILFP){max⁡Z1=30x1+50x2+94x3+94x4+27x5+19x6+91x7-898x1+40x2+78x3+56x4+29x5+23x6+43x7+4max⁡Z2=14x1+46x2+76x3+65x4+46x5+7x6+35x7+212x1+18x2+40x3+51x4+70x5+98x6+50x7+49s.t.21x1+3x2+8x3-9x4-x5+26x6+34x7≤4133x1+28x2+29x3+14x4+9x5-7x6-9x7≤4928x1-x2+40x3+38x4+28x5+43x6+35x7≤106x1,x7¯∈N.Following the steps described above to solve (MOILFP), we find the efficient set given in Table 2.During the construction of the search tree, 50 nodes were created: the root node, 36 nodes of the branching process, and 13 of the cutting process; 19 nodes among them were fathomed. Only 17 solutions were generated from a total of 42 feasible solutions (the entire feasible set).In Table1, we compare the final results obtained for the present example using Chergui and Moulaï’s method [2] and its improved version.Table 1
Comparison between Chergui and Moulai's method and its improved version on this example.
Old method
New method
Number of efficient sol.
7
7
Number of integer sol. generated/number feasible sol.
32/42
17/42
Number of created nodes
223
50
Number of simplex iterations
610
148Table 2
The efficient set of the problem.
x
Z
(
x
)
(
0
,
0
,
0
,
0
,
0
,
0
,
1
)
T
(
83
47
,
56
99
)
T
(
0
,
0
,
0
,
1
,
0
,
0
,
1
)
T
(
177
103
,
121
150
)
T
(
0
,
0
,
1
,
1
,
0
,
0
,
0
)
T
(
30
23
,
81
70
)
T
(
0
,
1
,
0
,
1
,
0
,
0
,
1
)
T
(
227
143
,
167
168
)
T
(
0
,
1
,
0
,
1
,
0
,
0
,
0
)
T
(
34
25
,
66
59
)
T
(
0
,
2
,
0
,
0
,
0
,
0
,
1
)
T
(
183
127
,
148
135
)
T
(
0
,
0
,
0
,
2
,
0
,
0
,
0
)
T
(
45
29
,
1
)
TIn what follows, we give the calculation details for some nodes of the problem’s search tree.Node 0. We first calculate the payoff table and thus the nadir point by simply finding the individual optima of both objectives with Seshan and Tikekar’s method. The results obtained are shown in Table 3.Table 3
Results obtained by Seshan and Tikekar's method.
Z
1
Z
2
λ
max
⁡
Z
1
83
47
2
2
2
83
47
56
99
83
47
max
⁡
Z
2
83
47
2
2
2
30
23
81
70
81
70The nadir point isNd=(30/23,56/99).We then define the linear program(P0) as max⁡{c1x-(83/47)d1x∣x∈X0}, where c1=(30,50,94,94,27,19,91), d1=(98,40,78,56,29,23,43), x=(x1,…,x7)T, and X0 is the set of x∈R7 satisfying the three constraints of the (MOILFP) problem.Recall that the objective function of(P0) taken here c1x-(83/47)d1x can be replaced by any linear objective function.SetL={P0} and Eff=∅. The resolution of (P0) gives the optimal solution x0=(0,0,0,0,0,0,41/34)T which is not integer. Since only x7 is fractional this is the variable that we branch on. We obtain the two following subproblems:
(7)Subproblem1:(P1){(P0)x7≥2Subproblem2:(P2){(P0)x7≤1,
where L={P1,P2}.Node 2. Select from L the problem (P2). The resolution of this problem yields the optimal integer solution x2=(0,0,0,0,0,0,1)T with the corresponding criterion vector Z2=(83/47,56/99)T. Then Eff={x2}. The set of nonbasic variables N2={1,2,3,4,5,6,11} and the reduced gradient vectors are given in Table 4.Table 4
Reduced gradient vectors corresponding to Node 2.
N
2
x
1
x
2
x
3
x
4
x
5
x
6
x
11
γ
¯
1
−6724
−970
−2056
−230
−1138
−1016
−708
γ
¯
2
1274
3546
5284
3579
634
−4795
−665We haveH2={1,2,3,4,5}≠N2. We create a new problem (P3) by adding to (P2) the constraint x1+x2+x3+x4+x5≥1. Consider L={P1,P3}.Node 18. The potentially nondominated solutions found so far are (83/47,56/99)T, (177/103,121/150)T, and (43/30,43/50)T.The resolution of(P18) gives the optimal solution (1,0,0,0,0,0,0)T with the criterion vector (11/51,35/51)T which is dominated then Eff remains the same.We haveId118=121/281<Nd1=30/23; we then fathom the Node 18.Node 29. The potentially nondominated solutions found so far are (83/47,56/99)T, (177/103,121/150)T, (43/30,43/50)T, and (30/23,81/70)T.The resolution of(P29) gives the optimal solution (0,0,1,0,1,0,1)T with the criterion vector (102/77,178/209)T. This latter is dominated by (43/30,43/50)T; therefore, Eff remains the same. Here, the local ideal point Id29 is not dominated so we proceed to the construction of the set H29: see Table 5.Table 5
Reduced gradient vectors corresponding to Node 29.
N
29
x
1
x
2
x
6
x
8
x
18
x
19
x
20
γ
¯
1
−52290
−5734
−47474
−1758
−15500
−54530
−18874
γ
¯
2
−57196
−2128
−89977
−2846
−14004
−98349
−30121Since we haveH29=∅, we fathom the Node 29.Node 43. The potentially nondominated solutions found so far are (83/47,56/99)T, (177/103,121/150)T, (30/23,81/70)T, (227/143,167/168)T, and (34/25,66/59)T.The resolution of(P43) gives the optimal solution (0,1,0,1,1,0,1)T with the criterion vector (127/86,213/238)T which is dominated; then Eff remains the same.We have thatId43=(127/86,309/331)T is dominated by (227/143,167/168)T; we then fathom the Node 43.


## 5. Computational Results

The method described in Section3 and the one presented in [2] (referred in Table 6 as New Algorithm and Old Algorithm, respectively) were implemented in a Matlab 7.0 environment and tested on randomly generated MOILFP problems. The data are uncorrelated integers uniformly distributed in the interval [1,99] for the numerator and denominator coefficients, [-10,50] for the numerator constant, [1,50] for the denominator constant, and [-10,50] for constraints coefficients. For each constraint, the right-hand side value was set to α% of the sum of its coefficients. For each instance (n,m,k) (n is the number of variables, m the number of constraints, and k the number of objectives), a series of 10 problems were solved. Computational experiments were carried out on a computer with 2,53 GHz Core i3 Processor and 3 GB of memory. Table 6 summarizes the obtained results where mean and maximum number of created nodes (Tree Size), number of efficient solutions (|Eff|), and execution time in seconds are reported. Thex mark in the table refers to more than 2 hours of execution time in the CPU Time column and a number of created nodes of order of millions in Tree Size column.Table 6
The results obtained by both new and old methods on random MOILFPs.
n
m
k
α%
New algorithm
Old algorithm
CPU Time (sec)
Tree Size
CPU Time (sec)
Tree size
|
Eff
|
Mean
Max
Mean
Max
Mean
Max
Mean
Max
Mean
Max
20
5
2
25
6,59
23,19
835,20
2803
264,37
334,41
38220,80
47461
13,10
18
20
10
2
25
1,99
4,13
279,30
482
103,94
175,14
10798,30
18766
7,40
12
30
5
2
16,67
44,15
181,59
3050,30
12703
x
x
x
x
18,60
42
30
10
2
16,67
18,78
63,32
1201,90
3151
x
x
x
x
11,90
25
40
10
2
12,5
69,12
154,84
2717,60
5642
x
x
x
x
15,10
23
60
10
2
10
972,01
3109,24
18568,70
54107
x
x
x
x
20,20
39
30
5
3
16,67
439,07
851,79
14023,30
25618
x
x
x
x
80,30
164
40
10
3
12,5
693,44
1597,12
15013
37819
x
x
x
x
78,40
213
30
10
4
16,67
448,76
850,53
11202,30
19734
x
x
x
x
189,30
335Table 7
The results of the first type instance concerning the number of saturated nodes using each of the 4 fathoming rules.
Problem number
Number of saturated nodes using
H
l
Nadir point
Ideal point
Infeasibility
Total
1
0
16
65
37
118
2
0
38
5
33
76
3
4
13
234
131
382
4
2
34
512
612
1160
5
3
32
362
320
717
6
3
4
115
68
190
7
0
59
120
105
284
8
2
22
139
67
230
9
0
3
47
40
90
10
3
35
55
56
149Due to the important amount of information to be provided, we have not presented the number of nodes saturated corresponding to each of the four fathoming rules used in our method. However, we can give in Table7, as an example, what we have found for the 10 problems treated of the first type instance that is with 20 variables, 5 constraints, and 2 objectives.As expected, the results obtained by the new method are much better compared to those obtained by the original one in all the treated instances. Indeed, the old method takes more than two hours of execution time for a number of variables exceeding twenty whereas the new one does not reach half an hour for sixty variables (972,01 sec. on average). One can also notice the influence of the use of nadir and ideal points in the search tree size; for example, in the biobjective case, the number of nodes of the search tree corresponding to a MOILFP problem with twenty variables is of order of tens of thousands on average for the old method; this number of nodes is attained only for sixty variables and more for the new method. We should also notice that the method we propose is more suited for the biobjective case; this is because, first, the computation of the nadir point can be done quickly using the payoff table and, second, the less calculation performed (two reoptimizations) to obtain the ideal point at each stage.


## 6. Conclusion

In this paper, we have presented an improvement of Chergui and Moulaï’s method [2] which generates the whole efficient set of MOILFP problems. One of the main changes that we have made was the addition of two fathoming rules using both ideal and nadir points resulting in a remarkable computational savings. Also, we have proposed to linearize one of the fractional objective functions to solve linear programs as subproblems rather than fractional linear programs which facilitates the use of the dual simplex algorithm and reduces the number of simplex iterations performed. We should finally point out that this method does not require any nonlinear optimization and its tree structure can be exploited for construction of a parallel algorithm to handle large scale problems.



---

*Source: 306456-2014-07-01.xml*