Transformation of Combinatorial Optimization Problems Written in Extended SQL into Constraint Problems
Transformation of Combinatorial Optimization Problems Written in Extended SQL into Constraint Problems
复制标题
用扩展SQL编写的组合优化问题转化为约束问题
DOI：
10.1145/3236950.3236963
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sakai Masahiko
中科院分区：
文献类型：
--
作者：
Sakanashi Genki;Sakai Masahiko
组合优化是一个重要领域，它为各种问题提供了最佳解决方案之一。本文重点介绍 SQL 风格的声明性语言，以简化描述组合优化问题，并提供由最先进的 CP/SMT 求解器支持的解决方法。从语义的角度来看，组合问题的搜索空间被给出为有限关系集。搜索空间中的关系通过问题的约束进行过滤，类似于函数语言中列表上的过滤函数，得到的关系就是问题的解。根据这个概念，我们通过引入一些对关系集的操作来扩展结构化查询语言（SQL）：生成一组关系，根据约束过滤一组关系，以及选择相对于目标函数的最佳关系之一。为了实现有效的实现，一组关系被表示为一对包含具有有限域的变量和变量约束的关系。这使我们能够通过 CP/SMT 求解器求解目标问题。我们还给出了图顶点着色优化问题的实验结果。
The combinatorial optimization is an important area, which gives one of the best solutions for various problems. This paper focuses on an SQL style of declarative languages to ease describing combinatorial optimization problems, and provides their solution method powered by state-of-the-art CP/SMT solvers. From the semantic point of view, the search space of a combinatorial problem is given as a finite set of relations. Relations in the search space are filtered by constraints of the problem in similar to the filter-function on lists in functional languages, and the resulted relations are solutions of the problem. According to this notion, we extended Structured Query Language (SQL) by introducing some operations on sets of relations: generating a set of relations, filtering a set of relations according to constraints, and selecting one of the optimum relations with respect to a goal function. Toward an effective implementation, a set of relations is represented as a pair of a relation containing variables with finite domains and constraints on variables. This enables us to solve the target problem by CP/SMT solvers. We also give an experimental result on the graph vertex coloring optimization problem.