MAX HORN SAT AND THE MINIMUM CUT PROBLEM IN DIRECTED HYPERGRAPHS

In this paper we consider the Maximum Horn Satisfiability problem, whi ch is reduced to the problem of finding a minimum cardinality cut on a directed hypergraph. For the latter problem, we propose different IP formulations, related to three different definitions of hyperpath weig ht. We investigate the properties of their linear relaxations, showing that they define a hierarchy. The weakest relaxation is shown to be e quivalent to the relaxation of a well known IP formulation of Max Horn SAT, and to a max-flow problem on hypergraphs. The tightest relaxatio n, which is a disjunctive programming problem, is shown to have intege r optimum. The intermediate relaxation consists in a set covering prob lem with a possible exponential number of constraints. This latter rel axation provides an approximation of the convex hull of the integer so lutions which, as proven by the experimental results given, is much ti ghter than the one known in the literature. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.