[Bug-glpk] [Fwd: RE: [Fwd: MIP solver bug]]

[Andrew Makhorin]

-------- Forwarded Message --------
From: address@hidden
To: address@hidden
Cc: address@hidden, address@hidden, address@hidden,
address@hidden
Subject: RE: [Bug-glpk] [Fwd: MIP solver bug]
Date: Thu, 12 Jan 2017 00:38:42 +0000

Hi Chris & Andrew,

Thanks for reply.

Yes, this is our big-M problem with original setup, i.e. x- M b  < 0, x + M b > 0
We have just updated glpk from v55 to v60 and found the issue.

I had impression that the new setup of problem is not solvable either with 
default parameters: x - lower_bound_x b > 0, x - upper_bound_x b < 0.
Will double check tomorrow.

Re MIP presolver, I do notice that without presolver the solver returns some 
dummy solution.

Is Pesudocost branching better in general? Any particular user case?

Many thanks,
Emma 

Dong Mei (Emma) Wang
Quantitative Analyst    i
Markets
RBS
135 Bishopsgate, London, EC2M 3UR, GB
Office: +44 20 7638 7590   |  Mobile: +44 7584403047 

-----Original Message-----
From: Chris Matrakidis [mailto:address@hidden 
Sent: 11 January 2017 21:27
To: Wang, Dong mei (NatWest Markets)
Cc: Bug Glpk; Andrew Makhorin; Odetti, Andrea (NatWest Markets)
Subject: Re: [Bug-glpk] [Fwd: MIP solver bug]

*********************************************
" This message originates from outside our organisation. Consider carefully 
whether you should click on any links, open any attachments or reply. If in 
doubt, forward to ~ Phishing"
*********************************************

Hi Emma,

> The attached example can be solved quickly in 4.56 but not in 4.57 and 
> afterwards.

Starting with version 4.56 Andrew is improving the solver routines, however I 
don't think this is the issue here.

Using GLPK 4.60 (the latest released version), I can quickly solve your problem 
with pseudocost brancing, However if I disable the MIP presolver (--nointopt) I 
get a different solution, which is strongly indicating accuracy issues. Indeed 
the line:
A: min|aij| = 2.451e-011  max|aij| = 1.158e+077  ratio = 4.724e+087 indicates 
that there are some very large values in the problem, which can cause problems 
like this. Is this a big M formulation like the one you showed last week?

Best Regards,

Chris Matrakidis

PS. The output from the first run is:

GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
 --pcost --glp \Users\Chris\Downloads\lp.txt Reading problem data from 
'\Users\Chris\Downloads\lp.txt'...
332 rows, 190 columns, 5043 non-zeros
95 integer variables, all of which are binary
5563 lines were read
GLPK Integer Optimizer, v4.60
332 rows, 190 columns, 5043 non-zeros
95 integer variables, all of which are binary Preprocessing...
95 constraint coefficient(s) were reduced
154 rows, 190 columns, 3899 non-zeros
95 integer variables, all of which are binary Scaling...
 A: min|aij| = 1.307e-009  max|aij| = 7.569e+005  ratio = 5.792e+014
GM: min|aij| = 1.939e-004  max|aij| = 5.157e+003  ratio = 2.659e+007
EQ: min|aij| = 3.761e-008  max|aij| = 1.000e+000  ratio = 2.659e+007
2N: min|aij| = 4.643e-008  max|aij| = 1.710e+000  ratio = 3.684e+007 
Constructing initial basis...
Size of triangular part is 154
Solving LP relaxation...
GLPK Simplex Optimizer, v4.60
154 rows, 190 columns, 3899 non-zeros
      0: obj =  1.934670808e+006 inf =  1.688e+005 (93)
    231: obj =  1.673470251e-009 inf =  1.269e-015 (0) 1 OPTIMAL LP SOLUTION 
FOUND Integer optimization begins...
+   231: mip =     not found yet >=              -inf        (1; 0)
Warning: numerical instability (dual simplex, phase II)
+ 15741: >>>>>  3.256673153e-008 >=  1.666194294e-009  94.9% (20; 368)
+ 15741: mip =  3.256673153e-008 >=     tree is empty   0.0% (0; 583)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   1.4 secs
Memory used: 1.2 Mb (1220521 bytes)


Without MIP presolving:

GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
 --pcost --glp \Users\Chris\Downloads\lp.txt --nointopt Reading problem data 
from '\Users\Chris\Downloads\lp.txt'...
332 rows, 190 columns, 5043 non-zeros
95 integer variables, all of which are binary
5563 lines were read
Scaling...
 A: min|aij| = 2.451e-011  max|aij| = 1.158e+077  ratio = 4.724e+087
GM: min|aij| = 1.939e-004  max|aij| = 5.157e+003  ratio = 2.659e+007
EQ: min|aij| = 3.761e-008  max|aij| = 1.000e+000  ratio = 2.659e+007 
Constructing initial basis...
Size of triangular part is 328
GLPK Simplex Optimizer, v4.60
332 rows, 190 columns, 5043 non-zeros
Preprocessing...
154 rows, 190 columns, 3899 non-zeros
Scaling...
 A: min|aij| = 1.307e-009  max|aij| = 1.158e+077  ratio = 8.862e+085
GM: min|aij| = 1.939e-004  max|aij| = 5.157e+003  ratio = 2.659e+007
EQ: min|aij| = 3.761e-008  max|aij| = 1.000e+000  ratio = 2.659e+007 
Constructing initial basis...
Size of triangular part is 154
      0: obj =  1.934670808e+006 inf =  1.884e+045 (1)
      4: obj =  1.934670808e+006 inf =  1.394e-026 (0)
*    76: obj = -3.027563880e+006 inf =  4.264e-027 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.60
332 rows, 190 columns, 5043 non-zeros
95 integer variables, all of which are binary Integer optimization begins...
+    76: mip =     not found yet >=              -inf        (1; 0)
+    76: >>>>> -3.027563880e+006 >= -3.027563880e+006   0.0% (1; 0)
+    76: mip = -3.027563880e+006 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.6 Mb (603108 bytes)
******************************************************************

NatWest Markets is a marketing name of The Royal Bank of Scotland plc. 

This communication and any attachments are confidential and intended solely for 
the addressee. If you are not the intended recipient please advise us 
immediately and delete it. Unless specifically stated in the message or 
otherwise indicated, you may not duplicate, redistribute or forward this 
message and any attachments are not intended for distribution to, or use by any 
person or entity in any jurisdiction or country where such distribution or use 
would be contrary to local law or regulation. The Royal Bank Of Scotland plc or 
any affiliated entity ("RBS") accepts no responsibility for any changes made to 
this message after it was sent.

Unless otherwise specifically indicated, the contents of this communication and 
its attachments are for information purposes only and should not be regarded as 
an offer or solicitation to buy or sell a product or service, confirmation of 
any transaction, a valuation, indicative price or an official statement. Where 
this communication has been prepared by an RBS trading desk, that desk may have 
a position or interest in the products or services mentioned that is 
inconsistent with any views expressed in this message. In evaluating the 
information contained in this message, you should know that it could have been 
previously provided to other clients and/or internal RBS personnel, who could 
have already acted on it.

RBS cannot provide absolute assurances that all electronic communications (sent 
or received) are secure, error free, not corrupted, incomplete or virus free 
and/or that they will not be lost, mis-delivered, destroyed, delayed or 
intercepted/decrypted by others. Therefore RBS disclaims all liability with 
regards to electronic communications (and the contents therein) if they are 
corrupted, lost destroyed, delayed, incomplete, mis-delivered, intercepted, 
decrypted or otherwise misappropriated by others.

Any electronic communication that is conducted within or through RBS systems 
will be subject to being archived, monitored and produced to regulators and in 
litigation in accordance with RBS's policy and local laws, rules and 
regulations. Unless expressly prohibited by local law, electronic 
communications may be archived in countries other than the country in which you 
are located, and may be treated in accordance with the laws and regulations of 
the country of each individual included in the entire chain.

Copyright 2014 The Royal Bank of Scotland plc. All rights reserved. See 
http://www.natwestmarkets.com/legal/s-t-discl.html for further risk disclosure.

******************************************************************