Extending EGENET with lazy constraint consistency

Abstract

Constraint satisfaction problems (CSPs) occur widely in real-life applications such as bin-packing, planning and scheduling. EGENET, a neural network simulator based on the min-conflict heuristic, has had remarkable success in solving hard CSPs such as hard graph-colouring problems. Consistency techniques such as arc consistency have been extensively used to improve the search behaviour of complete search methods, by removing values and combinations of values that cannot take part in any solution. They are not typically used for stochastic search methods such as EGENET. In this paper we show how to efficiently incorporate consistency methods in EGENET. This improves the convergence behaviour of EGENET and also makes it able to detect insoluble CSPs. We compare the improved EGENET against the original version and versions incorporating state-of-art consistency techniques such as AC-4 or PC-4.