Cplex模型：无解

Question

我的 C++ Concert Cplex 有问题。我正在尝试重新创建最短路径问题。文本文件的输出是：

Minimize
 obj: 2 x_12 + x_13 + 2 x_21 + x_24 + x_31 + 3 x_34 + x_42 + 3 x_43 + x9
Subject To
 c1: x_12 + x_13 - x_21 - x_31 + x_14 - x_41  = 1
 c2: - x_12 + x_21 + x_24 - x_42 + x_23 - x_32  = 0
 c3: - x_13 + x_31 + x_34 - x_43 - x_23 + x_32  = 0
 c4: - x_24 - x_34 + x_42 + x_43 - x_14 + x_41  = -1
Bounds
      x9 = 0
End

然后我使用下面的代码来获得解决方案：

    IloCplex spp(model);
    spp.setParam(IloCplex::RootAlg, IloCplex::AutoAlg);
    spp.solve();
    IloArray<IloNumArray> vals(env);
    env.out() << "Solution status = " << spp.getStatus() << endl;
    env.out() << "Solution value  = " << spp.getObjValue() << endl;
    env.out() << "Values x       = " << vals << endl;

但是我不断得到的输出是：

Solution status = Optimal
Solution value = 0
Values x       =  []

有人知道我的程序有什么问题吗？谢谢

编辑：

我的模型是在程序本身中构建的，这是第一部分：

    IloEnv env;
    IloModel model(env);
    IloArray<IloNumVarArray> x(env);
    IloRangeArray c(env);
    IloInt nnodes = G.size();
    IloInt i, j;
    IloEnv env = model.getEnv();

    //SHORTEST PATH PROBLEM

    for (i = 0; i < nnodes; i++){   //x decision variables
        x.add(IloNumVarArray(env, nnodes, 0, IloInfinity));
    }
    for (i = 0; i < nnodes; i++){
        for (j = 0; j < nnodes; j++){
            stringstream sts;
            sts << "x_" << i + 1 << j + 1;
            x[i][j].setName(sts.str().c_str()); //SET NAMES
        }
    }

    //set objective min sum_(all ij)[c_ij][x_ij]
    IloExpr obj(env);
    for (i = 0; i < nnodes; i++){
        for (j = 0; j < nnodes; j++){
            obj += G[i][j] * x[i][j];
        }
    }
    model.add(IloMinimize(env, obj));
    obj.end();

    //constraints sum_j[x_ij]-sum_j[x_ji] = 1 for s, -1 for t, or 0
    for (i = 0; i < nnodes; i++){
        int ss = 0;
        if (i == s) ss = 1;
        if (i == t) ss = -1;
        IloExpr sum1(env);
        IloExpr sum2(env);
        for (j = 0; j < nnodes; j++){
            sum1 += x[i][j];
            sum2 += x[j][i];
        }
        c.add(sum1 - sum2 == ss);
        sum1.end();
        sum2.end();
    }
    model.add(c);

    //solving---------------------------------------------------------
    IloCplex spp(model);

    //write to file
    spp.exportModel("model1.lp");
    spp.solve();

Answer 1

显然您没有从文件中读取模型。这是一个example。所以在你的情况下：

  #include <ilcplex/ilocplex.h>
  ILOSTLBEGIN

  int main (int argc, char **argv)
  {
     IloEnv   env;
     try {
        IloModel model(env);
        IloCplex cplex(model);

        IloObjective   obj;
        IloNumVarArray var(env);
        IloRangeArray  con(env);

        cplex.importModel(model, "tmp.lp", obj, var, con);
        cplex.extract(model);

        // Optimize the problem and obtain solution.
        if ( !cplex.solve() ) {
           env.error() << "Failed to optimize LP" << endl;
           throw(-1);
        }

        IloNumArray vals(env);
        env.out() << "Solution status = " << cplex.getStatus() << endl;
        env.out() << "Solution value  = " << cplex.getObjValue() << endl;
        cplex.getValues(vals, var);
        env.out() << "Values        = " << vals << endl;
        cplex.getSlacks(vals, con);
        env.out() << "Slacks        = " << vals << endl;
        cplex.getDuals(vals, con);
        env.out() << "Duals         = " << vals << endl;
        cplex.getReducedCosts(vals, var);
        env.out() << "Reduced Costs = " << vals << endl;
     }
     catch (IloException& e) {
        cerr << "Concert exception caught: " << e << endl;
     }
     catch (...) {
        cerr << "Unknown exception caught" << endl;
     }

     env.end();

     return 0;
  }  // END main

其中 tmp.lp 是您的 LP 模型文件。运行我有这个代码

Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 12 columns.
Aggregator did 1 substitutions.
All rows and columns eliminated.
Presolve time = 0.00 sec. (0.01 ticks)
Solution status = Optimal
Solution value  = 0
Values        = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
Slacks        = [0, 0, 0, 0]
Duals         = [1, 0, 0, 1]
Reduced Costs = [1, 0, 3, 2, 2, 4, 0, 2, 1, 0, 0, 0, 0]

Answer 2

您的代码中似乎缺少某些内容。在模型创建代码的开头，您声明了 IloNumVars x:

的二维数组

IloEnv env;
IloModel model(env);
IloArray<IloNumVarArray> x(env);
IloRangeArray c(env);

但后来你说你用来获取解决方案的代码如下所示：

IloCplex spp(model);
spp.setParam(IloCplex::RootAlg, IloCplex::AutoAlg);
spp.solve();
IloArray<IloNumArray> vals(env);
env.out() << "Solution status = " << spp.getStatus() << endl;
env.out() << "Solution value  = " << spp.getObjValue() << endl;
env.out() << "Values x       = " << vals << endl;

我看不到你在哪里做任何事情来将 vals（IloNums 的二维数组）与 x 中的值（模型中的 IloNumVars 的二维数组）相关联。我认为您应该在 IloNumVars 上调用类似 spp.getValue(...) 的方法以将值放入 IloNums 数组中。

Answer 3

首先让我在你引用的议员中说点什么。对于 cplex 为您提供的解决方案，有两种完全有效的解决方案：

x_14 = 1, all other x_ijs = 0 or  x_41 = -1 all other x_ijs = 0

导致 objective 值 0。

将 x_14 和 x_41 作为变量但与 objective 中的任何成本无关，您基本上鼓励了从源头到下沉的免费旅行。问题不在于您的模型，它工作正常。这是您构建图形的方式，但它是。

Cplex模型：无解

Cplex model: no solution

c++

shortest-path

cplex