透過自適應增強拉格朗日方法自動調整二次無約束二元最佳化形式的限制項參數

Abstract

通常為了解決變數多的NP問題，會需要花費非常多的時間去求解，但我們可以利用啟發式演算法來在合理的時間範圍內求得進似解，其中著名的模擬退火就是其中之一，另一個利用了量子現象的次經驗演算法來求解NP問題的著名方法則是量子退火。但是這兩個演算法能夠解決的問題有限制，只能求解沒有限制條件的問題，不過大部分的NP問題都含有限制條件，所以必須要預處理問題將其轉化成無限制條件問題，在本論文中，我們將有約束的問題轉化為二次無約束二進制優化（QUBO）問題或伊辛模型問題，然後通過模擬退火和量子退火找到可行解。我們採用了三種方法來選擇QUBO問題中適當的約束(懲罰)項參數(係數)，第一個方法是懲罰法，第二個是增廣拉格朗日法，第三個則是解決前面兩種會有的潛在缺陷而提出的自適應增廣拉格朗日法。我們在模擬退火和量子退火機器上測試了這三種方法在三種類型問題上的解：隨機 QUBO 問題、旅行推銷員問題和背包問題。通過分析找到可行解所需的迭代次數、可行解與最優解之間的差距以及找到最優解的概率來評估這三種方法的性能。結果發現，自適應增廣拉格朗日方法的性能優於其他兩種方法。

Typically, it would take a considerable amount of time to solve nondeterministic polynomial (NP) time problems with many variables. Heuristic algorithms can be used to obtain approximate solutions within a reasonable time frame. Among these, the well-known simulated annealing is one classical method. Another method that utilizes quantum property to solve NP problems is quantum annealing. These two algorithms can only solve problems without constraints, but most NP problems do involve constraints. Therefore, it is necessary to preprocess the problems to transform them into unconstrained ones. In this thesis, we transform constrained problems into quadratic unconstrained binary optimization (QUBO) problems or Ising model problems, and then find feasible solutions via simulated and quantum annealing. We employ three methods for choosing suitable parameters (coefficients) of constraint (penalty) terms in the QUBO problems. The first method is the penalty method, the second is the augmented Lagrangian method, and the third is the adaptive augmented Lagrangian method proposed to address potential flaws in the first two methods. We tested the three methods for finding solutions on simulated annealing and quantum annealing machines for three different kinds of problems: random QUBO problems, the traveling salesman problem, and the knapsack problem. The performance of the three methods is evaluated by analyzing the number of iterations to find a feasible solution, the gap between the feasible solution and the optimal solution, and the probability of finding the optimal solution. It is found that the adaptive augmented Lagrangian method has a better performance than the other two methods.