We consider a system of nonlinear ordinary differential equations for the solution of linear programming (LP) problems that was first proposed in the mathematical biology literature as a model for the foraging behavior of acellular slime mold Physarum polycephalum, and more recently considered as a method to solve LPs. We study the convergence time of the continuous Physarum dynamics in the context of the linear programming problem, and derive a new time bound to approximate optimality that depends on the relative entropy between projected versions of the optimal point and of the initial point. The bound scales logarithmically with the LP cost coefficients and linearly with the inverse of the relative accuracy, establishing the efficiency of the dynamics for arbitrary LP instances with positive costs.
@cite_18: Physarum polycephalum (true slime mold) has recently emerged as a fascinating example of biological computation through morphogenesis. Despite being a single cell organism, experiments have observed that through its growth process, the Physarum is able to solve various minimum cost flow problems. This paper analyzes a mathematical model of the Physarum growth dynamics. We show how to encode general linear programming (LP) problems as instances of the Physarum. We prove that under the growth dynamics, the Physarum is guaranteed to converge to the optimal solution of the LP. We further derive an efficient discrete algorithm based on the Physarum model, and experimentally verify its performance on assignment problems.
@cite_4: In this paper we study dynamics inspired by Physarum polycephalum (a slime mold) for solving linear programs [NTY00, IJNT11, JZ12]. These dynamics are arrived at by a local and mechanistic interpretation of the inner workings of the slime mold and a global optimization perspective has been lacking even in the simplest of instances. Our first result is an interpretation of the dynamics as an optimization process. We show that Physarum dynamics can be seen as a steepest-descent type algorithm on a certain Riemannian manifold. Moreover, we prove that the trajectories of Physarum are in fact paths of optimizers to a parametrized family of convex programs, in which the objective is a linear cost function regularized by an entropy barrier. Subsequently, we rigorously establish several important properties of solution curves of Physarum. We prove global existence of such solutions and show that they have limits, being optimal solutions of the underlying LP. Finally, we show that the discretization of the Physarum dynamics is efficient for a class of linear programs, which include unimodular constraint matrices. Thus, together, our results shed some light on how nature might be solving instances of perhaps the most complex problem in P: linear programming.
The generalization of the Physarum dynamics to linear programming problems that we consider here has been first suggested by Johannson and Zou @cite_18 . Most relevant to the current paper is the work of Straszak and Vishnoi @cite_4 , who initiated the rigorous study of the Physarum dynamics for LP problems of the form . Straszak and Vishnoi proved that a solution to the dynamics exists over the entire time horizon @math , and that a bound on the convergence time of the continuous dynamics can be expressed in terms of the parameter @math , the of the constraint matrix @math , as summarized by their theorem that we quote here for comparison.