前言：这是我3月22日写的关于线性求解器gecode的笔记。我喜欢gecode的文档，以及它简洁明了的C++源代码。计划跟不上快速的变化。当时激动万分，真没想到3月22日是五个月以来最后一次写出如此工整的笔记；在那之后，我陷入了一场巨大的拉锯战——我没有时间再写笔记了。我打开了这篇笔记（我什至忘记了，这几天整理资料才想起来），但拉锯战最终收效甚微；当时我什至没有想到。既然提到“线性优化”这个话题，我的第一反应就是拒绝。我非常喜欢这张纸条。略读之后，我能回忆起当时总结的所有重点。这几个月的教训是：不要以为什么都能学，什么都能涉猎，赶紧定下一个细分方向，埋头苦干。以后很长一段时间，我可能没有时间更新这篇笔记。我当时的期望“gecode是一个优秀的线性求解器，但是中文网上几乎没有系统的教材，学一个学期就写一套。”在不久的将来实现它是不可能的。共勉。我会回来看你的，老头儿。Gecode基础知识Gecode基础知识[1]SendMoreMoney[3]必须注意的点[4]rel-关系约束[5]distinct-pairwisedifferentconstraints[6]branch-定义分支规则[7]关于打印[8]以SendMoreMoney为例[2]搜索引擎的使用[9]异常处理[10]Gist-可视化解决过程[11]设置目标值[12]注意地址[13]以SendMoreMoney为例SendMoreMoney我们赋值给这八个字母赋值（分配一个数字）：SENDMORY使等式成立：SEND+MORE=MONEY，其中每个字母都是不同的数字。还是不明白？为了告诉您答案，我们最终将SEND+MORE=MONEY替换为9567+1085=10652。这说明解法成功，其中S为9，E为5...必须注意的点码有：https://gitee.com/piperliu/math_codes_economics_management/tree/master/gecode_MPG_notes/codes/03sendmoremoney/sendmoremoney.cpp[14]//使用整数变量和整数约束//我们需要includegecode/int.hh头文件#include//使用搜索引擎（求解逻辑），我们需要gecode/search。hh头文件#include//所有的gecode函数都在gecode这个命名空间里//所以，为了避免Gecode::IntVarArray的麻烦//我们使用namespaceGecode;usingnamespaceGecode简化代码;//所有模型必须继承Gecode::SpaceclassSendMoreMoney:publicSpace{protected://这里声明了一个整型变量数组lIntVarArrayl;public://在构造函数中声明模型//l(*this,8,0,9)意思是：//-变量数组l是这个模型的(this)//-变量数组l包含8个变量//-这些变量的取值范围是[0,9]SendMoreMoney(void):l(*this,8,0,9){//我们声明了一些变量IntVars(l[0]),e(l[1]),n(l[2]),d(l[3]),m(l[4]),o(l[5]),r(l[6]),y(l[7]);//下面是一些约束的实现，暂时先不管具体含义//noleadingzerosrel(*this,s,IRT_NQ,0);rel(*this,m,IRT_NQ,0);//alllettersdistinctdistinct(*this,l);//线性方程//这里有一些Args变量//我把Var理解为决策变量，或者说是自变量//而Args是根据Var变化的，中间变量//本身不主动变化，受影响通过VarsIntArgsc(4+4+5);IntVarArgsx(4+4+5);c[0]=1000;c[1]=100;c[2]=10;c[3]=1;x[0]=s;x[1]=e;x[2]=n;x[3]=d;c[4]=1000;c[5]=100;c[6]=10;c[7]=1;x[4]=m;x[5]=o;x[6]=r;x[7]=e;c[8]=-10000;c[9]=-1000;c[10]=-100;c[11]=-10;c[12]=-1;x[8]=m;x[9]=o;x[10]=n;x[11]=e;x[12]=y;线性(*this,c,x,IRT_EQ,0);//定义分支和定界规则//postbranchingbranch(*this,l,INT_VAR_SIZE_MIN(),INT_VAL_MIN());}//必须声明一个copyconstructor//必须有变量更新//searchsupportSendMoreMoney(SendMoreMoney&s):Space(s){l.update(*this,s.l);}//声明复制方法（用于搜索）virtualSpace*copy(void){returnnewSendMoreMoney(*this);}//printsolutionvoidprint(void)const{std::cout<e(m);deletem;//searchandprintallsolutionswhile(SendMoreMoney*s=e.next()){s->print();deletes;}return0;}如上，我们实现了一个问题，我在中文注释里做了说明值得注意的是：所有的gecode函数都在命名空间Gecode中，所有模型都必须继承Gecode::Space，除了基本的构造函数，必须声明一个拷贝构造函数，并且必须在拷贝构造函数updates中声明一个拷贝方法（用于搜索）决策变量（如l.update(*this,s.l);），这一点尤为重要，否则程序不会报错，求解过程出错。原因是我们的求解器在求解过程中会不断分配空间实例。如果在复制构造函数中没有更新决策变量，则无法执行回溯和保存等操作。我把Var理解为决策变量或者自变量；而args是根据Var变化的中介变量，本身并不主动变化，而是受Var变化的影响。注意无论是变量还是约束，在声明的时候，第一个参数都是*this。你可以这样理解：孩子这样一个变量，孩子一出生，就必须清楚ta的监护人是谁，否则，孩子不依赖就活不下去了。在这里，我们的变量和约束取决于存在问题的SendMoreMoney类。rel-关系约束rel(*this,s,IRT_NQ,0);上面的语句表示：变量s不等于0，其中：IRT_NQ表示不等于，后面会看到所有逻辑符号表示rel表示关系distinct-Pairwisedifferentconstraintsdistinct(*this,l);这里不细说distinct的用法，只说明它的作用：l数组中的变量必须成对不同。其他的约束就不详细描述了，后面会提到。branch-定义分支规则。在求解过程中，不同的搜索方法对求解结果有不同的影响。因此，定义合适的分支规则就显得尤为重要。branch(*this,l,INT_VAR_SIZE_MIN(),INT_VAL_MIN());这里，对于变量数组l中的变量，我们先选择搜索范围最小的变量（INT_VAR_SIZE_MIN()），如果是变量，则将已有的最小值赋给它（INT_VAL_MIN()）。分支的其他规则和用法稍后讨论。关于print解决后gecode会自动调用print进行输出。我们可以自由发挥，重载打印函数，让解变成我想要的形式。//printsolutionvoidprint(void)const{std::cout<print();m->status();//第二个print()std::cout<<"2"<print();DFSe(m);//第三个print()std::cout<<"3"<print();deletem;//searchandprintallsolutionswhile(SendMoreMoney*s=e.next()){//第四个print()std::cout<<"4"<print();deletes;}return0;}你可以看到我在上面放了4个打印，让我们看看我们有的范围搜索到目前为止。输入如下。1{[1..9],[0..9],[0..9],[0..9],[1..9],[0..9],[0..9],[0..9]}2{9,[4..7],[5..8],[2..8],1,0,[2..8],[2..8]}3{9,[4..7],[5..8],[2..8],1,0,[2..8],[2..8]}4{9,5,6,7,1,0,8,2}当我们声明这个问题（初始化模型）的时候，我们的模型根据约束做了一些基本的操作，体现在这里：S的范围应该是[1,9]M的范围应该是[1,9]，这个很好理解，因为我们有约束rel(*this,s,IRT_NQ,0);,rel(*this,m,IRT_NQ,0);.约束传播只有在我们调用status()之后才会起作用。status函数的原始注释是QueryspacestatusPropagatesthespaceuntilfixpointorfailure；更新统计信息stat；并且：如果空间失败，则返回SpaceStatus::SS_FAILED。如果空间没有失败但空间没有分支，则返回SpaceStatus::SS_SOLVED。否则，返回SpaceStatus::SS_BRANCH。我的理解是对现有的解空间做一个基础的探索，直到分支需要做决定或者探索失败。值得注意的是，如果我们取消上面的m->status();句，那么3对应的print()还是{9,[4..7],[5..8],[2..8],1,0,[2..8],[2..8]}。这意味着在为我们的模型声明搜索引擎时调用status()一次。如下所示，在while中我们要返回每次探索的解决方案。值得注意的是，一个解决方案也是一个模型（问题实例）。while(SendMoreMoney*s=e.next()){//第四个print()std::cout<<"4"<print();deletes;}这里e是基于DFS深度优先搜索的搜索引擎，e.next()是基于DFS规则对下一个探索方向的探索结果。如果探索到最后，那么e.next()就会返回NULL，此时while停止跳出循环。异常处理实际上，为了捕获Gecode异常，使用try{}catch(){}是一个不错的选择。intmain(intargc,char*argv[]){try{//main}catch(Exceptione){std::cerr<<"Gecodeexception:"<usingnamespaceGecode;...intmain(intargc,char*argv[]){SendMoreMoney*m=newSendMoreMoney;Gist::dfs(m);deletem;return0;}我们引入gist.hh头文件来相对简单地可视化main中的dfs过程。gist的功能可以用鼠标探索，还有其他的调用方式。gist功能比较强大，这里不再赘述。另外，也可以使用手动增加实解的功能。代码见https://gitee.com/piperliu/math_codes_economics_management/tree/master/gecode_MPG_notes/codes/03sendmoremoney/sendmoremoneyGist_2.cpp[16]添加了inspectsettingtargetvalue设置对于targetvalue，我们需要声明代价函数，并用变量来表示搜索过程中变量的传递（用于目标函数的计算）。这里不详细讨论。这并不复杂，我们将在以后的笔记中讨论。
