Transformation of Combinatorial Optimization Problems Written in Extended SQL into Constraint Problems
Sakanashi Genki, Masahiko Sakai · 2018
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.