Abstraction by Interchangeability in Resource Allocation

Abstract

Resource allocation is a difficult constraint satisfaction problem that has many practical applications. Fully automatic systems are often rejected by the ultimate users because, in many real-world environments, constraints cannot be formalized completely. On the other hand, humans are overwhelmed by the complexity of their task. We present a new way of solving the resource allocation, where a computer builds dynamic abstractions that simplify problem solving to the point that the user can intervene in the solution of the problem. These abstractions are based on the concept of interchangeability introduced by Freuder. In this paper, we describe a heuristic for decomposing a resource allocation problem into abstractions that reflect interchangeable sets of tasks or resources. We assess the "quality" of the discovered neighborhood interchangeable sets by comparing them to the ones obtained by the exact algorithm described by Freuder, both for data taken from a real-world application and for randomly generated problems.