Boolean programming, truth-teller-liar puzzles and related graphs

摘要

In this paper we present some Boolean programming (0-1 programming) problems and some truth-teller-liar puzzles (using only 'and' connectives). We translate the puzzles to Boolean programming problems. The constraints of our problems are equalities and inequalities; we write them to atomic form. Using these atomic restrictions we construct a graph-representation. When there are some nonlinear constraints, they are represented by so-called critical edges. We give some transformations of graphs. We show a graph-algorithm to get a/all solution(s) of the presented Boolean programming problems and puzzles, with examples. A version of the algorithm to get the optimal solution will also be given.