Couenne says "infeasible problem" although I found an initial solution by hand.

[Burcu Akyildiz]

Dear All,

It is a nonlinear MIP model with continuous, binary and integer variables. When I try to solve it with couenne it says that it is infeasible. But I have already found an initial solution by hand that suits model. I am attaching this hand-made initial solution also. 

I do not undertsand why couenne gives a infeasible result. Would you please help me in this concern? I am attaching the model and data in AMPL format. Below you can see the result page, when I run the model. Thank you! 

ampl: model C:\Users\BURCU\Desktop\Tez\AMPL_TEZ\Facility-baFN4.mod; data C:\Users\BURCU\Desktop\Tez\AMPL_TEZ\Facility-baFN4.dat; solve;

Couenne 0.5.6 -- an Open-Source solver for Mixed Integer Nonlinear Optimization

Mailing list: cou...@list.coin-or.org

Instructions: http://www.coin-or.org/Couenne

couenne: 

ANALYSIS TEST: Reformulating problem: 0.5 seconds

NLP0012I 

              Num      Status      Obj             It       time                 Location

NLP0014I             1      INFEAS 0.96000003       70 60.098

Loaded instance "C:\Users\BURCU\AppData\Local\Temp\at7600.nl"

Constraints:         3796

Variables:           2271 (1121 integer)

Auxiliaries:         1474 (287 integer)

Coin0506I Presolve 73 (-3599) rows, 78 (-3667) columns and 261 (-10185) elements

Clp0006I 0  Obj 0 Primal inf 15608 (32)

Clp0006I 33  Obj 3.0982e-014 Primal inf 2.999994 (6)

Clp0006I 35  Obj 3.0988e-014

Clp0000I Optimal - objective value 0

Clp0032I Optimal objective 0 - 35 iterations time 0.032, Presolve 0.02

Clp0000I Optimal - objective value 0

NLP Heuristic: NLP0014I             2      INFEAS 0.99999999       32 1.229

no solution.

Clp0000I Optimal - objective value 0

Optimality Based BT: 3 improved bounds

Probing: 23 improved bounds

NLP Heuristic: time limit reached.

Cbc0013I At root node, 0 cuts changed objective from 0 to 0 in 1 passes

Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 0 row cuts average 0.0 elements, 57 column cuts (57 active)

Cbc0010I After 0 nodes, 1 on tree, 1e+050 best solution, best possible -1.7976931e+308 (22.91 seconds)

Optimality Based BT: 0 improved bounds

Optimality Based BT: 0 improved bounds

Optimality Based BT: 0 improved bounds

Optimality Based BT: 0 improved bounds

Cbc0001I Search completed - best objective 1e+050, took 298 iterations and 62 nodes (164.06 seconds)

Cbc0035I Maximum depth 10, 0 variables fixed on reduced cost

  "Finished"

Linearization cuts added at root node:       3672

Linearization cuts added in total:           3672  (separation time: 0.016s)

Total solve time:                         164.125s (164.125s in branch-and-bound)

Lower bound:                                 -inf

Upper bound:                                  inf  (gap: --)

Branch-and-bound nodes:                        62

Performance of                           FBBT:       0.266s,       64 runs. fix:          0 shrnk:   0.826375 ubd:    7.02954 2ubd:    2.46442 infeas:         24

couenne: Infeasible problem

[Burcu Akyildiz]

Hi All,

No answers for so far. :(

I just made a search through the net and found out that Couenne gave "infeasible solution" for other people's models when there are binary variables. I changed my binary variables to continious variables, and couenne works! But ofcourse the result is meaningless. Would you please help me to solve the model with my binary variables?

[Pietro Belotti]

This problem seems to expose a bug in the bound reduction code. A solution can actually be found by excluding bound reduction, i.e., by adding the following line to the option file couenne.opt:

feasibility_bt no

Recall that couenne.opt must be in the same directory where AMPL is run.

[Mario Basallo]

Dear Ms. Akyildiz

Attached in this mail you will find a facility layout model that has been successfully solved by Baron. Althought it is not the same as your model, it might be usefull. 

Regards,

Mario Basallo

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+unsubscribe@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Robert Fourer]

When I solve Facility-baFN4.mod and Facility-baFN4.dat with the setting "option presolve 0, show_stats 1;" AMPL tells me there are "4454 constraints, all linear" in this problem.  So I can drop the objective function, making this into a linear feasibility problem, and send it to, say, Gurobi; with option gurobi_options set to 'outlev 1', Gurobi reports

   Coefficient statistics:
     Matrix range     [5e-01, 1e+25]
     Objective range  [0e+00, 0e+00]
     Bounds range     [1e+00, 1e+00]
     RHS range        [1e+00, 1e+25]
   Warning: Model contains large matrix coefficient range
   Warning: Model contains large rhs
            Consider reformulating model or setting NumericFocus parameter
            to avoid numerical issues.

With a range of 25 orders of magnitude in the matrix coefficients and right-hand side (RHS), it should not be surprising that reliable results are hard to obtain; a range of even 8 orders of magnitude can cause difficulties.  Looking through the output of "expand", the problem is seen to be with the "nonoverlap" constraints like this one:

   subject to nonoverlap1['d1','d1']:
        -x1['d1'] + x2['d1'] + 1e+25*zx['d1','d1'] <= 1e+25;

The values of the variables in Gurobi's "feasible" solution are

   ampl: display x1['d1'],x2['d1'],zx['d1','d1'];
   x1['d1'] = 0
   x2['d1'] = 14
   zx['d1','d1'] = 1

These fail to satisfy constraint nonoverlap1['d1','d1'] mathematically, but are feasible in computing since 14 + 1e+25 cannot be distinguished from 1e+25 in double-precision floating point arithmetic:

   ampl: print 14 + 1e+25;
   1e+25

All of the constraints of this kind derive from two model statements:

   subject to nonoverlap1 {i in DEPT,j in DEPT}: x2[j] <= x1[i] + M*(1-zx[i,j]);
   subject to nonoverlap2 {i in DEPT,j in DEPT}: y2[j] <= y1[i] + M*(1-zy[i,j]);

with M set in the data as

   param M:= 9999999999999999999999999 ;        

(which is not distinguishable from 1e+25 in double-precision floating point either).  It should be possible to pick a MUCH smaller value of M for which these constraints are still valid, and that will take care of at least one obstacle to solving this problem effectively.

See also The Big M.

Bob Fourer
am...@googlegroups.com