branching problem with unbounded variables

[svigerske]

Issue created by migration from Trac.

Original creator: @svigerske

Original creation time: 2012-01-18 13:39:01

Assignee: somebody

Version:

Hi,

for the QCP

var x1;
var x2;

minimize obj: 3*(-5 + x1)^2 - 10.875*x1 + x1*x2 - x2 + 4*(-6 + x2)^2;

subject to

e2: 3*x1^2 + 2*x1*x2 + 2*x2^2 <= 42;

I have the problem that Couenne repeatedly tries to branch on the same variable, which seems to lead to a very unbalanced tree. On Windos, this results in a crash when Couenne stops due to a timelimit. Presumably, the crash is a stack overflow when Cbc tries to free the tree when recursively calling the CbcNode destructor.

Here is some output when increasing the branching_print_level. It goes on like this "forever".

 ----------------- setup list done, 2 objects
 Branch: x0   will branch on 5.25527e+032 (cur. 2.62763e+032)
 [8.46186e+016,1.797
 69e+308]; firstBranch_ = 0
 ::branch: at 5.25526912165016940000e+032
 Branching: x0   >= 5.25526912165016940000e+032
  x0 >= 5.25527e+032 [8.46186e+016,1.79769e+308]; ::branch: at
 5.2552691216501694
 0000e+032
 Branching: x0   <= 5.25526912165016940000e+032
 Branch: x0 <= 5.25527e+032 [8.46186e+016,1.79769e+308]
 ----------------- setup list
 ----------------- setup list done, 2 objects
 Branch: x0   will branch on 5.25527e+032 (cur. 2.62763e+032)
 [8.46186e+016,1.797
 69e+308]; firstBranch_ = 0
 ::branch: at 5.25526912165016940000e+032
 Branching: x0   >= 5.25526912165016940000e+032
  x0 >= 5.25527e+032 [8.46186e+016,1.79769e+308]; ::branch: at
 5.2552691216501694
 0000e+032
 Branching: x0   <= 5.25526912165016940000e+032
 Branch: x0 <= 5.25527e+032 [8.46186e+016,1.79769e+308]
 ----------------- setup list
 ----------------- setup list done, 2 objects
 Branch: x0   will branch on 5.25527e+032 (cur. 2.62763e+032)
 [8.46186e+016,1.797
 69e+308]; firstBranch_ = 0

I'm using Couenne stable/0.4 rev. 788.

Stefan

[svigerske]

Comment by @merraksh created at 2012-01-23 21:51:03

Stefan,

I cannot reproduce the problem. I'm using revision 790, but I believe there are no influent changes between 788 and 790. I have used no option file and tried to submit that model to Couenne both with and without "option presolv 0;" of AMPL. Can you create a .nl file and submit it?

Pietro

[svigerske]

Comment by @svigerske created at 2012-01-26 11:25:23

Hi,

I don't have AMPL. But maybe the problem is passed differently from GAMS to Couenne than from AMPL to Couenne. E.g., in GAMS the quadratic term is expanded.

So, with problem_print_level 5, I get

objectives:
min (((x_0*x_1)+(3*(x_0^2))+(4*(x_1^2)))+219-40.875*x_0-49*x_1)
constraints:
((2*(x_0*x_1))+(3*(x_0^2))+(2*(x_1^2))) <= 42
variables:
x_0 [ -1e+50 , 1e+50 ]
x_1 [ -1e+50 , 1e+50 ]
end

If you have AMPL, maybe try the equivalent model

var x1;
var x2;

minimize obj: x1*x2 + 3*x1^2 + 4*x2^2 + 219 - 40.875*x1-49*x2;

subject to

e2: 2*x1*x2 + 3*x1^2 + 2*x2^2 <= 42;

[svigerske]

Comment by @merraksh created at 2012-07-31 13:05:22

With the recent revisions 874 this should no longer happen. It was related to a new upper bound being ignored by ClpModel if greater than 1e27. Now all new potential bounds are checked before branching.

[svigerske]

Comment by @merraksh created at 2012-07-31 13:05:22

Resolution: fixed