优化多项式时出现最大深度级别错误。在下面的输出中，我注意到 LP 迭代似乎停止了。为什么 scip 会在很多变量上分支，而再也不会调用 LP 求解器？我正在使用 Ipopt 运行它。
我不能尝试增加最大深度级别，因为它 #defined 是 65535，而且我不想重建 scip。
下面是我的输入文件和输出。
$cat mytest.pip
Maximize
obj:5 x1^1*x2^1*x3^1*x7^1*x8^1*x18^1*x19^2 + 3 x1^1*x2^1*x3^1*x10^1*x13^1*x15^1*x19^2 - 6 x1^1*x4^1*x11^1*x15^1*x18^2*x19^2 + 8 x2^3*x4^1*x8^1*x11^1*x14^2 + 9 x2^1*x3^1*x9^1*x11^1*x13^1*x17^2*x18^1 - 3 x4^1*x8^1*x12^1*x14^1*x17^1*x18^2*x20^1 + 1 x5^3*x6^2*x9^1*x18^1*x20^1 - 6 x5^2*x8^1*x16^4*x17^1 + 10 x6^1*x8^1*x15^3*x16^2*x19^1 + 10 x9^1*x12^1*x14^1*x15^1*x16^2*x19^2
Bounds
1 <= x1 <= 150
1 <= x2 <= 150
1 <= x3 <= 150
1 <= x4 <= 150
1 <= x5 <= 150
1 <= x6 <= 150
1 <= x7 <= 150
1 <= x8 <= 150
1 <= x9 <= 150
1 <= x10 <= 150
1 <= x11 <= 150
1 <= x12 <= 150
1 <= x13 <= 150
1 <= x14 <= 150
1 <= x15 <= 150
1 <= x16 <= 150
1 <= x17 <= 150
1 <= x18 <= 150
1 <= x19 <= 150
1 <= x20 <= 150
Integers
x1
x2
x3
x4
x5
x6
x7
x8
x9
x10
x11
x12
x13
x14
x15
x16
x17
x18
x19
x20
End
$ ./scip -f mytest.pip
SCIP version 3.1.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 2.0.0] [GitHash: 577ee45]
Copyright (c) 2002-2014 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)
External codes:
Readline 6.3 GNU library for command line editing (gnu.org/s/readline)
SoPlex 2.0.0 Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 568f354]
cppad-20140000.1 Algorithmic Differentiation of C++ algorithms developed by B. Bell (www.coin-or.org/CppAD)
ZLIB 1.2.8 General purpose compression library by J. Gailly and M. Adler (zlib.net)
GMP 5.1.3 GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
ZIMPL 3.3.2 Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
Ipopt 3.11.9 Interior Point Optimizer developed by A. Waechter et.al. (www.coin-or.org/Ipopt)
user parameter file <scip.set> not found - using default parameters
read problem <mytest.pip>
============
original problem has 21 variables (0 bin, 20 int, 0 impl, 1 cont) and 1 constraints
solve problem
=============
feasible solution found by trivial heuristic after 0.0 seconds, objective value 1.000000e+05
presolving:
(round 1) 0 del vars, 0 del conss, 0 add conss, 1 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2) 0 del vars, 0 del conss, 0 add conss, 2 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 3) 0 del vars, 0 del conss, 55 add conss, 2 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 4) 0 del vars, 0 del conss, 55 add conss, 2 chg bounds, 0 chg sides, 0 chg coeffs, 56 upgd conss, 0 impls, 0 clqs
(round 5) 3 del vars, 3 del conss, 55 add conss, 73 chg bounds, 0 chg sides, 0 chg coeffs, 56 upgd conss, 0 impls, 0 clqs
(round 6) 3 del vars, 3 del conss, 55 add conss, 102 chg bounds, 0 chg sides, 0 chg coeffs, 57 upgd conss, 0 impls, 0 clqs
(round 7) 3 del vars, 3 del conss, 55 add conss, 107 chg bounds, 0 chg sides, 0 chg coeffs, 57 upgd conss, 0 impls, 0 clqs
presolving (8 rounds):
3 deleted vars, 3 deleted constraints, 55 added constraints, 107 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
0 implications, 0 cliques
presolved problem has 73 variables (0 bin, 20 int, 52 impl, 1 cont) and 53 constraints
12 constraints of type <abspower>
41 constraints of type <quadratic>
Presolving Time: 0.04
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
0.1s| 1 | 0 | 47 | - | 447k| 0 | 1 | 73 | 53 | 73 | 190 | 0 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.1s| 1 | 0 | 48 | - | 480k| 0 | 1 | 73 | 54 | 73 | 191 | 1 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.2s| 1 | 0 | 49 | - | 481k| 0 | 1 | 73 | 54 | 73 | 192 | 2 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.2s| 1 | 0 | 50 | - | 483k| 0 | 1 | 73 | 54 | 73 | 193 | 3 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.2s| 1 | 0 | 51 | - | 484k| 0 | 1 | 73 | 54 | 73 | 194 | 4 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.2s| 1 | 0 | 52 | - | 486k| 0 | 1 | 73 | 54 | 73 | 195 | 5 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.2s| 1 | 0 | 53 | - | 487k| 0 | 1 | 73 | 54 | 73 | 196 | 6 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.2s| 1 | 2 | 171 | - | 502k| 0 | 1 | 73 | 54 | 73 | 196 | 6 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.2s| 100 | 101 | 479 | 4.3 | 566k| 98 | 0 | 73 | 54 | 73 | 164 | 139 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.2s| 200 | 201 | 774 | 3.6 | 669k| 198 | 0 | 73 | 54 | 73 | 237 | 241 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
0.5s| 300 | 301 | 1070 | 3.4 | 831k| 271 | 0 | 73 | 54 | 73 | 86 | 410 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.6s| 400 | 402 | 1077 | 2.6 | 884k| 271 | 0 | 73 | 54 | 73 | 87 | 412 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.6s| 500 | 502 | 1077 | 2.1 | 929k| 271 | 0 | 73 | 54 | 73 | 87 | 412 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.6s| 600 | 602 | 1077 | 1.7 | 973k| 326 | 0 | 73 | 54 | 73 | 87 | 412 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
0.6s| 700 | 702 | 1077 | 1.5 |1020k| 426 | 0 | 73 | 54 | 73 | 87 | 412 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
...
9.4s| 65800 | 65802 | 1079 | 0.0 | 30M| 65k| 0 | 73 | 54 | 73 | 87 | 412 | 0 | 0 | 1.178930e+19 | 1.000000e+05 | Large
[src/scip/tree.c:777] ERROR: maximal depth level exceeded
[src/scip/tree.c:969] ERROR: Error <-16> in function call
[src/scip/tree.c:5268] ERROR: Error <-16> in function call
[src/scip/tree.c:5514] ERROR: Error <-16> in function call
[src/scip/scip.c:30672] ERROR: Error <-16> in function call
[src/scip/branch_pscost.c:610] ERROR: Error <-16> in function call
[src/scip/branch.c:1581] ERROR: Error <-16> in function call
[src/scip/branch.c:2503] ERROR: Error <-16> in function call
[src/scip/solve.c:3863] ERROR: Error <-16> in function call
[src/scip/solve.c:4312] ERROR: Error <-16> in function call
[src/scip/scip.c:13633] ERROR: Error <-16> in function call
[src/scip/scipshell.c:98] ERROR: Error <-16> in function call
[src/scip/scipshell.c:284] ERROR: Error <-16> in function call
[src/scip/scipshell.c:332] ERROR: Error <-16> in function call
SCIP Error (-16): maximal branching depth level exceeded
首先感谢您提交此问题。我们确定了两个主要问题。
-
您的模型在数值上不稳定，因为经过一些迭代后，某些变量边界被设置为逗号前 1^{13} 和逗号后面 1^{-4} 的大小。在浮点运算中，有 15-16 个有效符号。这就是为什么使用"ceil"和"floor"功能可能会产生不可预测的结果。目前我们不确定如何处理这个问题，但我们正在努力。此时，您可以尝试通过更改数字的参数来更改精度，例如，
numerics/epsilon and numerics/hugeval. -
经过一些迭代后，变量边界的大小为 1^{13}。特别是，SCIP 分支在每次迭代中对同一变量和下限正好增加 1。换句话说，SCIP 可能执行深度优先搜索，并且由于积分变量 x_{i} 的范围为 150，因此为替换多项式中的乘积而引入的变量范围增加到 11390625000000。显然，SCIP 遇到了深度限制。此外，由于上述数值问题，SCIP 在分支其中一个节点中的某些变量后无法识别边界变化。如果 SCIP 选择此节点，则不需要再次解析 LP。
如果您改进了模型，请随时再次发布或向我们发送电子邮件至 SCIP 邮件列表。
亲切问候
雅 各 布