Quantum-Inspired Solvers on Mixed-Integer Linear Programming Problem

被引：0
作者：
Wang, Hao [1 ]
Pan, Yu [2 ]
Cui, Wei [1 ]
机构：
[1] South China Univ Technol, Sch Automat Sci & Engn, Guangzhou 510641, Guangdong, Peoples R China
[2] Zhejiang Univ, Coll Control Sci & Engn, Hangzhou 310058, Peoples R China
来源：
2022 41ST CHINESE CONTROL CONFERENCE (CCC) | 2022年
基金：
中国国家自然科学基金;
关键词：
Mixed-integer Linear Programming; Solver; Annealer; Coherent Ising Machine; FORMULATION; NETWORK;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Mixed-integer linear programming (MILP) plays a crucial role in artificial intelligence, biochemistry, finance, cryptography, etc. Notwithstanding popular for decades, the researches of MILP solvers are still limited by the resource consumption caused by complexity and failure of Moore's Law. Quantum-inspired Ising machines, as a new computing paradigm, can be used to solve integer programming problems by reducing them into Ising models. Therefore, it is necessary to understand the technical evolution of quantum inspired solvers to break the bottleneck. In this paper, the concept and traditional algorithms for MILP are introduced. Then, focused on Ising model, the principle and implementations of annealers and coherent Ising machines are summarized. Finally, the paper discusses the challenges and opportunities of miniaturized solvers in the future.
引用
收藏
页码：5693 / 5698
页数：6
相关论文
共 56 条
[1]  
Aadit N. A., 2021, ARXIV211002481
[2]  
Aarts EHL, 1987, SIMULATED ANNEALING, P7, DOI DOI 10.1007/978-94-015-7744-1_2
[3]   SCIP: solving constraint integer programs [J].
Achterberg, Tobias .
MATHEMATICAL PROGRAMMING COMPUTATION, 2009, 1 (01) :1-41
[4]   INTEGER LINEAR-PROGRAMMING FORMULATION FOR A VEHICLE-ROUTING PROBLEM [J].
ACHUTHAN, NR ;
CACCETTA, L .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 52 (01) :86-89
[5]   Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems [J].
Ajagekar, Akshay ;
Humble, Travis ;
You, Fengqi .
COMPUTERS & CHEMICAL ENGINEERING, 2020, 132
[6]   Computational protein design as an optimization problem [J].
Allouche, David ;
Andre, Isabelle ;
Barbe, Sophie ;
Davies, Jessica ;
de Givry, Simon ;
Katsirelos, George ;
O'Sullivan, Barry ;
Prestwich, Steve ;
Schiex, Thomas ;
Traore, Seydou .
ARTIFICIAL INTELLIGENCE, 2014, 212 :59-79
[7]  
[Anonymous], 2017, arXiv preprint arXiv:1709.08102
[8]   Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer [J].
Aramon, Maliheh ;
Rosenberg, Gili ;
Valiante, Elisabetta ;
Miyazawa, Toshiyuki ;
Tamura, Hirotaka ;
Katzgraber, Helmut G. .
FRONTIERS IN PHYSICS, 2019, 7 (APR)
[9]   Mixed integer programming: A historical perspective with Xpress-MP [J].
Ashford, Robert .
ANNALS OF OPERATIONS RESEARCH, 2007, 149 (01) :5-17
[10]  
Cai Jun, 2014, A practical heuristic for finding graph minors
123456