[Coin-discuss] Cglpreproccesing seems "improve" the objective too much

[John J Forrest]

Problem was in part of presolve which was performing a transformation 
which was not valid for integer variables - so a coefficient of 4.004 and 
a rhs of of 4 forced several variables to have lower bounds of 1.0.  I 
suspect the problem is then infeasible - which can take  along time to 
solve.

I have made the smallest change I could think of to CoinPresolve to get 
round problem.

John Forrest



Esben Mose Hansen <esben at ange.dk> 
Sent by: coin-discuss-bounces at list.coin-or.org
03/06/2007 09:53 AM
Please respond to
Discussions about open source software for Operations Research 
<coin-discuss at list.coin-or.org>


To
coin-discuss at list.coin-or.org
cc

Subject
[Coin-discuss] Cglpreproccesing seems "improve" the objective too much






Hi,

I (accidentially, but nevermind that) made a problem which you can 
download at

http://sirius.ange.dk/public/esbennasty.mps

glpsol (and cplex for that matter) solves this problem with little 
problem:

[...]
Integer optimization begins...
+   702: mip =     not found yet >=              -inf        (1; 0)
+   808: mip =   4.004013250e+07 >=   4.003317291e+07 < 0.1% (51; 0)
+   833: mip =   4.003812500e+07 >=   4.003317291e+07 < 0.1% (57; 13)
+  1508: mip =   4.003812500e+07 >=   4.003616868e+07 < 0.1% (58; 317)
+  1558: mip =   4.003812500e+07 >=     tree is empty   0.0% (0; 471)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   6.0 secs
Memory used: 2.3M (2460604 bytes)

Note the optimal solution... 4.0038*10e7. Runnning this through cbc (both 
trunk and devel) gives this:

Problem BLANK has 729 rows, 1265 columns and 7965 elements
Optimal - objective value 4.00332e+07
Cgl0003I 0 fixed, 1065 tightened bounds, 0 strengthened rows, 0 
substitutions
Cgl0003I 0 fixed, 5 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 585 rows, 1052 columns (1052 integer) and 
7448 
elements
processed model has 585 rows, 1052 columns and 7448 elements
Optimal - objective value 4.00492e+07
[...]
Cbc0010I After 0 nodes, 1 on tree, 1e+50 best solution, best possible 
4.20303e+07 (1.39 seconds)


Note how the objective value "improved" from 4.00332e07 to 4.00492e07... 
something that is larger than the minimal solution. Later on it 
further "improves" this solution:

Cuts at root node changed objective from 4.00492e+07 to 4.20303e+07

and then it just starts adding nodes to the tree until it probably runs 
out of 
memory at some point.

My conclusion is that something is wrong with CglProcess... but I'd like 
to 
hear someone elses opinion in this matter :)

-- 
regards, Esben

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20070307/7de2d118/attachment.html>