Exploiting user-supplied Decompositions inside Heuristics

Many mixed-integer models are sparse and can, therefore, usually be decomposed into weakly connected blocks. Such decompositions could be determined algorithmically or be specified by the user. We limit ourselves to the later, as the user usually has a very precise idea of which decomposition makes sense for structural reasons. In the present work, we address the exploitation of user-supplied decompositions within the non-commercial solver SCIP to control heuristics. In order to demonstrate the potential, three different heuristics leveraging such decomposition information are considered. Our results show that such an approach has a positive influence on the overall solution behavior of SCIP, provided that the decomposition information supplied describes the basic structural properties of the model appropriately for the particular heuristic.


Halbig, K., Göß, A., & Weninger, D.. (2023). Exploiting user-supplied Decompositions inside Heuristics.



View Exploiting user-supplied Decompositions inside Heuristics