为什么 Cplex 提供了一个松弛约束的解决方案？
Why does Cplex provide a solution with slack on constraints?
我在 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 提供了一个在给定问题约束的情况下可行的解决方案。但是，当分支并求解分支中的单纯形以创建可行解时，为什么该单纯形的计算会导致这两个非绑定约束？我该怎么做才能确保 Cplex 始终至少提供一个解决方案，其中这两个约束之一具有约束力？
- 我试图包括没有松弛的解决方案，以测试预期的解决方案是否被 Cplex 识别为可行的解决方案（即，为了测试用 C++ 编程的数学模型是否没有错误）；
- 我试图增加 Cplex 的公差 (IloCplex::Param::MIP::Tolerances::MIPGap);
- 我尝试关闭 Cplex 的动态搜索 (IloCplex::Param::MIP::Strategy::Search)。
None 次尝试解决了问题。
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 提供的所有可行解决方案中，对于所有约束对，至少其中一个是绑定的（没有松弛）。
我想我知道答案了。
Cplex 的启发式算法有时会找到 LP 非最优的整数解。这是此行为的 example。这确实会产生不连贯的解决方案。许多 MIP 建模构造（绝对值、min/max 公式等）假设所有整数解都是 LP 最优解。最好，Cplex 会清理这些解决方案。
我使用的解决方法如下。在 Cplex 使用 MIP 解决方案停止后，总是 修复所有离散变量并解析为 LP。这将清除 LP 非最优的整数解决方案。一个可能的例外：如果问题被证明是全局最优的，那么这可能就不需要了（我对此有点偏执，所以我总是添加最终的 LP）。我还没有在其他求解器中看到这种行为。
我假设 CPLEX 因达到您的时间限制而中止，因此该解决方案未被证明是最佳解决方案。这是正确的吗？
这不是错误。 CPLEX 不会为终止的用户做出此类保证 运行。当找到满足用户 requests/settings 的解决方案时，CPLEX 会尽快停止。
要获得您正在寻找的行为，那么在 C API 中您可以使用 :
解决固定问题。由于生成的问题是纯 LP，您现在可以调用：
- 解决这个固定 LP
的 CPXlpopt()
- 从 LP 求解中查询对偶等。
并且如 link 中所述，您可以将 solveFixed() 用于更高级别的 API。
丹尼尔也在这里回答了你的交叉post :
如有不明之处请在IBM开发者论坛回复，谢谢。
我在 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 提供了一个在给定问题约束的情况下可行的解决方案。但是，当分支并求解分支中的单纯形以创建可行解时，为什么该单纯形的计算会导致这两个非绑定约束？我该怎么做才能确保 Cplex 始终至少提供一个解决方案，其中这两个约束之一具有约束力？
- 我试图包括没有松弛的解决方案，以测试预期的解决方案是否被 Cplex 识别为可行的解决方案（即，为了测试用 C++ 编程的数学模型是否没有错误）；
- 我试图增加 Cplex 的公差 (IloCplex::Param::MIP::Tolerances::MIPGap);
- 我尝试关闭 Cplex 的动态搜索 (IloCplex::Param::MIP::Strategy::Search)。
None 次尝试解决了问题。
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 提供的所有可行解决方案中，对于所有约束对，至少其中一个是绑定的（没有松弛）。
我想我知道答案了。
Cplex 的启发式算法有时会找到 LP 非最优的整数解。这是此行为的 example。这确实会产生不连贯的解决方案。许多 MIP 建模构造（绝对值、min/max 公式等）假设所有整数解都是 LP 最优解。最好，Cplex 会清理这些解决方案。
我使用的解决方法如下。在 Cplex 使用 MIP 解决方案停止后，总是 修复所有离散变量并解析为 LP。这将清除 LP 非最优的整数解决方案。一个可能的例外：如果问题被证明是全局最优的，那么这可能就不需要了（我对此有点偏执，所以我总是添加最终的 LP）。我还没有在其他求解器中看到这种行为。
我假设 CPLEX 因达到您的时间限制而中止，因此该解决方案未被证明是最佳解决方案。这是正确的吗？
这不是错误。 CPLEX 不会为终止的用户做出此类保证 运行。当找到满足用户 requests/settings 的解决方案时，CPLEX 会尽快停止。
要获得您正在寻找的行为，那么在 C API 中您可以使用 :
解决固定问题。由于生成的问题是纯 LP，您现在可以调用：
- 解决这个固定 LP 的 CPXlpopt()
- 从 LP 求解中查询对偶等。
并且如 link 中所述，您可以将 solveFixed() 用于更高级别的 API。
丹尼尔也在这里回答了你的交叉post :
如有不明之处请在IBM开发者论坛回复，谢谢。