---
title: "A Divide-and-Conquer Approach for Solving Interval Algebra Networks"
authors:
  - "Jason Jingshi Li"
  - "Jinbo Huang"
  - "Jochen Renz"
doi: ""
url: "https://ijcai.org/proceedings/2009/101"
pdf: "https://ijcai.org/proceedings/2009/0101.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "572-576"
track: ""
keywords:
---

# A Divide-and-Conquer Approach for Solving Interval Algebra Networks

Jason Jingshi Li, Jinbo Huang, Jochen Renz

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 572-576.

## Abstract

Deciding consistency of constraint networks is a fundamental problem in qualitative spatial and temporal reasoning. In this paper we introduce a divide-and-conquer method that recursively partitions a given problem into smaller sub-problems in deciding consistency. We identify a key theoretical property of a qualitative calculus that ensures the soundness and completeness of this method, and show that it is satisfied by the Interval Algebra (IA) and the Point Algebra (PA). We develop a new encoding scheme for IA networks based on a combination of our divide-and-conquer method with an existing encoding of IA networks into SAT. We empirically show that our new encoding scheme scales to much larger problems and exhibits a consistent and significant improvement in efficiency over state-of-the-art solvers on the most difficult instances.Jason Jingshi Li, Jinbo Huang, Jochen Renz