Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 519.157
M.I. Schlesinger,1 B. Flach,2 E. Vodolazskiy3

FINDING A GIVEN NUMBER OF SOLUTIONS TO A SYSTEM OF FUZZY CONSTRAINTS

Abstract. A minimax modification of a fuzzy constraint satisfaction problem is considered, where constraints determine not whether a given solution is feasible but the numerical value of satisfiability. The algorithm is proposed that finds a given number of solutions with the highest value of satisfiability in polynomial time for a subclass of problems with constraints invariant to some majority operator. It is essential that knowing the operator itself is not required. Moreover, it is not necessary to guarantee its existence. For any system of fuzzy constraints, the algorithm either finds a given number of best solutions or declines the problem. The latter is only possible when no such operator exists.

Keywords: discrete optimization, minimax problems, labeling, invariants, polymorphisms.



FULL TEXT

1 International Scientific and Training Center of Information Technologies and Systems, National Academy of Sciences of Ukraine and Ministry of Education and Science of Ukraine, Kyiv, Ukraine,
e-mail: schles@irtc.org.ua.

2 Center of Machine Vision, Czech Technical University in Prague, Prague, Czech Republic,
e-mail: flachbor@cmp.felk.cvut.cz.

3 International Scientific and Training Center of Information Technologies and Systems, National Academy of Sciences of Ukraine and Ministry of Education and Science of Ukraine, Kyiv, Ukraine,
e-mail: waterlaz@gmail.com.

© 2018 Kibernetika.org. All rights reserved.