Problem decomposition in distributed problem-solving systems

Distributed Problem Solving (DPS) is defined as the cooperative solution of problems by a decentralized and loosely coupled collection of problem solvers (agents), each of them knowing how to execute only some of the necessary tasks. This approach considers the problem-solving process as occurring in three phases: problem decomposition, subproblem solution, and answer synthesis. In the problem decomposition phase, one has to determine which tasks will be executed by each agent and when. One of the key research questions in the problem decomposition process is how to decompose a problem in order to minimize the cost of resources needed for its solution. In this article, we construct mathematical programming models in order to describe the decomposition process under the above criterion, study its complexity, and present exact and heuristic algorithms for its solution. Our work was motivated by the operation of an actual system that can be considered as a distributed problem solver for the assessment of irrigation projects design.