Weight-free relaxation

Summary form only given. Many distributed optimization problems such as resource allocation or routing can be treated by the global minimization of some quadratic energy function of the problem variables. The three ways in which the model departs from current treatments are discussed. The constraints between variables can be classified into hard constraints, which specify mandatory properties of solutions that must be satisfied, and soft constraints or costs, which are quantifiable and specify desirable properties of solutions. Another important distinction exists between local constrains that can be evaluated by a single node in a distributed network and global constraints whose satisfaction cannot be verified without knowing the state of the whole network. Previous models have failed to adequately distinguish between these constraint classes. Furthermore, they lead to an inherently cumbersome computer implementation, namely the emulation of value-passing networks using analog voltages or floating-point numbers. The authors significantly reduce these shortcomings with a new model referred to as weight-free relaxation.<>