최대 심도 레벨 초과

Question

다항식을 최적화 할 때 최대 심도 레벨 오류가 발생합니다. 아래 출력에서 ​​LP 반복이 멈춘 것으로 나타났습니다. 왜 많은 변수에서 분기를 건너 뛰고 LP 해석기를 다시 호출하지 않습니까? Ipopt로 실행하고 있습니다.

# 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 

Answer 1

먼저이 문제를 보내 주셔서 감사합니다. 우리는 두 가지 주요 문제를 확인했습니다. 몇 가지 반복 후 약간의 변수 범위가 1^{13}의 크기와 값으로 설정되어 있기 때문에

1. 귀하의 모델 솔기는 수치 적으로 불안정하기 전 1^{- 4} 쉼표 뒤에. 부동 소수점 연산에는 15-16 개의 중요한 신호가 있습니다. 'ceil'및 'floor'기능을 사용하면 예측할 수없는 결과가 발생할 수 있습니다. 현재 우리는이 문제를 어떻게 처리해야할지 확신하지 못하고 있습니다. 이 시점에서 변수 범위는 1^{13}의 크기에 몇 가지 반복 후, 예를 들어 수치에 대한 매개 변수를 변경하여

   numerics/epsilon and  numerics/hugeval. 
   

2. 를 정밀도를 변경하려고 할 수 있습니다. 특히, SCIP는 동일한 변수의 각 반복에서 분기하고, 하한은 정확히 하나씩 증가합니다. 즉, SCIP는 깊이 우선 검색을 수행하고 정수 변수 x_ {i}의 범위가 150이므로 다항식의 제품을 바꾸기 위해 도입 된 변수 범위가 11390625000000으로 증가합니다. 분명히 SCIP 깊이 한계까지 흐른다. 또한 위에서 언급 한 수치 문제로 인해 SCIP는 노드 중 하나에서 일부 변수를 분기 한 후에 바운드 변경을 인식하지 못합니다. SCIP이이 노드를 선택하면 LP를 다시 풀 필요가 없습니다.

모델을 개선 한 경우 다시 게시하거나 SCIP 메일 링리스트에 전자 메일을 보내주십시오.

종류에 관해서, 당신의 변수의 경계에와 [1.15] 문제는 가능하게하는 범위를 제한 한 후 재생 그냥 재미를 위해

야콥