Exploiting user-supplied Decompositions inside Heuristics

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.