Parallelizing the branch-and-bound with isomorphism pruning algorithm for classifying orthogonal arrays

美國空軍理工學院開發了一種結合分支界限法與同構修剪的平行化演算法，在計算正交陣列時達成線性加速。該研究不僅優化既有模型，更首次完整分類出所有非 OD 等價的 OA(192,k,2,4)（k=9,10,11）。

整數線性規劃與分支界限法搜尋樹優化

整數線性規劃（ILP，變數受限為整數的數學模型）廣泛應用於求解具有嚴格整數條件的最佳化問題。在解決這類問題時，學界主要依賴分支界限法（B&B，一種尋找整數解的最佳化演算法）進行求解。此方法會遞迴地依照變數的可能數值進行分支，將原本龐大的母問題切割為許多子問題，進而建構出一棵龐大的 B&B 搜尋樹。每進入一個分支節點，系統便會捨棄變數的整數限制，改為計算相對容易的線性規劃（LP）鬆弛解。

在演算法的執行過程中，系統會根據節點的評估結果進行「修剪」。如果某個節點的 LP 鬆弛問題無解，或是其最佳目標值已經超越了目前已知的可行解，該節點底下的所有分支就會被直接捨棄。這個修剪動作能大幅減少不必要的運算，確保系統只需專注於具有潛在最佳解的搜尋路徑。整個演算法可以設定為找到第一個全域最佳解即刻停止，或是持續運行直到蒐集完所有符合條件的最佳解為止。

對於 B&B 演算法而言，找出所有最佳解所需的 CPU 運算時間，幾乎與搜尋樹內的節點總數呈現線性正相關。樹狀結構越龐大，需要的硬體資源與運算時間就越驚人。因此，如何透過調整變數的排序、開發新的分支策略，或是轉換數學模型來縮小搜尋樹的規模，一直是演算法研究的核心挑戰。過去的研究甚至證明，在特定的 50 變數背包問題中，運用特定數學轉換法可以將搜尋樹縮減至少 1,000 萬倍。

導入 LP 鬆弛對稱群與同構修剪機制

在許多複雜的 ILP 問題中，變數之間往往存在高度的「對稱性」。所謂的對稱群（Symmetry group），是指一組能將任何可行解映射到另一個可行解，且不改變目標函數結果的變數排列組合。當 ILP 問題具有龐大的對稱群時，傳統的 B&B 演算法會重複評估大量具有相同可行性與目標值的節點，導致極為嚴重的運算浪費。

為了解決這種冗餘計算，Margot 在 2007 年開發了帶有「同構修剪」機制的 B&B 演算法。該技術利用 ILP 對稱群中的一個特定子群進行強化修剪，藉此縮小搜尋樹的規模。在這個框架下，若兩個解能透過對稱群互相轉換，就會被認定為同構解。演算法在過濾這些同構解時，只會保留字典序最小（Lexicographically minimum）的代表解，避免在完全等價的分支上虛耗 CPU 資源。採用越大的子群進行修剪，能刪除的冗餘節點就越多。

目前在實際應用中，能夠透過已知方法有效取得的最大對稱子群，稱為 LP 鬆弛對稱群（$G^{LP}$）。Geyer 等學者設計了一套實用演算法，能透過解析特定圖論結構的自同構群來找出 $G^{LP}$。只要將這個對稱群與同構修剪演算法結合，系統就能自動篩選出所有非同構的最佳解集合，這也是本篇研究用來分類正交陣列的核心數學工具。

正交陣列頻率向量與 ILP 稀疏矩陣建構

本研究的應用標的為正交陣列（Orthogonal array，一種具備高度統計均衡特性的矩陣結構），具體標記為 OA(N,k,s,t)。這代表一個具有 N 列、k 行，由 s 種不同符號組成，且強度為 t 的特殊矩陣。根據定義，在該矩陣任意挑選的 t 行中，所有可能的符號組合都必須剛好出現等比例的次數。正交陣列在實驗設計、軟體測試與編碼理論中具有極高的實用價值。

為了解析正交陣列，研究者會為每個陣列定義一個頻率向量，用來記錄每種特定符號組合在陣列列中出現的次數。過去的學者已證明，尋找特定正交陣列的問題，可以完全等價地轉換為解開一個特殊的 ILP 矩陣方程式。由於目標函數會將所有變數的總和固定為 N，這意味著該方程式的所有可行解本身就是最佳解。為了加快 B&B 演算法的處理速度，研究團隊更運用高斯消去法提取出方程式的列空間基底，將原本的矩陣轉化為更為稀疏的等價系統以加速運算。

此外，針對陣列符號或行列進行互換的操作，被定義為 OD 等價（OD-equivalent，透過符號與行列置換達成的等效陣列）。研究指出，在強度 t 為偶數且 s=2 的情況下，$G^{LP}$ 至少會包含所有的 OD 等價操作群，這為後續的同構修剪提供了極佳的發揮空間與基礎。

演算法三階段平行化與遞移作用切割任務

為了讓同構修剪 B&B 演算法能夠應付極端龐大的計算量，本研究開發了一套由三個方法（Method 1 到 3）組成的平行化架構。Method 1 主要負責尋找合適的「瓶頸子問題」。它會在 B&B 搜尋樹中實施廣度優先搜尋（BFS，一層一層橫向展開節點的演算法），直到抵達預先設定的第 m 層為止。這樣的展開方式能夠確保問題被均勻地切割為多個獨立區塊。

取得切割好的子問題後，系統會交由 Method 2 進行接手。Method 2 的核心工作，是針對這些子問題同時執行帶有同構修剪的平行運算。而 Method 3 則是兩者的集大成者，它規範了整套演算法必須先透過廣度優先搜尋抵達第 m 層，隨後再對剩餘未修剪的葉節點執行深度優先搜尋（DFS，沿著單一分支深入探索到底的演算法）。透過數學證明，系統即使在切割後的子樹上獨立套用對稱群進行修剪，也不會遺漏任何合法且字典序最小的最佳解。

這個平行化策略之所以能夠成功，關鍵在於對稱群 $G^{LP}$ 對 ILP 變數具備遞移作用（Transitive action）。這表示對於方程式中的任意兩個變數，對稱群必定存在某個轉換操作，能夠將其中一個變數映射為另一個。基於這個遞移特性，研究團隊可以大膽將第一個變數強制固定為不同的最大可能值，不僅排除了許多無效的搜尋空間，還能將一個超大問題完美切割為運算時間與記憶體消耗幾乎相同的平行任務。

首次突破 OA(192) 分類與程式開發實作

在實際投入硬體運算時，這套平行化架構展現了卓越的計算效率。在針對具有特定條件的 OA(N,9,2,4) 陣列進行測試時，系統能將極端複雜的分類任務等分為數個負載均衡的運算區塊。在驗證階段，該方法在分類所有非 OD 等價的 OA(128,9,2,4) 與 OA(144,9,2,4) 時，皆達成了理想的線性加速表現，證明了演算法的擴展潛力。

最受矚目的成果，在於研究團隊成功突破了過去被視為計算盲區的 OA(192,9,2,4)，這是目前規模最小但尚未被完整分類的案例。透過設定分支變數上限並結合 Method 3 的自動任務切割機制，多執行緒系統成功完成了這個維度的運算。在取得 k=9 的全集基礎後，團隊更進一步運用陣列拓展技術，在數學史上首次完成了 k=10 與 k=11 的完整非同構分類。

這項純數與演算法結合的重大專案，不僅仰賴嚴謹的群論推導，也導入了現代化的開發工具。作者特別註明，整個平臺的初步切割與平行化管理腳本均是以 Perl 語言編寫，而在編寫這些複雜程式碼的過程中，更大量運用了 Google 的 Gemini AI 作為輔助工具。經過嚴格的人工除錯與理論驗證，AI 輔助開發不僅加快了實作進度，更證明了現代化工具在協助頂尖演算法研究上的實質價值。

同構修剪與平行運算的結合，大幅縮小線性規劃搜尋空間，推動高階正交陣列突破分類極限。