最近在做network flow方面的优化问题，归纳起来是求解线性规划问题，于是尝试了几种优化工具，下面把自己的使用心得写下来，因为自己在搜集资料的时候发现网上这方面的好资源不是非常多，比如对优化工具的探讨大多在一个比较浅的层次上，我就深刻感觉到在使用中遇到问题往往除了官方资料很难找到答案，但官方资料太过庞杂，初学者不可能完全掌握，所以到现在对于有些工具我还有一些疑问，写出来希望有精通这方面的人可以给我解答补充。
首先当然是Matlab自带的linprog,下面通过一个Max Flow的例子来简单说明一下，请看下图：
这是一个很经典的问题，所有讲到网络流问题一般都会用到这个例子，下面解释一下它的求解过程，这也基本是用linprog求解lp问题的代码格式，这里有五个变量（e1,e2,e3,e4,e5），求解每条边上的流数，f是目标函数，最大流其实就是从S点出去的流，是e1+e2边流的和，由于linprog中第一个变量默认求得是最小值，所以目标函数要取反；
下面就是约束条件了，A <= b是不等式约束，Aeq = beq是等式约束，具体到网络问题中，每条边的流量不能超过它的capacity constraint,对于每个结点，进入的流量应当等于流出的流量（流量守恒），这两类约束根据图看代码一目了然，最后的lb是变量的下界约束，这里当然是零，还可以有一个ub，表示变量的上界约束，最后输入到linprog中的变量一般有7个，分别就是前面分析得目标函数：f；不等式约束：A <= b；等式约束：Aeq = beq，变量上下界约束：lb,ub.
这个例子当然很简单，但是将其扩展到复杂的网络拓扑时写代码其实非常不方便；不过让我放弃linprog最主要的原因还是跟后来的两个工具（lpsolve,gurobi）相比，同样的问题它解出的值总是不一样，比如网络流问题，lpsolve与gurobi可以解出整数值，但用linprog则一般解出的都是小数值，这对我的问题不是一个合适的解。再尝试其它的一些LP问题（非网络流），lpslove与gurobi的求解结果基本相似，但linprog求解结果和这两者有极大的差异，这种情况让我不大敢放心使用这种工具了。当然出现这种情况也有可能是我某个调用参数设置得不对，但我找过很多资料均不能回答我的问题，所以暂且搁置。
lpsolve,yalmip的安装及使用说明可以参考这一篇博客的内容, lpsolve如果直接在它的IDE环境中使用是非常方便的，基本上LP表达式怎样写就可以怎样运行，举一个例子说明，例子来源~cheung/Courses/323/Syllabus/NetFlow/,顺便说一下，这个网站上NetFlow的
课件生动易懂，个人认为非常适合初学者。如下的一个图求解最大流问题（这幅图已经标注出求解结果了）：
lpsolve IDE环境中只需输入如下的文本，是不是非常简单直观：
然后按一个运行按钮（红框标注），出现以下的求解结果，红框标注的是结果，蓝框标注的是求解信息，包括耗费时间等等：
关于lpsolve IDE环境的详细使用说明可以参考其使用手册（lpsolve下载主页上可自由下载），看到这里也许有人会问，上面的例子很简单，如果对于复杂的网络拓扑，自己手动输入这些表达式显然是不现实的， 那该怎么办，好在lpsolve可以集成在别的开发环境中，它提供了一整套API，可供调用，具体也请参考使用手册，上面提到的博客里对于matlab调用lpsolve有简单的说明，这里补充说一下，mxlpsolve(‘write_lp’,lp,’a.lp’)这个语句可以生成IDE环境里可直接执行的脚本文件（C，JAVA等接口也有类似语句），这样复杂的问题可以用高级编程语言建模，然后生成LP脚本文件单独在IDE中运行，是不是很方便。
以上这个Max Flow的例子直接用matlab自带的linprog工具箱求解，写出代码是：
f = [ -1 -1 -1 0 0 0 0 0 0 0 0 0 ];A = [];b = [];Aeq = [1 0 0 -1 -1 0 0 0 0 0 0 00 1 0 0 0 -1 -1 -1 0 0 0 00 0 1 0 0 0 0 0 -1 0 0 00 0 0 1 0 1 0 0 0 -1 0 00 0 0 0 1 0 1 0 1 0 -1 00 0 0 0 0 0 0 1 0 0 0 -1 ];beq = zeros(6,1);lb = zeros(12,1);ub = [3;2;2;5;1;1;3;1;1;4;2;4];x = linprog(f,A,b,Aeq,beq,lb,ub);求解结果如下，可以看到虽然最大流的值是正确的，但其它边上的流却与lpsolve求解结果有很大差别：
接触了yalmip后，可以用yalmip方便的建模，基本LP表达式怎么写，yalmip语句就怎么写，用yalmip为LP问题建模是一个非常方便的过程，至此我认为我的问题用MATLAB + Yalmip + lpsolve就解决了，直到我发现了以下两个问题，让我不得不放弃这一套工具。
为了学习用Yalmip建模，再调用一种合适的solver求解，我找到了湖北工程学院学报上一篇论文《基于Yalmip工具箱的整数规划模型求解方法》，主要看中它贴出了源代码，而且实例又非常简单，作为入门yalmip的材料个人认为很合适，我把它的代码中的solver换成了lpsolve，但没想到求解了一个下午都没有求出来，这个问题只有84个变量，按照lpsolve宣称的性能本不应如此，难道是代码的效率不高？但这是个很简单的程序，按理说不存在代码优化问题。然后我按照源代码的求解器换成了gurobi，结果如论文所述，1s不到就解好了，关于gurobi的安装，使用包括入门学习后文会详述。
勇气执着的背负起那厚重的行囊，奔向远方。
