Methods for identifying optimal product concepts using conjoint analysis typ- ically assume a deterministic, first-choice rule. As a consequence, these methods: (i) ignore uncertainty in preference estimates when evaluating new product concepts; (ii) force the assignment of a single "status-quo" item to each consumer; and (iii) allow an estimate of the expected market share, but not the associated variability in choice probabilities across consumers. We describe the mathematical representation of a problem concerning optimal product design that allows consumers to make probabilistic choices. We then describe a solution procedure that generalizes a previously-known dynamic-programming algorithm to accommodate probabilistic choice rules. We examine the performance of the proposed algorithm in both a simulation and an application. We assess in the simulation how well the proposed heuristic performs in identifying an optimal or near-optimal product concept using a probabilistic choice rule. We compare these market share predictions with those obtained using a deterministic choice rule, and find that the difference in the two predictions (i) increases with the number of attributes and attribute levels, and the number of alternatives in consideration sets; and (ii) decreases with the heterogeneity in consumer preferences. We describe an application of the proposed method for designing television sets. As in the simulation, we find that ignoring preference uncertainty changes market share predictions. We find near-optimal product concepts that have similar expected market shares but different distributions of choice probabilities across consumers. Among these, product concepts with a higher variance in the choice probabilities are better from the standpoint of defending market share against new products that might be subsequently introduced in the market.