Search Results

Documents authored by Mallach, Sven

Document
DOI: 10.4230/OASIcs.ATMOS.2025.8
Refined Integer Programs and Polyhedral Results for the Target Visitation Problem

Authors: Sven Mallach

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
The Target Visitation Problem (TVP) combines the Traveling Salesman Problem and the Linear Ordering Problem, and thus serves as a natural model for route planning applications where both the travel costs and the order of the sites to visit matter. More precisely, in addition to the costs that apply for the selected links connecting two subsequently visited sites, the relative urgency of visiting one site before another is quantified and taken into account. In this article, we present refined integer linear programming formulations for the TVP, along with clarifications and extensions regarding the description of the polytopes associated with their feasible solution sets by a minimal set of linear equations and facet-defining inequalities. The practical effectiveness of exploiting the proposed improvements by means of a branch-and-cut algorithm is demonstrated in a computational study. In addition, we report the optimal values for some previously unsolved instances.
Cite as

Sven Mallach. Refined Integer Programs and Polyhedral Results for the Target Visitation Problem. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mallach:OASIcs.ATMOS.2025.8,
  author =	{Mallach, Sven},
  title =	{{Refined Integer Programs and Polyhedral Results for the Target Visitation Problem}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{8:1--8:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.8},
  URN =		{urn:nbn:de:0030-drops-247647},
  doi =		{10.4230/OASIcs.ATMOS.2025.8},
  annote =	{Keywords: Route planning, Transportation, Logistics, Traveling salesman problem, Linear ordering problem, Polyhedral Combinatorics, Branch-and-cut, Integer Programming, Linear programming}
}
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},
  URN =		{urn:nbn:de:0030-drops-192520},
  doi =		{10.4230/LITES-v002-i001-a002},
  annote =	{Keywords: Compiler optimization, Application-specific processors, Address code generation, Offset assignment, Integer programming}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact