Mixed-Integer Programming

又稱: MIP, MILP, MIQP, MICP
類別: Planning & manipulation › Trajectory optimisation
標籤: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems

一種最佳化，其中部分變數必須取整數值（通常為 0 或 1），讓單一問題能結合離散的選擇與連續的量。

定義

混合整數規劃（Mixed-integer programming，MIP）是在連續變數與限定為整數之變數混合的情況下進行的最佳化，其中整數變數最常見的是取值為 0 或 1 的二元變數。二元變數編碼離散的決策：路徑經過哪個區域、下一步由哪隻腳著地、某個接觸是否作用、哪台機器人負責哪項任務。連續變數則承載其餘的量，例如位置、速度與力。常見的類別依剩餘問題的形式命名：混合整數線性規劃（MILP）、混合整數二次規劃（MIQP），以及更一般的混合整數凸規劃（MICP）。

這類問題一般而言是 NP 困難的，但現代求解器能妥善處理許多實際的實例。它們使用分支定界：去掉整數要求後求解連續鬆弛問題，挑出一個結果為分數的變數，拆成兩個分別迫使它往下或往上取整的子問題，並剪除任何鬆弛解已經比目前找到的最佳整數解還差的分支。割平面會在過程中收緊鬆弛。Gurobi 與 CPLEX 等商用求解器，以及 SCIP、HiGHS 與 CBC 等開源求解器，都實作了這些方法。

問題的寫法與使用哪個求解器同樣重要。邏輯條件常以大 M 約束（big-M constraints）編碼，它藉由一個二元變數與一個很大的常數來開啟或關閉某個約束；常數太大會削弱鬆弛，並造成數值問題。鬆弛緊的表述求解起來快得多，這也是凸集合圖等結構化方法被設計成讓其鬆弛接近真實問題的原因之一。

為何重要

許多機器人規劃問題有一部分是離散的：從障礙物左邊或右邊繞過、選擇接觸序列、分派任務。混合整數規劃在單次最佳化中精確處理這些選擇，並常給出答案離最佳有多遠的界限，而不是仰賴手工設計的啟發式規則或取樣。

主要應用

腿足機器人的落腳點與接觸序列規劃
無人機與機器手臂穿越凸區域的軌跡規劃
機器人機隊的任務分派與排程
具離散模式的混合模型預測控制
具離散動作選擇的任務與運動規劃

實際應用

一個為人形機器人規劃踏石落腳點的團隊，把每塊石頭可行走的表面表示為一個凸多邊形。對接下來的每一步，他們加入選擇腳落在哪個多邊形上的二元變數，以及只對所選多邊形作用的約束，再加上代表腳部位置的連續變數，以及步長與轉向的限制。代價函數獎勵朝目標的進展，並懲罰彆扭的步伐。混合整數求解器回傳一個步伐序列，通常在為重新規劃設定的時間限制內完成，同時給出找到的最佳解與最佳界限之間的間隙。如果求解時間太長，團隊會減少一次規劃的步數、收緊大 M 值，或以前一次的計畫做暖啟動。

常見誤解

混合整數規劃對機器人來說一定太慢 — 規模小、表述良好的問題可以快到足以進行線上重新規劃
把連續鬆弛取整就能得到最佳整數解 — 除非鬆弛是緊的，否則取整結果可能不可行，或遠離最佳
在大 M 約束中，任何大的 M 值都可以 — 過大的值會削弱鬆弛並造成數值困難
因時間限制而停止的求解器就是失敗了 — 它通常會回傳目前為止的最佳解，以及一個說明該解有多好的最佳性間隙

誰需要了解

運動規劃與落腳點規劃工程師
機隊排程與任務分派開發者
以最佳化為基礎之控制的研究人員
研讀最佳化的機器人學學生

影片

Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com

維基百科

整数规划

Open Source Robotics