On the resolution of bipolar max-min equations. (English) Zbl 1389.90368

Li, Pingke; Jin, Qingwei

Kybernetika 52, No. 4, 514-530 (2016).

Summary: This paper investigates bipolar max-min equations which can be viewed as a generalization of fuzzy relational equations with max-min composition. The relation between the consistency of bipolar max-min equations and the classical boolean satisfiability problem is revealed. Consequently, it is shown that the problem of determining whether a system of bipolar max-min equations is consistent or not is NP-complete. Moreover, a consistent system of bipolar max-min equations, as well as its solution set, can be fully characterized by a system of integer linear inequalities.

MSC:

90C70	Fuzzy and other nonstochastic uncertainty mathematical programming
49M37	Numerical methods based on nonlinear programming

Keywords:

bipolar max-min equations; fuzzy relational equations; satisfiability; linear inequalities

Software:

SATO; Siege; BerkMin; Chaff