Hi Sebastian,> I think the crucial point is that node4 isn't aware of its own > restriction (after the first R2 reduction). > If you normalize the new matrix (shifting costs in the adjacent vector > until each row/column has minima 0) after a R2 reduction of a node with > infinite spill cost the problem should disappear.<snip>> Did you consider this option?We did. The success of normalization in this case depends on whether you attempt to normalize rows first, then columns, or the other way around. Currently rows are normalized first, then columns. In your example the infinite costs are thus propagated onto element 1 of node 0, rather than node 4, which leaves us where we started. Switching the normalization order would fix this example, but not the general issue. Bernhard and I devised a stronger normalization scheme for matrices containing infinities which would fix this problem in the one-register (two option) case. For problems with two or more registers however normalization will not help us, and even R1 can be dangerous*, hence our current approach: Do not apply R1 or R2 to a node with infinite costs unless you can prove it's colorable. Cheers, Lang. *I've got an example around here somewhere. It's more involved, but I can dig it up if you'd like.
Lang Hames wrote:> Hi Sebastian, > > > We did. The success of normalization in this case depends on whether > you attempt to normalize rows first, then columns, or the other way > around. > > Currently rows are normalized first, then columns. In your example the > infinite costs are thus propagated onto element 1 of node 0, rather > than node 4, which leaves us where we started. > > Switching the normalization order would fix this example, but not the > general issue. >You can consider infinite vector options and ignore the corresponding rows/columns during normalization. This would fix the ordering problem for infinite options: After the normalization of the rows: node0 [ label="0: [ 1.875000e-02, inf ]" ] node4 [ label="4: [ 5.357143e-02, 0]" ] node0 -- node4 [ label="[ 0, inf ]\n[0, 0 ]\n" ] After the normalization of the columns: node0 [ label="0: [ 1.875000e-02, inf ]" ] node4 [ label="4: [ 5.357143e-02, inf]" ] node0 -- node4 [ label="[ 0, 0 ]\n[0, 0 ]\n" ] (consider second row as deleted)> Bernhard and I devised a stronger normalization scheme for matrices > containing infinities which would fix this problem in the one-register > (two option) case.Is that the one described above?> For problems with two or more registers however > normalization will not help us, and even R1 can be dangerous*, hence > our current approach: Do not apply R1 or R2 to a node with infinite > costs unless you can prove it's colorable. > > Cheers, > Lang. > > *I've got an example around here somewhere. It's more involved, but I > can dig it up if you'd like. >Yes, please. Best regards, Sebastian
>> Bernhard and I devised a stronger normalization scheme... > Is that the one described above?Yes.>> *I've got an example around here somewhere. It's more involved, but I >> can dig it up if you'd like. >> > Yes, please.Ahh it looks like my example was wrong. You're quite right - with the stronger normalization scheme R1 and R2 should be safe for all nodes. I'll update the PBQP solver to reflect this. - Lang.