Detecting Semantic Groups in MIP Models
Detecting Semantic Groups in MIP Models
复制标题
检测 MIP 模型中的语义组
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Domenico Salvagnin
中科院分区：
文献类型：
--
作者：
Domenico Salvagnin
目前最先进的MIP技术缺乏一个强大的建模语言的基础上的全球约束，一个工具，长期以来一直是标准的约束编程。一般来说，即使是关于变量和约束的基本语义信息也对底层求解器隐藏。例如，在具有不可拆分流的网络设计模型中，路由和弧容量变量都可以是二进制的，并且求解器将无法通过单独查看类型来区分两组语义不同的变量。如果可用，这种语义划分可以由求解器的不同部分使用，primis中的语义学，以提高整体性能。在本文中，我们将描述几个启发式程序，所有的分区细化的概念的基础上，自动恢复语义变量（和约束）组从一个平面MIP模型。计算实验上的异构测试床的模型，其原始的高级别划分是已知的先验，表明所提出的方法是相当有效的。
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.