開(kāi)源線性規(guī)劃求解器（Linear Programming solver）LP_Solve和CLP的PK
01 Introduction
前幾天老板讓測(cè)一下一些open source LP solver的穩(wěn)定性。先看看本次上場(chǎng)的主角：
lp_solve is a free (see LGPL for the GNU lesser general public license) linear (integer) programming solver based on the revised simplex method and the Branch-and-bound method for the integers. http://web.mit.edu/lpsolve/doc/ Clp (Coin-or linear programming) is an open-source linear programming solver. It is primarily meant to be used as a callable library, but a basic, stand-alone executable version is also available. It is designed to find solutions of mathematical optimization problems of the form. https://github.com/coin-or/clp CPLEX Optimizer provides flexible, high-performance mathematical programming solvers for linear programming, mixed integer programming, quadratic programming and quadratically constrained programming problems. These solvers include a distributed parallel algorithm for mixed integer programming to leverage multiple computers to solve difficult problems.
CPLEX可不是open-source的哦，這里主要是作為baseline，這樣就可以看看lp_solve和Clp跟目前state of the art commercial solver的差距了。
02 Setting
開(kāi)始之前，還是先做一些準(zhǔn)備工作。首先是測(cè)試數(shù)據(jù)集，本次測(cè)試了兩個(gè)數(shù)據(jù)集：
NETLIB (91 cases) : http://www.netlib.org/lp/data/index.html L1 (34 cases) : http://www-eio.upc.edu/~jcastro/mindist_sdc.html
數(shù)據(jù)集中的文件有些是.mps，部分solver可以直接讀取。而NETLIB中的是compressed MPS，需要用他提供的工具進(jìn)行解壓。當(dāng)然也可以從這里下載現(xiàn)成的：
https://github.com/zrjer/LP-TEST-PROBLEM-FROM-NETLIB/tree/master/netlib_mps
測(cè)試平臺(tái)是ubuntu 18.04，lp_solve和clp用的是python調(diào)用，而CPLEX還是用Java調(diào)用的（別問(wèn)，問(wèn)就是使起來(lái)順手），反正這些平臺(tái)只是起到一個(gè)調(diào)用的作用，應(yīng)該不會(huì)影響求解的時(shí)間（I think so~錯(cuò)了麻煩多多指正）。
然后講講python下怎么配置lp_solve和clp吧：
lp_solve windows平臺(tái)：直接到 https://www.lfd.uci.edu/~gohlke/pythonlibs/#lp_solve 這里下載對(duì)應(yīng)版本的輪子然后pip進(jìn)行安裝，注意版本對(duì)應(yīng)。 linux平臺(tái)：用conda安裝，參考這里 https://anaconda.org/conda-forge/lpsolve55 Clp Clp是一個(gè)solver，Coin-or團(tuán)隊(duì)又為python開(kāi)發(fā)了一個(gè)包叫CyLP（https://github.com/coin-or/CyLP） ，可以直接用來(lái)調(diào)用他們家的求解器 (CLP, CBC, and CGL)，所以下面講講怎么裝CyLP。 windows平臺(tái)：直接 pip install cylp，會(huì)自動(dòng)安裝clp等求解器。linux平臺(tái)：比較麻煩，需要用conda先安裝cbc等求解器，具體方法參照CyLP的說(shuō)明，比較麻煩。
然后把測(cè)試的code準(zhǔn)備好，再寫(xiě)個(gè)shell腳本進(jìn)行批量測(cè)試：
dir=MPS_Files
for?file?in?$dir/*;?do
????python?lpsolve_run.py?$file
done
意思是讀取中的所有文件，然后挨個(gè)傳入code里面讓他跑，當(dāng)然跑完了記得在程序中把一些結(jié)果記錄一下哦。最后把code和腳本upload到服務(wù)器上，執(zhí)行一下./run_lpsolve.sh，然后就可以安心去刷劇摸魚(yú)等結(jié)果啦。
03 Computational Results
由于lpsolve只能使用單線程模式，因此在實(shí)驗(yàn)中也限制了CPLEX也只能使用單線程。關(guān)于表格一些列的說(shuō)明：
variable: 模型中變量的個(gè)數(shù)。 constraint: 模型中約束的個(gè)數(shù)。 non_zero: 約束Ax=b中，矩陣A中非0元素的個(gè)數(shù)。 objective: 問(wèn)題的目標(biāo)值。 time: 求解所花的時(shí)間。
3.1 Netlib
一共有96個(gè)算例，其中有5個(gè)CPLEX讀取錯(cuò)誤（我也不知道為啥。。），剩下91個(gè)算例中（平均variable=2524，平均constraint=978，平均non_zero=14763）：
cplex能全部解到最優(yōu)，平均求解時(shí)間為0.48s（yyds？）。 lpsolve只求得了88個(gè)算例的最優(yōu)解，這87個(gè)的平均求解的時(shí)間為0.89s。有三個(gè)算例在長(zhǎng)時(shí)間內(nèi)（大于2000s）無(wú)法得出可行解（表中標(biāo) NA的單元格），手動(dòng)終止了（用我導(dǎo)的話說(shuō)，that's why lpsolve is free...）。clp比lpsolve更穩(wěn)定一點(diǎn)，得出的所有結(jié)果和cplex一致，時(shí)間上也低于lpsolve。 不同的地方在表格中已經(jīng)加粗了。
一些有趣的現(xiàn)象
對(duì)于E226.SIF這個(gè)case，對(duì)比了幾個(gè)solver，求解結(jié)果分別如下：
官方報(bào)告的optimal: -18.7519 cplex, gurobi, clp: -11.64 matlab: -18.7519 lpsolve: -25.86
會(huì)不會(huì)是模型解析的問(wèn)題呢？我把他們的模型打出來(lái)看過(guò)了，模型都是一樣的，只是求解的結(jié)果不一樣。
至于為什么會(huì)這樣，看到網(wǎng)上一個(gè)比較有趣的回答：
MIP solvers work with floating-point data. For problems such as yours that have wide variations in the magnitude in the data, this leads to round-off errors. Any LP solver will have to perform operations on this data that can amplify the problem. In some cases like your problem, this can make the solver conclude that the problem is infeasible when it isn't. When you fix variables, the solver does fewer floating point operations.
the commercial solvers solvers like Gurobi or cplex generally do a better job of working with numerically difficult data like yours. Gurobi has a parameter QuadPrecision that works with higher-precision floating point numbers. Most solvers have a parameter that will make the solver work better with numerically-difficult data. For example LPSolve has a parameter epsint that will make it relax what the it considers an integer. The default for the parameter is 10e-7, so 0.9999999 would be considered to be an integer, but 0.9999998 would not be. You can make this value larger, but you risk receiving unacceptable results.
You are experiencing a leaky abstrction. Your problem is technically in the scope of Mixed-Integer Programming, but MIP solvers are not designed to solve it. Mixed Integer Programming is an NP-Hard problem. It is impossible to have a solver that works quickly and reliably on all inputs. MIP solvers try to work well on problems that come from diverse areas like portfolio optimization, supply chain planning, and network flows. They aren't designed to solve cryptology problems.
出處：https://stackoverflow.com/questions/16001462/solving-an-integer-linear-program-why-are-solvers-claiming-a-solvable-instance
3.2 L1數(shù)據(jù)集
共34個(gè)cases，初步觀察有以下的結(jié)論：
lpsolve和clp差不多，cplex依然領(lǐng)先很多。 有好幾個(gè)cases，幾個(gè)solver得出的解不一樣，表中標(biāo)粗的部分。
最后經(jīng)過(guò)測(cè)試發(fā)現(xiàn)，CPLEX中的pre_solve有可能會(huì)影響到最后的結(jié)果，按理說(shuō)不應(yīng)該影響才是，摘一點(diǎn)官網(wǎng)的介紹：
Presolve consists in modifying the model to improve it so that it can be solved more efficiently.
CP Optimizer presolves the input model before search. Presolve consists in modifying the model to improve it so that it can be solved more efficiently. Presolve works by
simplifying the model by reducing linear constraints by removing redundancies and fixed expressions and
strengthening the model to achieve more domain reduction by aggregating constraints or factorizing common subexpressions.
As a consequence, the overall engine memory consumption can increase because an internal model is created to perform the improvement operations
有可能是solver的一些bug。在lpsolve中也遇到過(guò)，用pre_solve以后居然直接說(shuō)問(wèn)題infeasible了？？？interesting。
04 Conclusion
這里有份開(kāi)源的榜單，里面測(cè)了更多的solver，數(shù)據(jù)也更加權(quán)威，可以看到有很多國(guó)產(chǎn)的solver在榜單中都取得了很不錯(cuò)的成績(jī)，希望國(guó)產(chǎn)的MILP也快快提上日程。
http://plato.asu.edu/ftp/lpsimp.html
總結(jié)一下，作為開(kāi)源免費(fèi)的LP solver， clp是一個(gè)不錯(cuò)的選擇，目前cylp也還在逐漸開(kāi)發(fā)。Google的or tools沒(méi)有測(cè)因?yàn)樗麄兊膒ython接口還沒(méi)有很完善。lp_solve比較出名了，但是感覺(jué)還是不太穩(wěn)定吧，幫助文檔倒是寫(xiě)得不錯(cuò)。
推薦閱讀：
干貨 | 想學(xué)習(xí)優(yōu)化算法，不知從何學(xué)起？
干貨 | 運(yùn)籌學(xué)從何學(xué)起？如何快速入門運(yùn)籌學(xué)算法？
干貨 | 學(xué)習(xí)算法，你需要掌握這些編程基礎(chǔ)（包含JAVA和C++）
干貨 | 算法學(xué)習(xí)必備訣竅：算法可視化解密
