Opened 10 years ago

Closed 10 years ago

#6 closed defect (fixed)

Couenne returns infeasible solutions

Reported by: algernon64 Owned by: pbelotti
Priority: major Milestone:
Component: component1 Version:
Keywords: Cc:

Description

Hi,

I have been running Couenne to solve several problems involving binary integer variables. I have observed that for most of these problems, the solver is returning infeasible solutions. From what I have observed, this seems to affect the value of the binary variables. For example, in one problem, the value of a variable in the solution should be 1 but is 0. Changing this value to 1 leads to a feasible and what seems to be optimal solution.

I'm using latest stable release on Linux (x64).

I've verified that on Couenne 0.2.2 it works correctly.

Attached is one of the problems in which this error happens (I'm sending the model file).

Regards, Juan

Attachments (1)

myproblem.mod (118.0 KB) - added by algernon64 10 years ago.

Download all attachments as: .zip

Change History (8)

Changed 10 years ago by algernon64

comment:1 Changed 10 years ago by pbelotti

Hi Juan,

I tried the model on the stable versions 0.2 and 0.3 of Couenne, and I could not notice any difference. This is the value of all variables as given by the command "display _var;" in AMPL, in the order specified in your .mod file --- continuous variables alternated to binaries:

_var [*] :=
 1  0        15  0        29  0        43  0        57  0        71  0
 2  0        16  0        30  0        44  0        58  0        72  0
 3  0        17  0        31  0        45  0        59  0        73  0
 4  0        18  0        32  0        46  0        60  0        74  0
 5  0        19  0        33 27.6105   47 38.892    61  0        75  0
 6  0        20  0        34  1        48  1        62  0        76  0
 7 38.902    21 29.2395   35  0        49 28.3895   63 48.8257   77 26.7605
 8  1        22  1        36  0        50  0        64  1        78  1
 9  0        23  0        37  0        51  0        65  0        79  0
10  0        24  0        38  0        52  0        66  0        80  0
11 27.0451   25  0        39  0        53  0        67  0
12  1        26  0        40  0        54  0        68  0
13  0        27 28.9549   41  0        55  0        69 11.2
14  0        28  1        42  0        56  0        70  1
;

Also, a similar command "display _con;" in AMPL shows that all constraints are satisfied. One thing I noticed is that the nonzero variable _var[49] (corresponding to x24, I believe) is not paired by a binary _var[50] (associated to b24), while it appears to be so everywhere else. Is this what you expect?

Pietro

comment:2 Changed 10 years ago by algernon64

Hi,

What does the output of the command "display _con;" mean? It is showing all zeros in my case, which doesn't correspond to the correct values of the constraints.

Also, the solution you provided is not feasible. If you observe the constraints 241-250 in the model, the sum of binary variables in each constraint must equal 1. In this case, _var[50] must be 1 to satisfy constraint c247, which is the problem I mentioned initially.

Juan

comment:3 Changed 10 years ago by pbelotti

  • Owner somebody deleted

comment:4 Changed 10 years ago by pbelotti

  • Owner set to pbelotti
  • Status changed from new to assigned

comment:5 Changed 10 years ago by pbelotti

Hi,

this seems to be a bug in reformulation. Constraint 247 is

b24 + b25 + b26 + b27 - 1 = 0

Due to the last three constraints of your model, Couenne translates it into

b24 + b17 + b18 + b19 - 1 = 0

and the optimal solution found does satisfy this. However, Couenne failed to return to AMPL a complete solution, where b25=b17 etc. -- this is why the original constraint was violated.

I think I fixed this in trunk, stable/0.3, and also stable/0.2. I find it strange that, as you said, it did work on 0.2.2, but I'd ask you anyway to try.

The result I get now seems to satisfy c247 (its slack is 0), and the solution seems different:

c247.slack = 0

b24 + b17 + b18 + b19 - 1 = 0

_var [*] :=
 1   0        17   0        33  28.0026   49  27.9974   65   0
 2   0        18   0        34   1        50   1        66   0
 3   0        19  27.332    35   0        51   0        67   0
 4   0        20   1        36   0        52   0        68   0
 5   0        21 118.733    37   0        53   0        69  18.4885
 6   0        22   0        38   0        54   0        70   1
 7  51.2312   23   0        39   0        55   0        71   0
 8   1        24   0        40   0        56   0        72   0
 9   0        25   0        41   0        57   0        73   0
10   0        26   0        42   0        58   0        74   0
11  28.668    27   0        43   0        59   0        75   0
12   1        28   0        44   0        60   0        76   0
13   0        29  27.0046   45   0        61   0        77  19.8847
14   0        30   1        46   0        62   0        78   1
15   0        31   0        47  39.4124   63  39.414    79   0
16   0        32   0        48   1        64   1        80   0
;

_con.slack [*] :=
  1  56              66 280             131  -5.68434e-14   196 220.703
  2  56              67 196.668         132  -5.68434e-14   197 220.703
  3  56              68 224             133  56             198 130.251
  4  56              69 169.663         134 112             199 213.583
  5 168              70 169.663         135 112             200 113.663
  6   0              71 196.668         136 168             201 113.663
  7  56              72 280             137 168             202 112
  8  56              73 280             138  56             203 102.889
  9  56              74 280             139  -5.68434e-14   204 139.332
 10  55.4656         75 168             140  56             205 139.332
 11 102.355          76 224             141  56             206 186.221
 12  18.4885         77 280             142 112             207 260.115
 13   0              78 280             143 112             208 113.663
 14  19.8847         79  84.668         144 280             209 113.663
 15  19.8847         80 112             145 280             210  56
 16  19.8847         81 168             146 280             211 112
 17   0              82  57.6634        147 280             212 112
 18   0              83  57.6634        148 280             213 102.889
 19   0              84  84.668         149 280             214  55.4656
 20  19.8847         85 113.663         150 280             215 102.355
 21  19.8847         86  92.4427        151 280             216 149.244
 22 112              87  92.4427        152 280             217  55.4656
 23  83.332          88 112             153 280             218 149.779
 24  18.2213         89 102.889         154 280             219 241.627
 25  36.4427         90 139.332         155 280             220  55.4656
 26  27.332          91  92.4427        156 280             221  36.9771
 27  65.1107         92  92.4427        157 186.221         222  83.8664
 28  18.2213         93  92.4427        158 149.244         223 149.244
 29  46.8893         94 186.221         159  56             224 196.134
 30   0              95 139.332         160 168             225 280
 31  56              96  56             161 168             226 280
 32  46.8893         97 168             162 280             227 280
 33 168              98 168             163 280             228 280
 34 168              99 280             164 186.221         229 120.843
 35 140.668         100 139.332         165 233.111         230 167.733
 36 168             101  92.4427        166 139.332         231  83.8664
 37  46.8893        102 112             167 186.221         232  36.9771
 38  46.8893        103 168             168 280             233 168
 39  56             104 280             169 102.355         234   0
 40  56             105 280             170  55.4656        235  65.3779
 41  46.8893        106 186.221         171 112             236   0
 42  36.4427        107 112             172  56             237  65.3779
 43 140.668         108 102.355         173 168             238 112.267
 44 224             109  55.4656        174 280             239  46.8893
 45 112             110  73.9541        175   0             240  93.7787
 46 168             111  73.9541        176   0             241  65.3779
 47 168             112  55.4656        177  56             242   0
 48 224             113  73.9541        178   0             243   0
 49  56             114  55.4656        179   0             244   0
 50  56             115  18.4885        180  84.668         245   0
 51  56             116  65.3779        181  84.668         246   0
 52  83.332         117  83.8664        182  84.668         247   0
 53  18.2213        118 112             183  57.6634        248   0
 54  83.332         119  -5.68434e-14   184  57.6634        249   0
 55  74.2213        120  -5.68434e-14   185  84.668         250   0
 56  -5.68434e-14   121  -5.68434e-14   186 168             251   0
 57  -5.68434e-14   122 280             187 112             252   0
 58 112             123 280             188 168             253   0
 59 177.111         124 280             189 168             254   0
 60 130.221         125 280             190 112             255   0
 61  65.1107        126 280             191  63.4769        256   0
 62  56             127 280             192 119.477         257   0
 63  -5.68434e-14   128 280             193 146.809         258   0
 64  -5.68434e-14   129  56             194 146.809         259   0
 65 280             130 168             195 110.366
;

As for the question 'What does the output of the command "display _con;" mean?', I think I got it wrong. I thought it meant to display the violation of the constraints, but in AMPL this is done by

display _con.slack;

and, AFAIK, shows negative values for violated constraints. The command "display _con;" just prints the duals.

Pietro

comment:6 Changed 10 years ago by algernon64

Hi,

I've now tested the latest 0.3 svn version on a number of similar problems and it works correctly.

The version I initially tested which worked was the 0.2.2 source tarball which I obtained from the coin-or projects page.

Juan

comment:7 Changed 10 years ago by pbelotti

  • Resolution set to fixed
  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.