Optimal Boolean Programming with Graphs

Abstract

In this paper, we solve some special types of linear and non-linear Boolean programming problems. We present a method for transforming the used linear 0-1 inequalities into a weighted directed graph. Allowing equalities our conditions are nonlinear, but the transformation to weighted directed graphs works also in these cases. In graph representations, the critical edges are used to represent the non-linear conditions. Basic, modified and extended Boolean programming problems are investigated. Linear goal-functions are used in optimization. The presented algorithm, similarly as algorithms for knapsack-problems, gives a relatively good solution, moreover, the algorithm extended by the backtrack graph-search strategy, guarantees optimal solutions for the considered problems.