DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2019.63

Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

Authors: Michael Jünger and Sven Mallach

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract

Solving the NP-hard Maximum Cut or Binary Quadratic Optimization Problem to optimality is important in many applications including Physics, Chemistry, Neuroscience, and Circuit Layout. The leading approaches based on linear/semidefinite programming require the separation of so-called odd-cycle inequalities for solving relaxations within their associated branch-and-cut frameworks. In their groundbreaking work, F. Barahona and A.R. Mahjoub have given an informal description of a polynomial-time separation procedure for the odd-cycle inequalities. Since then, the odd-cycle separation problem has broadly been considered solved. However, as we reveal, a straightforward implementation is likely to generate inequalities that are not facet-defining and have further undesired properties. Here, we present a more detailed analysis, along with enhancements to overcome the associated issues efficiently. In a corresponding experimental study, it turns out that these are worthwhile, and may speed up the solution process significantly.

Cite as

Michael Jünger and Sven Mallach. Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:LIPIcs.ESA.2019.63,
  author =	{J\"{u}nger, Michael and Mallach, Sven},
  title =	{{Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{63:1--63:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.63},
  URN =		{urn:nbn:de:0030-drops-111840},
  doi =		{10.4230/LIPIcs.ESA.2019.63},
  annote =	{Keywords: Maximum cut, Binary quadratic optimization, Integer linear programming}
}

Document

DOI: 10.4230/LITES-v002-i001-a002

More General Optimal Offset Assignment

Authors: Sven Mallach

Published in: LITES, Volume 2, Issue 1 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 1

Abstract

This manuscript presents exact approaches to the general offset assignment problem arising in the address code generation phase of compilers for application-specific processors. First, integer programming models for architecture-dependent and theoretically motivated special cases of the problem are established. Then, these models are extended to provide the first widely applicable formulations for the most general problem setting, supporting processors with several address registers and complex addressing capabilities. Existing heuristics are similarly extended and practical applicability of the proposed methods is demonstrated by experimental evaluation using an established and large benchmark set. The experiments allow us to study the impact of exploiting more complex memory addressing capabilities on the address computation costs of real-world programs. We also show how to integrate operand reordering techniques for commutative instructions into existing solution approaches.

Cite as

Sven Mallach. More General Optimal Offset Assignment. In LITES, Volume 2, Issue 1 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 1, pp. 02:1-02:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{mallach:LITES-v002-i001-a002,
  author =	{Mallach, Sven},
  title =	{{More General Optimal Offset Assignment}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:18},
  ISSN =	{2199-2002},
  year =	{2015},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v002-i001-a002},
  doi =		{10.4230/LITES-v002-i001-a002},
  annote =	{Keywords: Compiler optimization, Application-specific processors, Address code generation, Offset assignment, Integer programming}
}

Search Results

Documents authored by Mallach, Sven

Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

Abstract

Cite as

More General Optimal Offset Assignment

Abstract

Cite as

Thanks for your feedback!

Could not send message