Skip to content
所有標籤

#linear-programming

5 篇文章

Classical and Motion Planning,從 robot-cook PDDL 到 RRT* 再到 LP 圖解|CMU 07-380 作業 2

07-380 HW2 分三塊:程式作業先寫煎餅機器人的 PDDL,交給 unified-planning+Fast Downward 求最優計畫,再在 rrt.py 實作 RRT 與 RRT*(Q2–Q7);書面作業考 GraphPlan、一題 LP 建模與兩題 LP 圖解;另有只限校內的 Gradescope 線上題。本文只講題目結構、需要的概念與本機 autograder 怎麼跑,不附解答。

Optimization,自己寫 LP 求解器和 branch and bound,書面串起 PCA 與 MAP|CMU 07-380 作業 3

HW3 分三塊:程式作業要你用頂點枚舉寫出 LP 求解器,再在上面疊 branch and bound 解整數規劃,外加三題文字建模;書面四題分別是整數規劃手算、Amazon 送貨路線的倫理、PCA 的 SVD 計算,以及證明 Laplace 先驗等價 L1。截止日是 10/1,本文只講結構和需要的概念,不給解答。

Linear Programming,為什麼最優解落在可行域的頂點|CMU 07-380 第 5 堂

07-380 Lec5 用 Diet Problem 把一段文字題寫成 min cᵀx s.t. Ax ⪯ b,再畫成圖:每條限制是一個半平面,cost 是一個方向,等成本線垂直於 c。沿著 −c 推到最後一刻碰到可行域的地方,一定包含某個頂點,所以演算法只要看限制邊界的交點:頂點枚舉全部檢查,simplex 從一個頂點貪心走到鄰居。

Integer Programming,先鬆弛成 LP 再用 branch and bound 分支|CMU 07-380 第 6 堂

07-380 Lec6 在 LP 上多加一條 x ∈ ℤᴺ,頂點解就可能不是整數,而且在 LP 解附近找整數點也不保證對。解法是先把整數限制拿掉(relaxation),用 LP 算出下界,再對某個非整數座標分成 xᵢ ≤ floor 與 xᵢ ≥ ceil 兩支,全部丟進依 LP 目標值排序的 priority queue;第一個被取出的整數解就是最優解。

從演算法工具箱走向 LP、編碼與 ML|Stanford CS161 第 18 堂

期末課以 slides 回顧 CS161 工具箱,再用 LP duality、Reed–Solomon 與 ML-assisted algorithms 指向後續方向;官方沒有提供 notes。