arXiv:1509.06332v2 [] 23 Sep 2015

A note on linear fractional set packing problem
Pooja Pandey ∗
Department of Mathematics, Simon Fraser University
250 - 13450 102nd Avenue, Surrey, BC, V3T 0A3, Canada

Abstract
In this note we point out various errors in the paper by Rashmi Gupta and R.
R. Saxena, Set packing problem with linear fractional objective function, International
Journal of Mathematics and Computer Applications Research (IJMCAR), 4 (2014) 9
- 18. We also provide some additional results.

1

Introduction

The set packing problem, set covering problem, and set partitioning problem are among
the most well-studied problems in combinatorial optimization and they have wide range of
real life applications [1, 2, 3, 4, 5, 8]. Arora, Puri and Swarup [1, 2] developed couple of
solution algorithms for the set covering problem with the linear fractional objective function,
where they exploited the structural properties of the set covering problems. Later, Gupta
and Saxena [7] extended these results for the set packing problems with the linear fractional
objective function.
In this note, we show that the properties established in [7] are incorrect. Gupta and
Saxena [6] extended results of [1, 2] to the linear fractional set packing problems, but these
extensions suffer many drawbacks since they overlooked the structural properties of the set
packing problem and ignore the required conditions for their results to be correct.

2

The linear fractional set packing problem

Let E = {1, 2, . . . , m} be a finite set and F = {S1 , S2 , . . . , Sn } be a family of subsets of E.
The index set for elements of F is denoted by G = {1, 2, . . . , n}. For each element j ∈ G, a
cost cj and a weight dj are prescribed. We refer to cj as the linear cost of the set Sj and
c = (c1 , . . . , cn ) as the linear cost vector. Similarly dj is referred to as the linear weight of
the set Sj and d = (d1 , . . . , dn ) as the linear weight vector. α and β are constants where β > 0.
∗

Corresponding author. Email: poojap@sfu.ca

1

A subset H of G is said to be a pack of E if
T
Sj Sk = ∅.

S

j∈H

Sj = E, and j, k ∈ H, j 6= k, implies

Then
Ph the linear set packing problem (LSPP) is to select a pack H = {π(1), . . . , π(h)} such
that i=1 cπ(i) is maximized. Likewise the linear fractional set packing problem (LFSPP) is
Ph
cσ(i) + α
to select a pack H = {σ(1), . . . , σ(h)} such that Phi=1
is maximized.
d
+
β
σ(i)
i=1
For each i ∈ E, consider the vector ai = (ai1 , ai2 , . . . , ain ) where
(
1 if i ∈ Sj
aij =
0 otherwise.

and A = (aij )m×n be an m × n matrix. Also, consider the decision variables x1 , x2 , . . . , xn
where
(
1 if j is in the pack
xj =
0 otherwise.
The vector of decision variables is represented as x = (x1 , . . . , xn )T and  is column
vector of size n where all entries equal to 1. Then the LSPP and LFSPP can be formulated
respectively as 0-1 integer programs
LSPP:

Maximize cx
Subject to Ax ≤ 
x ∈ {0, 1}n

(1)
(2)

and
LFSPP:

cx + α
dx + β
Subject to Ax ≤ 
x ∈ {0, 1}n

Maximize

(3)
(4)

It is assumed that c ≥ , α = 0 and β is a scalar such that dx + β > 0. Throughout the
paper we will assume that dx + β > 0 for any feasible solution of LFSPP.
The continuous relaxations of LSPP and LFSPP, denoted respectively by LSPP(C) and
LFSPP(C), are obtained by replacing the constraint set x ∈ {0, 1}n by x ≥ , respectively
in LSPP and LFSPP.
The family of feasible solutions of both LSPP and LFSPP is given by S = {x|Ax ≤
, x ∈ {0, 1}n } and the family of feasible solutions for their continuous relaxations is given
by S̄ = {x|Ax ≤ , x ≥ }.

2

Following are some definitions given in [7]. A solution x ∈ S which satisfies (3) and (4)
is said to be a pack solution. For any pack H, a column of A corresponding to j ∈ G is said
to be redundant if H + {j} is also a pack. If a pack corresponds to one or more redundant
columns, it is called a redundant pack. A pack H ∗ is said to be a prime pack, if none of the
columns corresponding to j ∗ ∈ G is redundant. A solution corresponding to the prime pack
is called a prime packing solution.
The linear fractional set covering problem (LFSCP) is obtained by replacing (3) with
Ax ≥ 

(5)

and changing the problem from maximization to minimization problem in the 0-1 integer
formulation of LFSPP. Any x ∈ {0, 1}n satisfying (5) is called a cover solution.
Any x ∈ S is called a cover solution and an optimal solution to the underlying problem
LFSCP is called an optimal cover solution. Note that each cover solution corresponds to a
cover and viceversa. A cover P is said to be redundant if P − {j} with j ∈ P is also a cover.
A cover which is not redundant is called a prime cover. The incidence vector x corresponds
to prime cover is called a prime cover solution.
For the linear fractional set covering problem, Arora, Puri, and Swarup [1] proved that
every optimal cover is a prime cover, if cj ′ s and dj ′ s satisfy certain conditions.
Gupta and Saxena [7] claimed an extension of the above result to LFSPP, assuming
c ≥ , d ≥  and dx + β > 0. More precisely, they claimed:
Theorem 2.1. (Theorem 2 of [7]) If the objective function in LFSPP has finite value then,
there exists a prime pack solution where this value is attained.
This result is not true as established by the following example. Let


1 1 0
β = 2, c = (1, 2, 5), d = (4, 4, 6), and A =
1 0 1

For the LFSPP with A, c, d and β defined as above, it can be verified that x∗ = (0, 0, 1)T
5
is an optimal solution with the objective function value
= 0.625. The optimal pack
8
corresponding to x∗ is H ∗ = {3} which is a redundant pack since H ∗ + {2} = {2, 3} is also a
pack. All other pack solutions and their respective objective function values are listed below:
x1 = (1, 0, 0)T prime pack solution
x2 = (0, 1, 1)T prime pack solution
x3 = (0, 0, 0)T redundant pack solution
x4 = (0, 1, 0)T redundant pack solution
3

1
= 0.16666
6
7
= 0.5833
f (x2 ) =
12
f (x3 ) = 0
1
f (x4 ) = = 0.3333
3
f (x1 ) =

None of these corresponds to an optimal solution for LFSPP. In particular, no prime
pack solution is optimal for the instances of LFSPP constructed above, which contradicts
Theorem 2.1. However, a variation of the Theorem 2.1 can be proved as noted below.
Theorem 2.2. There always exists a prime pack optimal solution for LFSPP if
(a) c >  and d <  or
(b) any ratio of the partial sums of ci ’s or di ’s is greater than the value of the objective
function at the pack solution and also the partial sum of di ’s is positive.
Proof. Let us assume that there exists an optimal pack H1 for LFSPP which is a redundant
optimal pack of LFSPP. Since H1 is a redundant pack, a prime pack H2 can be derived from
H1 by adding redundant columns of H1 .
The objective function value of LFSPP for H1 and H2 are ZH1 and ZH2 respectively:
P
P
P
cj
j∈H1 cj +
j∈H1 cj
P j∈{H2 −H1 }
Z H1 = P
and ZH2 = P
j∈H1 dj + β
j∈H1 dj +
j∈{H2 −H1 } dj + β

(a) Since c >  and d < , therefore,

cj +

j∈H1

X

j∈H1

dj + β >

X

dj +

X

and

X

j∈H1

cj <

j∈H1

X

cj

(6)

X

dj + β

(7)

j∈{H2 −H1 }

j∈{H2 −H1 }

Since denominator of the objective function value is always positive, dividing inequality
(6) by (7), we get:

which gives

P
P
P
cj
j∈H1 cj +
j∈H1 cj
P
P j∈{H2 −H1 }
<P
j∈H1 dj + β
j∈H1 dj +
j∈{H2 −H1 } dj + β
Z H1 < Z H2 .

This shows that H2 is an optimal pack for LFSPP instead of H1 , contradicts the optimality of H1 , therefore H1 is a prime pack of LFSPP . This completes the proof of
part (a).
Note: In this case if we relax c > , then above theorem is no longer true.

4

(b) It is given that any ratio of the partial sums of ci ’s or di ’s is greater than the value of the
objective function at the pack solution and also the partial sum of di ’s is positive and
denominator of the objective function is positive for any feasible solution of LFSPP,
therefore:
P

P j∈{H2 −H1 }
j∈{H2 −H1 }

P

cj

> ZH1 , which implies

dj

P
j∈H1 cj
>P
, cross multiplication gives
j∈H1 dj + β
X
X
cj )
>(
dj )(

j∈{H2 −H1 } cj

P

j∈{H2 −H1 }

(

X

cj )(

X

dj

dj + β)

j∈H1

j∈{H2 −H1 }

adding both sides (

P

j∈H1

X

(

cj )(

cj )(

P

X

j∈H1

dj + β) will give

X

cj )(

X

cj )(

dj + β) + (

X

X

dj + β) >

j∈H1

j∈{H2 −H1 }

j∈H1

j∈H1

X

dj + β) + (

j∈H1

j∈H1

(

j∈H1

j∈{H2 −H1 }

dj )(

j∈{H2 −H1 }

X

cj )

j∈H1

after simplifying, we get
(

X

j∈H1

dj + β)(

X

cj +

j∈H1

X

cj ) > (

X

cj )(

j∈H1

j∈{H2 −H1 }

X

j∈H1

dj + β +

X

dj )

j∈{H2 −H1 }

which is equivalent to
P
P
P
( j∈H1 cj + j∈{H2 −H1 } cj
( j∈H1 cj )
P
P
.
> P
( j∈H1 dj + β)
j∈H1 dj + β +
j∈{H2 −H1 } dj )
which gives

Z H2 > Z H1 .
Therefore, the objective function value of any prime pack is always greater than any
corresponding redundant pack, therefore, the optimal pack is a prime pack. This
completes the proof of part (b).

Lemma 2.3. If c and d are integer numbers, k, l = 1, . . . , n, ld + β > 0 and k + l ≤ n, then
kc + lc
kc
<
,
kd + β
kd + ld + β
5

if c > 0

and

kc + lc
kc
>
,
kd + β
kd + ld + β

if c < 0.

Proof. For given integer numbers c and d, if c > 0 then
lcβ > 0

(8)

add (kc)(kd + β) + (kc)(ld) both sides of the inequality (8), we get
(kc)(kd + β) + (kc)(ld) + lcβ > (kc)(kd + β) + (kc)(ld)

(9)

after rearranging inequality (9) we get
(kc)(kd + β) + (lc)(kd + β)
(kd + β)(kc + lc)

> (kc)(kd + β) + (kc)(ld) which is same as
> (kc)(kd + ld + β)

(10)

since (kd + β) > 0 and (kd + ld + β) > 0, divide both sides of the inequality (10) by
(kd + β)(kd + ld + β) , we get
kc
kc + lc
<
kd + β
kd + ld + β

(11)

which proves the first part.
Now if c < 0 then
kc + lc
kc
>
,
kd + β
kd + ld + β
this can be proved in a similar manner as we did the first part.
This completes the proof.
Theorem 2.4. If ci = c, and di = d, ∀i = 1, . . . , n, and H ∗ is an optimal pack of LFSPP:
(a) if c > 0, then H ∗ is a largest cardinality prime pack solution of LFSPP, (b) if c < 0,
then H ∗ is a smallest cardinality pack solution of LFSPP.
Proof. (a) If c > 0 :
if H ∗ is not a prime pack then we can always add redundant columns for H ∗ and find a
prime pack H ∗∗ of LFSPP and corresponding objective function values for H ∗ and H ∗∗ are
following:
P
P
P
∗∗
∗ c
j∈H ∗ c +
j∈H ∗ c
P j∈{H −H }
and ZH ∗∗ = P
ZH ∗ = P
j∈H ∗ d + β
j∈H ∗ d +
j∈{H ∗∗ −H ∗ } d + β
using first part of Lemma 2.3 we can claim that

ZH ∗ < ZH ∗∗
6

which contradicts the optimality of H ∗ . Therefore, H ∗ is a prime pack of the given LFSPP.
If among all prime packs of LFSPP H ∗ is not of the largest cardinality then there exist
a prime cover H o of LFSPP such that |H ∗| < |H o | and
P
P
j∈H o c
j∈H ∗ c
and ZH o = P
ZH ∗ = P
j∈H ∗ d + β
j∈H o d + β
P
P
since |H ∗| < |H o| , then j∈H ∗ c < j∈H o c, along with the first part of Lemma 2.3 we
can claim that
ZH ∗ < ZH o
which contradicts the optimality of H ∗ . Therefore, H ∗ if the prime pack of the largest
cardinality among all prime packs of LFSPP.
(b) If c < 0 :
If among all packs of LFSPP H ∗ is not of the smallest cardinality then there exist a pack
H of LFSPP such that |H ∗| > |H o | and
P
P
j∈H ∗ c
j∈H o c
ZH ∗ = P
and ZH o = P
j∈H ∗ d + β
j∈H o d + β
P
P
but since |H ∗ | > |H o| , then j∈H ∗ c < j∈H o c, along with the second part of Lemma
2.3 we can claim that
ZH ∗ < ZH o
o

which contradicts the optimality of H ∗ . Therefore, H ∗ is the pack of LFSPP of the
smallest cardinality. This completes the proof.

3

Conclusion

I would like to explore non-linear set packing problems in future research. I would like to
thank Prof. Abraham P. Punnen for his valuable suggestions during the preparation of this
note.

References
[1] Arora, S.R., Swaroop, Kanti, and Puri, M.C., The set covering problem with linear
fractional functional, Indian Journal of Pure and Applied Mathematics, 8, (1977) 578588.
[2] Arora, S.R., and Puri, M.C., Enumeration Technique for the Set Covering Problem with
Linear Fractional Functional as its Objective Functions, ZAMM - Journal of Applied
Mathematics and Mechanics, 57, (1977) 181-186.
7

[3] Bazaraa, Mokhtar S.; Goode, Jamie J, A cutting-plane algorithm for the quadratic setcovering problem, Operations Research, 23, (1975) 150 - 158.
[4] Bector, C. R. and Bhatt. S. K., A linearization technique for solving integral linear
fractional program, Proc. fifth Manitoba Conference on Numerical Mathematics, (1975)
221 - 229.
[5] Garfinkel, M. and Nemhauser. G. L, Integer Programming, A Wiley-Interscience Publication, John Wiley and Sons (1973).
[6] Gupta, Rashmi, and Saxena, R. R., Linearization technique for solving quadratic set
packing and partitioning problems, International Journal of Mathematics and Computer
Applications Research, 4, (2014) 9 - 20.
[7] Gupta, Rashmi, and Saxena, R. R., Set packing problem with linear fractional objective
function, International Journal of Mathematics and Computer Applications Research, 4,
(2014) 9 - 18.
[8] Lemke, C. E., Salkin, H. M. and Spielberg K., Set covering by single branch enumeration
with linear programming sub-problem, Operations Research, 19, (1971) 998 - 1022.

8

