Extending GENET to Solve Fuzzy Constraint Satisfaction Problems

Abstract

Despite much research that has been done on con-straint satisfaction problems (CSP’s), the framework is sometimes inflexible and the results are not very satisfactory when applied to real-life problems. With the incorporation of the concept of fuzziness, fuzzy constraint satisfaction problems (FCSP’s) have been exploited. FCSP’s model real-life problems better by allowing individual constraints to be either fully or partially satised. GENET, which has been shown to be ecient and eective in solving certain tradi-tional CSP’s, is extended to handle FCSP’s. Through transforming FCSP’s into 0 − 1 integer programming problems, we display the equivalence between the un-derlying working mechanism of fuzzy GENET and the discrete Lagrangian method. Simulator of fuzzy GENET for single-processor machines is implemented. Benchmarking results conrm its feasibility in tackling CSP’s and flexibility in dealing with over-constrained problems.