bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Andrew Makhorin
Subject: [Bug-glpk] [Fwd: MIP solver bug]
Date: Fri, 06 Jan 2017 14:57:05 +0300

-------- Forwarded Message --------
From: address@hidden
To: address@hidden, address@hidden
Cc: 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.
******************************************************************

Attachment: mip.txt
Description: mip.txt


reply via email to

[Prev in Thread] Current Thread [Next in Thread]