AbstractsBusiness Management & Administration

Companies rely heavily on new products as a source of profit. New products are usually introduced in several configurations to comprise a product line. A product line enables a firm to satisfy the heterogeneous preferences of today’s customers. Important in practice, the product line design problem has also drawn tremendous interest from academia. Since the 1970s researchers have been working on the problem of constructing an optimal product line using partworth data obtained from conjoint studies. In this dissertation, we focus on solving the share-of-choice product line problem. The objective is to determine the product attributes of a set of products for a firm to offer so as to maximize the projected market share provided by the set of products in the line; i.e., the number of respondents for whom at least one new product’s utility exceeds a specific hurdle. Previous contributions to this NP-Hard problem include a series of heuristics. We present a new branch-and-price algorithm that embeds a column generation procedure within a branch-and-bound process to obtain exact optimal integer solutions to the product line problem. The dissertation provides a great deal of detail about the issues encountered in implementing the branch-and-price algorithm (e.g., pricing scheme, column management and tree traversal strategy). Computational results using real and large simulated datasets demonstrate that the algorithm is capable of identifying provably optimal solutions very quickly. We design an experiment to isolate the factors to which the solution times of the branch-and-price algorithm are most sensitive. The effectiveness of previously published heuristics has only been evaluated on small problems for which complete enumeration is possible. We benchmark the performance of the branch-and-price algorithm against two heuristics (i.e., the segment-by-segment approach and the sequential approach) in the context of preference heterogeneity using test problems of realistic size. All published heuristics treat estimated partworths as errorless instead of statistical estimates, leaving the robustness of heuristics to partworth uncertainty unknown. We analyze the robustness of the branch-and-price algorithm and the sequential method to within-person variation in estimated partworths by conducting an experiment with a test phase and a validation phase. The increase of unique of product lines indicates that the sequential method is less robust to the partworth uncertainty than the branch-and-price algorithm.