加载中…Cplex学习总结2：Cplex求解MIP之Branch&Cut
(2009-12-11 16:04:51)
标签：
cplexoptimizationsoftwareacademic杂谈 |
分类： 建模优化 |
问题一: Cplex使用的Branch&Cut的原理是什么（Principle）？
（1）首先，Cplex会对进行preprocessing，主要是删除一些冗余的行（约束）和列（变量），是模型变得容易求解。
（2）解RP问题并检查Cuts： 对于一个节点，Cplex首先松弛掉Integrality Constraints求解其Relaxation Problem(RP)。如果RP问题不可行，删除掉此节点，并去寻找另外的没有搜索过的节点(Active Node); 如果RP问题可行，先逐个检查cuts是否被违背，如果有一个cut被违背，则将其加入模型RP，重新求解(resolve)，如此进行，直到所有的cuts都满足，如果在Adding cuts后，一旦出现Resolve不可行（说明这个节点也不可行），则也将此节点删除，并去寻找另外的Active Nodes。总之，这一步结束后，要么因为不可行此节点被删掉并转入其它active nodes，要么RP问题可行且所有的Cuts都满足。
（3）检查Integrality Feasibility: 如果第（2）步中节点RP问题可行且所有的Cuts都满足，则进一步检查整数可行性。如果整数可行，分两种情况：目标函数好于或等于current Incumbent，则将当前节点置为Incumbent，并选择新的Active node继续搜索; 目标函数坏于current Incumbent，则删除此节点，并选择新的Active node继续搜索。如果整数不可行，则根据某个非整数变量Branching，生成子结点并置当前节点为disactived（可以删去）。
问题二：如何利用Cplex求解MIP（How）？
（1） 将模型转化为MIP形式，将user-Cuts作为普通约束加入，并生成模型IloModel；
（2） 利用IloCplex的Solve函数求解。
（3） 调整性能步骤一：参数调整
常常调的参数有： IloCplex::RootAlg，IloCplex::NodeAlg，IloCplex::MIPEmphasis，IloCplex::EpOpt。具体
使用见 Cplex User guide.
（4） 调整性能步骤二：User-cuts, user-Branching, user-Node selecting，user-heuristic
User-cuts 常常在求解之前就作为普通的约束加进去了，所以这里不需要考虑；利用Goals实现user-Branching，见ilogoalex1.cpp；利用Nodeuator和Goals实现user-Node
selecting；利用SolutionGoal实现User-heuristic（慎用，因为生成的可行解可能违背大量的Cuts，而是效率下降）。
问题三：添加User-Cuts的最佳时机在什么时候？
在优化之前，将其直接作为普通约束加入。
（1）首先，Cplex会对进行preprocessing，主要是删除一些冗余的行（约束）和列（变量），是模型变得容易求解。
（2）解RP问题并检查Cuts： 对于一个节点，Cplex首先松弛掉Integrality Constraints求解其Relaxation Problem(RP)。如果RP问题不可行，删除掉此节点，并去寻找另外的没有搜索过的节点(Active Node); 如果RP问题可行，先逐个检查cuts是否被违背，如果有一个cut被违背，则将其加入模型RP，重新求解(resolve)，如此进行，直到所有的cuts都满足，如果在Adding cuts后，一旦出现Resolve不可行（说明这个节点也不可行），则也将此节点删除，并去寻找另外的Active Nodes。总之，这一步结束后，要么因为不可行此节点被删掉并转入其它active nodes，要么RP问题可行且所有的Cuts都满足。
（3）检查Integrality Feasibility: 如果第（2）步中节点RP问题可行且所有的Cuts都满足，则进一步检查整数可行性。如果整数可行，分两种情况：目标函数好于或等于current Incumbent，则将当前节点置为Incumbent，并选择新的Active node继续搜索; 目标函数坏于current Incumbent，则删除此节点，并选择新的Active node继续搜索。如果整数不可行，则根据某个非整数变量Branching，生成子结点并置当前节点为disactived（可以删去）。
问题二：如何利用Cplex求解MIP（How）？
（1） 将模型转化为MIP形式，将user-Cuts作为普通约束加入，并生成模型IloModel；
（2） 利用IloCplex的Solve函数求解。
（3） 调整性能步骤一：参数调整
（4） 调整性能步骤二：User-cuts, user-Branching, user-Node selecting，user-heuristic
问题三：添加User-Cuts的最佳时机在什么时候？
喜欢
0
赠金笔