c++ - 为什么 Cplex 提供了一个松弛约束的解决方案？

Question

我在 Visual Studio (C++) 中开发了一个线性数学规划模型，并使用 Cplex (12.7.1) 解决了这个问题。但是我注意到 Cplex 有一些奇怪的行为。对于某些问题实例，Cplex 提供了一个可行的(非最佳解决方案)，可以通过消除对某些约束的松懈来轻松改进。数学模型的简化示例如下:

最小化A

受制于

cX – dY <= A

dY – cX <= A

X,Y二进制,A连续,c,d参数

给定所提供的可行(非最佳)解决方案中的 X 和 Y 值，两个约束都有松弛。给定决策变量 X 和 Y 的值，可以很容易地减少连续 A 变量(即，通过消除至少两个约束中的一个的松弛)。我知道 Cplex 提供了一个在给定问题约束的情况下可行的解决方案。但是，当分支并求解分支中的单纯形以创建可行解时，为什么该单纯形的计算会导致这两个非绑定(bind)约束？我该怎么做才能确保 Cplex 始终至少提供一个解决方案，其中这两个约束之一具有约束力？

• 我尝试在没有松弛的情况下包含解决方案，以测试预期的解决方案是否被 Cplex 识别为可行的解决方案(即，为了测试用 C++ 编程的数学模型是否没有错误)；
• 我尝试增加 Cplex 的公差 (IloCplex::Param::MIP::Tolerances::MIPGap)；
• 我尝试关闭 Cplex 的动态搜索 (IloCplex::Param::MIP::Strategy::Search)。

这些尝试都没有解决问题。

int nozones = 2;
int notrucks = 100;
int notimeslots = 24;
IloEnv env; 
IloModel model(env);
IloExpr objective(env);
IloExpr constraint(env);

NumVar3Matrix X(env, notimeslots);
for (i = 0; i < notimeslots; i++)
{
    X[i] = NumVarMatrix(env, notrucks);
    for (l = 0; l < notrucks; l++)
    {
        X[i][l] = IloNumVarArray(env, nozones);
        for (k = 0; k < nozones; k++)
        {
            X[i][l][k] = IloNumVar(env, 0, 1, ILOINT);
        }
    }
}

NumVar3Matrix A(env, nozones);
for (k = 0; k < nozones; k++)
{
    A[k] = NumVarMatrix(env, notimeslots);
    for (int i0 = 0; i0 < notimeslots; i0++)
    {
        A[k][i0] = IloNumVarArray(env, notimeslots);
        for (int i1 = 0; i1 < notimeslots; i1++)
        {
            A[k][i0][i1] = IloNumVar(env, 0, 9999, ILOFLOAT); 
        }
    }
}

//objective function
for (int k0 = 0; k0 < nozones; k0++)
{
    for (int i0 = 0; i0 < notimeslots; i0++)
    {
        for (int i1 = 0; i1 < notimeslots; i1++)
        {
            if (i0 > i1)
            {
                double denominator = (PP.mean[k0] * (double)(notimeslots*notimeslots)); //parameter
                objective += A[k0][i0][i1] / denominator;
            }
        }
    }
}

model.add(IloMinimize(env, objective)); 

//Constraints
for (int k0 = 0; k0 < nozones; k0++)
{
    for (int i0 = 0; i0 < notimeslots; i0++)
    {
        for (int i1 = 0; i1 < notimeslots; i1++)
        {
            if (i0 > i1)
            {
                for (int l0 = 0; l0 < notrucks; l0++)
                {
                    constraint += c[k0][l0] * X[i0][l0][k0];
                    constraint -= d[k0][l0] * X[i1][l0][k0];    
                }

                constraint -= A[k0][i0][i1];
                model.add(constraint <= 0);
                constraint.clear();

                for (int l0 = 0; l0 < notrucks; l0++)
                {
                    constraint -= c[k0][l0] * X[i0][l0][k0];
                    constraint += d[k0][l0] * X[i1][l0][k0];                
                }
                constraint -= A[k0][i0][i1];
                model.add(constraint <= 0);
                constraint.clear();
            }
        }
    }
}

请在下面找到日志:

CPXPARAM_TimeLimit                               10
CPXPARAM_Threads                                 3
CPXPARAM_MIP_Tolerances_MIPGap                   9.9999999999999995e-08
CPXPARAM_MIP_Strategy_CallbackReducedLP          0
Tried aggregator 2 times.
MIP Presolve eliminated 412 rows and 384 columns.
MIP Presolve modified 537 coefficients.
Aggregator did 21 substitutions.
Reduced MIP has 595 rows, 475 columns, and 10901 nonzeros.
Reduced MIP has 203 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.09 sec. (8.97 ticks)
Found incumbent of value 1254245.248934 after 0.11 sec. (10.55 ticks)
Probing time = 0.00 sec. (0.39 ticks)
Tried aggregator 1 time.
Reduced MIP has 595 rows, 475 columns, and 10901 nonzeros.
Reduced MIP has 203 binaries, 272 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (4.47 ticks)
Probing time = 0.00 sec. (0.55 ticks)
Clique table members: 51.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 3 threads.
Root relaxation solution time = 0.05 sec. (15.41 ticks)

    Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                      1254245.2489    13879.8564            98.89%
*     0+    0                      1225612.3997    13879.8564            98.87%
*     0+    0                      1217588.5782    13879.8564            98.86%
*     0+    0                      1209564.7566    13879.8564            98.85%
*     0+    0                      1201540.9350    13879.8564            98.84%
*     0+    0                      1193517.1135    13879.8564            98.84%
*     0+    0                      1185493.2919    13879.8564            98.83%
*     0+    0                      1177589.9029    13879.8564            98.82%
      0     0   334862.8273   139  1177589.9029   334862.8273      387   71.56%
*     0+    0                       920044.8009   334862.8273            63.60%
      0     0   335605.5047   162   920044.8009     Cuts: 248      516   63.52%
*     0+    0                       732802.2256   335605.5047            54.20%
*     0+    0                       669710.6005   335605.5047            49.89%
      0     0   336504.5144   153   669710.6005     Cuts: 248      617   49.75%
      0     0   338357.1160   172   669710.6005     Cuts: 248      705   49.48%
      0     0   338950.0580   178   669710.6005     Cuts: 248      796   49.39%
      0     0   339315.6848   189   669710.6005     Cuts: 248      900   49.33%
      0     0   339447.9616   193   669710.6005     Cuts: 248      977   49.31%
      0     0   339663.6342   203   669710.6005     Cuts: 228     1091   49.28%
      0     0   339870.9021   205   669710.6005     Cuts: 210     1154   49.25%
*     0+    0                       531348.6042   339870.9021            36.04%
      0     0   340009.1008   207   531348.6042     Cuts: 241     1225   35.87%
      0     0   340855.1873   202   531348.6042     Cuts: 231     1318   35.85%
      0     0   341229.8328   202   531348.6042     Cuts: 248     1424   35.78%
      0     0   341409.5769   200   531348.6042     Cuts: 248     1502   35.75%
      0     0   341615.2848   286   531348.6042     Cuts: 248     1568   35.71%
      0     0   341704.8400   300   531348.6042     Cuts: 225     1626   35.69%
      0     0   341805.5681   222   531348.6042     Cuts: 191     1687   35.67%
*     0+    0                       489513.3319   341805.5681            30.17%
      0     0   341834.6048   218   489513.3319     Cuts: 169     1739   30.17%
      0     0   341900.1390   228   489513.3319     Cuts: 205     1788   30.16%
      0     0   341945.8278   211   489513.3319     Cuts: 197     1855   30.15%
*     0+    0                       489468.1697   341945.8278            30.14%
      0     2   341945.8278   202   489468.1697   341945.8278     1855   30.14%
Elapsed time = 5.53 sec. (446.68 ticks, tree = 0.01 MB, solutions = 14)
*   199+  154                       484741.1904   341968.3817            29.45%
    263   222   342462.1403   198   484741.1904   341968.3817    12287   29.45%
*   550+  420                       461678.3486   341993.1725            25.92%
    555   403   411858.3790   117   461678.3486   341993.1725    21480   25.92%
*   566+  319                       439985.4277   341993.1725            22.27%
    660   321   350009.7742   289   439985.4277   341993.1725    16141   22.27%
*   670+  427                       438464.9662   342020.7550            22.00%

Flow cuts applied:  15
Mixed integer rounding cuts applied:  65
Zero-half cuts applied:  6
Gomory fractional cuts applied:  15

Root node processing (before b&c):
  Real time             =    5.53 sec. (446.21 ticks)
Parallel b&c, 3 threads:
  Real time             =    4.50 sec. (1093.39 ticks)
  Sync time (average)   =    0.59 sec.
  Wait time (average)   =    0.04 sec.
                         ------------
Total (root+branch&cut) =   10.03 sec. (1539.61 ticks)

预期的结果是，在 Cplex 提供的所有可行解决方案中，对于所有约束对，至少其中一个是绑定(bind)的(没有松弛)。

Answer 1

我假设 CPLEX 因达到您的时间限制而中止，因此该解决方案未被证明是最佳解决方案。这是正确的吗？

这不是错误。 CPLEX 不对用户终止的运行做出此类保证。当找到满足用户请求/设置的解决方案时，CPLEX 会尽快停止。

要获得您正在寻找的行为，然后在 C API 中您可以使用:

https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.9.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/mip/para/51_soln_fixed.html

解决固定问题。由于生成的问题是纯 LP，您现在可以调用:

• 解决这个固定 LP 的 CPXlpopt()
• 从 LP 求解中查询对偶等。

如链接中所述，您可以将 solveFixed() 用于更高级别的 API。

Daniel 也在这里回答了您的交叉帖子:

https://developer.ibm.com/answers/questions/499882/why-does-cplex-provide-feasible-solutions-with-con/

https://developer.ibm.com/answers/questions/499879/why-does-cplex-provide-slack-on-constraints-when-p/

如有不明之处请在IBM开发者论坛回复，谢谢。