Opened 8 years ago
Closed 7 years ago
#18 closed defect (fixed)
branching problem with unbounded variables
Reported by: | stefan | Owned by: | somebody |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | component1 | Version: | |
Keywords: | Cc: |
Description
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
Change History (3)
comment:1 Changed 8 years ago by pbelotti
comment:2 Changed 8 years ago by stefan
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;
comment:3 Changed 7 years ago by pbelotti
- Resolution set to fixed
- Status changed from new to closed
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.
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