From Streamlined Combinatorial Search to Efficient Constructive Procedures

Authors

  • Ronan Le Bras Cornell University
  • Carla Gomes Cornell University
  • Bart Selman Cornell University

DOI:

https://doi.org/10.1609/aaai.v26i1.8147

Keywords:

Combinatorial Search, Streamlining, Constraint Satisfaction, Human Computation, Constructive Procedures, Spatially Balanced Latin Squares, Schur Numbers

Abstract

In recent years, significant progress in the area of search, constraint satisfaction, and automated reasoning has been driven in part by the study of challenge problems from combinatorics and finite algebra. This work has led to the discovery of interesting discrete structures with intricate mathematical properties. While some of those results have resolved open questions and conjectures, a shortcoming is that they generally do not provide further mathematical insights, from which one could derive more general observations. We propose an approach that integrates specialized combinatorial search, using so-called streamlining, with a human computation component. We use this approach to discover efficient constructive procedures for generating certain classes of combinatorial objects of any size. More specifically, using our framework, we discovered two complementary efficient constructions for generating so-called Spatially Balanced Latin squares (SBLS) of any order N, such that 2N+1 is prime. Previously constructions for SBLSs were not known. Our approach also enabled us to derive a new lower bound for so-called weak Schur numbers, improving on a series of earlier results for Schur numbers.

Downloads

Published

2021-09-20

How to Cite

Le Bras, R., Gomes, C., & Selman, B. (2021). From Streamlined Combinatorial Search to Efficient Constructive Procedures. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 499-506. https://doi.org/10.1609/aaai.v26i1.8147

Issue

Section

Constraints, Satisfiability, and Search