Designing communication networks for distributed control agents

This paper is concerned with a bicriteria combinatorial optimization problem and its applications to the design of communication networks for distributed controllers. In a bipartite graph, a subset of the edges yields a communication network for which we pay a price but, on the other hand, it induces another network that encompasses the former and for which we receive a reward. The problem is then to find the efficient solutions. The paper delivers an IP formulation for the problem of finding supported solutions, which is shown to be NP-Hard, along with families of strong valid inequalities, which are shown to draw the LP bounds closer to the Pareto optimal frontier. To approximate the frontier, heuristics are integrated in a problem-solving architecture called asynchronous team and then put to the test in two prototypical scenarios.