Hello Emma, if you use an unreasonably high M you will get rounding errors.
The Big M method does not imply using as high a value as possible. To the contrary you should use the smallest M that does not restrict the solution. In your example: Use M = 1 for the rows constraining y. And M = 0.0005 for the rows constraining x. Best regards Heinrich Schuchardt On 01/06/2017 12:57 PM, Andrew Makhorin wrote: > -------- Forwarded Message -------- > To: [email protected], [email protected] > Subject: MIP solver bug > Date: Fri, 6 Jan 2017 11:25:23 +0000 > > Hi GLPK team, > > > > I found some issue when I use MIP solver to solve the following big M > problem: > > =================================================== > > Minimise -x - y > > > > s.t. > > > > 0 < x + 2y < 1 > > -1 < x + y < 1 > > > > x - M a < 0 > > x + M a > 0 > > y - M b < 0 > > y + M b > 0 > > a + b = 1 > > > > 0 < x < 0.0005 > > 0 < y < 1 > > > > · a, b are binary variables. > > · M is a large constant, says, 1e16 > > ======================================================= > > > > The solver gives optimal solution: > > > > x = 0.0005 > > y = 0.49975 > > a = 0 > > b = 1 > > > > which is contradictory to the constraint > > x - M a <= 0 > > > > It only happens once x is in a small range, such as [0, 0.0005]. > > > > I also notice that some constraint have been remove from output from > solver: > > =================================================================== > > Writing problem data to 'c:\temp\mip.txt'... > > 27 lines were written > > GLPK Integer Optimizer, v4.55 > > 7 rows, 4 columns, 14 non-zeros > > 2 integer variables, all of which are binary > > Preprocessing... > > 1 constraint coefficient(s) were reduced > > 5 rows, 4 columns, 10 non-zeros > > 2 integer variables, all of which are binary > > Scaling... > > A: min|aij| = 1.000e+000 max|aij| = 1.000e+016 ratio = 1.000e+016 > > GM: min|aij| = 9.640e-003 max|aij| = 1.037e+002 ratio = 1.076e+004 > > EQ: min|aij| = 9.299e-005 max|aij| = 1.000e+000 ratio = 1.075e+004 > > 2N: min|aij| = 6.104e-005 max|aij| = 1.110e+000 ratio = 1.819e+004 > > Constructing initial basis... > > Size of triangular part is 5 > > Solving LP relaxation... > > GLPK Simplex Optimizer, v4.55 > > 5 rows, 4 columns, 10 non-zeros > > * 0: obj = 0.000000000e+000 infeas = 0.000e+000 (0) > > * 2: obj = -5.002500000e-001 infeas = 5.821e-014 (0) > > OPTIMAL LP SOLUTION FOUND > > Integer optimization begins... > > + 2: mip = not found yet >= -inf (1; 0) > > + 2: >>>>> -5.002500000e-001 >= -5.002500000e-001 0.0% (1; 0) > > + 2: mip = -5.002500000e-001 >= tree is empty 0.0% (0; 1) > > INTEGER OPTIMAL SOLUTION FOUND > > ===================================================================== > > > > I suspect that the constraint > > x - M a < 0 > > has been removed, whilst we need that constraint to select one of x and > y. > > > > Is anyway to avoid the logic of removing constraints? > > > > > > Many thanks, > > Emma > > > > > > Dong Mei (Emma) Wang > Quantitative Analyst > Markets > RBS > 135 Bishopsgate, London, EC2M 3UR, GB > Office: +44 20 7638 7590 | Mobile: +44 7584403047 > > > > > > > ****************************************************************** > 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 > _______________________________________________ Bug-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/bug-glpk
