EXAMPLE 2 Violating Proportionality

EXAMPLE 2 Violating Proportionality

The SUPERSUDS CORPORATION is developing its marketing plans for next year’s new products. For three of these products, the decision has been made to purchase a total of five TV spots for commercials on national television networks. The problem we will fo- cus on is how to allocate the five spots to these three products, with a maximum of three spots (and a minimum of zero) for each product.

Table 12.3 shows the estimated impact of allocating zero, one, two, or three spots to each product. This impact is measured in terms of the profit (in units of millions of dollars) from the additional sales that would result from the spots, considering also the cost of producing the commercial and purchasing the spots. The objective is to allocate five spots to the products so as to maximize the total profit.

This small problem can be solved easily by dynamic programming (Chap. 11) or even by inspection. (The optimal solution is to allocate two spots to product 1, no spots to product 2, and three spots to product 3.) However, we will show two different BIP formulations for illustrative purposes. Such a formulation would become necessary if this small problem needed to be incorporated into a larger IP model involving the allocation of resources to marketing activities for all the corporation’s new products.

One Formulation with Auxiliary Binary Variables. A natural formulation would be to let x1, x2, x3 be the number of TV spots allocated to the respective products. The contribution of each xj to the objective function then would be given by the correspond- ing column in Table 12.3. However, each of these columns violates the assumption of pro- portionality described in Sec. 3.3. Therefore, we cannot write a linear objective function in terms of these integer decision variables.

Now see what happens when we introduce an auxiliary binary variable yij for each positive integer value of xi = j ( j = 1, 2, 3), where yij has the interpretation

There is little to choose between this BIP model and the preceding one other than personal taste. They have the same number of binary variables (the prime consideration in determining computational effort for BIP problems). They also both have some special structure (constraints for mutually exclusive alternatives in the first model and constraints for contingent decisions in the second) that can lead to speedup. The second model does have more functional constraints than the first.