×

Exact first-choice product line optimization. (English) Zbl 1444.90071

Summary: A fundamental problem faced by firms is that of product line design: given a set of candidate products that may be offered to a collection of customers, what subset of those products should be offered to maximize the profit that is realized when customers make purchases according to their preferences? In this paper, we consider the product line design problem when customers choose according to a first-choice rule and present a new mixed-integer optimization formulation of the problem. We theoretically analyze the strength of our formulation and show that it is stronger than alternative formulations that have been proposed in the literature, thus contributing to a unified understanding of the different formulations for this problem. We also present a novel solution approach for solving our formulation at scale, based on Benders decomposition, which exploits the surprising fact that Benders cuts for both the relaxation and the integer problem can be generated in a computationally efficient manner. We demonstrate the value of our formulation and Benders decomposition approach through two sets of experiments. In the first, we use synthetic instances to show that our formulation is computationally tractable and can be solved an order of magnitude faster for small- to medium-scale instances than the alternate, previously proposed formulations. In the second, we consider a previously studied product line design instance based on a real conjoint data set, involving over 3,000 candidate products and over 300 respondents. We show that this problem, which required a week of computation time to solve in prior work, is solved by our approach to full optimality in approximately 10 minutes.
The e-companion is available at https://doi.org/10.1287/opre.2018.1825.

MSC:

90B60 Marketing, advertising
90C11 Mixed integer programming

Software:

Gurobi; JuMP; Julia
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aouad A, Farias VF, Levi R (2015) Assortment optimization under consider-then-choose choice models Working paper, London Business School, London.Google Scholar
[2] Aouad A, Farias VF, Levi R, Segev D (2017) The approximability of assortment optimization under ranking preferences. Oper. Res. 66(6):1661-1669.Link, Google Scholar · Zbl 1446.90094
[3] Belloni A, Freund R, Selove M, Simester D (2008) Optimizing product line designs: Efficient methods and comparisons. Management Sci. 54(9):1544-1552.Link, Google Scholar · Zbl 1232.90168
[4] Bertsimas D, Mišić VV (2017) Robust product line design. Oper. Res. 65(1):19-37.Link, Google Scholar · Zbl 1364.90353
[5] Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization (Athena Scientific, Belmont, MA).Google Scholar
[6] Bertsimas D, Weismantel R (2005) Optimization Over Integers (Dynamic Ideas, Belmont, MA).Google Scholar
[7] Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65-98.Crossref, Google Scholar · Zbl 1356.68030 · doi:10.1137/141000671
[8] Blanchet J, Gallego G, Goyal V (2016) A Markov chain approximation to choice modeling. Oper. Res. 64(4):886-905.Link, Google Scholar · Zbl 1348.90614
[9] Bront JJM, Méndez-Díaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769-784.Link, Google Scholar · Zbl 1233.90061
[10] Chen KD, Hausman WH (2000) Technical note: Mathematical properties of the optimal product line selection problem using choice-based conjoint analysis. Management Sci. 46(2):327-332.Link, Google Scholar · Zbl 1231.90159
[11] Contreras I, Cordeau J-F, Laporte G (2011) Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6):1477-1490.Link, Google Scholar · Zbl 1242.90094
[12] Cordeau J-F, Stojković G, Soumis F, Desrosiers J (2001) Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Sci. 35(4):375-388.Link, Google Scholar · Zbl 1069.90525
[13] Davis JM, Gallego G, Topaloglu H (2014) Assortment optimization under variants of the nested logit model. Oper. Res. 62(2):250-273.Link, Google Scholar · Zbl 1295.90076
[14] Dobson G, Kalish S (1988) Positioning and pricing a product line. Marketing Sci. 7(2):107-125.Link, Google Scholar
[15] Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295-320.Crossref, Google Scholar · Zbl 1368.90002 · doi:10.1137/15M1020575
[16] Farias VF, Jagabathula S, Shah D (2013) A nonparametric approach to modeling choice with limited data. Management Sci. 59(2):305-322.Link, Google Scholar
[17] Feldman JB, Topaloglu H (2017) Revenue management under the Markov chain choice model. Oper. Res. 65(5):1322-1342.Link, Google Scholar · Zbl 1411.91497
[18] Geoffrion AM, Graves GW (1974) Multicommodity distribution system design by benders decomposition. Management Sci. 20(5):822-844.Link, Google Scholar · Zbl 0304.90122
[19] Green PE, Krieger AM (1985) Models and heuristics for product line selection. Marketing Sci. 4(1):1-19.Link, Google Scholar
[20] Green PE, Krieger AM (1993) Conjoint analysis with product-positioning applications. Eliashberg J, Lilien GL, eds. Handbooks in Operations Research and Management Science, vol. 5 (Elsevier, Amsterdam), 467-515.Google Scholar · Zbl 0898.90001
[21] Gurobi Optimization, Inc. (2017) Gurobi Optimizer Reference Manual (Gurobi Optimization, Inc., Beaverton, Oregon).Google Scholar
[22] Honhon D, Jonnalagedda S, Pan XA (2012) Optimal algorithms for assortment selection under ranking-based consumer choice models. Manufacturing Service Oper. Management 14(2):279-289.Link, Google Scholar
[23] Kohli R, Jedidi K (2015) Error theory for elimination by aspects. Oper. Res. 63(3):512-526.Link, Google Scholar · Zbl 1377.91090
[24] Kohli R, Krishnamurti R (1987) A heuristic approach to product design. Management Sci. 33(12):1523-1533.Link, Google Scholar
[25] Kohli R, Krishnamurti R (1989) Optimal product design using conjoint analysis: Computational complexity and algorithms. Eur. J. Oper. Res. 40(2):186-195.Crossref, Google Scholar · Zbl 0663.90053 · doi:10.1016/0377-2217(89)90329-9
[26] Kohli R, Sukumar R (1990) Heuristics for product-line design using conjoint analysis. Management Sci. 36(12):1464-1478.Link, Google Scholar
[27] Kohli R., Boughanmi K., Kohli V (2019) Randomized algorithms for lexicographic inference. Oper. Res. 67(2):357-375.Abstract, Google Scholar · Zbl 1455.90106
[28] Kraus UG, Yano CA (2003) Product line selection and pricing under a share-of-surplus choice model. Eur. J. Oper. Res. 150(3):653-671.Crossref, Google Scholar · Zbl 1033.90062 · doi:10.1016/S0377-2217(02)00522-2
[29] Li G., Rusmevichientong P, Topaloglu H (2015) The d-level nested logit model: Assortment and price optimization problems. Oper. Res. 63(2):325-342.Link, Google Scholar · Zbl 1327.90315
[30] Lubin M, Dunning I (2015) Computing in operations research using Julia. INFORMS J. Comput. 27(2):238-248.Link, Google Scholar · Zbl 1331.90001
[31] Luo L (2011) Product line design for consumer durables: An integrated marketing and engineering approach. J. Marketing Res. 48(1):128-139.Crossref, Google Scholar · doi:10.1509/jmkr.48.1.128
[32] McBride RD, Zufryden FS (1988) An integer programming approach to the optimal product line selection problem. Marketing Sci. 7(2):126-140.Link, Google Scholar
[33] Mišić VV (2016) Data, models and decisions for large-scale stochastic optimization problems. Doctoral thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
[34] Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (Wiley Interscience, New York).Crossref, Google Scholar · Zbl 0652.90067 · doi:10.1002/9781118627372
[35] Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801-817.Crossref, Google Scholar · Zbl 1402.90158 · doi:10.1016/j.ejor.2016.12.005
[36] Rusmevichientong P, Topaloglu H (2012) Robust assortment optimization in revenue management under the multinomial logit choice model. Oper. Res. 60(4):865-882.Link, Google Scholar · Zbl 1262.90205
[37] Rusmevichientong P, Shmoys D, Tong C, Topaloglu H (2014) Assortment optimization under the multinomial logit model with random choice parameters. Production Oper. Management 23(11):2023-2039.Crossref, Google Scholar · doi:10.1111/poms.12191
[38] Schön C (2010a) On the optimal product line selection problem with price discrimination. Management Sci. 56(5):896-902.Link, Google Scholar · Zbl 1232.90226
[39] Schön C (2010b) On the product line selection problem under attraction choice models of consumer behavior. Eur. J. Oper. Res. 206(1):260-264.Crossref, Google Scholar · Zbl 1188.91106 · doi:10.1016/j.ejor.2010.01.012
[40] Talluri K, van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15-33.Link, Google Scholar · Zbl 1168.91427
[41] Toubia O, Simester DI, Hauser JR, Dahan E (2003) Fast polyhedral adaptive conjoint estimation. Marketing Sci. 22(3):273-303.Link, Google Scholar
[42] Toubia O, Hauser JR, Simester DI (2004) Polyhedral methods for adaptive choice-based conjoint analysis. J. Marketing Res. 41(1):116-131.Crossref, Google Scholar · doi:10.1509/jmkr.41.1.116.25082
[43] van Ryzin G., Vulcano G (2015) A market discovery algorithm to estimate a general class of nonparametric choice models. Management Sci. 61(2):281-300.Link, Google Scholar
[44] Yee M,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.