This pages is dedicated to our arXiv 2024 preprint “A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem”.
S. Haller, B. Savchynskyy
“A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem”
arXiv 2408.02086 Preprint 2024 [PDF]
BibTeX entry:
@misc{haller2024mwis,
title={A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem},
author={Stefan Haller and Bogdan Savchynskyy},
year={2024},
eprint={2408.02086},
archivePrefix={arXiv},
primaryClass={math.OC},
url={https://arxiv.org/abs/2408.02086},
}
Our solver uses a simple JSON graph format:
{
"nodes": [10.0, 20.0, 30.0], /* Costs for each node */
"cliques": [[0, 1, 3]], /* Array of cliques (indices into nodes array) */
}
(The above example shows a fully connected graph of three nodes.)
Download JSON model files: mwis2024_json.tar.zst (112 MiB, SHA256: 00406a5d0d5a9403ff5feddfa9d4751738d66c0799a455b19860baf99a7fc0da)
For the specification of the metis format refer to the Metis Software Package Manual. However, note that only the edge graph representation is supported, i.e., the edges for all cliques are enumerated in its entirety.
Download Metis model files: mwis2024_metis.tar.zst (2.2 GiB, SHA256: 2ae0b875326948858cc9e293b2f2635bf6f92b610e6cf02671cce01490246472)
In the paper we subdivide the large and relatively diverse collection of AVR datasets into three groups (LARGE, MEDIUM and SMALL). The groups are selected based on the number of nodes in the problem instances. More information are presented in the paper.
{
"AVR-LARGE": [
"AVR_000",
"AVR_001",
"AVR_002",
"AVR_003",
"AVR_004",
"AVR_005",
"AVR_006",
"AVR_007",
"AVR_008",
"AVR_009",
"AVR_010",
"AVR_011",
"AVR_012",
"AVR_013",
"AVR_014",
"AVR_015",
"AVR_016"
],
"AVR-MEDIUM": [
"AVR_017",
"AVR_018",
"AVR_020",
"AVR_021",
"AVR_022",
"AVR_023",
"AVR_025",
"AVR_026",
"AVR_028",
"AVR_029",
"AVR_031",
"AVR_032",
"AVR_033",
"AVR_035",
"AVR_036",
"AVR_037"
],
"AVR-SMALL": [
"AVR_019",
"AVR_024",
"AVR_027",
"AVR_030",
"AVR_034"
],
"MSCD": [
"MSCD_000",
"MSCD_001",
"MSCD_002",
"MSCD_003",
"MSCD_004",
"MSCD_005",
"MSCD_006",
"MSCD_007",
"MSCD_008",
"MSCD_009",
"MSCD_010",
"MSCD_011",
"MSCD_012",
"MSCD_013",
"MSCD_014",
"MSCD_015",
"MSCD_016",
"MSCD_017",
"MSCD_018",
"MSCD_019",
"MSCD_020"
]
}
The AVR problem instances have been original obtained from the Amazon MWIS VR Dataset page. The problem instances have been used as is. We converted the text file representation into our JSON clique graph format as well as into the Metis edge graph format.
{
"AVR_000": "CR-S-L-1",
"AVR_001": "CR-S-L-2",
"AVR_002": "CR-S-L-4",
"AVR_003": "CR-S-L-6",
"AVR_004": "CR-S-L-7",
"AVR_005": "CR-T-C-1",
"AVR_006": "CR-T-C-2",
"AVR_007": "CR-T-D-4",
"AVR_008": "CR-T-D-6",
"AVR_009": "CR-T-D-7",
"AVR_010": "CW-S-L-1",
"AVR_011": "CW-S-L-2",
"AVR_012": "CW-S-L-4",
"AVR_013": "CW-S-L-6",
"AVR_014": "CW-S-L-7",
"AVR_015": "CW-T-C-1",
"AVR_016": "CW-T-C-2",
"AVR_017": "CW-T-D-4",
"AVR_018": "CW-T-D-6",
"AVR_019": "MR-D-01",
"AVR_020": "MR-D-03",
"AVR_021": "MR-D-05",
"AVR_022": "MR-D-FN",
"AVR_023": "MR-W-FN",
"AVR_024": "MT-D-01",
"AVR_025": "MT-D-200",
"AVR_026": "MT-D-FN",
"AVR_027": "MT-W-01",
"AVR_028": "MT-W-200",
"AVR_029": "MT-W-FN",
"AVR_030": "MW-D-01",
"AVR_031": "MW-D-20",
"AVR_032": "MW-D-40",
"AVR_033": "MW-D-FN",
"AVR_034": "MW-W-01",
"AVR_035": "MW-W-05",
"AVR_036": "MW-W-10",
"AVR_037": "MW-W-FN"
}
Download source code used in the paper: mwis2024_code.tar.zst (488K, SHA256: 36c73f09ba101abce8bd96bd504e1063f332fe6ebc6f3f0a2d7a50fb04b84d30)
Note that for we distribute the code for each variant mentioned in the paper in separate subdirectories.
Download raw log files: mwis2024_logs.tar.zst (12.2 GiB, SHA256: cd932adfe8b97b81246a342237373e0639238fb5c054be2ca9a0393cb33b544b)
Download compiled benchmark results: mwis2024_benchmark.json.zst (60 MiB, SHA256: b5bd5200771c52fe60fe9577023b80380a2a8534a1f0094ad49110defc55f8a4)
Format: For each solver run we store the tuples [$iteration, $time, $upper_bound, $lower_bound] in a JSON array.