c ++ cplex访问当前解决方案以添加约束
c++ cplex access current solution to add constraint
我正在尝试使用 C++ 和 Concert Technology 在 CPLEX 中求解 LP 模型。
我想实现约束(subtour elimination constraints,更具体地说)需要查询当前解决方案中我的两个变量的值:
变量数组 xvar 表示边,yvar 表示节点。
我通过在修改后的图上解决 n(= 节点数)Min-Cut-Problems 来实现这些约束,该修改图是通过添加人工源和人工汇并将它们连接到原始图的每个节点来构建的.
根据我目前所读的内容,我是否需要惰性约束或回调或 none?
这是我创建模型并解决它的地方,访问解决方案中变量的值等:
// Step 2: Construct the necessary CPLEX objects and the LP model
IloCplex solver(env);
std::cout<< "Original Graph g: " <<std::endl;
std::cout<< net.g() <<std::endl;
MCFModel model(env, net);
// Step 3: Load the model into cplex and solve
solver.extract(model);
solver.solve();
// Step 4: Extract the solution from the solver
if(solver.getStatus() != IloAlgorithm::Optimal) throw "Could not solve to optimality!";
IloNumArray xsol ( env, net.g().nEdges() );
IloNumArray ysol ( env, net.g().nNodes() );
IloNumArray rsol ( env, net.g().nGroups() );
IloNumArray wisol ( env, net.g().nGroups() );
IloNum ksol;
NumMatrix wsol ( env, net.g().nGroups());
for(IloInt i = 0; i < net.g().nGroups(); i++){
wsol[i] = IloNumArray( env, net.g().nGroups() );
}
solver.getValues(xsol, model.xvar());
solver.getValues(ysol, model.yvar());
solver.getValues(rsol, model.rvar());
solver.getValues(wisol, model.wivar());
ksol=solver.getValue(model.kvar());
for (IloInt i = 0; i < net.g().nGroups(); i++){
wsol[i] = wisol;
}
// Step 5: Print the solution.
我需要变量 xvar 和 yvar 的当前值的约束是在此处创建的:
//build subset constraint y(S) -x(E(S))>= y_i
void MCFModel::buildSubsetCons(){
IloExpr lhs(m_env);
IloCplex cplex(m_env);
IloNumArray xtemp ( m_env, m_net.g().nEdges() );
IloNumArray ytemp ( m_env, m_net.g().nNodes() );
std::vector<Edge> mg_twin;
std::vector<int> mg_weights;
int mg_s;
int mg_t;
SGraph mgraph;
std::vector<int> f;
int nOrigEdges = m_net.g().nEdges();
int nOrigNodes = m_net.g().nNodes();
cplex.getValues(xtemp, m_xvar);
cplex.getValues(ytemp, m_yvar);
mgraph = m_net.g().mod_graph();
mg_s = mgraph.nNodes()-1;
mg_t = mgraph.nNodes();
std::cout<<"modified graph:"<<std::endl;
std::cout<<mgraph<<std::endl;
// fill the weight of original edges with 1/2*x_e
foreach_edge(e, m_net.g()){
mg_weights.push_back((xtemp[e->idx()])/2);
}
// fill the weight of the edges from artificial source with zero
for(int i=0; i<m_net.g().nNodes(); i++){
mg_weights.push_back(0);
}
// fill the weight of the edges to artificial sink with f(i)
// first step: calculate f(i):
//f.resize(m_net.g().nNodes());
foreach_node(i, m_net.g()){
foreach_adj_edge(e, i, m_net.g()){
f[i] = f[i] + xtemp[e->idx()];
}
f[i] = (-1)*f[i]/2;
f[i] = f[i] + ytemp[i];
}
// second step: fill the weights vector with it
for(int i=0; i<m_net.g().nNodes(); i++){
mg_weights.push_back(f[i]);
}
// calculate the big M = abs(sum_(i in N) f(i))
int M;
foreach_node(i, m_net.g()){
M = M + abs(f[i]);
}
// Build the twin vector of the not artificial edges for mgraph
mg_twin.resize(2*nOrigEdges + 2*nOrigNodes);
for(int i=0; i < nOrigEdges ; ++i){
mg_twin[i] = mgraph.edges()[nOrigEdges + i];
mg_twin[nOrigEdges + i] = mgraph.edges()[i];
}
//Start the PreflowPush for every node in the original graph
foreach_node(v, m_net.g()){
// "contract" the edge between s and v
// this equals to higher the weights of the edge (s,v) to a big value M
// weight of the edge from v to s lies in mg_weights[edges of original graph + index of node v]
mg_weights[m_net.g().nEdges() + v] = M;
//Start PreflowPush for v
PreflowPush<int> pp(mgraph, mg_twin, mg_weights, mg_s, mg_t);
std::cout << "Flowvalue modified graph: " << pp.minCut() << std::endl;
}
}
对象pp是为了解决具有人工源和汇的修改图mgraph上的最小割问题。原图在m_net.g().
当我编译并 运行 它时,出现以下错误:
terminate called after throwing an instance of 'IloCplex::Exception'
Aborted
在我看来,不可能像这样访问 xvar 和 yvar 的值?
我非常感谢任何帮助,因为我完全不知道如何做到这一点。
非常感谢!!
两件事...
我。我强烈建议您使用 try-catch 来更好地理解 CPLEX 异常。您也许可以像这样理解异常的性质。事实上,我建议您使用 try-catch-catch 设置,类似于:
try {
//... YOUR CODE ...//
}
catch(IloException& e) {
cerr << "CPLEX found the following exception: " << e << endl;
e.end();
}
catch(...) {
cerr << "The following unknown exception was found: " << endl;
}
二.在优化过程中与 CPLEX 交互的唯一方法是通过回调,并且在 Subtour Elimination Constraints (SEC) 的情况下,您需要将整数和小数 SEC 分开。
II.1 INTEGER: 第一个是最简单的,O(n)
例程将帮助您识别节点解决方案的所有连接组件,然后您可以添加后续削减以防止此特定 SEC 出现在其他节点中。您可以使用 addLocal()
函数在本地强制执行您的剪切,即仅在当前子树上执行,或者使用 add()
函数在全局执行,即在整个分支剪切树上执行。在任何情况下,始终记得添加 .end()
以终止切割容器。否则你会遇到严重的内存泄漏问题,相信我,大声笑。此回调需要通过惰性约束回调 (ILOLAZYCONSTRAINTCALLBACK
)
完成
II.2 FRACTIONAL: 第二个要复杂得多。使其工作的最简单方法是使用 Lysgaard 教授的 CVRPSEP 库。它是当今计算容量切割、Multistar、广义多星、框架容量、强化梳和 hypotour 切割的最有效方法。此外,使用任何现有代码 link 都相当容易。 linkage也需要嵌入到求解过程中,因此也需要回调。在这种情况下,它将是用户剪切回调 (ILOUSERCUTCALLBACK
)。
很高兴为您服务
Y
我正在尝试使用 C++ 和 Concert Technology 在 CPLEX 中求解 LP 模型。
我想实现约束(subtour elimination constraints,更具体地说)需要查询当前解决方案中我的两个变量的值: 变量数组 xvar 表示边,yvar 表示节点。
我通过在修改后的图上解决 n(= 节点数)Min-Cut-Problems 来实现这些约束,该修改图是通过添加人工源和人工汇并将它们连接到原始图的每个节点来构建的.
根据我目前所读的内容,我是否需要惰性约束或回调或 none?
这是我创建模型并解决它的地方,访问解决方案中变量的值等:
// Step 2: Construct the necessary CPLEX objects and the LP model
IloCplex solver(env);
std::cout<< "Original Graph g: " <<std::endl;
std::cout<< net.g() <<std::endl;
MCFModel model(env, net);
// Step 3: Load the model into cplex and solve
solver.extract(model);
solver.solve();
// Step 4: Extract the solution from the solver
if(solver.getStatus() != IloAlgorithm::Optimal) throw "Could not solve to optimality!";
IloNumArray xsol ( env, net.g().nEdges() );
IloNumArray ysol ( env, net.g().nNodes() );
IloNumArray rsol ( env, net.g().nGroups() );
IloNumArray wisol ( env, net.g().nGroups() );
IloNum ksol;
NumMatrix wsol ( env, net.g().nGroups());
for(IloInt i = 0; i < net.g().nGroups(); i++){
wsol[i] = IloNumArray( env, net.g().nGroups() );
}
solver.getValues(xsol, model.xvar());
solver.getValues(ysol, model.yvar());
solver.getValues(rsol, model.rvar());
solver.getValues(wisol, model.wivar());
ksol=solver.getValue(model.kvar());
for (IloInt i = 0; i < net.g().nGroups(); i++){
wsol[i] = wisol;
}
// Step 5: Print the solution.
我需要变量 xvar 和 yvar 的当前值的约束是在此处创建的:
//build subset constraint y(S) -x(E(S))>= y_i
void MCFModel::buildSubsetCons(){
IloExpr lhs(m_env);
IloCplex cplex(m_env);
IloNumArray xtemp ( m_env, m_net.g().nEdges() );
IloNumArray ytemp ( m_env, m_net.g().nNodes() );
std::vector<Edge> mg_twin;
std::vector<int> mg_weights;
int mg_s;
int mg_t;
SGraph mgraph;
std::vector<int> f;
int nOrigEdges = m_net.g().nEdges();
int nOrigNodes = m_net.g().nNodes();
cplex.getValues(xtemp, m_xvar);
cplex.getValues(ytemp, m_yvar);
mgraph = m_net.g().mod_graph();
mg_s = mgraph.nNodes()-1;
mg_t = mgraph.nNodes();
std::cout<<"modified graph:"<<std::endl;
std::cout<<mgraph<<std::endl;
// fill the weight of original edges with 1/2*x_e
foreach_edge(e, m_net.g()){
mg_weights.push_back((xtemp[e->idx()])/2);
}
// fill the weight of the edges from artificial source with zero
for(int i=0; i<m_net.g().nNodes(); i++){
mg_weights.push_back(0);
}
// fill the weight of the edges to artificial sink with f(i)
// first step: calculate f(i):
//f.resize(m_net.g().nNodes());
foreach_node(i, m_net.g()){
foreach_adj_edge(e, i, m_net.g()){
f[i] = f[i] + xtemp[e->idx()];
}
f[i] = (-1)*f[i]/2;
f[i] = f[i] + ytemp[i];
}
// second step: fill the weights vector with it
for(int i=0; i<m_net.g().nNodes(); i++){
mg_weights.push_back(f[i]);
}
// calculate the big M = abs(sum_(i in N) f(i))
int M;
foreach_node(i, m_net.g()){
M = M + abs(f[i]);
}
// Build the twin vector of the not artificial edges for mgraph
mg_twin.resize(2*nOrigEdges + 2*nOrigNodes);
for(int i=0; i < nOrigEdges ; ++i){
mg_twin[i] = mgraph.edges()[nOrigEdges + i];
mg_twin[nOrigEdges + i] = mgraph.edges()[i];
}
//Start the PreflowPush for every node in the original graph
foreach_node(v, m_net.g()){
// "contract" the edge between s and v
// this equals to higher the weights of the edge (s,v) to a big value M
// weight of the edge from v to s lies in mg_weights[edges of original graph + index of node v]
mg_weights[m_net.g().nEdges() + v] = M;
//Start PreflowPush for v
PreflowPush<int> pp(mgraph, mg_twin, mg_weights, mg_s, mg_t);
std::cout << "Flowvalue modified graph: " << pp.minCut() << std::endl;
}
}
对象pp是为了解决具有人工源和汇的修改图mgraph上的最小割问题。原图在m_net.g().
当我编译并 运行 它时,出现以下错误:
terminate called after throwing an instance of 'IloCplex::Exception'
Aborted
在我看来,不可能像这样访问 xvar 和 yvar 的值? 我非常感谢任何帮助,因为我完全不知道如何做到这一点。 非常感谢!!
两件事...
我。我强烈建议您使用 try-catch 来更好地理解 CPLEX 异常。您也许可以像这样理解异常的性质。事实上,我建议您使用 try-catch-catch 设置,类似于:
try {
//... YOUR CODE ...//
}
catch(IloException& e) {
cerr << "CPLEX found the following exception: " << e << endl;
e.end();
}
catch(...) {
cerr << "The following unknown exception was found: " << endl;
}
二.在优化过程中与 CPLEX 交互的唯一方法是通过回调,并且在 Subtour Elimination Constraints (SEC) 的情况下,您需要将整数和小数 SEC 分开。
II.1 INTEGER: 第一个是最简单的,O(n)
例程将帮助您识别节点解决方案的所有连接组件,然后您可以添加后续削减以防止此特定 SEC 出现在其他节点中。您可以使用 addLocal()
函数在本地强制执行您的剪切,即仅在当前子树上执行,或者使用 add()
函数在全局执行,即在整个分支剪切树上执行。在任何情况下,始终记得添加 .end()
以终止切割容器。否则你会遇到严重的内存泄漏问题,相信我,大声笑。此回调需要通过惰性约束回调 (ILOLAZYCONSTRAINTCALLBACK
)
II.2 FRACTIONAL: 第二个要复杂得多。使其工作的最简单方法是使用 Lysgaard 教授的 CVRPSEP 库。它是当今计算容量切割、Multistar、广义多星、框架容量、强化梳和 hypotour 切割的最有效方法。此外,使用任何现有代码 link 都相当容易。 linkage也需要嵌入到求解过程中,因此也需要回调。在这种情况下,它将是用户剪切回调 (ILOUSERCUTCALLBACK
)。
很高兴为您服务 Y