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

[Heinrich Schuchardt]

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: address@hidden, address@hidden
> 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
> address@hidden
> https://lists.gnu.org/mailman/listinfo/bug-glpk
>