Li, X;
Han, X;
Zhou, Z;
Yuan, M;
Zeng, J;
Wang, J;
(2021)
Grassland: A Rapid Algebraic Modeling System for Million-variable Optimization.
In: Demartini, G and Zuccon, G and Culpepper, JS and Huang, Z and Tong, H, (eds.)
CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management.
(pp. pp. 3925-3934).
Association for Computing Machinery (ACM): New York, NY, USA.
Preview |
Text
2108.04586v1.pdf - Other Download (1MB) | Preview |
Abstract
An algebraic modeling system (AMS) is a type of mathematical software for optimization problems, which allows users to define symbolic mathematical models in a specific language, instantiate them with given source of data, and solve them with the aid of external solver engines. With the bursting scale of business models and increasing need for timeliness, traditional AMSs are not sufficient to meet the following industry needs: 1) million-variable models need to be instantiated from raw data very efficiently; 2) Strictly feasible solution of million-variable models need to be delivered in a rapid manner to make up-to-date decisions against highly dynamic environments. Grassland is a rapid AMS that provides an end-to-end solution to tackle these emerged new challenges. It integrates a parallelized instantiation scheme for large-scale linear constraints, and a sequential decomposition method that accelerates model solving exponentially with an acceptable loss of optimality. Extensive benchmarks on both classical models and real enterprise scenario demonstrate 6-10x speedup of Grassland over state-of-the-art solutions on model instantiation. Our proposed system has been deployed in the large-scale real production planning scenario of Huawei. With the aid of our decomposition method, Grassland successfully accelerated Huawei's million-variable production planning simulation pipeline from hours to 3-5 minutes, supporting near-real-time production plan decision making against highly dynamic supply-demand environment.
| Type: | Proceedings paper |
|---|---|
| Title: | Grassland: A Rapid Algebraic Modeling System for Million-variable Optimization |
| Event: | CIKM '21: The 30th ACM International Conference on Information & Knowledge Management |
| ISBN-13: | 9781450384469 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3459637.3481925 |
| Publisher version: | https://doi.org/10.1145/3459637.3481925 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | algebraic modeling system, large-scale optimization |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10142951 |
Loading...
Loading...Loading...| 1. |  United States | 6 |
| 2. |  Russian Federation | 3 |
| 3. |  India | 2 |
| 4. |  United Kingdom | 2 |
| 5. |  Australia | 1 |
| 6. |  China | 1 |
| 7. |  Lithuania | 1 |
| 8. |  Turkey | 1 |
| 9. |  Romania | 1 |
Archive Staff Only
 |
View Item |
