Exploiting user-supplied Decompositions inside Heuristics

Katrin Halbig (), Adrian Göß () and Dieter Weninger ()
Additional contact information
Katrin Halbig: Friedrich-Alexander-Universität Erlangen-Nürnberg, Department of Data Science
Adrian Göß: University of Technology Nuremberg (UTN), Analytics & Optimization Lab
Dieter Weninger: Friedrich-Alexander-Universität Erlangen-Nürnberg, Department of Data Science

Journal of Heuristics, 2025, vol. 31, issue 4, No 5, 38 pages

Abstract: Abstract Numerous industrial fields, like supply chain management, face mixed-integer optimization problems on a regular basis. Such problems typically show a sparse structure and vary in size, as well as complexity. However, in order to satisfy customer demands, it is crucial to find good solutions to all such problems quickly. Current research often focuses on the development of a tailored approach for one specific problem class with a common structure. Information supplied by everyday users is usually overlooked, but may result in a decomposition with weakly connected blocks due to the structural sparsity. Hence, we present three heuristics to exploit decomposition information and analyze their value based on the type of decomposition. In particular, we newly introduce the heuristic Dynamic Partition Search, enhance the Penalty Alternating Direction Method published earlier in a basic form, and extend a framework from literature to Decomposition Kernel Search. All heuristics are implemented in the non-commercial solver SCIP. We examine their performance in a comprehensive computational study across three different test sets. The computational results indicate that knowledge about relevant decomposition information can boost the solution process of mixed-integer optimization problems.

Keywords: Mixed-integer programming; Heuristic; Decomposition; Optimization solver; Supply chain management; 90C11; 90C59; 90C90; 90B06 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09572-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:4:d:10.1007_s10732-025-09572-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09572-3

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().