Mining Value-Based Item Packages – An Integer Programming Approach - Data Mining: Theory, Methodology, Techniques, and Applications - page 82

3. The total storage space required for the selected items of ˆ does not exceed
the available space of S units;
4. The total revenue made by frequent item sets of F is at least Minrev ;
5. The net profit (total revenue - the total cost) is maximized.
We now provide an ILP model for the OIPP described above. Let y i denote the 0-1
decision variable that assumes value 1 whenever item i is chosen. Let z j denote the 0-
1 decision variable that assumes value 1 whenever the frequent item set X j is covered
by the set of selected items, that is, by the set of items { i: y i = 1}.

N

∑
=

y ≤ N U

Lower and upper bound constraints: N L ≤

(1)

i 1

Occurrence constraint of X j : ∑
∈

y - n z ≥ 0 ,

1 ≤ j ≤ k

(2)

i j j

i X

j

k N

∑∑
=

( b s ) f z ≤ S Item storage space constraint:

(3)

ij i j j

j 1 i = 1

k

Lower bound constraint on revenue: ∑
=

p f z ≥ Minrev

(4)

j j j

j 1

Restrictions on variables: y i = 0 or 1, z j = 0 or 1

(5)

k k N

Objective function: Maximize ∑
=

- ∑∑
=

p f z ( b c ) f z

(6)

j j j ij i j j

j 1 i = 1

j 1

In this value based frequent item set problem the input information regarding X 1 ,
…, X k , p j , f j , s i and c i must be extracted through data mining of frequent item sets.
For the above model (1) - (6), the constraints and the objective function may be
validated as follows:
Let the set of selected items to cover all the selected frequent item sets be denoted

N

by ˆ = { i: y i = 1}. It is easy to see that | ˆ | = ∑
=

y and the constraint (1) provides

i 1

the lower and upper bound restrictions on this number. The number of items common

to the set ˆ and the frequent item set X j is given by ∑
∈

y . Whenever ∑
∈

y = |X j |

i X i X

j j

= n j , the set ˆ covers the frequent item set X j . The constraint (2) ensures that the
decision variable z j is 1 if and only if the frequent item set X j is covered by ˆ . In this
case note that F={ X j : z j = 1} is the collection of frequent item sets selected. The
storage space required by an item i of the selected item sets in F is ∑
=

k

b s f z

,

ij i j j

j 1