Constraints Satisfaction through Recursive Neural Networks with Mixed Penalties: a Case Study

摘要

This paper investigates an industrial assignment problem. It is modelized as a constraint satisfaction problem of large size with linear inequalities and binary variables. A new analog neuron-like network is proposed to find out feasible solutions to problems having several thousands of 0/1 variables. The approach developed in this paper is based on mixed-penalty functions: exterior penalty functions together with interior penalty functions. Starting from a near-binary solution satisfying each linear inequality, the network generates trial solutions located outside or inside the feasible set, in order to minimize an energy function which measures the total binary infeasibility of the system. The performances of the network are demonstrated on real data sets.