检索结果-内蒙古大学图书馆

PYSCIPOPT-ML: EMBEDDING TRAINED MACHINE LEARNING MODELS INTO MIXED-INTEGER PROGRAMS

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Turner, Mark Chmiela, Antonia Koch, Thorsten Winkler, Michael Zuse Institute Berlin Department of Mathematical Optimization Takustr. 7 Berlin14195 Germany Chair of Software and Algorithms for Discrete Optimization Institute of Mathematics Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany Gurobi GmbH Ulmenstr. 37-39 Frankfurt am Main60325 Germany

A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems, information about the relationships between variables is either incomplete or highly complex, making it difficult or even impossible to model the problem directly. To overcome these hurdles, machine learning (ML) predictors are often used to represent these relationships and are then embedded in the MIP as surrogate models. Due to the large amount of available ML frameworks and the complexity of many ML predictors, formulating such predictors into MIPs is a highly non-trivial task. In this paper, we introduce PySCIPOpt-ML, an open-source tool for the automatic formulation and embedding of trained ML predictors into MIPs. By directly interfacing with a broad range of commonly used ML frameworks and an open-source MIP solver, PySCIPOpt-ML provides a way to easily integrate ML constraints into optimisation problems. Alongside PySCIPOpt-ML, we introduce, SurrogateLIB, a library of MIP instances with embedded ML constraints, and present computational results over SurrogateLIB, providing intuition on the scale of ML predictors that can be practically embedded. © 2023, CC BY.

关键词： Machine learning

Progress in Mathematical Programming Solvers from 2001 to 2020

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Koch, Thorsten Berthold, Timo Pedersen, Jaap Vanaret, Charlie Technische Universität Berlin Software and Algorithms for Discrete Optimization Straße des 17. Juni 135 Berlin10623 Germany Zuse Institute Berlin Takustraße 7 Berlin14195 Germany Fair Isaac Germany GmbH Stubenwald-Allee 19 Bensheim64625 Germany

This study investigates the progress made in lp and milp solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving lp/milp, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for lp and around 50 for milp, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time. © 2022, CC BY-NC-ND.

关键词： Computer hardware

ADAPTIVE CUT SELECTION IN MIXED-INTEGER LINEAR PROGRAMMING

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Turner, Mark Koch, Thorsten Serrano, Felipe Winkler, Michael Software and Algorithms for Discrete Optimization Institute of Mathematics Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany Zuse Institute Berlin Department of Mathematical Optimization Takustr. 7 Berlin14195 Germany I2DAMO GmbH Englerallee 19 Berlin14195 Germany Gurobi GmbH Ulmenstr. 37-39 Frankfurt am Main60325 Germany

Cutting plane selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017 and a neural network verification data set. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://***/Opt-Mucca/*** Codes 90-05 © 2022, CC BY.

关键词： Reinforcement learning

The variational bayesian inference for network autoregression models

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Lai, Wei-Ting Chen, Ray-Bing Chen, Ying Koch, Thorsten Department of Statistics National Cheng Kung University Tainan Taiwan Institute of Data Science National Cheng Kung University Tainan Taiwan Department of Mathematics National University of Singapore Singapore Risk Management Institute National University of Singapore Singapore Institute of Data Science National University of Singapore Singapore Chair of Software and Algorithms for Discrete Optimization Technische Universität Berlin Berlin Germany Department of Applied Algorithmic Intelligence Methods Zuse Institute Berlin Berlin Germany

We develop a variational Bayesian (VB) approach for estimating large-scale dynamic network models in the network autoregression framework. The VB approach allows for the automatic identification of the dynamic structure of such a model and obtains a direct approximation of the posterior density. Compared to Markov Chain Monte Carlo (MCMC) based sampling approaches, the VB approach achieves enhanced computational efficiency without sacrificing estimation accuracy. In the simulation study conducted here, the proposed VB approach detects various types of proper active structures for dynamic network models. Compared to the alternative approach, the proposed method achieves similar or better accuracy, and its computational time is halved. In a real data analysis scenario of day-ahead natural gas flow prediction in the German gas transmission network with 51 nodes between October 2013 and September 2015, the VB approach delivers promising forecasting accuracy along with clearly detected structures in terms of dynamic dependence. Copyright © 2021, The Authors. All rights reserved.

关键词： Computational efficiency

Enabling Research through the SCIP optimization Suite 8.0

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bestuzheva, Ksenia Besançon, Mathieu Chen, Wei-Kun Chmiela, Antonia Donkiewicz, Tim van Doornmalen, Jasper Eifler, Leon Gaul, Oliver Gamrath, Gerald Gleixner, Ambros Gottwald, Leona Graczyk, Christoph Halbig, Katrin Hoen, Alexander Hojny, Christopher van der Hulst, Rolf Koch, Thorsten Lübbecke, Marco Maher, Stephen J. Matter, Frederic Mühmer, Erik Müller, Benjamin Pfetsch, Marc E. Rehfeldt, Daniel Schlein, Steffan Schlösser, Franziska Serrano, Felipe Shinano, Yuji Sofranac, Boro Turner, Mark Vigerske, Stefan Wegscheider, Fabian Wellner, Philipp Weninger, Dieter Witzig, Jakob Zuse Institute Berlin Department AIS2T Takustr. 7 Berlin14195 Germany ZIB-AIS2T Germany School of Mathematics and Statistics Beijing Institute of Technology Beijing100081 China RWTH Aachen University Lehrstuhl für Operations Research Kackertstr. 7 Aachen52072 Germany Eindhoven University of Technology Department of Mathematics and Computer Science Netherlands ZIB-AIS2T I2DAMO GmbH Englerallee 19 Berlin14195 Germany ZIB-AIS2T HTW Berlin Germany Friedrich-Alexander Universität Erlangen-Nürnberg Department of Data Science Cauerstr. 11 Erlangen91058 Germany University of Twente Department of Discrete Mathematics and Mathematical Programming P.O. Box 217 Enschede7500 AE Netherlands Technische Universität Berlin Software and Algorithms for Discrete Optimization Straße des 17. Juni 135 Berlin10623 Germany ZIB Department A2IM Takustr. 7 Berlin14195 Germany RWTH Aachen-Lehrstuhl für OR Germany University of Exeter College of Engineering Mathematics and Physical Sciences Exeter United Kingdom Technische Universität Darmstadt Fachbereich Mathematik Dolivostr. 15 Darmstadt64293 Germany TU Darmstadt Fachbereich Mathematik Germany ZIB-A2IM Germany TU Berlin Germany ZIB-A2IM Software and Algorithms for Discrete Optimization Institute of Mathematics TU Berlin Germany GAMS Software GmbH c/o ZIB-AIS2T Germany

The SCIP optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this paper is on the role of the SCIP optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP's application as a research tool and as a platform for further developments. Further, the paper gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon *** Codes 90C05, 90C10, 90C11, 90C30, 90C90, 65Y05 Copyright © 2023, The Authors. All rights reserved.

关键词： Integer programming

The SCIP optimization suite 8.0

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bestuzheva, Ksenia Besançon, Mathieu Chen, Wei-Kun Chmiela, Antonia Donkiewicz, Tim Van Doornmalen, Jasper Eifler, Leon Gaul, Oliver Gamrath, Gerald Gleixner, Ambros Gottwald, Leona Graczyk, Christoph Halbig, Katrin Hoen, Alexander Hojny, Christopher Van Der Hulst, Rolf Koch, Thorsten Lübbecke, Marco Maher, Stephen J. Matter, Frederic Mühmer, Erik Müller, Benjamin Pfetsch, Marc E. Rehfeldt, Daniel Schlein, Steffan Schlösser, Franziska Serrano, Felipe Shinano, Yuji Sofranac, Boro Turner, Mark Vigerske, Stefan Wegscheider, Fabian Wellner, Philipp Weninger, Dieter Witzig, Jakob Zuse Institute Berlin Department AIS2T Takustr. 7 Berlin14195 Germany School of Mathematics and Statistics Beijing Institute of Technology Beijing100081 China RWTH Aachen University Lehrstuhl für Operations Research Kackertstr. 7 Aachen52072 Germany Technische Universiteit Eindhoven Department of Mathematics and Computer Science P.O. Box 513 Eindhoven5600 MB Netherlands I2DAMO GmbH Englerallee 19 Berlin14195 Germany Friedrich-Alexander Universität Erlangen-Nürnberg Department of Data Science Cauerstr. 11 Erlangen91058 Germany University of Twente Department of Discrete Mathematics and Mathematical Programming P.O. Box 217 Enschede7500 AE Netherlands Technische Universität Berlin Software and Algorithms for Discrete Optimization Straße des 17. Juni 135 Berlin10623 Germany Zuse Institute Berlin Department A2IM Takustr. 7 Berlin14195 Germany University of Exeter College of Engineering Mathematics and Physical Sciences Exeter United Kingdom Technische Universität Darmstadt Fachbereich Mathematik Dolivostr. 15 Darmstadt64293 Germany Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany Software and Algorithms for Discrete Optimization Institute of Mathematics Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany GAMS Software GmbH C/o Zuse Institute Berlin Department AIS2T Takustr. 7 Berlin14195 Germany

The SCIP optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in *** Codes 90C05, 90C10, 90C11, 90C30, 90C90, 65Y05 Copyright © 2021, The Authors. All rights reserved.

关键词： Integer programming

Article's Scientific Prestige: Measuring the impact of individual articles in the Web of Science

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Chen, Ying Koch, Thorsten Zakiyeva, Nazgul Liu, Kailiang Xu, Zhitong Chen, Chun-Houh Nakano, Junji Honda, Keisuke Department of Mathematics National University of Singapore 2 Science Drive 2 Singapore117543 Singapore Risk Management Institute National University of Singapore 21 Heng Mui Keng Terrace 04-03 Singapore119613 Singapore Technische Universität Berlin Software and Algorithms for Discrete Optimization Straße des 17. Juni 135 Berlin10623 Germany Zuse Institute Berlin Applied Algorithmic Intelligence Methods Department Takustraße 7 Berlin14195 Germany Research Institute Chongqing Internet Institute Building 5B No. 16 South Huashan Road Chongqing Liang Jiang New Area Chongqing China Department of Statistics and Data Science National University of Singapore 6 Science Drive 2 Singapore117546 Singapore The Institute of Statistical Science Academia Sinica 128 Academia Road Nankang Taipei11529 Taiwan Department of Global Management Chuo University 742-1 Higashinakano Hachioji Tokyo192-0393 Japan Institute of Statistical Mathematics 10-3 Midoricho Tachikawa Tokyo190-0014 Japan

We performed a citation analysis on the Web of Science publications consisting of more than 63 million articles and 1.45 billion citations on 254 subjects from 1981 to 2020. We proposed the Article's Scientific Prestige (ASP) metric and compared this metric to number of citations (#Cit) and journal grade in measuring the scientific impact of individual articles in the large-scale hierarchical and multi-disciplined citation network. In contrast to #Cit, ASP, that is computed based on the eigenvector centrality, considers both direct and indirect citations, and provides steady-state evaluation cross different disciplines. We found that ASP and #Cit are not aligned for most articles, with a growing mismatch amongst the less cited articles. While both metrics are reliable for evaluating the prestige of articles such as Nobel Prize winning articles, ASP tends to provide more persuasive rankings than #Cit when the articles are not highly cited. The journal grade, that is eventually determined by a few highly cited articles, is unable to properly reect the scientific impact of individual articles. The number of references and coauthors are less relevant to scientiffc impact, but subjects do make a difference. Copyright © 2022, The Authors. All rights reserved.

关键词：