Instance Submission and Solution Server for
Maximum Cut and Binary Quadratic Optimization Problems
This page offers a service to solve Maximum Cut and unconstrained Binary Quadratic Optimization problems using the exact method McSparse. It is run jointly by Jonas Charfreitag, Michael Jünger, Sven Mallach, and Petra Mutzel.
Instances can be uploaded using the interface below. If a submitted instance is valid and of reasonable size, and if you provide a valid email-address, the instance will be passed to our solvers and either an optimal solution or, if a time limit is exceeded, intermediate results will be sent to the address specified. The format of the results files is described here. Please note that this service comes without any guarantee or warranty. If you have questions, please contact mcsparse [ at ] uni-bonn.de.
Submit your instance ...
Each instance has to be either an .mc or a .bq file as defined here.
A new instance library (prototype) currently under development can be accessed here here. Moreover, a collection of example instances (zip archive, 5.1 MB, mostly corresponding to the BiqMacLibrary) can be downloaded here.
For submission, such files can also be bundled into the top-level (no directories) of a tar.gz or zip archive.
By submitting an instance, you express your consent that it may be freely used by the project members, and you confirm that you use this service solely for non-profit scientific or private intent.
If you use our service in connection with a scientific publication, please include the following BibTeX citation:
@inproceedings{CJMM22,
author = {Jonas Charfreitag and Michael J{\"u}nger and Sven Mallach and Petra Mutzel},
title = {{M}c{S}parse: {E}xact Solutions of Sparse Maximum Cut and Sparse Unconstrained Binary Quadratic Optimization Problems},
editor = {Cynthia A. Phillips and Bettina Speckmann},
booktitle = {2022 Proceedings of the Symposium on Algorithm Engineering and Experiments ({ALENEX})},
year = {2022},
pages = {54--66},
doi = {10.1137/1.9781611977042.5}
}
For Spin Glass instances, please consider using the Spin Glass Server. Besides using our services, especially for dense problems, we strongly recommend our partner project BiqMac, run by Franz Rendl, Giovanni Rinaldi, and Angelika Wiegele, as well as the further solvers BiqBin and BiqCrunch.
This work is supported by the transdisciplinary research network "TRA 1 Modelling" at the University of Bonn as part of the Excellence Strategy of the federal and state governments, and by the Hausdorff Center for Mathematics (HCM) funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy EXC-2047/1 390685813. In particular, we are grateful to the HCM for financing compute infrastructure employed to provide the McSparse service to the scientific community.