Optimal product design using conjoint analysis: Computational complexity and algorithms

The problem of maximizing the share of a new product introduced in a competitive market is shown to be NP-hard. A direct graph representation of the problem is used to construct shortest-path and dynamic-programming heuristics. Both heuristics are shown to have arbitrarily-bad worst-case bounds. Computational experience with real-size problems is reported. Both heuristics identify near-optimal solutions for the simulated problems, the dynamic-programming heuristic performing better than the shortest-path heuristic.