[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] Conflict graph issue
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] Conflict graph issue |
Date: |
Fri, 08 Nov 2013 04:01:40 +0400 |
> 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).
>
>From your printout it follows that no binary variable is included in the
conflict graph (since all G.neg and G.pos are zero); therefore, G.nv,
the number of vertices in CG, also should be zero. In this case any call
to cfg_get_adjacent would cause an error, because on entry it checks
that 1 <= v && v <= nv. Most likely you inspect CG at some wrong point,
i.e. before it has been completely built.
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: [Bug-glpk] Conflict graph issue,
Andrew Makhorin <=