An exact algorithm for the share-of-choice problem

Products and services can be thought of as bundles of attributes that are each made up of many levels. Consumers consider tradeoffs between various attributes and levels before making a purchase decision for a product. A popular marketing research technique called conjoint analysis is used to study these tradeoffs. The data on consumer preferences is generally decomposed using a regression procedure into utility values that the consumer associates with each level of every attribute. In the design of a new product, it is critical to determine a judicious combination of attribute levels that is likely to perform well in a market containing competitor products. Using these utility measures, a firm can design products that would best meet consumer expectations and the seller's objectives.; A popular way to measure the success of a new product is to calculate the amount of market share it is expected to capture in a competitive market. Researchers have proposed the share-of-choice problem whose objective is to maximize the number of respondents from a conjoint study who prefer a new product to their status-quo products. The share-of-choice problem is NP-hard. The linear-programming based branch-and-bound algorithm is inefficient in solving real world instances of the share-of-choice problem. Several heuristic procedures to solve the share-of-choice problem have appeared in the literature. In this research, an exact algorithm is proposed to solve real world instances of the share-of-choice problem to optimality. An experiment is designed to test the run-time performance of the exact algorithm using a set of simulated problems that mimic real world problem characteristics. We also suggest potential extensions of the exact algorithm to solve modified versions of the share-of-choice problem, and also to solve the related product line design problem.