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

We generalize their problem specification to include different types of resource
restrictions and develop an integer linear programming formulation for the same. The
Optimal Item Packages Problem (OIPP) is to choose a set of frequent item sets that
we term as item packages, so as to maximize the total net profit subject to conditions
on maximum storage space for selected items and minimum total revenue from the
selected frequent item sets. Our formulation of the problem is much more flexible
compared to Brij et al's [2], as the model can adapt to not only different resource
restrictions but also to various bounds on the number of items to be included in the
final selection. For example, it can specify the minimum and maximum number of
elements in the final solution.

3.1 Motivation for OIPP

In many real-life businesses, a transaction may consist of a specific set of items
forming a package. For example, while buying a car, a customer's choice may be
made easier by having a number of fixed packages offered by the supplier. In some
other businesses, it may not make sense to separate any item from a given package;
e.g. medical procedures, travel packages etc.
Alternatively, a vendor may be interested in finding out from previous sales as to
which, if any, set of items exist that could be offered as a package. This packaging of
items (or products) could potentially offer him certain amount of profit under a
number of resource constraints. For instance, the resource constraints could be
available stocking space, budget (minimum cost or maximum profit), quantity (that
needs to be sold) etc. He may be further interested in doing a sensitivity analysis as to
how far the resources can be stretched while the given solution remains optimal.
Again, in another instance, the vendor may like to see how a change in a certain
resource affects his profitability (for example, if he is able to organize a little more
space for storage or invest a little more money). For a travel bureau, a constraint could
be time-oriented resources (like, a travel consultant's time),

OIPP: For a given database {I t k} be a pre-specified

list of k frequent item sets. Let f j and n j respectively denote the number of transactions
that exactly include X j (i.e. f j = |{t: I t = X j }| ) and the number of items in X j , 1

⊂ I : 1 ≤ t ≤ T}, let {X j : 1 ≤ j ≤

k.
The constant b ij assumes the value 1 whenever item i is a member of the frequent item
set X j , i

≤ j ≤

k. Let p j denote the revenue made by the frequent item set X j
whenever X j forms a transaction. Let c i denote the cost incurred (per unit) while
selecting item i, 1

∈ I, 1 ≤ j ≤

N. Let s i denote the storage space (in appropriate units)
required per unit for item i whenever the item is selected. Furthermore, let S denote
the total available storage space. Find, a subset ˆ of {i: 1

≤ i ≤

≤ i ≤ N} and a subset F of

the set of frequent item sets {X j : 1 ≤ j ≤ k} such that they satisfy the following

properties:
1.

The number of items in ˆ is bounded below and above by positive integers
N L and N U respectively;

A frequent item set X j is selected in F if and only if X j is covered by ˆ , that
is, X j

2.

ˆ ;

⊆