Optimal Decoupling in Linear Constraint Systems


  • Cees Witteveen Delft University of Technology
  • Michel Wilson Delft University of Technology
  • Tomas Klos Delft University of Technology




Decomposition, Linear Programming, Scheduling


Decomposition is a technique to obtain complete solutions by assembling independently obtained partial solutions. In particular, constraint decomposition plays an important role in distributed databases, distributed scheduling and violation detection: It enables conflict-free local decision making, while avoiding communication overloading. One of the main issues in decomposition is the loss of flexibility due to decomposition. Here, flexibility roughly refers to the freedom in choosing suitable values for the variables in order to satisfy the constraints. In this paper, we concentrate on linear constraint systems and efficient decomposition techniques for them. Using a generalization of a flexibility metric developed for Simple Temporal Networks, we show how an efficient decomposition technique for linear constraint systems can be derived that minimizes the loss of flexibility. As a by-product of this decomposition technique, we propose an intuitively attractive flexibility metric for linear constraint systems where decomposition does not incur any loss of flexibility.




How to Cite

Witteveen, C., Wilson, M., & Klos, T. (2014). Optimal Decoupling in Linear Constraint Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.9039