Resource allocation in networks using abstraction and constraint satisfaction techniques

Abstract. Most work on constraint satisfaction problems (CSP) starts with a standard problem denition and focuses on algorithms for nd-ing solutions. However, formulating a CSP so that it can be solved by such methods is often a dicult problem in itself. In this paper, we consider the problem of routing in networks, an important problem in communication networks. It is as an example of a problem where a CSP formulation would lead to unmanageable solution complexity. We show how an abstraction technique results in tractable formulations and makes the machinery of CSP applicable to this problem.