zbMATH — the first resource for mathematics

Detecting semantic groups in MIP models. (English) Zbl 06598675
Quimper, Claude-Guy (ed.), Integration of AI and OR techniques in constraint programming. 13th international conference, CPAIOR 2016, Banff, AB, Canada, May 29 – June 1, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-33953-5/pbk; 978-3-319-33954-2/ebook). Lecture Notes in Computer Science 9676, 329-341 (2016).
Summary: Current state-of-the-art MIP technology lacks a powerful modeling language based on global constraints, a tool which has long been standard in constraint programming. In general, even basic semantic information about variables and constraints is hidden from the underlying solver. For example, in a network design model with unsplittable flows, both routing and arc capacity variables could be binary, and the solver would not be able to distinguish between the two semantically different groups of variables by looking at type alone. If available, such semantic partitioning could be used by different parts of the solver, heuristics in primis, to improve overall performance. In the present paper we will describe several heuristic procedures, all based on the concept of partition refinement, to automatically recover semantic variable (and constraint) groups from a flat MIP model. Computational experiments on a heterogeneous testbed of models, whose original higher-level partition is known a priori, show that one of the proposed methods is quite effective.
For the entire collection see [Zbl 1337.68017].
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI