2

优化多项式时出现最大深度级别错误。在下面的输出中，我注意到 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
4

1 回答 1

1

首先感谢提交这个问题。我们发现了两个主要问题。

  1. 您的模型接缝在数值上不稳定，因为在一些迭代之后，一些变量界限被设置为在逗号之前的大小为 1^{13} 和逗号后面的大小为 1^{-4} 的东西。在浮点运算中，有 15-16 个有效符号。这就是为什么使用 'ceil' 和 'floor' 函数可能会产生不可预知的结果。目前我们不确定如何处理这个问题，但我们正在努力。此时，您可以尝试通过更改数值的参数来更改精度，例如，

    numerics/epsilon    and     numerics/hugeval.

  2. 经过一些迭代后，变量边界的大小为 1^{13}。特别是，SCIP 在每次迭代中对同一个变量进行分支，并且下限恰好增加 1。换句话说，SCIP 可能执行深度优先搜索，并且由于您的积分变量 x_{i} 的范围是 150，因此为替换多项式中的产品而引入的变量范围增加到 11390625000000。显然，SCIP进入深度限制。此外，由于上面提到的数值问题，SCIP 在其中一个节点中的某些变量上分支后无法识别绑定变化。如果 SCIP 选择该节点，则不需要再次求解 LP。

如果您改进了模型，请随时再次发布或向我们发送电子邮件至 SCIP 邮件列表。

亲切的问候，

雅各布

于 2014-12-16T21:09:14.163 回答