DiversiTree: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems

References

• Achterberg T, Heinz S, Koch T (2008) Counting solutions of integer programs using unrestricted subtree detection. Perron L, Trick MA, eds. Integration of AI and OR Techniques Constraint Programming for Combinatorial Optimization Problems. 5th International Conference CPAIOR 2008, vol. 5015, Lecture Notes in Computer Science (Springer, Berlin), 278–282.Google Scholar
• Ahanor I, Medal H, Trapp AC (2023) DiversiTree: Computing diverse sets of near-optimal solutions to mixed-integer optimization problems. http://dx.doi.org/10.1287/ijoc.2022.0164.cd, https://github.com/INFORMSJOC/2022.0164.Google Scholar
• Baste J, Fellows MR, Jaffke L, Masařík T, de Oliveira Oliveira M, Philip G, Rosamond FA (2022) Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. Artificial Intelligence 303:103644.Crossref, Google Scholar
• Bertsimas D, King A, Mazumder R (2016) Best subset selection via a modern optimization lens. Ann. Statist. 44(2):813–852.Crossref, Google Scholar
• Bixby RE, Ceria S, McZeal CM, Savelsbergh MWP (1998) An updated mixed integer programming library: MIPLIB 3.0. Optima 58:12–15.Google Scholar
• Biyouki SA, Hwangbo H (2021) Blind image deblurring based on kernel mixture. Preprint, submitted January 15, https://arxiv.org/abs/ 2101.06241.Google Scholar
• Boehmer N, Niedermeier R (2021) Broadening the research agenda for computational social choice: Multiple preference profiles and multiple solutions. Proc. 20th Internat. Conf. on Autonomous Agents and MultiAgent Systems (ACM, New York), 1–5.Google Scholar
• Cai Q, He L, Xie Y, Feng R, Ma J (2021) Simple and effective strategies to generate diverse designs for truss structures. Structures 32:268–278.Crossref, Google Scholar
• Cameron TR, Charmot S, Pulaj J (2021) On the linear ordering problem and the rankability of data. Preprint, submitted April 12, https://arxiv.org/abs/ 2104.05816.Google Scholar
• Ceria S, Cordier C, Marchand H, Wolsey LA (1998) Cutting planes for integer programs with general integer variables. Math. Programming 81(2):201–214.Crossref, Google Scholar
• Church RL, Baez CA (2020) Generating optimal and near-optimal solutions to facility location problems. Environment Planning B Urban Analytics City Sci. 47(6):1014–1030.Crossref, Google Scholar
• Danna E, Woodruff DL (2009) How to select a small set of diverse solutions to mixed integer programming problems. Oper. Res. Lett. 37(4):255–260.Crossref, Google Scholar
• Danna E, Fenelon M, Gu Z, Wunderling R (2007) Generating multiple solutions for mixed integer programming problems. Proc. Internat. Conf. on Integer Programming and Combinatorial Optim. (Springer, Berlin), 280–294.Crossref, Google Scholar
• Demirovic E, Schwind N (2020) Representative solutions for bi-objective optimisation. Proc. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1436–1443.Google Scholar
• Eckstein J (1996) Parallel branch-and-bound methods for mixed integer programming. Applications on Advanced Architecture Computers (SIAM, Philadelphia), 141–153.Crossref, Google Scholar
• Eysenbach B, Gupta A, Ibarz J, Levine S (2018) Diversity is all you need: Learning skills without a reward function. Preprint, submitted October 9, https://arxiv.org/abs/ 1802.06070.Google Scholar
• Gamrath G, Anderson D, Bestuzheva K, Chen W-K, Eifler L, Gasse M, Gemander P, et al. (2020) The SCIP Optimization Suite 7.0. Technical report, Optimization Online.Google Scholar
• Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel PM, et al. (2021) MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Math. Programming Comput. 13(3):443–490.Crossref, Google Scholar
• Glover F, Kuo C-C, Dhir KS (1998) Heuristic algorithms for the maximum diversity problem. J. Inform. Optim. Sci. 19(1):109–132.Google Scholar
• Glover F, Løkketangen A, Woodruff DL (2000) Scatter search to generate diverse MIP solutions. Computing Tools for Modeling, Optimization and Simulation (Springer, Berlin), 299–317.Crossref, Google Scholar
• Greistorfer P, Løkketangen A, Voß S, Woodruff DL (2008) Experiments concerning sequential vs. simultaneous maximization of objective function and distance. J. Heuristics 14(6):613–625.Crossref, Google Scholar
• He Y, Cai K, Zhao Z-L, Yi MX (2020) Stochastic approaches to generating diverse and competitive structural designs in topology optimization. Finite Elements Analysis Design 173:103399.Crossref, Google Scholar
• Joseph RV, Dasgupta T, Tuo R, Wu CFJ (2015) Sequential exploration of complex surfaces using minimum energy designs. Technometrics 57(1):64–74.Crossref, Google Scholar
• Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna E, et al. (2011) MIPLIB 2010. Math. Programming Comput. 3(2):103–163.Crossref, Google Scholar
• Kumar S, Kumar A, Levine S, Finn C (2020) One solution is not all you need: Few-shot extrapolation via structured MaxEnt RL. Adv. Neural Inform. Processing Systems 33:8198–8210.Google Scholar
• Kuo C-C, Glover F, Dhir KS (1993) Analyzing and modeling the maximum diversity problem by zero-one programming. Decision Sci. 24(6):1171–1185.Crossref, Google Scholar
• Lavine M (2021) Whim: Function approximation where it matters. Comm. Statist. Simulation Comput. 50(12):3839–3869.Crossref, Google Scholar
• Lee S, Phalakornkule C, Domach MM, Grossmann IE (2000) Recursive milp model for finding all the alternate optima in lp models for metabolic networks. Comput. Chemical Engrg. 24(2–7):711–716.Crossref, Google Scholar
• Liebchen C, Möhring R (2003) Information on MIPLIB’s timetab-instances. Technical report, Department of Mathematics, Technische Universität Berlin, Berlin.Google Scholar
• Liebchen C, Peeters L (2002) On cyclic timetabling and cycles in graphs. Technical report, Technical University, Berlin.Google Scholar
• Mouret J-B, Clune J (2015) Illuminating search spaces by mapping elites. Preprint, submitted April 20, https://arxiv.org/abs/ 1504.04909.Google Scholar
• Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, et al. (2011) Scikit-learn: Machine learning in Python. J. Machine Learn. Res. 12:2825–2830.Google Scholar
• Petit T, Trapp AC (2015) Finding diverse solutions of high quality to constraint optimization problems. Proc. 24th Internat. Joint Conf. on Artificial Intelligence (IJCAI, California).Google Scholar
• Petit T, Trapp AC (2019) Enriching solutions to combinatorial problems via solution engineering. INFORMS J. Comput. 31(3):429–444.Link, Google Scholar
• Rodríguez-Mier P, Poupin N, de Blasio C, Le Cam L, Jourdan F (2021) DEXOM: Diversity-based enumeration of optimal context-specific metabolic networks. PLOS Comput. Biology 17(2):e1008730.Crossref, Google Scholar
• Rudin C, Chen C, Chen Z, Huang H, Semenova L, Zhong C (2022) Interpretable machine learning: Fundamental principles and 10 grand challenges. Statist. Survey 16:1–85.Crossref, Google Scholar
• Schittekat P, Sörensen K (2009) OR practice—Supporting 3PL decisions in the automotive industry by generating diverse solutions to a large-scale location-routing problem. Oper. Res. 57(5):1058–1067.Link, Google Scholar
• Semenova L, Rudin C, Parr R (2019) A study in Rashomon curves and volumes: A new perspective on generalization and model simplicity in machine learning. Preprint, submitted August 5, https://arxiv.org/abs/ 1908.01755.Google Scholar
• Serra T (2020) Enumerative branching with less repetition. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. Lecture Notes in Computer Science (Springer, Berlin), 399–416.Google Scholar
• Serra T, Hooker JN (2020) Compact representation of near-optimal integer programming solutions. Math. Programming 182(1–2):199–232.Crossref, Google Scholar
• Sharifnia SME, Biyouki SA, Sawhney R, Hwangbo H (2021) Robust simulation optimization for supply chain problem under uncertainty via neural network metamodeling. Comput. Industry Engrg. 162:107693.Crossref, Google Scholar
• Trapp AC, Konrad RA (2015) Finding diverse optima and near-optima to binary integer programs. IIE Trans. 47(11):1300–1312.Crossref, Google Scholar
• Tsoupidi RM, Lozano RC, Baudry B (2020) Principles and practice of constraint programming. Proc. 26th Internat. Conf. Lecture Notes in Computer Science (Springer, Berlin), 791–808.Google Scholar
• Van Hentenryck P, Coffrin C, Gutkovich B (2009) Constraint-based local search for the automatic generation of architectural tests. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin), 787–801.Google Scholar
• Voll P, Jennings M, Hennen M, Shah N, Bardow A (2015) The optimum is not enough: A near-optimal solution paradigm for energy systems synthesis. Energy 82:446–456.Crossref, Google Scholar
• Wang B, Zhou Y, Zhou Y, Xu S, Niu B (2018) Diverse competitive design for topology optimization. Structural Multidisciplinary Optim. 57(2):891–902.Crossref, Google Scholar
• Watters LJ (1967) Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper. Res. 15(6):1171–1174.Link, Google Scholar
• Zahavy T, O’Donoghue B, Barreto A, Mnih V, Flennerhag S, Singh S (2021) Discovering diverse nearly optimal policies with successor features. Preprint, submitted June 1, https://arxiv.org/abs/ 2106.00669.Google Scholar
• Zaslavsky E, Singh M (2006) A combinatorial optimization approach for diverse motif finding applications. Algorithms Molecular Biology 1(1):1–13.Crossref, Google Scholar
• Zhou Y, Haftka RT, Cheng G (2016) Balancing diversity and performance in global optimization. Structural Multidisciplinary Optim. 54(4):1093–1105.Crossref, Google Scholar