A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

References

• Anderson R, Huchette J, Ma W, Tjandraatmadja C, Vielma JP (2020) Strong mixed-integer programming formulations for trained neural networks. Math. Programming 183(1):3–39.Crossref, Google Scholar
• Angulo G, Ahmed S, Dey SS, Kaibel V (2015) Forbidden vertices. Math. Oper. Res. 40(2):350–360.Link, Google Scholar
• Balas E (1985) Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebraic Discrete Methods 6(3):466–486.Crossref, Google Scholar
• Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3):3–44.Crossref, Google Scholar
• Baltean-Lugojan R, Misener R (2018) Piecewise parametric structure in the pooling problem: From sparse strongly-polynomial solutions to NP-hardness. J. Global Optim. 71(4):655–690.Crossref, Google Scholar
• Bärmann A, Martin A, Schneider O (2023) The bipartite Boolean quadric polytope with multiple-choice constraints. SIAM J. Optim. 33(4):2909–2934.Crossref, Google Scholar
• Bienstock D, Munoz G (2018) LP formulations for polynomial optimization problems. SIAM J. Optim. 28(2):1121–1150.Crossref, Google Scholar
• Biggs M, Hariss R, Perakis G (2023) Constrained optimization of objective functions determined from random forests. Production Oper. Management 32(2):397–415.Crossref, Google Scholar
• Buchheim C, Crama Y, Rodríguez-Heck E (2019) Berge-acyclic multilinear 0–1 optimization problems. Eur. J. Oper. Res. 273(1):102–107.Crossref, Google Scholar
• Ceria S, Soares J (1999) Convex programming for disjunctive convex optimization. Math. Programming 86(3):595–614.Crossref, Google Scholar
• Chen YC, Mišić VV (2021) Assortment optimization under the decision forest model. Preprint, submitted March 25, http://dx.doi.org/10.2139/ssrn.3812654.Google Scholar
• Chen YC, Mišić VV (2022) Decision forest: A nonparametric approach to modeling irrational choice. Management Sci. 60(10):7090–7111.Link, Google Scholar
• Cortez P, Cerdeira A, Almeida F, Matos T, Reis J (2009) Modeling wine preferences by data mining from physicochemical properties. Decision Support Systems 47(4):547–553.Crossref, Google Scholar
• Crama Y (1993) Concave extensions for nonlinear 0–1 maximization problems. Math. Programming 61(1):53–60.Crossref, Google Scholar
• Crama Y, Rodríguez-Heck E (2017) A class of valid inequalities for multilinear 0–1 optimization problems. Discrete Optim. 25:28–47.Crossref, Google Scholar
• Dash S, Günlük O, Wei D (2018) Boolean decision rules via column generation. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Deepa C, Sathiya Kumari K, Pream Sudha V (2010) A tree based model for high performance concrete mix design. Internat. J. Engrg. Sci. Tech. 2(9):4640–4646.Google Scholar
• Del Pia A, Khajavirad A (2018a) The multilinear polytope for acyclic hypergraphs. SIAM J. Optim. 28(2):1049–1076.Crossref, Google Scholar
• Del Pia A, Khajavirad A (2018b) On decomposability of multilinear sets. Math. Programming 170(2):387–415.Crossref, Google Scholar
• Del Pia A, Khajavirad A (2024) A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs. Math. Programming 207:269–301.Crossref, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Fernández-Delgado M, Cernadas E, Barro S, Amorim D (2014) Do we need hundreds of classifiers to solve real world classification problems? J. Mach. Learn. Res. 15(1):3133–3181.Google Scholar
• Ferreira KJ, Lee BHA, Simchi-Levi D (2016) Analytics for an online retailer: Demand forecasting and price optimization. Manufacturing Service Oper. Management 18(1):69–88.Link, Google Scholar
• Gupte A, Kalinowski T, Rigterink F, Waterer H (2020) Extended formulations for convex hulls of some bilinear functions. Discrete Optim. 36:100569.Crossref, Google Scholar
• Gurobi Optimization LLC (2021) Gurobi optimizer reference manual. Accessed August 14, 2024, http://www.gurobi.com.Google Scholar
• He T, Tawarmalani M (2021) A new framework to relax composite functions in nonlinear programs. Math. Programming 190(1):427–466.Crossref, Google Scholar
• Herrera M, Torgo L, Izquierdo J, Pérez-García R (2010) Predictive models for forecasting hourly urban water demand. J. Hydrology 387(1–2):141–150.Crossref, Google Scholar
• Hoffman AJ (1976) Total unimodularity and combinatorial theorems. Linear Algebra Appl. 13(1–2):103–108.Crossref, Google Scholar
• Huchette J, Vielma JP (2023) Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools. Oper. Res. 71(5):1835–1856.Link, Google Scholar
• Ibaraki T (1976) Integer programming formulation of combinatorial optimization problems. Discrete Math. 16(1):39–52.Crossref, Google Scholar
• Kim J, Richard JPP, Tawarmalani M (2024) A snapshot of the software and data used in the paper “A reciprocity between tree ensemble optimization and multilinear optimization”. Accessed August 14, 2024, http://dx.doi.org/10.5281/zenodo.11407841.Google Scholar
• Kim J, Tawarmalani M, Richard JPP (2021) Convexification of permutation-invariant sets and an application to sparse principal component analysis. Math. Oper. Res. 47(4):2547–2584.Link, Google Scholar
• Kim J, Taslimi B, Richard JPP, Tawarmalani M (2019) Polyhedral results for tree ensembles optimization. 2019 INFORMS Annual Meeting (INFORMS, Catonsville, MD).Google Scholar
• Kis T, Horváth M (2021) Ideal, non-extended formulations for disjunctive constraints admitting a network representation. Math. Programming 194:831–869.Crossref, Google Scholar
• Luedtke J, Namazifar M, Linderoth J (2012) Some results on the strength of relaxations of multilinear functions. Math. Programming 136(2):325–351.Crossref, Google Scholar
• Ma J, Sheridan RP, Liaw A, Dahl GE, Svetnik V (2015) Deep neural nets as a method for quantitative structure–activity relationships. J. Chem. Inform. Model. 55(2):263–274.Crossref, Google Scholar
• Misener R, Floudas CA (2012) Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math. Programming 136(1):155–182.Crossref, Google Scholar
• Mišić VV (2020) Optimization of tree ensembles. Oper. Res. 68(5):1605–1624.Link, Google Scholar
• Mistry M, Letsios D, Krennrich G, Lee RM, Misener R (2021) Mixed-integer convex nonlinear optimization with gradient-boosted trees embedded. INFORMS J. Comput. 33(3):1103–1119.Link, Google Scholar
• Moré JJ, Wild SM (2009) Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20(1):172–191.Crossref, Google Scholar
• Rikun AD (1997) A convex envelope formula for multilinear functions. J. Global Optim. 10(4):425–437.Crossref, Google Scholar
• Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Schrijver A (1983) Short proofs on the matching polyhedron. J. Combinatorial Theory Series B 34(1):104–108.Crossref, Google Scholar
• Sherali HD (1997) Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Math. Vietnam. 22(1):245–270.Google Scholar
• Stubbs RA, Mehrotra S (1999) A branch-and-cut method for 0-1 mixed convex programming. Math. Programming 86(3):515–532.Crossref, Google Scholar
• Su G, Wei D, Varshney KR, Malioutov DM (2016) Learning sparse two-level Boolean rules. Proc. 2016 IEEE 26th Internat. Workshop Mach. Learning Signal Processing (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Svetnik V, Liaw A, Tong C, Culberson JC, Sheridan RP, Feuston BP (2003) Random forest: A classification and regression tool for compound classification and QSAR modeling. J. Chem. Inform. Comput. Sci. 43(6):1947–1958.Crossref, Google Scholar
• Tawarmalani M (2010) Inclusion certificates and simultaneous convexification of functions. Accessed August 14, 2024, http://www.optimization-online.org/DB_HTML/2010/09/2722.html.Google Scholar
• Tawarmalani M, Sahinidis NV (2002) Convex extensions and envelopes of lower semi-continuous functions. Math. Programming 93(2):247–263.Crossref, Google Scholar
• Thebelt A, Kronqvist J, Mistry M, Lee RM, Sudermann-Merx N, Misener R (2021) ENTMOOT: A framework for optimization over ensemble tree models. Comput. Chemical Engrg. 151:107343.Crossref, Google Scholar
• Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3–57.Crossref, Google Scholar
• Vielma JP, Nemhauser GL (2011) Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Programming 128(1):49–72.Crossref, Google Scholar
• Vielma JP, Ahmed S, Nemhauser G (2010) Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions. Oper. Res. 58(2):303–315.Link, Google Scholar
• Xu Y, Adams W, Gupte A (2021) Polyhedral analysis of symmetric multilinear polynomials over box constraints. Preprint, submitted December 11, https://arxiv.org/abs/2012.06394.Google Scholar
• Yeh IC (1998) Modeling of strength of high-performance concrete using artificial neural networks. Cement Concrete Res. 28(12):1797–1808.Crossref, Google Scholar