J Shanghai Jiaotong Univ Sci

Journal of Shanghai Jiaotong University(Science) >

2020 , Vol. 25 >Issue 5: 623 - 629

DOI: https://doi.org/10.1007/s12204-020-2220-1

Numerical Computation of a Mixed-Integer Optimal Control Problem Based on Quantum Annealing

Expand
  • (1. Automation School, Beijing University of Posts and Telecommunications, Beijing 100876, China;
    2. Qingdao Topscomm Communication Co., Ltd., Qingdao 266024, Shandong, China)

Online published: 2020-09-11

Fold

Abstract

It is extremely challenging to solve the mixed-integer optimal control problems (MIOCPs) due to
the complex computation in solving the integer decision variables. This paper presents a new method based
on quantum annealing (QA) to solve MIOCP. The QA is a metaheuristic which applies quantum tunneling in
the annealing process. It has a faster convergence speed in optimal-searching and is less likely to run into local
minima. Hence, QA is applied to deal with this kind of optimization problems. First, MIOCP is transformed into
a mixed-integer nonlinear programming (MINLP). Then, a method based on QA is adopted to solve the MINLP
and acquire the optimal solution. At last, two benchmark examples including Lotka-Volterra type fishing problem
and distillation column are presented and solved. The effectiveness of the methodology is verified by the acquired
optimal schemes.

Key words： mixed-integer; optimal control; quantum annealing; distillation column

Cite this article

LIU Zhe, LI Shurong, GE Yulei . Numerical Computation of a Mixed-Integer Optimal Control Problem Based on Quantum Annealing[J]. Journal of Shanghai Jiaotong University(Science), 2020 , 25(5) : 623 -629 . DOI: 10.1007/s12204-020-2220-1

References

[1] KOCIS G R, GROSSMANN I E. Global optimization of nonconvex mixed-integer nonlinear programming(MINLP) problems in process synthesis [J]. Industrial & Engineering Chemistry Research, 1988, 27(8): 1407-1421.
[2] ALLGOR R J, BARTON P I. Mixed-integer dynamic optimization I: Problem formulation [J]. Computers &Chemical Engineering, 1999, 23(4/5): 567-584.
[3] KESAVAN P, ALLGOR R J, GATZKE E P, et al.Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs [J]. Mathematical Programming, 2004, 100(3): 517-535.
[4] FLOUDAS C A. Nonlinear and mixed-integer optimization:Fundamentals and applications [M]. New York: Oxford University Press, 1995.
[5] BERGER J, BOUKHTOUTA A, BENMOUSSA A,et al. A new mixed-integer linear programming model for rescue path planning in uncertain adversarial environment[J]. Computers & Operations Research, 2012,39(12): 3420-3430.
[6] BIEGLER L T, SENTONI G B. Efficient formulation and solution of nonlinear model predictive control problem [J]. Latin American Applied Research, 2000,30(4): 315-324.
[7] GE Y, LI S, CHANG P, et al. Optimization of ASP flooding based on dynamic scale IDP with mixedinteger[J]. Applied Mathematical Modelling, 2017, 44:727-742.
[8] PENG Z, YANG Z, TU J. Genetic algorithm based tikhonov regularization method for displacement reconstruction[J]. Journal of Shanghai Jiao Tong University(Science), 2019, 24(3): 294-298.
[9] GACEM A, BENATTOUS D. Hybrid genetic algorithm and particle swarm for optimal power flow with non-smooth fuel cost functions [J]. International Journal of System Assurance Engineering and Management,2017, 8(1): 146-153.
[10] TAKSHI H, DOGAN G, ARSLAN H. Joint optimization of device to device resource and power allocation based on genetic algorithm [J]. IEEE Access, 2018, 6:21173-21183.
[11] ROSHANI A, GIGLIO D. Simulated annealing algorithms for the multi-manned assembly line balancing problem: Minimising cycle time [J]. International Journal of Production Research, 2017, 55(10): 2731-2751.
[12] FINNILA A B, GOMEZ M A, SEBENIK C, et al.Quantum annealing: A new method for minimizing multidimensional functions [J]. Chemical Physics Letters,1994, 219(5/6): 343-348.
[13] CROSSON E, HARROW A W. Simulated quantum annealing can be exponentially faster than classical simulated annealing [C]//IEEE 57th Annual Symposium on Foundations of Computer Science. New runswick, NJ, USA: IEEE, 2016: 714-723.
[14] SYRICHAS A, CRISPIN A. Large-scale vehicle routing problems: Quantum Annealing, tunings and results[J]. Computers & Operations Research, 2017, 87:52-62.
[15] CHEN H, KONG X, CHONG B, et al. Experimental demonstration of a quantum annealing algorithm for the traveling salesman problem in a nuclear-magneticresonance quantum simulator [J]. Physical Review A,2011, 83: 032314.
[16] ZHOU F, ZHANG Z, WU C, et al. Optimization of numerical control program and machining simulation based on VERICUT [J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(6): 763-768.
[17] DAS A, CHAKRABARTI B K. Colloquium: Quantum annealing and analog quantum computation [J].Reviews of Modern Physics, 2008, 80: 1061-1081.
[18] SAGER S. A benchmark library of mixed-integer optimal control problems [M]//Mixed Integer Nonlinear Programming. New York: Springer, 2012: 631-670.
[19] BANSAL V, SAKIZLIS V, ROSS R, et al. New algorithms for mixed-integer dynamic optimization [J].Computers & Chemical Engineering, 2003, 27(5): 647-668.

Options
Outlines

/

〈 〉