[Bug-glpk] [Fwd: Conflict graph issue]

[Andrew Makhorin]

-------- Forwarded Message --------
From: Jose L Walteros <address@hidden>
Reply-to: address@hidden
To: address@hidden
Subject: Conflict graph issue
Date: Thu, 7 Nov 2013 16:00:48 -0500

Dear developers,


I have been playing for a while with the conflict graph (CG) library
"cfg.h" and I think I found a minor detail that can possibly be
improved. I was extracting the CG of the instance gt2.mps (attached
file) from the MIPLIB3.0 library,


The conflict graph of this instance is empty, meaning that the only
edges correspond to the trivial conflicts, i.e, (x_i=1,x_i=0). Before
running the code, I didn't know that the CG was empty, otherwise I
wouldn't have done it. 


this instance has 188 integer variables, 24 which are binary. I found
that glpk generated 24 vertices as well as the following info.


 
        G.ref
       G.neg
       G.pos
[1]
                33
                 0
                 0
[2]
                34
                 0
                 0
[3]
                35
                 0
                 0
[4]
                36
                 0
                 0
[5]
                37
                 0
                 0
[6]
                38
                 0
                 0
[7]
                39
                 0
                 0
[8]
                40
                 0
                 0
[9]
                41
                 0
                 0
[10]
                42
                 0
                 0
[11]
                43
                 0
                 0
[12]
                44
                 0
                 0
[13]
               100
                 0
                 0
[14]
               108
                 0
                 0
[15]
               116
                 0
                 0
[16]
               124
                 0
                 0
[17]
               132
                 0
                 0
[18]
               140
                 0
                 0
[19]
               148
                 0
                 0
[20]
               156
                 0
                 0
[21]
               164
                 0
                 0
[22]
               172
                 0
                 0
[23]
               180
                 0
                 0
[24]
               188
                 0
                 0
 
This makes sense because the CG is empty. However, something that was
strange to me is that, when I was extracting the adjacency lists of the
vertices (using degree = cfg_get_adjacent(G, i, adj);  ), degree was =
11 and the adj array was not empty. 


I think in this case degree should be equal to 1 and adj  a singleton
[0] (taking into account that glpk vectors start at 1).


I know that this is minor, but you may find it useful.


Thanks.

----------------------------------------------------
Jose L. Walteros 
Ph.D. Student
Dept. of Industrial & Systems Engineering
401 Weil Hall
University of Florida 
Gainesville, FL 32611-6595, USA
Phone: 352-214-2533
Email: address@hidden

gt2.mps
Description: Binary data