17 results found
Tsay C, Kronqvist J, Thebelt A, et al., 2021, Partition-based formulations for mixed-integer optimization of trained ReLU neural networks, Publisher: arXiv
This paper introduces a class of mixed-integer formulations for trained ReLUneural networks. The approach balances model size and tightness by partitioningnode inputs into a number of groups and forming the convex hull over thepartitions via disjunctive programming. At one extreme, one partition per inputrecovers the convex hull of a node, i.e., the tightest possible formulation foreach node. For fewer partitions, we develop smaller relaxations thatapproximate the convex hull, and show that they outperform existingformulations. Specifically, we propose strategies for partitioning variablesbased on theoretical motivations and validate these strategies using extensivecomputational experiments. Furthermore, the proposed scheme complements knownalgorithmic approaches, e.g., optimization-based bound tightening capturesdependencies within a partition.
Kronqvist J, Misener R, Tsay C, 2021, Between steps: Intermediate relaxations between big-M and convex hull formulations, Publisher: arXiv
This work develops a class of relaxations in between the big-M and convexhull formulations of disjunctions, drawing advantages from both. The proposed"P-split" formulations split convex additively separable constraints into Ppartitions and form the convex hull of the partitioned disjuncts. Parameter Prepresents the trade-off of model size vs. relaxation strength. We examine thenovel formulations and prove that, under certain assumptions, the relaxationsform a hierarchy starting from a big-M equivalent and converging to the convexhull. We computationally compare the proposed formulations to big-M and convexhull formulations on a test set including: K-means clustering, P_ball problems,and ReLU neural networks. The computational results show that the intermediateP-split formulations can form strong outer approximations of the convex hullwith fewer variables and constraints than the extended convex hullformulations, giving significant computational advantages over both the big-Mand convex hull.
Kronqvist J, Misener R, 2020, A disjunctive cut strengthening technique for convex MINLP, OPTIMIZATION AND ENGINEERING, ISSN: 1389-4420
Thebelt A, Kronqvist J, Mistry M, et al., 2020, ENTMOOT: A framework for optimization over ensemble tree models, Publisher: arXiv
Gradient boosted trees and other regression tree models perform well in awide range of real-world, industrial applications. These tree models (i) offerinsight into important prediction features, (ii) effectively manage sparsedata, and (iii) have excellent prediction capabilities. Despite theiradvantages, they are generally unpopular for decision-making tasks andblack-box optimization, which is due to their difficult-to-optimize structureand the lack of a reliable uncertainty measure. ENTMOOT is our new frameworkfor integrating (already trained) tree models into larger optimizationproblems. The contributions of ENTMOOT include: (i) explicitly introducing areliable uncertainty measure that is compatible with tree models, (ii) solvingthe larger optimization problems that incorporate these uncertainty aware treemodels, (iii) proving that the solutions are globally optimal, i.e. no bettersolution exists. In particular, we show how the ENTMOOT approach allows asimple integration of tree models into decision-making and black-boxoptimization, where it proves as a strong competitor to commonly-usedframeworks.
Kronqvist J, Bernal DE, Grossmann IE, 2020, Using regularization and second order information in outer approximation for convex MINLP, MATHEMATICAL PROGRAMMING, Vol: 180, Pages: 285-310, ISSN: 0025-5610
Kronqvist J, Bernal DE, Lundell A, et al., 2019, A review and comparison of solvers for convex MINLP, OPTIMIZATION AND ENGINEERING, Vol: 20, Pages: 397-455, ISSN: 1389-4420
Kronqvist J, Bernal DE, Lundell A, et al., 2019, A center-cut algorithm for quickly obtaining feasible solutions and solving convex MINLP problems, COMPUTERS & CHEMICAL ENGINEERING, Vol: 122, Pages: 105-113, ISSN: 0098-1354
Kronqvist J, Lundell A, 2019, CONVEX MINLP - AN EFFICIENT TOOL FOR DESIGN AND OPTIMIZATION TASKS?, 9th International Conference on the Foundations of Computer Aided Process Design (FOCAPD), Publisher: ELSEVIER SCIENCE BV, Pages: 245-250, ISSN: 1570-7946
Lundell A, Kronqvist J, 2019, Integration of Polyhedral Outer Approximation Algorithms with MIP Solvers Through Callbacks And Lazy Constraints, 14th International Global Optimization Workshop (LeGO), Publisher: AMER INST PHYSICS, ISSN: 0094-243X
Kronqvist J, Lundell A, Westerlund T, 2018, Reformulations for utilizing separability when solving convex MINLP problems, 13th Global Optimization Workshop (GOW), Publisher: SPRINGER, Pages: 571-592, ISSN: 0925-5001
Manngard M, Kronqvist J, Boling JM, 2018, Structural learning in artificial neural networks using sparse optimization, NEUROCOMPUTING, Vol: 272, Pages: 660-667, ISSN: 0925-2312
Javaloyes-Anton J, Kronqvist J, Caballero JA, 2018, Simulation-Based Optimization of Chemical Processes Using the Extended Cutting Plane Algorithm, 28th European Symposium on Computer-Aided Process Engineering (ESCAPE), Publisher: ELSEVIER SCIENCE BV, Pages: 463-469, ISSN: 1570-7946
Eronen V-P, Kronqvist J, Westerlund T, et al., 2017, Method for solving generalized convex nonsmooth mixed-integer nonlinear programming problems, JOURNAL OF GLOBAL OPTIMIZATION, Vol: 69, Pages: 443-459, ISSN: 0925-5001
Lundell A, Kronqvist J, Westerlund T, 2017, SHOT A global solver for convex MINLP in Wolfram Mathematica, 27th European Symposium on Computer-Aided Process Engineering (ESCAPE), Publisher: ELSEVIER SCIENCE BV, Pages: 2137-2142, ISSN: 1570-7946
Kronqvist J, Lundell A, Westerlund T, 2017, A center-cut algorithm for solving convex mixed-integer nonlinear programming problems, 27th European Symposium on Computer-Aided Process Engineering (ESCAPE), Publisher: ELSEVIER SCIENCE BV, Pages: 2131-2136, ISSN: 1570-7946
Kronqvist J, Lundell A, Westerlund T, 2016, The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, 12th Global Optimization Workshop on Mathematical and Applied Global Optimization, Publisher: SPRINGER, Pages: 249-272, ISSN: 0925-5001
Kronqvist J, Lundell A, Westerlund T, 2015, The extended supporting hyperplane algorithmfor convex mixed-integer nonlinear programming, Journal of Global Optimization, ISSN: 0925-5001
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.