
Generalized Matching Code
A commandline tool for solving generalized matching problems (a.k.a. bmatchings, or degreeconstrained subgraphs) is available here. The archive contains binaries for Linux and MacOSX. There is also a precompiled MEX interface for Matlab. To get started follow these instructions. There's a README with more details if you have questions, or if things do not work as expected.

Usage> bmatch [arg1 value] [arg2 value] ... Solves: optimize_Yij sum_ij W_ij Y_ij s.t. l_i <= sum_j Y_ij <= u_i, 1 <= i <= n and Wij and Yij are symmetric Arguments [with default values]: w weights [NULL] input file, NULL => std. input d degrees [NULL] input file, NULL => std. input o output [NULL] output file, NULL => std. output l const_l [1 ] positive integer, negative => std. input u const_u [1 ] positive integer, negative => std. input s sparse [0 ] 0 => matrix, 1 => IJW input format m method [1 ] selects algorithm v verbose [0 ] positive integer Algorithm: 1. exact maxwgt solution using goblin via subgraph complement 2. exact mincost solution using goblin 3. greedy 1/2 approximation to maxwgt solution 4. greedy 1/2 approximation to maxwgt solution with recursion 5. bipartite relaxation to maxwgt solution using belief propagation Notes: Selfloops are handled: a selfloop increases the degree of a node by 2. Weights must be positive (Wij >= 0). Edges with zeroweight (Wij==0) are not allowed to partake in the matching. If the weights, degrees or output file is not specified, then the corresponding input [output] data is entered in [written to] the display. The format should match the examples given in the data directory. Enter a blank line to terminate input of a given data. The output weight is calculated as sum_{i<=j} Wij Yij, except when beleif propagation is used, whose output is not necessarily symmetric. For BP, the output weight is 0.5 * sum_{i,j} Wij Yij. The lower bounds are ignored by methods 35. Bipartite relaxation assumes that the degree upper bounds can be met with equality. For Known Issues and Troubleshooting tips, see the full README.
> bmatch INPUT WEIGHTS(dense)> 1 2 2 3 INPUT DEGREES> 1 MATCHING> 0 1 1 0
> bmatch w data/matrix_in_1.txt v 1 u 2 bmatch_ijw> returning 2 edges MATCHING> 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 bmatch done: method = exact maxwgt solution using goblin via subgraph complement in # nodes = 4 in # edges = 6 out # edges = 4 wgt = 28 time (sec.) = 0
> bmatch w data/matrix_in_2.txt v 1 u 3 bmatch_ijw> returning 4 edges MATCHING> 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 bmatch done: method = exact maxwgt solution using goblin via subgraph complement in # nodes = 4 in # edges = 10 out # edges = 6 wgt = 35 time (sec.) = 0
> bmatch w data/matrix_in_2.txt v 1 u 3 m 3 bmatch_ijw> returning 5 edges MATCHING> 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 bmatch done: method = greedy 1/2 approximation to maxwgt solution in # nodes = 4 in # edges = 10 out # edges = 5 wgt = 29 time (sec.) = 0 > bmatch w data/matrix_in_2.txt u 2 v 1 m 5 beliefprop.solve> Reached maximum iterations without converging MATCHING> 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 bmatch done: method = bipartite relaxation to maxwgt solution using belief propagation in # nodes = 4 in # edges = 16 out # edges = 8 wgt = 28.5 time (sec.) = 0
> bmatch w data/ijw_in_3.txt u 17 s 1 v 1 m 1 bmatch_ijw> returning 306 edges MATCHING> 0 1 1 0 3 1 0 6 1 0 7 1 . . . . . . . . . 30 30 1 30 31 1 30 32 1 31 31 1 bmatch done: method = exact solution using goblin mincost solver via subgraph complement in # nodes = 34 in # edges = 595 out # edges = 289 wgt = 22.47 time (sec.) = 3 > bmatch w data/ijw_in_3.txt o data/ijw_out_3.txt u 17 s 1 v 1 m 3 bmatch_ijw> returning 284 edges bmatch done: method = greedy 1/2 approximation to maxwgt solution in # nodes = 34 in # edges = 595 out # edges = 284 wgt = 11.57 time (sec.) = 1 > bmatch w data/ijw_in_3.txt o data/ijw_out_3.txt u 17 s 1 v 1 m 4 bmatch done: method = greedy 1/2 approximation to maxwgt solution with recursion in # nodes = 34 in # edges = 595 out # edges = 287 wgt = 11.59 time (sec.) = 0
> bmatch w data/ijw_in_5.txt d data/degree_in_5.txt o data/ijw_out_5.txt s 1 v 1 m 1 bmatch_ijw> returning 2123 edges bmatch done: method = exact solution using goblin mincost solver via subgraph complement in # nodes = 200 in # edges = 4463 out # edges = 2340 wgt = 1.384e+04 time (sec.) = 182 > bmatch w data/ijw_in_5.txt d data/degree_in_5.txt o data/ijw_out_5.txt s 1 v 1 m 3 bmatch_ijw> returning 1504 edges bmatch done: method = greedy 1/2 approximation to maxwgt solution in # nodes = 200 in # edges = 4463 out # edges = 1504 wgt = 8892 time (sec.) = 0 > bmatch w data/ijw_in_5.txt d data/degree_in_5.txt o data/ijw_out_5.txt s 1 v 1 m 4 bmatch_ijw> returning 1504 edges bmatch_ijw> returning 375 edges bmatch_ijw> returning 132 edges bmatch_ijw> returning 50 edges bmatch_ijw> returning 27 edges bmatch_ijw> returning 5 edges bmatch_ijw> returning 0 edges bmatch done: method = greedy 1/2 approximation to maxwgt solution with recursion in # nodes = 200 in # edges = 4463 out # edges = 2093 wgt = 1.23e+04 time (sec.) = 1
> bmatch v 1 INPUT WEIGHTS(dense)> 0 2.5 1 2.5 0 1 1 1 0 INPUT DEGREES> 1 1 2 bmatch> solving problem ... bmatch_ijw> returning 2 edges MATCHING> 0 1 0 1 0 0 0 0 0 bmatch done: method = exact solution using goblin mincost solver via subgraph complement in # nodes = 3 in # edges = 3 out # edges = 1 wgt = 2.5 time (sec.) = 13 > bmatch v 1 INPUT WEIGHTS(dense)> 0 3.5 2 3.5 0 2 2 2 0 INPUT DEGREES> 1 1 2 bmatch> solving problem ... bmatch_ijw> returning 1 edges MATCHING> 0 0 1 0 0 1 1 1 0 bmatch done: method = exact solution using goblin mincost solver via subgraph complement in # nodes = 3 in # edges = 3 out # edges = 2 wgt = 4 time (sec.) = 14
> bmatch m 2 v 1 INPUT WEIGHTS(dense)> 0 2.5 1 2.5 0 1 1 1 0 INPUT DEGREES> 1 2 1 2 0 2 bmatch> solving problem ... bmatch_ijw> returning 2 edges MATCHING> 0 0 1 0 0 1 1 1 0 bmatch done: method = exact mincost solution using goblin in # nodes = 3 in # edges = 3 out # edges = 2 wgt = 2 time (sec.) = 15 > bmatch m 2 v 1 INPUT WEIGHTS(dense)> 0 3.5 2 3.5 0 2 2 2 0 INPUT DEGREES> 1 2 1 2 0 2 bmatch> solving problem ... bmatch_ijw> returning 1 edges MATCHING> 0 1 0 1 0 0 0 0 0 bmatch done: method = exact mincost solution using goblin in # nodes = 3 in # edges = 3 out # edges = 1 wgt = 3.5 time (sec.) = 21
Many thanks to Vlad Shchogolev, Bert Huang and Blake Shaw for their code and examples. Blake has helped to improve the robustness of the code. Vlad implemented prototypes. This tool integrates Bert's BP code directly. For a standalone BP implementation, please visit Bert's page.
This tool links to the impressive Goblin Graph Library and LGPL licensing issues apply. To experiment with this library, please download the source code directly from the Goblin site. I would be happy to share the source that has been modified slightly for Mac OS X.