Entropy based algorithm for combinatorial optimization problems with mobile sites and resources
Puneet Sharma, Srinivasa M. Salapaka, Carolyn L. Beck · 2008
In this paper, we propose an algorithm for solving combinatorial resource allocation problems with mobile sites and resources. We consider the instantaneous coverage problem, which is formulated in a Maximum Entropy Principle (MEP) framework, and identify a metric for optimal coverage between mobile sites and resources. This metric, referred to as the Free Energy has been motivated by principles of statistical physics. The determination of resource locations and velocities is cast as a control problem to ensure that the time derivative of Free Energy function is always non-increasing. This guarantees coverage through the time horizon. The issues of scalability and localization are also addressed by taking into account inter-resource interaction levels.