# An Exact Method for a Discrete Multiobjective Linear Fractional Optimization

Authors: Mohamed El-Amine Chergui; Mustapha Moulaï
Journal: Journal of Applied Mathematics and Decision Sciences
 (2008)

---

## Abstract

Integer linear fractional programming problem with multiple objective (MOILFP) is an important field of research and has not received as much attention as did multiple objective linear fractional programming. In this work, we develop a branch and cut algorithm based on continuous fractional optimization, for generating the whole integer efficient solutions of the MOILFP problem. The basic idea of the computation phase of the algorithm is to optimize one of the fractional objective functions, then generate an integer feasible solution. Using the reduced gradients of the objective functions, an efficient cut is built and a part of the feasible domain not containing efficient solutions is truncated by adding this cut. A sample problem is solved using this algorithm, and the main practical advantages of the algorithm are indicated.


---

## Body

## 1. Introduction

Fractional programming has been widely reviewed by
many authors (Schaible [1], Nagih, and Plateau [2]) and there are entire books
and chapters devoted to this subject (Craven [3], Stancu-Minasian [4], Horst et al. [5], and Frenk and
Schaible [6]). A
bibliography, with 491 entries presented by Stancu-Minasian [7], attracts our attention to
the amount of work that has been done in the field in recent years. This
bibliography of fractional programming is a continuation of five previous
bibliographies by the author [8]. Schaible [1] has published a comprehensive review of the work in
fractional programming, outlining some of its major developments.
Stancu-Minasian's textbook [4] contains the state-of-the-art theory and practice of
fractional programming, allowing the reader to quickly become acquainted with
what has been done in the field.The mathematical optimization problems with a goal
function that is a ratio of two linear functions have many applications: in
finance (corporate planning, bank balance sheet management), marine
transportation, water resources, health care, and so forth. Indeed, in such
situations, it is often a question of optimizing a ratio debt/equity, output/employee,
actual cost/standard cost, profit/cost, inventory/sales, risk-assets/capital,
student/cost, doctor/patient, and so on subject to some constraints [9]. In addition, if the
constraints are linear, we obtain the linear fractional programming (LFP)
problem.Different approaches have been proposed in the
literature to solve both continuous LFP and integer linear fractional
programming (ILFP) problems. These can be divided in studies that have
developed solution methods (e.g., [4, 10–14]) and those which concentrated on applications (e.g.,
[4, 6]).The multiple objective linear fractional programming
(MOLFP) problem is one of the most popular models used in multiple criteria
decision making. Numerous studies and applications have been reported in the
literature in hundreds of books, monographs, articles, and books' chapters. For
an overview of these studies and applications, see, for instance, [4, 7–9, 15, 16, 17, 18, 19, 20, 21, 22], and references therein.Contrary to the multiple objective linear programming
(MOLP) problem, Steuer [9] shows that the efficient solutions set in MOLFP
problem is not necessarily closed; some interior points of the feasible
solutions set may be efficient, while others are not, and efficient extreme
solutions need not all be connected by a path of efficient edges. It becomes
difficult to generate the whole efficient solutions. As the efficient set may
be too difficult to determine, Kornbluth and Steuer [20] propose an algorithm for
MOLFP problem that generates the set of the so-called weakly efficient
solutions by means of a simplex-based algorithm. A new technique to optimize a
weighted sum of the linear fractional objective functions is proposed by Costa
[19]. This technique
generates only one nondominated solution of the MOLFP problem associated with a
given weight vector. At each stage of the technique, the nondominated domain is
divided in two subdomains and each of them is analyzed in order to discard the
one not containing the nondominated solutions. The process ends when the
remaining domains are so little that the differences among their nondominated
solutions are lower than a predefined error.In this paper, we have proposed a technique for
generating the efficient set of the MOLFP problem with integer variables by
using all the decision criteria in an active way. This last problem, called
MOILFP, is more difficult to solve than the MOLFP problem taking into account
the integrity of variables. Indeed, finding all efficient solutions of multiobjective
combinatorial optimization problems is, in general,NP-complete [23].We should like to point out that the MOILFP problem
has not received as much attention as did the multiple objective integer linear
programming (MOILP) problem, what justified our interest to study this problem.In [15], a considerable computation is necessary to obtain an
optimal integer solution of an ILFP problem in the first stage, since the
authors used a branch and bound method (see, e.g., [24]). In our method, we use
only the Cambini and Martein's [10] method to obtain an optimal solution for the relaxed
ILFP problem and an integer solution is detected by the branching process of
the branch and bound method. In addition, a cutting plane is constructed taking
into account all the criteria. In this manner, we are able to eliminate not
only noninteger solutions of the feasible domain, but also integer solutions
which are not efficient. Thus our method avoids to scan all the integer
feasible solutions of the problem.The notations and definitions used throughout this
work are presented in Section2. In Section 3, the algorithm generating all
efficient solutions for the MOILFP problem is developed and the main
theoretical results are proposed. An illustrative example is given in Section 4
and a computational experience is reported in Section 5. Section 6 provides
some concluding remarks.


## 2. Problem Formulation

The purpose of this paper is to develop an exact
method for solving themultiple objective integer linear fractional program (MOILFP):(2.1)(p){maxZ1(x)=c1x+α1d1x+β1maxZ2(x)=c2x+α2d2x+β2⋮maxZk(x)=ckx+αkdkx+βkx∈S,xinteger where k≥2;ci,di are 1×n vectors; αi,βi  are scalars for each i∈{1,2,…,k}; S={x∈ℝn∣Ax≤b,x≥0}; A is an m×n real matrix; and b∈ℝm.
Throughout this article, we assume that S is a nonempty, compact polyhedron set in ℝn and dix+βi>0 over S for all i∈{1,2,…,k}.Many approaches for analyzing and solving the MOLFP
problem use the concept of efficiency. A pointx∈ℝn is called an efficient solution, or Pareto-optimal solution, for MOLFP problem when x∈S,
and there exists no point y∈S such that Zi(y)≥Zi(x), for all i∈{1,…,k} and Zi(y)>Zi(x) for at least one i∈{1,…,k}.
Otherwise, x is not efficient and the vector Z(y)dominates the vector Z(x),
where Z(x)=(Zi(x))i=1,…,k.The approach adopted in this work for detecting all
integer efficient solutions of problem(P) is based on solving a linear fractional
programming problem, at each stage l:(2.2)(p1)maxZ1(x)=c1x+α1d1x+β1,x∈Sl, with S0=S and without the integrity constraint of
variables. Note that in place of Z1,
one can similarly consider the problem (Pl) with another objective Zi for any i∈{2,…,r}.If the optimal solution of(Pl) is integer, it is compared to all of the
potentially efficient solutions already found and the set of efficient
solutions is actualized. The growth direction of each criterion is determined
by using its gradient. The method uses this information to deduce a cut able to
delete integer solutions which are not efficient for the problem (P) and determines a new integer solution. In the
case where this optimal solution is not integer, two new linear fractional
programs are created by using the branching process well known in branch and
bound method. Each of them will be solved like the problem (Pl).To this aim—letxl∗ be the first integer solution obtained after
solving problem (Pl) by using, eventually, the branching process—one defines Bl as the set of indices of basic variables and Nl as the set of indices of nonbasic variables of xl∗.
Let γji¯ be the jth component of the reduced gradient vector γi¯ defined by (2.3) for each fixed i∈{1,2,…k};(2.3)γi¯=βi¯ci¯−αi¯di¯,where ci¯, di¯, αi,¯ and βi¯ are updated values. Let us note that the
gradient vector of Zi and the corresponding reduced gradient vector γi¯ for each fixed index i,i∈{1,2,…,k}, have the same sign. Thus calculating γi¯ is enough to determine the growth direction
for each criterion.In order to give the mathematical expression of the
cut, we define the following sets atxl∗:
(2.4)Hl={j∈Nl∣∃i∈{1,2,…,k};γji¯>0}∪{j∈Nl∣γji¯=0,∀i∈{1,2,…,k}},(2.5)Sl+1={x∈Sl∣∑j∈Hlxj≥1}.Anefficient cut is a cut which removes only
nonefficient integer solutions.In Section3, the approach to solve program (P) is presented.


## 3. Methodology for Solving MOILFP

In this section, an exact method based on the
branching process and using an efficient cut for generating all integer
efficient solutions for problem(P) is presented. First of all, the proposed
method is presented in detail, the algorithm for solving the multiple objective
integer linear fractional programming problems is then described. We finish the
section with the theoretical results which prove the convergence of the
algorithm.


### 3.1. Description of the Method

Starting with an optimal solution of an LFP problem,
the domain of feasible integer solutions is partitioned into subdomains using
the principle of branching to the search for integer solutions. As soon as an
integer solution is found in a new domain, it is compared to solutions already
found and hence the set of all the potentially efficient solutions is updated.
An efficient cut is then added for deleting integer solutions that are not
efficient. To construct this cut, the growth directions of the criteria are
used. The search for the efficient solutions is made in each subdomain created.
A given domain contains no efficient solutions when none criterion can grow.
This last is said an explored domain. The search for the efficient solutions is
stopped only if all created domains were explored domains.First, Cambini and Martein's [10] algorithm is used for
solving the following continuous linear fractional program:(3.1)(p){maxZ1(x)=c1x+α1d1x+β1,x∈S0.This is based on the concept of optimal level
solution. A feasible pointx¯ is an optimal level solution for the linear
fractional program (P0),
if x¯ is optimal for the linear
program:
(3.2)(Px¯){max(c1x+α1),d1x=d1x,¯x∈S0.If, in addition,x¯ is a vertex of the feasible solutions set S0,x¯ is said to be a basic optimal level solution.
Obviously, an optimal solution for the linear fractional program (P0) is a basic optimal level solution. According
to this, the algorithm generates a finite sequence of basic optimal level
solutions, the first one, say x0,
is an optimal solution for the linear program:(3.3)min(d1x+β1),x∈S0.Ifx0 is unique, then it is also a basic optimal
level solution for program (P0),
otherwise, solve the linear program (Px0) to obtain a basic optimal level solution.The solution of the program(P0) obtained in a finite sequence of optimal level
solutions is optimal if and only if γj1¯≤0 for all j∈J01,
where(3.4)J01={j∈N0∣dj1¯>0}.Otherwise, there exists an index j∈J01 for which γj1¯>0.
The nonbasic variable xr,r∈J01, which must enters the basis is indicated by
the index r such that(3.5)cr1¯dr1¯=max{cj1¯dj1¯,j∈J01}.The original format of the objectives fractional
functions and original structure of the constraints is maintained and the
iterations are carried out in an augmented simplex table which includesm+3k rows. The first m rows correspond to the original constraints,
the m+3(i−1)+1 and m+3(i−1)+2 rows correspond to the numerator and
denominator of the objective fractional function Zi,i∈{1,2,…,k},
of program (P),
respectively, and the m+3i row corresponds to the γli¯ vector at step l.At each stage of the algorithm, all the rows are
modified as usual through the pivot operation when the nonbasic variablexr,r∈J01, enters the basis, except the m+3i rows, for i∈{1,2,…,k}, which are modified using the γli¯ formula (2.3).Each program(Pl) corresponds to node l in a structured tree. A node l of the tree is fathomed if the corresponding
program (Pl) is not feasible or Hl=∅ (explored domain).If the optimal solutionx˜l of program (Pl) is not integer, let xj be one component of x˜l such that xj=αj, where αj is a fractional number. The node l of the tree is then separated in two nodes
which are imposed by the additional constraints xj≤⌊αj⌋ and xj≥⌊αj⌋+1, where ⌊αj⌋ indicates the greatest integer less than αj.
In each node, the linear fractional program obtained must be solved, until an
integer feasible solution is found. In presence of an integer feasible
solution, the efficient cut ∑j∈Hlxj≥1 is added to the program and the new program is
solved using the dual simplex method. The method terminates when all the
created nodes are fathomed.


### 3.2. Algorithm

The algorithm
generating the set of all integer efficient solutions of program(P) is presented in the following steps. The nodes
in the tree structure are treated according to the backtracking principle.Step 1.
Initialization:  l=0, create the first node with the program    (P0).  Eff=∅;
(integer-efficient set of program   (P)Step 2.
General step:   as long as a nonfathomed node exists in the tree, do:   choose the node not yet fathomed, having the greatest
number   l,  solve the corresponding linear fractional program (Pl) using the dual simplex method and the Cambini
and Martein's method. (Initially, for solving program (P0), only the Cambini and Martein's method is
used).
If program(Pl) has no feasible solutions, then the
corresponding node is fathomed.
Else, letx˜l be an optimal solution. If x˜l is not integer, go to Step 3, else go
to Step 4.Step 3.
Branching process   (partition of the problem into mutually disjoint and jointly
exhaustive sub-problems): choose one coordinate xj of x˜l such that xj:=αj,
with αj fractional number, and separate the actual
node l of the tree in two nodes k, k≥l+1,
and h, h≥l+1, h≠k.
In the current simplex table, the constraintxj≥⌊αj⌋ is added and a new domain is considered in
node k and similarly, the constraint xj≥⌊αj⌋+1 is added to obtain another domain in node h.
(Each created program must be solved using the same process until an integer
feasible solution is found),  go to Step 2.Step 4.
Update the setEff: if Z(x˜l) is not dominated by Z(x) for all x∈Eff,
then Eff:=Eff∪{x˜l}.
If there exists x∈Eff such that Z(x˜l) dominates Z(x),
then Eff:=Eff∖{x}∪{x˜l}.
Construct the efficient cut: determine the sets Nl and Hl.
IfHl=∅,
then the corresponding node is fathomed. Go to Step 2.
Else, add the efficient cut∑j∈Hlxj≥1 to the program (Pl).
Go to Step 2.The following theorems show that the algorithm
generates all integer efficient solutions of program(P) in a finite number of stages.
Theorem 3.1.
Suppose
thatHl≠∅ at the current integer solution xl∗.
If x is an integer efficient solution in domain Sl∖{xl∗},
then x∈Sl+1.Proof.
Letx be an integer solution in domain Sl∖{xl∗} such that x∉Sl+1,
then ∑j∈Hlxj=0,
that implies xj=0 for all index j∈Hl.
From the simplex table corresponding to the optimal
solutionxl∗,
the criteria are evaluated by
(3.6)Zi(x)=∑j∈Nlcji¯xj+αi¯∑j∈Nldji¯xj+βi¯fori∈{1,…,k},where (3.7)αi¯βi¯=Zi(xl∗). Then we can write (3.8)Zi(x)=∑j∈Nl∖Hlcji¯xj+αi¯∑j∈Nl∖Hldji¯xj+βi¯,∀i∈{1,…,k}.
In the other hand,γji¯=βi¯cji¯−αi¯dji¯≤0, for all index j∈Nl∖Hl and γji¯=βi¯cji¯−αi¯dji¯<0 for at least one criterion, implies that cji¯≤αi¯dji¯/βi¯ for all j∈Nl∖Hl because βi¯=dixl∗+βi>0 for all criterion i∈{1,…,k}.
The decision variables being nonnegative, we obtain cji¯xj≤(αi¯dji¯/βi¯)xj for all j∈Nl∖Hl and hence (3.9)∑j∈Nl∖Hlcji¯xj≤∑j∈Nl∖Hlαi¯dji¯βi¯xj⇒∑j∈Nl∖Hlcji¯xj+αi¯≤∑j∈Nl∖Hlαi¯dji¯βi¯xj+αi¯.
For any criterionZi, i∈{1,…,k},
the following inequality is obtained (3.10)Zi(x)=∑j∈Nl∖Hlcji¯xj+αi¯∑j∈Nl∖Hldji¯xj+βi¯⇒Zi(x)≤∑j∈Nl∖Hl(αi¯dji¯/βi¯)xj+αi¯∑j∈Nl∖Hldji¯xj+βi¯⇒Zi(x)≤(αi¯/βi¯)(∑j∈Nl∖Hldji¯xj+βi¯)∑j∈Nl∖Hldji¯xj+βi¯⇒Zi(x)≤αi¯βi¯⇒Zi(x)≤Zi(xl∗).
Consequently,Zi(x)≤Zi(xl∗) for all i∈{1,…,k} and Zi(x)<Zi(xl∗) for at least one index. Hence Z(xl∗) dominates Z(x) and the solution x is not efficient.Corollary 3.2.
Suppose thatHl≠∅ at the current integer solution xl∗.
Then the constraint ∑j∈Hlxj≥1 is an efficient cut.Proof.
By the
above theorem, no efficient solution is deleted when the constraint∑j∈Hlxj≥1 is added. We can say that this is an efficient
valid constraint. In the other hand, xl∗ does not satisfy this constraint since xj=0,
for all j∈Nl.
We conclude that the constraint is an efficient cut.Proposition 3.3.
IfHl=∅ at the current integer solution xl∗,
then Sl∖{xl∗} is an explored domain.Proof.
Hl=∅ means that xl∗ is an optimal integer solution for all
criterion, hence xl∗ is an ideal point in the domain Sl and Sl∖{xl∗} does not contain efficient solutions.Theorem 3.4.
The described algorithm terminates
in a finite number of iterations and generates all the efficient solutions of
program(P).Proof.
The setS of feasible solutions of problem (P),
being compact, contains a finite number of integer solutions. Each time an
optimal integer solution xl∗ is calculated, the efficient cut is added.
Thus according to the above theorem and corollary, at least the solution xl∗ is eliminated when one studies any subproblem (Pk),k>l,
but no efficient solution is deleted.


## 3.1. Description of the Method

Starting with an optimal solution of an LFP problem,
the domain of feasible integer solutions is partitioned into subdomains using
the principle of branching to the search for integer solutions. As soon as an
integer solution is found in a new domain, it is compared to solutions already
found and hence the set of all the potentially efficient solutions is updated.
An efficient cut is then added for deleting integer solutions that are not
efficient. To construct this cut, the growth directions of the criteria are
used. The search for the efficient solutions is made in each subdomain created.
A given domain contains no efficient solutions when none criterion can grow.
This last is said an explored domain. The search for the efficient solutions is
stopped only if all created domains were explored domains.First, Cambini and Martein's [10] algorithm is used for
solving the following continuous linear fractional program:(3.1)(p){maxZ1(x)=c1x+α1d1x+β1,x∈S0.This is based on the concept of optimal level
solution. A feasible pointx¯ is an optimal level solution for the linear
fractional program (P0),
if x¯ is optimal for the linear
program:
(3.2)(Px¯){max(c1x+α1),d1x=d1x,¯x∈S0.If, in addition,x¯ is a vertex of the feasible solutions set S0,x¯ is said to be a basic optimal level solution.
Obviously, an optimal solution for the linear fractional program (P0) is a basic optimal level solution. According
to this, the algorithm generates a finite sequence of basic optimal level
solutions, the first one, say x0,
is an optimal solution for the linear program:(3.3)min(d1x+β1),x∈S0.Ifx0 is unique, then it is also a basic optimal
level solution for program (P0),
otherwise, solve the linear program (Px0) to obtain a basic optimal level solution.The solution of the program(P0) obtained in a finite sequence of optimal level
solutions is optimal if and only if γj1¯≤0 for all j∈J01,
where(3.4)J01={j∈N0∣dj1¯>0}.Otherwise, there exists an index j∈J01 for which γj1¯>0.
The nonbasic variable xr,r∈J01, which must enters the basis is indicated by
the index r such that(3.5)cr1¯dr1¯=max{cj1¯dj1¯,j∈J01}.The original format of the objectives fractional
functions and original structure of the constraints is maintained and the
iterations are carried out in an augmented simplex table which includesm+3k rows. The first m rows correspond to the original constraints,
the m+3(i−1)+1 and m+3(i−1)+2 rows correspond to the numerator and
denominator of the objective fractional function Zi,i∈{1,2,…,k},
of program (P),
respectively, and the m+3i row corresponds to the γli¯ vector at step l.At each stage of the algorithm, all the rows are
modified as usual through the pivot operation when the nonbasic variablexr,r∈J01, enters the basis, except the m+3i rows, for i∈{1,2,…,k}, which are modified using the γli¯ formula (2.3).Each program(Pl) corresponds to node l in a structured tree. A node l of the tree is fathomed if the corresponding
program (Pl) is not feasible or Hl=∅ (explored domain).If the optimal solutionx˜l of program (Pl) is not integer, let xj be one component of x˜l such that xj=αj, where αj is a fractional number. The node l of the tree is then separated in two nodes
which are imposed by the additional constraints xj≤⌊αj⌋ and xj≥⌊αj⌋+1, where ⌊αj⌋ indicates the greatest integer less than αj.
In each node, the linear fractional program obtained must be solved, until an
integer feasible solution is found. In presence of an integer feasible
solution, the efficient cut ∑j∈Hlxj≥1 is added to the program and the new program is
solved using the dual simplex method. The method terminates when all the
created nodes are fathomed.


## 3.2. Algorithm

The algorithm
generating the set of all integer efficient solutions of program(P) is presented in the following steps. The nodes
in the tree structure are treated according to the backtracking principle.Step 1.
Initialization:  l=0, create the first node with the program    (P0).  Eff=∅;
(integer-efficient set of program   (P)Step 2.
General step:   as long as a nonfathomed node exists in the tree, do:   choose the node not yet fathomed, having the greatest
number   l,  solve the corresponding linear fractional program (Pl) using the dual simplex method and the Cambini
and Martein's method. (Initially, for solving program (P0), only the Cambini and Martein's method is
used).
If program(Pl) has no feasible solutions, then the
corresponding node is fathomed.
Else, letx˜l be an optimal solution. If x˜l is not integer, go to Step 3, else go
to Step 4.Step 3.
Branching process   (partition of the problem into mutually disjoint and jointly
exhaustive sub-problems): choose one coordinate xj of x˜l such that xj:=αj,
with αj fractional number, and separate the actual
node l of the tree in two nodes k, k≥l+1,
and h, h≥l+1, h≠k.
In the current simplex table, the constraintxj≥⌊αj⌋ is added and a new domain is considered in
node k and similarly, the constraint xj≥⌊αj⌋+1 is added to obtain another domain in node h.
(Each created program must be solved using the same process until an integer
feasible solution is found),  go to Step 2.Step 4.
Update the setEff: if Z(x˜l) is not dominated by Z(x) for all x∈Eff,
then Eff:=Eff∪{x˜l}.
If there exists x∈Eff such that Z(x˜l) dominates Z(x),
then Eff:=Eff∖{x}∪{x˜l}.
Construct the efficient cut: determine the sets Nl and Hl.
IfHl=∅,
then the corresponding node is fathomed. Go to Step 2.
Else, add the efficient cut∑j∈Hlxj≥1 to the program (Pl).
Go to Step 2.The following theorems show that the algorithm
generates all integer efficient solutions of program(P) in a finite number of stages.
Theorem 3.1.
Suppose
thatHl≠∅ at the current integer solution xl∗.
If x is an integer efficient solution in domain Sl∖{xl∗},
then x∈Sl+1.Proof.
Letx be an integer solution in domain Sl∖{xl∗} such that x∉Sl+1,
then ∑j∈Hlxj=0,
that implies xj=0 for all index j∈Hl.
From the simplex table corresponding to the optimal
solutionxl∗,
the criteria are evaluated by
(3.6)Zi(x)=∑j∈Nlcji¯xj+αi¯∑j∈Nldji¯xj+βi¯fori∈{1,…,k},where (3.7)αi¯βi¯=Zi(xl∗). Then we can write (3.8)Zi(x)=∑j∈Nl∖Hlcji¯xj+αi¯∑j∈Nl∖Hldji¯xj+βi¯,∀i∈{1,…,k}.
In the other hand,γji¯=βi¯cji¯−αi¯dji¯≤0, for all index j∈Nl∖Hl and γji¯=βi¯cji¯−αi¯dji¯<0 for at least one criterion, implies that cji¯≤αi¯dji¯/βi¯ for all j∈Nl∖Hl because βi¯=dixl∗+βi>0 for all criterion i∈{1,…,k}.
The decision variables being nonnegative, we obtain cji¯xj≤(αi¯dji¯/βi¯)xj for all j∈Nl∖Hl and hence (3.9)∑j∈Nl∖Hlcji¯xj≤∑j∈Nl∖Hlαi¯dji¯βi¯xj⇒∑j∈Nl∖Hlcji¯xj+αi¯≤∑j∈Nl∖Hlαi¯dji¯βi¯xj+αi¯.
For any criterionZi, i∈{1,…,k},
the following inequality is obtained (3.10)Zi(x)=∑j∈Nl∖Hlcji¯xj+αi¯∑j∈Nl∖Hldji¯xj+βi¯⇒Zi(x)≤∑j∈Nl∖Hl(αi¯dji¯/βi¯)xj+αi¯∑j∈Nl∖Hldji¯xj+βi¯⇒Zi(x)≤(αi¯/βi¯)(∑j∈Nl∖Hldji¯xj+βi¯)∑j∈Nl∖Hldji¯xj+βi¯⇒Zi(x)≤αi¯βi¯⇒Zi(x)≤Zi(xl∗).
Consequently,Zi(x)≤Zi(xl∗) for all i∈{1,…,k} and Zi(x)<Zi(xl∗) for at least one index. Hence Z(xl∗) dominates Z(x) and the solution x is not efficient.Corollary 3.2.
Suppose thatHl≠∅ at the current integer solution xl∗.
Then the constraint ∑j∈Hlxj≥1 is an efficient cut.Proof.
By the
above theorem, no efficient solution is deleted when the constraint∑j∈Hlxj≥1 is added. We can say that this is an efficient
valid constraint. In the other hand, xl∗ does not satisfy this constraint since xj=0,
for all j∈Nl.
We conclude that the constraint is an efficient cut.Proposition 3.3.
IfHl=∅ at the current integer solution xl∗,
then Sl∖{xl∗} is an explored domain.Proof.
Hl=∅ means that xl∗ is an optimal integer solution for all
criterion, hence xl∗ is an ideal point in the domain Sl and Sl∖{xl∗} does not contain efficient solutions.Theorem 3.4.
The described algorithm terminates
in a finite number of iterations and generates all the efficient solutions of
program(P).Proof.
The setS of feasible solutions of problem (P),
being compact, contains a finite number of integer solutions. Each time an
optimal integer solution xl∗ is calculated, the efficient cut is added.
Thus according to the above theorem and corollary, at least the solution xl∗ is eliminated when one studies any subproblem (Pk),k>l,
but no efficient solution is deleted.


## 4. An Illustrative Example

The following program(P) is given as an example of multiple objective
linear fractional programming (MOLFP) in Kornbluth and Steuer [20]:(4.1)maxZ1(x)=x1−4−x2+3,maxZ2(x)=−x1+4x2+1,maxZ3(x)=−x1+x2,subjectto−x1+4x2≤0,2x1−x2≤8,x1≥0,x2≥0,andintegers.Using the described algorithm, program(P0) is first resolved and the optimal solution is
given in the simplex Table 1:Table 1BRhsx3x4x28/72/71/7x132/71/74/7c1−4/7−1/7−4/7d1−13/72/71/7γ1−3/7−8/7c24/71/74/7d2−15/7−2/7−1/7γ21/78/7c324/7−1/73/7Sinceγj1≤0 for all j∈J01, J01=N0={3,4},
then the obtained solution (32/7,8/7) is optimal for program (P0),
but not integer. Therefore, two branches are possible.(1)
x1≥5⇔−1/7x3−4/7x4≥3/7.
This is not possible and (1) is fathomed.(2)
x1≤4⇔−1/7x3−4/7x4≤−4/7.This constraint is added and the dual simplex method
is applied. The integer optimal solution of program(P2) is obtained in Table
2.Table 2BRhsx3x5x211/41/4x1401x411/4−7/4c100−1d1−21/41/4γ10−2c2001d2−2−1/4−1/4γ202c33−1/43/4γj1≤0 for all j∈J21, J21=N2={3,5},
then the current solution (4,1) is optimal. Eff:={(4,1)}, H2={5}, and S3={x∈S2|x5≥1}.The constraintx5≥1 is added to the current simplex table and
after pivoting, we obtain Table 3.Table 3BRhsx2x6x3341x1301x42−1−2x510−1c110−1d1−3−10γ1−1−3c2−101d2−110γ2−11c3311J31=∅ then, (3,0) is an optimal integer solution and Eff:={(4,1),(3,0)}.Proceeding in this manner, we obtain Table4.Table 4BRhsx1x10x6310x3014/3x481−1x5410x720−1x9138x8011x20−1−1c1410d1−3−1−1γ1−1−4c2−4−10d2−111γ2−5−4c3001J41=∅ then, (0,0) is an optimal integer solution, Eff:={(4,1),(3,0),(0,0)}, N4={1,10}, H4={10}, and S5={x∈S4|x10≥1}.The constraintx10≥1 is added and we obtain Table 5.Table 5Rhsx11x10x621−1x3−111/3x471−2x531−1x720−1x9−235x8−110x21−10x11−11c131−1d1−2−10γ1−1−4c2−3−11d2−210γ2−5−4c3001The dual is not feasible, then the corresponding node
is fathomed.The algorithm terminates since all nodes are fathomed
and the integer efficient solutions set of program(P) is Eff={(4,1),(3,0),(2,0),(1,0),(0,0)}.


## 5. Computational Results

The computer program was coded in MATLAB 7.0 and run
on a 3.40 GHz DELL pentium 4, 1.00 GB RAM. The used software was developed by
the authors and was tested on randomly generated problems. We show the results
of the computational experiment in Table6.Table 6(n,m,α),(15,10,33)(20,10,25)(25,5,17)(25,10,17)EfficientMean99,50204,50200,4598,00SolutionsMax215324397228Min4236717CPUMean38,52185,96400,48306,74(second)Max54,39337,08673,17367,11Min23,094143,56193,87177,09SimplexMean75837,7126488,50521763,45255726,55IterationsMax101207365750719105306665Min558512717369414145324EfficientMean885,32341,502607,15979,00Cuts (EC)Max1152259339091268Min451679839440(EC)/(Cuts)Mean0,910,970,840,81The method was tested withm=5 and 10 constraints with r=4 objectives functions and n variables, n∈{15,20,25} randomly generated. The coefficients are
uncorrelated integers uniformly distributed in the interval [1,100] for constraints and [1,80] for objective functions about the first two
types of treated problems. For the latter two types of problems tested, the
integer values of the matrix constraints vary in the interval [1,50] and for those of criteria in [1,30]. The right-hand side value is set to α% of the sum of the coefficients (integer part)
of each constraint, where α∈{17,25,33}.
With each instance (n,m,α), a series of 20 problems is solved and the
whole efficient solution set was generated for all these problems.The method being exact, it was expected that the
iteration number of the simplex method is very large taking into account the
fact that, for this type of problems, the number of efficient solutions
increases quickly with the data size. In addition, we should like to point out
that the ratio EC/cuts tends toward the value one, showing that the number of
efficient cuts introduced into the method is very large compared to the full
number of cuts and indicating that this type of cuts has a positive impact on
the research of the whole of efficient solutions.


## 6. Conclusion

In this paper, an exact method for generating all
efficient solutions for multiple objective integer linear fractional
programming problems is presented The
method does not require any nonlinear optimization. A linear fractional program
is solved using the Cambini and Martein's algorithm in the original format and
then by using the well-known concept of branching in integer linear
programming, integer solutions are generated. The proposed efficient cut
exploits all the criteria in the simplex table, and only the parts of the
feasible solutions domain containing efficient solutions are explored. Also it
is easy to implement the proposed cut since to obtain integer solutionxk+1 from xk, one has just to append the cut in the simplex
table corresponding to xk and carry out pivoting iterations as in an
ordinary linear fractional programming problem. The described method solves
MOILFP problems in the general case. However, in order to make the algorithm
more powerful, the tree structure of the algorithm can be exploited for
construction of a parallel algorithm. For large scale problems, the number of
efficient solutions can be very high so that it becomes unrealistic to generate
them all. In this case, one can choose only the increasing directions of
criteria which satisfy a desirable augmentation. This can be made by building
the sets Hl in an interactive way at each step of the
algorithm.



---

*Source: 760191-2008-04-13.xml*