1. дома
  2. Вопрос и ответ
  3. максимальный уровень максимальной глубины захвата

максимальный уровень максимальной глубины захвата

2014-12-15 6 views
1

Я получаю ошибку максимального уровня глубины при оптимизации многочлена. На выходе ниже я заметил, что итерации 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

источник

2014-12-15 BeDutra

ответ

1

Прежде всего за отправку этой проблемы. Мы определили две основные проблемы.

  1. Ваши модели швы численно неустойчивы, потому что после нескольких итераций некоторые переменные границы устанавливаются на что-то с величиной 1^{13} до и 1^{- 4} после запятой. В арифметике с плавающей запятой имеется 15-16 значащих знаков. Вот почему использование функций «ceil» и «floor» может дать непредсказуемые результаты. В настоящее время мы не уверены, как справиться с этим, но мы над этим работаем. На данный момент, вы можете попытаться изменить Precisions путем изменения параметров для числовых значений, например,

    numerics/epsilon and  numerics/hugeval.

  2. После нескольких итераций переменных границ находятся в величине 1^{13}. В частности, SCIP-ветви на каждой итерации по одной и той же переменной, а нижняя граница - ровно одна. Другими словами, SCIP выполняет, вероятно, поиск по глубине и поскольку диапазон ваших интегральных переменных x_ {i} равен 150, диапазон переменных, которые вводятся для замены продуктов в вашем полиноме, увеличивается до 11390625000000. Очевидно, SCIP достигает предела глубины. Кроме того, из-за упомянутых выше числовых проблем SCIP не распознает связанные изменения после разветвления на некоторые переменные в одном из узлов. Если SCIP выбирает этот узел, LP не нужно снова решать.

Если у вас есть улучшенная модель, не стесняйтесь публиковать ее или отправить нам электронное письмо в список рассылки SCIP.

С наилучшими пожеланиями,

Jakob

источник

2014-12-16 21:09:14 Jakob

+0

Просто для удовольствия я играл с границами ваших переменных и ограничив границы в [1,15], ваша проблема становится возможным. Возможно, вам стоит попытаться рассчитать лучшие оценки с помощью собственных методов предварительной обработки. – Jakob

Смежные вопросы

 Смежные вопросы