MIPLIBing: Seamless Benchmarking of Mathematical Optimization Problems and Metadata Extensions
- PDF / 436,404 Bytes
- 6 Pages / 439.642 x 666.49 pts Page_size
- 32 Downloads / 226 Views
MIPLIBing: Seamless Benchmarking of Mathematical Optimization Problems and Metadata Extensions Thiago Serra1
· Ryan J. O’Neil2
Received: 13 February 2020 / Accepted: 18 August 2020 / © Springer Nature Switzerland AG 2020
Abstract Public libraries of problems such as Mixed Integer Programming Library (MIPLIB) are fundamental to creating a common benchmark for measuring algorithmic advances across mathematical optimization solvers. They also often provide metadata on problem structure, hardness with respect to state-of-the-art solvers, and solutions with the best objective function value on record. In this short paper, we discuss some ways in which such metadata can be leveraged to create a seamless testing experience. In particular, we present MIPLIBing: a Python library that automatically downloads queried subsets from the current versions of MIPLIB, MINLPLib, and QPLIB, provides a centralized local cache across projects, and tracks the best solution values and bounds on record for each problem. While inspired by similar use cases from other areas, we reflect on the specific needs of mathematical optimization and discuss opportunities to extend benchmark sets to facilitate experimentation with different model structures. Keywords Benchmarking · Mathematical optimization · Problem libraries
1 Introduction Mixed integer programming (MIP) is an enormously successful general-purpose modeling and optimization tool. A vast array of practical problems can be formulated as mixed integer linear programs (MILPs), one of the most fundamental forms Thiago Serra
[email protected] Ryan J. O’Neil [email protected] https://nextmv.io/
1
Bucknell University, Lewisburg, PA, USA
2
nextmv, Philadelphia, PA, USA
24
Page 2 of 6
SN Operations Research Forum
(2020) 1:24
of MIP, which take the form: max {cx | Ax ≤ b, x ∈ Zp × Rq }. Wide interest in improving MIP technology has led to significant algorithmic advances [4, 6, 14, 15, 17]. In fact, an even broader array of practical problems can be formulated if the objective function and the constraints are nonlinear and able to represent other forms of discontinuity. In the last decades, the software speedups obtained by such advances have at times outpaced the already impressive hardware speedups of modern computers [4]. Hence, although many practical problems belong to the NP-hard class and are therefore theoretically intractable at scale, modern solvers can frequently solve them at the sizes required by industry. Part of this success is undoubtedly due to open, standard benchmark instances gathered from real-world problems and shared by the community, which have been used to evaluate solvers in public benchmarks [18]. These test sets are fundamental to the study and advancement of solver performance. One of the earliest benchmarks was Netlib [10], a collection of linear programs (LPs) that could be queried and distributed by email in 1985. The Mixed Integer Programming Library (MIPLIB) is a collection of MILPs that use the same MPS file format and file compression to
Data Loading...
