feasible model declared infeasible

[svigerske]

Issue created by migration from Trac.

Original creator: @svigerske

Original creation time: 2011-09-19 13:46:45

Assignee: somebody

Version:

Hi,

with one instance, Couenne 0.4 reports infeasibility, even though SCIP reports the instance feasible (objective value 0.0).

An ampl conversion is

var x2 := 1;
var x3 >= 0;
var x4 := 1, >= 0;
var x5 := 1, <= 2;
var x6 := 2, <= 2;
var x7 := 1;
var x8 >= 0, <= 2;
var x9 := 1, >= 0, <= 2;
var x10 := 2, >= 0, <= 2;
var x11 := 1, >= 0;
var x12 >= 0;
var x13 >= 0;
var x14 := 4, >= 0;
var x15 := 2, >= 0;
var x16 >= 0;
var x17 >= 0;
var x18 >= 0;
var x19 >= 0;
var x20 := 4, >= 0;

minimize obj: (-1 + x2)^2;

subject to

e2:  - x2 + 3*x3 + x4 - x11 = -1;

e3:  - x2 + x3 + 3*x4 - x12 = 2;

e4:  - x2 + 3*x5 + x6 + x13 = 4;

e5:  - x2 + x5 + 3*x6 + x14 = 10;

e6:  - x2 + x3 + x4 + x5 + x6 + 10*x7 + x8 + x9 + x10 = 16;

e7:  - x2 + 3*x8 + x9 + x10 - x15 + x16 = 0;

e8:  - x2 + x8 + 3*x9 + x10 - x17 + x18 = 4;

e9:  - x2 + x8 + x9 + 3*x10 - x19 + x20 = 10;

e10: x11*x3 = 0;

e11: x12*x4 = 0;

e12: x13*(2 - x5) = 0;

e13: x14*(2 - x6) = 0;

e14: x15*x8 = 0;

e15: x16*(2 - x8) = 0;

e16: x17*x9 = 0;

e17: x18*(2 - x9) = 0;

e18: x19*x10 = 0;

e19: x20*(2 - x10) = 0;

Can you try to reproduce the problem?

Couenne output:

NLP0012I 
              Num      Status      Obj             It       time                 Location
NLP0014I             1         OPT 1.640146e-235.5g        4 0.002999g

Coin0506I Presolve 6 (-28) rows, 3 (-38) columns and 13 (-85) elements
Clp0006I 0  Obj 0.0001 Primal inf 0.0082958817 (1) Dual inf 1.9999999 (1)
Clp0006I 0  Obj 0.0001 Primal inf 0.0082958817 (1) Dual inf 1e+10 (2)
Clp0006I 3  Obj -0.015610312
Clp0000I Optimal - objective value -0.015610312
Clp0032I Optimal objective -0.01561031175 - 3 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value -0.015610312
NLP0014I             2         OPT 1.62459e-215.5g       23 0.014997g
Clp0000I Optimal - objective value -0.015610312
Cbc0006I The LP relaxation is infeasible or too expensive
Cbc0013I At root node, 0 cuts changed objective from -0.015610312 to -0.015610312 in 1 passes
Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 0 row cuts average 0.0 elements, 2 column cuts (2 active)
Cbc0001I Search completed - best objective 1e+50, took 0 iterations and 0 nodes (0.04 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
 Couenne convexifier cuts was tried 1 times and created 2 cuts of which 0 were active after adding rounds of cuts

Couenne 0.3 seems to work, too.

Stefan

[svigerske]

Comment by @merraksh created at 2011-09-24 12:23:00

Hi,

unfortunately I can't reproduce the problem. Below is the output I get with stable/0.4 with no couenne.opt file.

Couenne  --  an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: couenne`@`list.coin-or.org
Instructions: http://www.coin-or.org/Couenne
couenne: 
ANALYSIS TEST: NLP0012I 
              Num      Status      Obj             It       time                 Location
NLP0014I             1         OPT 1.4031777e-205.5g        5 0g
Coin0506I Presolve 4 (-16) rows, 2 (-34) columns and 8 (-54) elements
Clp0006I 0  Obj 0 Primal inf 0.0001748 (2)
Clp0006I 2  Obj 1.995e-20
Clp0000I Optimal - objective value 0
Clp0032I Optimal objective 0 - 2 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value 0
Cbc0012I Integer solution of 1.403175e-20 found by Couenne Rounding NLP after 0 iterations and 0 nodes (0.00 seconds)
NLP0014I             2         OPT 2.7792587e-245.5g       14 0g
Clp0001I Primal infeasible - objective value 0
Clp0001I Primal infeasible - objective value 0
Clp0006I 0  Obj 0
Clp0006I 0  Obj 0
Clp0000I Optimal - objective value 0
Cbc0001I Search completed - best objective 1.403175042267959e-20, took 0 iterations and 0 nodes (0.01 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost

    "Finished"

couenne: Optimal

You may want to disable some of the new feature to check which is responsible. Try for instance

use_semiaux no

Regards, Pietro

[svigerske]

Comment by @svigerske created at 2011-09-29 01:00:59

Setting use_semiaux no does not help.

I increased some print levels and below is the output. It seems that probing finds the problem infeasible. Can you see, why?

objectives:
min ((x_0^2)+1-2*x_0)
constraints:
(-x_0+3*x_1+x_2-x_9) = -1
(-x_0+x_1+3*x_2-x_10) = 2
(-x_0+3*x_3+x_4+x_11) = 4
(-x_0+x_3+3*x_4+x_12) = 10
(-x_0+x_1+x_2+x_3+x_4+10*x_5+x_6+x_7+x_8) = 16
(-x_0+3*x_6+x_7+x_8-x_13+x_14) = 0
(-x_0+x_6+3*x_7+x_8-x_15+x_16) = 4
(-x_0+x_6+x_7+3*x_8-x_17+x_18) = 10
(x_1*x_9) = 0
(x_2*x_10) = 0
((-(x_3*x_11))+2*x_11) = 0
((-(x_4*x_12))+2*x_12) = 0
(x_6*x_13) = 0
((-(x_6*x_14))+2*x_14) = 0
(x_7*x_15) = 0
((-(x_7*x_16))+2*x_16) = 0
(x_8*x_17) = 0
((-(x_8*x_18))+2*x_18) = 0
variables:
x_0 [ -1e+50 , 1e+50 ]
x_1 [ 0 , 1e+50 ]
x_2 [ 0 , 1e+50 ]
x_3 [ -1e+50 , 2 ]
x_4 [ -1e+50 , 2 ]
x_5 [ -1e+50 , 1e+50 ]
x_6 [ 0 , 2 ]
x_7 [ 0 , 2 ]
x_8 [ 0 , 2 ]
x_9 [ 0 , 1e+50 ]
x_10 [ 0 , 1e+50 ]
x_11 [ 0 , 1e+50 ]
x_12 [ 0 , 1e+50 ]
x_13 [ 0 , 1e+50 ]
x_14 [ 0 , 1e+50 ]
x_15 [ 0 , 1e+50 ]
x_16 [ 0 , 1e+50 ]
x_17 [ 0 , 1e+50 ]
x_18 [ 0 , 1e+50 ]
end
Problem size before reformulation: 19 variables (0 integer), 18 constraints.
Couenne: initial solution (value 0) is MINLP feasible
Couenne: new MINLP solution, value 0.0000000000e+00
created Expression Object: w_19 := (x_0^2) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_21 := (x_1*w_9) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_23 := (x_2*w_10) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_25 := (x_3*w_11) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_27 := (x_4*w_12) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_29 := (x_6*x_13) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_31 := (x_6*w_14) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_33 := (x_7*x_15) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_35 := (x_7*w_16) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_37 := (w_8*x_17) with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_39 := (w_8*w_18) with mid-point strategy [clamp=0.2, alpha=0.25]
Initializing auxiliaries
Problem size after  reformulation: 36 variables (0 integer), 10 constraints.
objectives:
min w_20
constraints:
w_21 = 0
w_23 = 0
w_26 = 0
w_28 = 0
w_29 = 0
w_32 = 0
w_33 = 0
w_36 = 0
w_37 = 0
w_40 = 0
variables:
x_0 [ -1e+50 , 1e+50 ]
x_1 [ 0 , 1e+50 ]
x_2 [ 0 , 1e+50 ]
x_3 [ -1e+50 , 2 ]
x_4 [ -1e+50 , 2 ]
x_5 [ -1e+50 , 1e+50 ]
x_6 [ 0 , 2 ]
x_7 [ 0 , 2 ]
w_8 (r:2, m:1) := (16+x_0-x_1-x_2-x_3-x_4-10*x_5-x_6-x_7) [ 0 , 2 ]
w_9 (r:2, m:1) := (1-x_0+3*x_1+x_2) [ 0 , inf ]
w_10 (r:2, m:1) := (-2-x_0+x_1+3*x_2) [ 0 , inf ]
w_11 (r:2, m:1) := (4+x_0-3*x_3-x_4) [ 0 , inf ]
w_12 (r:2, m:1) := (10+x_0-x_3-3*x_4) [ 0 , inf ]
x_13 [ 0 , 1e+50 ]
w_14 (r:3, m:1) := (x_0-3*x_6-x_7-w_8+x_13) [ 0 , inf ]
x_15 [ 0 , 1e+50 ]
w_16 (r:3, m:1) := (4+x_0-x_6-3*x_7-w_8+x_15) [ 0 , inf ]
x_17 [ 0 , 1e+50 ]
w_18 (r:3, m:1) := (10+x_0-x_6-x_7-3*w_8+x_17) [ 0 , inf ]
w_19 (r:2, m:1) := (x_0^2) [ 0 , inf ]
w_20 (r:3, m:1) := (1-2*x_0+w_19) [ -inf , inf ]
w_21 (r:3, m:1) := (x_1*w_9) [ 0 , 0 ] integer
w_23 (r:3, m:1) := (x_2*w_10) [ 0 , 0 ] integer
w_25 (r:3, m:1) := (x_3*w_11) [ -inf , inf ]
w_26 (r:4, m:1) := (2*w_11-w_25) [ 0 , 0 ] integer
w_27 (r:3, m:1) := (x_4*w_12) [ -inf , inf ]
w_28 (r:4, m:1) := (2*w_12-w_27) [ 0 , 0 ] integer
w_29 (r:2, m:1) := (x_6*x_13) [ 0 , 0 ] integer
w_31 (r:4, m:1) := (x_6*w_14) [ 0 , inf ]
w_32 (r:5, m:1) := (2*w_14-w_31) [ 0 , 0 ] integer
w_33 (r:2, m:1) := (x_7*x_15) [ 0 , 0 ] integer
w_35 (r:4, m:1) := (x_7*w_16) [ 0 , inf ]
w_36 (r:5, m:1) := (2*w_16-w_35) [ 0 , 0 ] integer
w_37 (r:3, m:1) := (w_8*x_17) [ 0 , 0 ] integer
w_39 (r:4, m:1) := (w_8*w_18) [ 0 , inf ]
w_40 (r:5, m:1) := (2*w_18-w_39) [ 0 , 0 ] integer
end

List of user-set options:

                                    Name   Value                used
             boundtightening_print_level = 4                     yes
                   branching_print_level = 4                     yes
                convexifying_print_level = 4                     yes
                        delete_redundant = yes                   yes
                            max_cpu_time = 499.965               yes
                    nlp_failure_behavior = fathom                yes
                     problem_print_level = 6                     yes
                             use_semiaux = no                    yes
NLP0012I 
              Num      Status      Obj             It       time                 Location
NLP0014I             1         OPT 1.640146e-235.5g        4 0.003999g
Couenne: 42 cuts (29 row, 13 col) for linearization
created Variable Object: x_0 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_1 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_2 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_3 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_4 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_6 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_7 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_8 := (16+x_0-x_1-x_2-x_3-x_4-10*x_5-x_6-x_7) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_8 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_9 := (1-x_0+3*x_1+x_2) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_9 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_10 := (-2-x_0+x_1+3*x_2) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_10 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_11 := (4+x_0-3*x_3-x_4) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_11 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_12 := (10+x_0-x_3-3*x_4) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_12 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_13 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_14 := (x_0-3*x_6-x_7-w_8+x_13) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_14 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_15 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_16 := (4+x_0-x_6-3*x_7-w_8+x_15) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_16 with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: x_17 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_18 := (10+x_0-x_6-x_7-3*w_8+x_17) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_18 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_21 := (x_1*w_9) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_21 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_23 := (x_2*w_10) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_23 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_26 := (2*w_11-w_25) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_26 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_28 := (2*w_12-w_27) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_28 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_29 := (x_6*x_13) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_29 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_32 := (2*w_14-w_31) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_32 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_33 := (x_7*x_15) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_33 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_36 := (2*w_16-w_35) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_36 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_37 := (w_8*x_17) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_37 with mid-point strategy [clamp=0.2, alpha=0.25]
created Expression Object: w_40 := (2*w_18-w_39) with mid-point strategy [clamp=0.2, alpha=0.25]
created Variable Object: w_40 with mid-point strategy [clamp=0.2, alpha=0.25]
Couenne initialized (0.019 seconds).

Coin0506I Presolve 6 (-23) rows, 3 (-38) columns and 13 (-75) elements
Clp0006I 0  Obj 0.0001 Primal inf 0.0082958817 (1) Dual inf 1.9999999 (1)
Clp0006I 0  Obj 0.0001 Primal inf 0.0082958817 (1) Dual inf 1e+10 (2)
Clp0006I 3  Obj -0.015610312
Clp0000I Optimal - objective value -0.015610312
Clp0032I Optimal objective -0.01561031175 - 3 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value -0.015610312
NLP0014I             2         OPT 1.62459e-215.5g       23 0.027995g
Clp0000I Optimal - objective value -0.015610312
  x_0.  x =          1, lb = -0.0156103, cutoff = 0-----------------
 [  0.968514,  0.982915] lb = -0.0156103 {fea=1,btr=0} 
 [  0.968514,  0.973806] lb = -0.0110699 {fea=1,btr=0} 
 [  0.968514,  0.969126] lb = -0.00197622 {fea=1,btr=0} 
  x_0.  x =          1, lb = -0.0156103, cutoff = 0-----------------
 [   1.02257,   1.04035] lb = -0.0156103 {fea=1,btr=0} 
 [   1.03474,   1.04035] lb = -0.0126518 {fea=1,btr=0} 
 [   1.04102,   1.04035] lb = -8.06182e-05 {fea=0,btr=0} 
  x_2.  x =          1, lb = -0.0156103, cutoff = 0-----------------
 [  0.990072,  0.994676] lb = -0.0156103 {fea=1,btr=0} 
 [  0.990072,  0.991888] lb = -0.0112907 {fea=1,btr=0} 
 [  0.990072,  0.990468] lb = -0.00299315 {fea=1,btr=0} 
  x_2.  x =          1, lb = -0.0156103, cutoff = 0-----------------
    # x0 = 1 iter   0: [ +0.966578 ->  +0.983289 --    +1.0436] /\/\  [  0.966578,  0.983289]<0.966578,1>=>     # x0 = 1 iter   1: [ +0.966578 ->  +0.974934 --    +1.0436] /\/\  [  0.966578,  0.974934]<0.966578,0.983289>=>     # x0 = 1 iter   2: [ +0.966578 ->  +0.970756 --    +1.0436] /\/\  [  0.966578,  0.970756]<0.966578,0.974934>=>     # x0 = 1 iter   0: [ +0.966578 --    +1.0218 <-    +1.0436] /\/\  [    1.0218,    1.0436]<1,1.0436>=>     # x0 = 1 iter   1: [ +0.966578 --    +1.0327 <-    +1.0436] /\/\  [    1.0327,    1.0436]<1.0218,1.0436>=>     # x0 = 1 iter   2: [ +0.966578 --   +1.03815 <-    +1.0436] /\/\  [   1.03815,    1.0436]<1.0327,1.0436>=>     # x2 = 1 iter   0: [ +0.989505 ->  +0.994752 --   +1.01189] /\/\  [  0.989505,  0.994752]<0.989505,1>=>     # x2 = 1 iter   1: [ +0.989505 ->  +0.992129 --   +1.01189] /\/\  [  0.989505,  0.992129]<0.989505,0.994752>=>     # x2 = 1 iter   2: [ +0.989505 ->  +0.990817 --   +1.01189] /\/\  [  0.989505,  0.990817]<0.989505,0.992129>=>     # x2 = 1 iter    [   1.00606,   1.01117] lb = -0.0156103 {fea=1,btr=0} 
 [   1.00923,   1.01117] lb = -0.0125536 {fea=1,btr=0} 
 [   1.01086,   1.01117] lb = -0.00282679 {fea=1,btr=0} 
  x_3.  x =          1, lb = -0.0156103, cutoff = 0-----------------
 [-1.79769e+308,-1.34078e+154] lb = -0.0156103 {fea=0,btr=0} 
 [-1.79769e+308,-1.15792e+77] lb = -0.0156103 {fea=0,btr=0} 
 [-1.79769e+308,-3.40282e+38] lb = -0.0156103 {fea=0,btr=0} 
    pruned by Probing
Cbc0006I The LP relaxation is infeasible or too expensive
Cbc0013I At root node, 0 cuts changed objective from -0.015610312 to -0.015610312 in 1 passes
Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 0 row cuts average 0.0 elements, 2 column cuts (2 active)
Cbc0001I Search completed - best objective 1e+50, took 0 iterations and 0 nodes (0.08 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
 Couenne convexifier cuts was tried 1 times and created 2 cuts of which 0 were active after adding rounds of cuts

Couenne finished. No feasible solution found.

0: [ +0.989505 --   +1.00595 <-   +1.01189] /\/\  [   1.00595,   1.01189]<1,1.01189>=>     # x2 = 1 iter   1: [ +0.989505 --   +1.00892 <-   +1.01189] /\/\  [   1.00892,   1.01189]<1.00595,1.01189>=>     # x2 = 1 iter   2: [ +0.989505 --    +1.0104 <-   +1.01189] /\/\  [    1.0104,   1.01189]<1.00892,1.01189>=>     # x3 = 1 iter   0: [-1.79769e+308 -> -1.34078e+154 --   +1.01189] /\/\  [-1.79769e+308,-1.34078e+154]<-1.79769e+308,1>=>     # x3 = 1 iter   1: [-1.79769e+308 -> -1.15792e+77 --   +1.01117] /\/\  [-1.79769e+308,-1.15792e+77]<-1.34078e+154,1>=>     # x3 = 1 iter   2: [-1.79769e+308 -> -3.40282e+38 --   +1.01054] /\/\  [-1.79769e+308,-3.40282e+38]<-1.15792e+77,1>=>

[svigerske]

Attachment out.gz by @merraksh created at 2011-09-29 01:04:28

Output file sent by Stefan

[svigerske]

Comment by @merraksh created at 2012-01-26 03:38:33

Stefan,

I just submitted a few changes to stable/0.4, merged from trunk, that should take care of a few such issues. The AMPL conversion that you have provided now gives me an optimal solution with an objective of 0. Can you please check if this works now?

Thanks, Pietro

[svigerske]

Comment by @svigerske created at 2012-01-26 11:17:40

Unfortunately, it still reports infeasible for me.

Can you attach the .nl file that you created? Maybe I can see why it behaves differently.

[svigerske]

Comment by @merraksh created at 2012-01-26 18:59:08

Here is the problem (I cannot attach it for technical problems).

g9 0 1 0 18 20110112 0 4 0 240  # problem ticket14
 19 18 1 0 18   # vars, constraints, objectives, ranges, eqns
 10 1   # nonlinear constraints, objectives
 0 0    # network constraints: nonlinear, linear
 17 18 0    # nonlinear vars in constraints, objectives, both
 0 0 0 1    # linear network variables; functions; arith, flags
 0 0 0 0 0  # discrete variables: binary, integer, nonlinear (b,c,o)
 63 1   # nonzeros in Jacobian, gradients
 0 0    # max name lengths: constraints, variables
 0 0 0 0 0  # common exprs: b,c,o,c1,o1
C0
o2
v7
v0
C1
o2
v8
v1
C2
o2
v9
o1
n2
v2
C3
o2
v10
o1
n2
v3
C4
o2
v11
v4
C5
o2
v12
o1
n2
v4
C6
o2
v13
v5
C7
o2
v14
o1
n2
v5
C8
o2
v15
v6
C9
o2
v16
o1
n2
v6
C10
n0
C11
n0
C12
n0
C13
n0
C14
n0
C15
n0
C16
n0
C17
n0
O0 0
o5
o0
n-1
v17
n2
x11
1 1
2 1
3 2
5 1
6 2
7 1
10 4
11 2
16 4
17 1
18 1
r
4 0
4 0
4 0
4 0
4 0
4 0
4 0
4 0
4 0
4 0
4 -1
4 2
4 4
4 10
4 16
4 0
4 4
4 10
b
2 0
2 0
1 2
1 2
0 0 2
0 0 2
0 0 2
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
2 0
3
3
k18
4
8
12
16
22
28
34
36
38
40
42
44
46
48
50
52
54
62
J0 2
0 0
7 0
J1 2
1 0
8 0
J2 2
2 0
9 0
J3 2
3 0
10 0
J4 2
4 0
11 0
J5 2
4 0
12 0
J6 2
5 0
13 0
J7 2
5 0
14 0
J8 2
6 0
15 0
J9 2
6 0
16 0
J10 4
0 3
1 1
7 -1
17 -1
J11 4
0 1
1 3
8 -1
17 -1
J12 4
2 3
3 1
9 1
17 -1
J13 4
2 1
3 3
10 1
17 -1
J14 9
0 1
1 1
2 1
3 1
4 1
5 1
6 1
17 -1
18 10
J15 6
4 3
5 1
6 1
11 -1
12 1
17 -1
J16 6
4 1
5 3
6 1
13 -1
14 1
17 -1
J17 6
4 1
5 1
6 3
15 -1
16 1
17 -1
G0 1
17 0

The output I get without any couenne.opt option file on Couenne stable/0.4 is as follows:

Couenne 0.4 --  an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: couenne`@`list.coin-or.org
Instructions: http://www.coin-or.org/Couenne

NLP0012I 
              Num      Status      Obj             It       time                 Location
NLP0014I             1         OPT 1.4031777e-205.5g        5 0g
Coin0506I Presolve 4 (-16) rows, 2 (-34) columns and 8 (-54) elements
Clp0006I 0  Obj 0 Primal inf 0.0001748 (2)
Clp0006I 2  Obj 1.995e-20
Clp0000I Optimal - objective value 0
Clp0032I Optimal objective 0 - 2 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value 0
Cbc0012I Integer solution of 1.403175e-20 found by Couenne Rounding NLP after 0 iterations and 0 nodes (0.00 seconds)
NLP0014I             2         OPT 2.7792587e-245.5g       14 0g
Clp0001I Primal infeasible - objective value 0
Clp0001I Primal infeasible - objective value 0
Clp0006I 0  Obj 0
Clp0006I 0  Obj 0
Clp0000I Optimal - objective value 0
Cbc0001I Search completed - best objective 1.403175042267959e-20, took 0 iterations and 0 nodes (0.01 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Clp0006I 0  Obj 0 Primal inf 0.015909802 (9)
Clp0006I 1  Obj 0
Clp0000I Optimal - objective value 0

couenne: Optimal

    "Finished"

[svigerske]

Comment by @svigerske created at 2012-02-05 17:46:16

Hi,

if I tweak the Couenne interface in a way that the problem printed by Couenne (before reformulation) looks like the one printed for your .nl file, then Couenne indeed finds the optimal solution.

The important difference was in the formulation of quadratic terms. While through AMPL you get things like x(1-y), you will get x-xy through the GAMS interface. Even though equivalent, Couenne seems to behave differently.

So what happens if you pass the following AMPL model to Couenne?

var x2 := 1;
var x3 >= 0;
var x4 := 1, >= 0;
var x5 := 1, <= 2;
var x6 := 2, <= 2;
var x7 := 1;
var x8 >= 0, <= 2;
var x9 := 1, >= 0, <= 2;
var x10 := 2, >= 0, <= 2;
var x11 := 1, >= 0;
var x12 >= 0;
var x13 >= 0;
var x14 := 4, >= 0;
var x15 := 2, >= 0;
var x16 >= 0;
var x17 >= 0;
var x18 >= 0;
var x19 >= 0;
var x20 := 4, >= 0;

minimize obj: 1 - 2*x2 + x2^2;

subject to

e2:  - x2 + 3*x3 + x4 - x11 = -1;

e3:  - x2 + x3 + 3*x4 - x12 = 2;

e4:  - x2 + 3*x5 + x6 + x13 = 4;

e5:  - x2 + x5 + 3*x6 + x14 = 10;

e6:  - x2 + x3 + x4 + x5 + x6 + 10*x7 + x8 + x9 + x10 = 16;

e7:  - x2 + 3*x8 + x9 + x10 - x15 + x16 = 0;

e8:  - x2 + x8 + 3*x9 + x10 - x17 + x18 = 4;

e9:  - x2 + x8 + x9 + 3*x10 - x19 + x20 = 10;

e10: x11*x3 = 0;

e11: x12*x4 = 0;

e12: x13*2 - x13*x5 = 0;

e13: x14*2 - x14*x6 = 0;

e14: x15*x8 = 0;

e15: x16*2 - x16*x8 = 0;

e16: x17*x9 = 0;

e17: x18*2 - x18*x9 = 0;

e18: x19*x10 = 0;

e19: x20*2 - x20*x10 = 0;

I guess the problem is similar to the one reported in ticket #18.

Stefan

[svigerske]

Comment by @merraksh created at 2012-02-06 04:36:01

Although x(1-y) = x-xy, they are reformulated differently and trigger different performances. I tried the model above and I get an optimal solution of 0 with x2=1. This is the output (with the latest stable/0.4):

Couenne 0.4 --  an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: couenne`@`list.coin-or.org
Instructions: http://www.coin-or.org/Couenne

NLP0012I 
              Num      Status      Obj             It       time                 Location
NLP0014I             1         OPT 05.5g        5 0g
Loaded instance "../../repos/problems/test/ticket14a.nl"
Constraints:           18
Variables:             19 (0 integer)
Auxiliaries:           17 (0 integer)

Coin0506I Presolve 6 (-23) rows, 3 (-33) columns and 13 (-75) elements
Clp0006I 0  Obj 0.0001 Primal inf 0.017925389 (1) Dual inf 1.9999999 (1)
Clp0006I 0  Obj 0.0001 Primal inf 0.017925389 (1) Dual inf 1e+10 (1)
Clp0006I 3  Obj -0.01412367
Clp0000I Optimal - objective value -0.01412367
Clp0032I Optimal objective -0.01412366957 - 3 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value -0.01412367
Cbc0012I Integer solution of 0 found by Couenne Rounding NLP after 0 iterations and 0 nodes (0.00 seconds)
NLP Heuristic: NLP0014I             2         OPT 05.5g       15 0g
no solution.
Clp0000I Optimal - objective value -0.01412367
Optimality Based BT: 6 improved bounds
Cbc0031I 2 added rows had average density of 2
Cbc0013I At root node, 3 cuts changed objective from -0.01412367 to -1.4045259e-05 in 5 passes
Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 5 row cuts average 2.0 elements, 41 column cuts (44 active)
Cbc0001I Search completed - best objective 0, took 5 iterations and 0 nodes (0.02 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost

couenne: Optimal

    "Finished"

Linearization cuts added at root node:         29
Linearization cuts added in total:             29  (separation time: 0s)
Total solving time:                          0.02s (0.02s in branch-and-bound)
Lower bound:                                    0
Upper bound:                                    0  (gap: 0.00%)
Branch-and-bound nodes:                         0

Also, I don't think this has to do with ticket #18, where some strange branching behavior occurs because of the inability of Couenne to provide a lower bound.

[svigerske]

Comment by @svigerske created at 2012-07-31 12:54:29

Seems to work fine with current stable/0.4.

[svigerske]

Comment by @merraksh created at 2012-07-31 12:56:42

Resolution: fixed