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

doi:10.1007/s12204-020-2220-1

Abstract

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

摘要： 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.

关键词: mixed-integer| optimal control| quantum annealing| distillation column

CLC Number:

TP 301

LIU Zhe, LI Shurong, GE Yulei . Numerical Computation of a Mixed-Integer Optimal Control Problem Based on Quantum Annealing[J]. J Shanghai Jiaotong Univ Sci, 2020, 25(5): 623-629.

References 19

[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.