運籌學教授葉蔭宇：作為 AI 基石，優化演算法如何在實際中應用？

本文於2017-06-27 刊載於雷鋒網。

作者：王金許

日前，雷鋒網報道了鈦媒體和杉數科技主辦的 2017 AI 大師論壇。其中，杉數科技首席科學顧問葉蔭宇出席了活動並發表了學術演講。作為在運籌學領域的頂尖學者，葉蔭宇以《優化演算法的思想及應用》為題，主要在運籌學應用的物流選址及路徑優化、庫存管理、投資組合優化三個方面詳細闡述了他的看法。

從古至今，「優化」一直是生產生活中重要的部分。而運籌學作為優化演算法的重要根基，在第二次世界大戰期間首先在英美兩國發展起來，學者把運籌學描述為就組織系統進行各種經營所作出決策的科學手段。二戰結束後，人們將運籌學應用到了企業和政府之中，為經濟發展加速，運籌學廣泛的引用在生產、服務、金融行業之中。在大數據時代，運籌學進一步蓬勃發展，而如何將大數據轉化為最優決策成為了運籌學重點課題。

葉蔭宇簡介：葉蔭宇是斯坦福大學李國鼎工程講座教授（K. T. Li Chair Professor），也是優化領域基石演算法之一——內點演算法的奠基人之一。因貢獻突出，他曾獲得美國運籌與管理學會馮·諾依曼理論獎，也是迄今為止唯一獲得此獎的華人學者。在業界，葉蔭宇擔任了優化軟體公司 MOSEK 科技顧問委員會主席、杉數科技的首席科學顧問。

以下為葉蔭宇演講內容，雷鋒網(公眾號：雷鋒網)進行了不改變原意的編輯 ：

1982 年剛到美國讀書的時候 AI 非常熱，但那時候年輕人不知道我差點就去搞 AI 了。那時候要搞所謂的專家系統 AI 空間，學的語言是學 Lisp，沒有很多的數據，人家有些就總結不出來，AI 就慢慢的冷下去了。我比較喜歡數學，就從事了運籌學。

什麼是運籌學？它是一種研究優化的學問，就是怎麼能夠在實際生活中，把事情做到極值，不僅僅是找一個可行的方案，而是一定要找到最優的方案。

Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear. 這是大數學家歐拉的話。這種理論也是基於自然形成，也是所謂的一個平衡，也是能量函數，到了極值。

說到運籌學，數學怎麼能接地氣，怎麼落到實地，怎麼真正對人們生活產生一些影響？數學家們就開始尋求這樣的方案。在二次大戰的時候，如何研究盟軍配置，還包括一些博弈問題，以前看過一個電影叫《A Beautiful Mind》，研究這個東西研究到博弈空間。

標誌性的結果就是 1947 年 George Dantzig 提出線性優化，為優化中最經典的演算法， 這就是里程碑的意義。之後到經濟發展中，運籌學得到很快的發展，特別是計算機的高速發展。以前是結構問題，可能是要 1 小時，現在可能不到 1 秒就可以解出來，所以這個硬體的控制，也有演算法的提高。

運籌學比 AI 要老，但是 AI 和機器學習又提供了一種機會，很多頂層的東西都是要靠優化，不管是學習還是剛才講到的要用決策問題。

整個來說，所謂優化在滿足我們時有很多要決策的，而且也都是需要比較量化的。滿足一定的約束條件下，使某一個函數最大，這就是優化問題，怎麼把一個問題變成這個東西，就需要建模。所以我們一般是從建模到求解，然後再到決策，然後我們就需要一套演算法來求解。

在這個裡面，把實際問題變成數學問題，再變成優化問題，然後來求解。什麼叫大數據，有很多不同的這個解釋，數據大到一定程度以後，就可以量化了。量化以後，我們可以用數學的方程、公式來描述它，然後來決策，變成一個量化的決策問題。

1982 年我去美國中間經歷了 AI，當時是最紅，現在又紅起來。但是有些點我覺得沒變的，優化好像始終是不動點一樣，不管是你在各行各業都需要它，因為在這點上也可以說起來像統計、數學還是一些機理。

這裡面有很多演算法的問題，學習有很多深度學習、MDP、機器學習等等。

我個人怎麼理解 AI？特別是大數據時代的商務決策，各自所採取的作用，我們要用到很多計算機、信息學，包括機器學習、數據搜集，然後我們要通過很多機器學習做一些規律性分析，然後建模做出決策。

從中醫的角度來說，有點像拉脈一樣，拉了脈以後老中醫有一個決策，中醫來說就是開處方葯。而在這個過程中如何判斷準確，開什麼處方，有些東西要用三錢，有些東西要四錢，但是有些中醫搞的不好就是比較模糊，「當歸少許」這個就不清楚。

所以這裡面是需要有一些量化、需求管理和規律性分析。我覺得機器學習確實做的好，但怎麼決策裡面都有一些很傳統的優化模型和運籌學模型。

我給大家舉幾個簡單的例子，為什麼有些決策模型並不需要深刻的理解就可以得出來？

一、物流選址及路徑優化

比如說這個選址問題，尋求一個區域內最優的倉庫選擇，成本最少。我要建一二三四五個庫建在什麼地方，那麼這裡面就要權衡很多，一次建設費多少，建設費之後我服務區域有多大，區域大了以後人家從很遠的地方跑過來運輸成本就高了，那麼你可以寫成一個像這樣的數學規劃方法。

那麼這樣的問題怎麼選才好，以前的演算法，我就把它寫成一個整數規劃。現在不行，好像有些演算法，像幾個月都算不出解來。現在很多東西，要隨時的，有些東西看成是網路，就要把這個點放在上面，進行隨時的調配、重新選址。這個時候我的演算法就非常快，然後就會有很多近似演算法，這裡面我們也做過一些工作，就是比較確定性的這個問題，這裡面的演算法，選址的問題。

那麼有一個問題就稍微更複雜一點，不是選址，那麼選一個倉庫提供一個區域服務，但是這個是叫 HUB 的選址，有些不是從倉庫發到某一個顧客上，某一個是要經過中轉站，再到顧客。

比如說航班的調運問題，那麼這個中轉站怎麼選才好，有一部分有問題，這裡面就會有一些選擇。通常我們把選址的問題，叫作戰略性的決策，一旦選了以後幾年都不會變。決策又分為戰略決策、戰術決策、operation 決策，而這裡面是 operation 決策。

我現在要送貨，送到這麼多的點上，如何都送出去然後回到出發的地點使整個距離最小，這是旅行商問題，這也是很經典、很確定性的。

在整個地方因為又叫車輛調度問題，當然實際問題比這更複雜，一輛車不能跑，可能幾千上萬輛車誰跑哪些地點、哪些區域、又怎麼選址，這裡面就非常非常複雜了，而且需要取貨，同時送貨，你取貨的話必須要保證在某一個時間點上，或者時間窗口。這個就是運籌學比較擅長的問題，要非常實時的做這些問題。

這是一個簡單的解決方案，分而治之，我現在有 5 輛車要服務這個區域，首先就建立一個服務區的概念，怎麼把這個大的區域分成 50 分，每一個區域選擇一個分點，這個我們叫區域選擇，非常的大。

選了以後，我知道我在分這個區域的時候，每個區域的這個工作量都是什麼，盡量的均勻的，要不然我一個區域很大，跑兩天跑不完，一個區域半天就跑完了。

這應用在實際問題中。大家看到了沒有，這裡面有 50 輛車，現在這個圖在做什麼，找路徑。這是一個實際問題，原來是一個大的地理數據圖，那麼這個問題是每一個街道都要跑的，我再劃分這個區域的時候每個區域里街道的總長度是基本上相似的。但是哪怕街道一樣，我要拿每一個顏色的這個就有這個扯進去跑，我在跑這個區域的時候，怎麼跑到最大，把所有的街道都跑一趟，這個時候就有路徑問題。

這個問題從優化、運籌學說是研究很老的問題。要把每個街道都走一道，然後這各區域就完成了，這個主要是為了地圖公司。

美國有一個很有名的地圖公司，後來諾基亞買了。我相信大家肯定用過 GPS，是兩個核心技術，一個核心技術也就是衛星定位，經度緯度定位以後，所以的地理信息位置，都是搜集過來的，那麼街道的地理數據，城市在不斷的變，所以每次都要派一輛車或者用圖像的信息把街道信息改變都要重新搜集進來，要派一輛車把每個街道跑一道。上面就一個攝像頭，非常高效，然後全部搜起來，去做這個事情。

這個時候每一個城市都要把這個街道跑一道的話，不可能跑一輛車，可能是 50 輛車，我們怎麼劃分這個車輛的區域，以前是用郵政編碼來分，由於城市的改變有些郵政編碼，有的會大好幾倍。這樣分就不合理，我們要根據這個瞬時情況進行分析。如何判斷有效，原來要用 75 輛車現在 60 輛就夠了，原來用兩天時間，現在一天半，我們確實講，效率提高了25% 到 30%，這個技術諾基亞還在用，全世界 26 個國家在使用。

我不知道大家剛才看到我在排序的過程中，在這個路徑過程當中大家也都沒有遇到，我原來認為我排出來最後的總路程最短，後來給我們提一個要求這裡面有多少是左轉多少是右轉，你能不能排路徑的時候，盡量向右轉。因為考慮的是要完成的時間，左轉所要花的時間，要比向右轉高 5 到 10 倍。因為有紅綠燈，所以我們用運籌學的辦法把這個解決掉。

再舉一個路徑優化的問題，大家都在搞所謂的無人倉。有一些小車搬運載有貨物的托盤到空閑工作台，然後小車搬運到托盤從工作台回到倉庫空儲位，我們叫回庫。然後小車搬運空托盤從工作台到托盤迴收處，我們叫回收。這裡面都是一些貨櫃，怎麼拖起來怎麼用，又要路徑又要協調。

我覺得在我們國內研究機器人，研究的比較多的是提高機器人自身的能力，我覺得做的非常好。個人能力都非常好，但是我們國家在很多問題上，缺少通盤調配和安排。機器人那麼強，在一個團隊工作的時候是不是就很強了，我們就比較缺乏統籌的軟體決策系統。就像我們中國足球到個人，也許有些能力很強，但是在一起就不行。我們很注重個人能力的提高，人都不要輸在起跑線上，但是我覺得我們國家，長期缺乏一種集體的、統籌的，這樣決策的開發，或者能力的提高。每個機器人都在瞎跑的話肯定不行，包括無人車。

很多公司都在考慮無人車的技術多強，但是其實最主要的問題是什麼，反而是無人車之間的協調、調配和統一指揮。

比如說這裡面是工作台，某一個區域的貨來了以後，我們來分擔，然後這是一個動圖，整個的這個貨品的分擔，這裡面有很多問題。我們在研究過程中，比如說這裡面的路徑，怎麼找路徑，從設計上來說，你是設計成單行線還是雙程線，這裡面有學問的，如果設置單行線跑的距離要長，碰撞的可能性就少一些，這裡面都可以通過優化來進行解決。

比如，我們跟合作的電商進行物流倉統籌調配，其中的演算法也都是算出來的。這裡面是三配，機器人怎麼配到貨櫃，怎麼收檢這個站，這個方法目前是用機器人去托盤，拖這個貨櫃，把整個的貨櫃用到旁邊的這個台上，然後又把這個拿下來，再把托盤送回去。

我們中國人就很喜歡把國外的東西搬過來，首先是機器人，把整個的貨櫃拖起來，可能那個貨櫃員就檢一個東西下來。那麼為什麼說貨櫃不動，而且貨源坐在機器人身上然後去檢貨呢，可能人需要多一點，但是貨櫃可以裝的更高了，空間利用率更高了。

我覺得我們大家可以想到一些更好的，但是這套技術可以用，而且人坐在機器上，不僅前後移動還可以升降貨櫃，可以放更高，運行過程中形成三位的倉庫而不是平面的倉庫，這樣我們就可以計算出來，包括貨的這個密度，增加多少，倉庫的利用率可以增加多少。那麼對於像我們國家，人力相對比較便宜，房非常貴，是不是就更好一點，但整個也是靠產品運輸來優化問題進行求解。

從優化的模型下，各種各樣的這個決策，還有演算法，我在國內跟工業界接觸也有一段時間，工業界總是覺得我們需要深度學習，需要機器學習，需要把預測的精度再提高 1%，提高 1%。我覺得有時候忽略了一點，有個測不準的這個定理到一定時候不可能提高的，有一個不確定的這個規律存在。

股票市場存在一兩百年，也沒有人能 100% 預測股票市場，所以在測不準的情況下，在決策上是不是可以做點工作，在知道測不準，可能有不同的這個狀況出現的情況下，我的決策是不是可以調整一下，從數據到決策我們是不是也可以做一些工作。比如說我可以保證我在期望值省時一些，但是我保證永遠不會破產，防備那些惡性大事件發生，所以這些模型在 OR 應用到很多的。

比如說路徑優化，搞了一個 PonyPlus，我給這個送貨員把一個任務今天要派 10 個單，給到這個送貨員，就搞一個輔助工具怎麼去路徑最好，排了一個，這裡面都有這樣一些工具。

二、庫存管理

這裡面最典型的是庫存問題，就是典型的知道你測不準，我怎麼能夠把局測做到最好，把庫存做到最好。以前早的時候還沒有深度學習，比如你是小零售商，你進貨進多少，進一個星期的貨，但是不知道這個星期有多少，多的有多的損失，少的有少的損失。所以這個時候運籌學就有一套方法來處理這個問題。

最近大家是否聽說過美聯航上面有一個人，因為機票賣多了，上了飛機被人拖下去，後來是賠了幾個億，為什麼說這是典型問題，是不確定環境下的決策？

飛機上座位是固定的 300 個，你事先只賣 300 張票，不會賣多，來的人都可以登記，問題是總有 5% 到 10% 的人，因為各種各樣的原因是不會來的。那麼你賣 300 張票，5% 到 10% 是不會來，那麼那部分就會損失，所以航空公司一般都會多賣一點。這個道理是一樣的它也要權衡，它知道有些人不來，我怎麼多賣幾張，最好的是有些人不來，不來的人數正好是我多賣的人數。但是永遠是測不準的，也就出現美聯航的這個問題。

一般我們決策是什麼，業內通過拍賣的形式，你願意乘坐下一次航班，給你多少錢，美聯航說到 600 塊錢就不向上提，所以我們要找一個權衡，多賣幾張最好。

這點我們做過很多實際案例特別是在我們國內比較大的電商里，幫他安排，通常周轉率在 29 天的，那麼現在降 16.5%，庫存的金額大家也都知道零售商最怕的就是庫存周轉率太低，買了人家的東西自己又賣不出去，庫存金額降 19.2%，現貨率提升了，GMV 上升 1.9%，而周轉天數下降到 16.5%。就是說我們主要是降低了這部分人力，在不損失這兩個標準的情況下。

還有一個辦法根據某一個電商的特點，叫閃購，出一份貨賣一個星期就不賣了，那麼這個時候他們通常這個電商把那個星期的預測，需要備多少貨就決定下來，我們採取兩階段的策略，首先我有一個總的估量，但是我發貨的時候是發三天的貨，通過第一天的銷量我再決定追不追貨，不知道大家聽懂了沒有，本來一周的需求量是 100，我實際送到前沿倉庫送 60 件，頭一天的這個銷量是夠，我是否需要把這 40 件補上去就看第一天的銷量，第一天的銷量對後續的這個預測度就更高。

王曦也是我們斯坦福的學生，現在是杉數的產品經理。設計了一個叫 Stockgo，根據我們跟電商還有其他接觸的這個規律，我們覺得應該給每一個中小電商，至少提供一個可能的工具，觀察庫存的周轉來確定，幫助他決策。

這裡面有很多的功能，比如說對目前庫存狀態的量化評估，對高精度的銷量預測，高精度的補貨策略，供應鏈管理的智能化轉型，包括很多的機器學習工具還有深度學習工具，對你的庫存狀態進行評估，精確到每一個 SKU，還有補貨策略，以及個性化的全雲端解決方案，也可以直接把數據傳送到杉數，然後幫你進行診脈。

總的目的是，把這些 OR 的東西對經濟起大作用，這是已經在跟很多 ERP 的公司發給他們使用，通常周轉率會提高到 50%，資金及人力成本降低，電商自動化庫存能力也都是在提高，這是一個小工具，到時候這些能夠為廣大的小電商服務。你也可以自己調整，但是至少給了你一個可能性。

三、投資組合優化

最後我就講一講最近還研究一些投資組合優化，也就是防範風險。

這裡面很多情況有一個叫 Markowitz，叫現代投資前沿理論。Markowitz 也是在我們斯坦福工作過一段時間，把投資組合的問題寫成一個二次規劃，它的目標函數不是線性函數，是二次函數，所有的約束也都是線性。

如何解這個問題解的最快，這個時候我們就有很多的問題，因為出現了二次函數呢，大家知道在統計中，二次的 X 的平方通常描述變化量，我們需要波動不太大，這就是簡單的這個二次函數，實際上要解的也就是二次規劃，常見的軟體 Barra、Axioma、ITG、Mosek 等。

那麼在交易過程當中，你的演算法你的求解器比人家快一些，我個人認為高頻交易的競賽也就是演算法速度的這個競賽。我知道國內就用到過這樣的模型，自己解需要解 10 秒鐘的時間。從 10 秒到 0.04 秒，這裡面有演算法的模型。

FICO 也是二次規劃的問題，很多大數據公司，越來越重視優化，我個人認為美國最早的大數據公司就是產生 FICO 的一家公司，國內是叫徵信打分，就是最早的一個公司把個人所有的信息收集起來給這個人的信譽打分。我 1982 年去美國要租房子到銀行開款，人家就必要 FICO，我說我是中國來的沒有，到美國租房要擔保首先就是看這個 FICO，打這個分。

這個公司後來做的很好，大家都用他的 FICO，也就提供這個服務，包括在網上查一查這個徵信也都要交錢，這是美國很早的大數據公司，收集很多公司對每個人也都有打分。就是我說的英國優化公司，就被這個 FICO 公司買下來，在大數據處理中需要優化，能力需要加強。

這裡面剛才我提到，我個人呢，包括杉數里我們很多人也跟美國運通公司做了很多，它是一個純信用卡公司，不是一個單元，實際上是一個擔保公司。信用卡消費什麼東西，你如果消費了什麼東西，把前期的這個還上，你沒什麼，要還不上就加利息，我總跟人家講運通公司是合法的高利貸公司，國內有些高利貸公司可能就是比較野蠻。但是他是比較合法的，利率確實比較高。

那麼它的資源是什麼，它的核心技術是什麼？就是防範風險，希望你消費但又希望你不要還錢而且希望你還錢不要還得太快，但是又不希望你永遠不還。當時在運通公司我們工作的時候，有一個專門的團隊就搞這個，是一個大數據公司，特別是個人的一些數據在那個時候沒有英特網，有比信用卡交易紀錄的更多數據，也都是這個數據來進行識別。具體項目我不清楚了。

有一個就是我們幫他搞了一個怎麼追債，運通公司信用卡如果三個月連續不還錢，人家不還錢不能雇殺手卸個脖子什麼的，所以必須要通過合理的方法博弈，心理學很複雜的過程。所以有一些和追債公司聯合起來一起搞。

很多是基於演算法的，國內公司搞的這個 AI 非常熱，趨勢跟隨很緊，在有些問題上結合中國特色進行研究和開發。我個人在 AI 革命過程中，看到了中國體制的這個優點。

為什麼呢？也就是說文化的優點，你過 AI 這個問題，說句實話，深度學習這一塊還是有很多理論依據，深度學習本身目前這個階段，理論還在發展，做事情這個過程有點像我們中醫，有什麼問題它很有效，但是真正說出一個道道來還說不出來，有的時候也不是 100% 的準確，但是準確起來非常好，一個癌症病人吃了幾副葯好了，怎麼解釋，解釋不了，所以我覺得特別適合中國的這個文化，不問緣由只看效果，西方在這塊反而比較保守的。

所以我就說中國相對來說數據還比較公開自由，壁壘意識沒那麼強，像美國大公司數據絕對不會給你的，所以我覺得為 AI 開闢了很多前途。

但是中國發展過程中忽略了演算法的力量，他們通常是以問題為根本，找了一些參考資料在開源軟體中找一個演算法進行試一試，這是要花非常大的這個功夫，確實是要耐得住寂寞，但是要用人家的開源軟體，不給的話永遠會被牽著鼻子走。我知道其實他們很需要線性規劃或者說其他的運營規劃。但是你要買人家，出於安全考慮也不行。

比如說 CPLEX，Mosek，現在有些大學、包括財經大學、杉數科技，不光是做實際應用，也培養自己的演算法開發，這樣的話就比較有核心技術了，真正的成為技術公司而不是諮詢公司。

所以大家投資要是很有錢的話，要耐得住寂寞，要有核心的技術等等這樣的一些東西。

未來的話，我覺得真是 AI、深度學習和機器學習提供了很多的支撐，模型規模也飛速增長，因為需要超大規模的優化演算法，以前我認為我就要搞出個萬能的演算法，解所有的線性規劃都要解得快，但是我後來反觀看AI是非常定製的，我可以對某一類方法用的好就用那個方法，不是追求某一個統一的演算法，或者類別法。反而是比較定製化的，用中國話來講比較實用主義一些。

不一定追求理論上的完美，有一個統一的演算法，所以這點上，我覺得反過來，AI 對我們的這個東西有很大的促進，什麼問題需要什麼樣的演算法，本身需要學習的過程。

還有一個問題，我們以前比較重視凸規劃，大量的問題是凸規劃。現在需要考慮如何集群化、軟硬體結合，如何利用 GPU 實現並行運算，包括應用在智慧供應鏈、智能金融、健康管理等領域，我對我們國家的挂號系統，有很多的問題能不能採取更好的方法，這樣的話對大家都有好處，這個東西，我們在 OR 叫排序。

總的來說我是搞運籌，因為也是搞優化的，1982 年到現在也大半輩子看到學術研究的起伏變化，我原來比較重視理論，很多問題都是寫文章，證明一些東西，也小有成就，但是人到年紀大的時候維護自己工作利益所在。我覺得最大的利益還是對一般人生活產生一些影響，因為誰也不知道很多理論證明的結果有什麼東西。

我仔細想，那些用 PonyPlus 的人，你證明不證明，我可能還是用這個方法。這就是到一定年齡的時候，就追求鼓勵這些年輕人，不光是有一定的學術造詣，把自己的學術成果轉化成技術，對人的基本生活產生影響，這才是 OR 的本質，OR 是一個接地氣的科學，是一個落地的科學，怎麼落地不能雲里霧裡說嚇死人，經過我們的試驗,還有杉數這些年輕人都是從斯坦福回來的學生，像運籌學，深度學習、機器學習確實對電商這些也都產生了一些影響。

所以我就希望大家多支持我們，使得中國的企業，從一個比較粗狂的形式進一步拓展為依賴於大數據、國際技術來進行決策的環境裡面。

原文鏈接：運籌學教授葉蔭宇：作為 AI 基石，優化演算法如何在實際中應用？