Constrained Potts mean field systems and their electronic implementation

The Potts mean field approach for solving combinatorial optimization problems subject to winner-takes-all constraints is extended for problems subject to additional constraints. Extra variables corresponding to the Lagrange multipliers are incorporated into the Potts formulation for the additional constraints to be satisfied. The extended Potts equations are solved by using constrained gradient descent differential systems. This gradient system is proven theoretically to always produce a legal local optimum solution of the constrained combinatorial optimization problems. An analog electronic circuit implementing the present method is designed on the basis of the previous Potts electronic circuit. The performance of the present method is theoretically evaluated for the constrained maximum cut problems. The lower bound of the cut size obtained with the present method is proven to be the same as that of the basic Potts scheme for the unconstrained maximum cut problems.