-------- Forwarded Message -------- From: [email protected] To: [email protected] Cc: [email protected], [email protected], [email protected], [email protected] 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:[email protected]] 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. ****************************************************************** _______________________________________________ Bug-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/bug-glpk
