Consider a convex relaxation F of a pseudo-boolean function f.
We say that the relaxation is totally half-integral if F(x) is a polyhedral function
with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints
of the form xi=xj, xi=1-xj, and xi=γ where γ ∈ {0,1,1/2} is a constant.
A well-known example is the roof duality relaxation for quadratic pseudo-boolean functions f.
We argue that total half-integrality is a natural requirement for generalizations of roof duality
to arbitrary pseudo-boolean functions.
Our contributions are as follows. First,
we provide a complete characterization of totally half-integral relaxations F
by establishing a one-to-one correspondence with bisubmodular functions.
Second, we give a new characterization of bisubmodular functions.
Finally, we show some relationships between
general totally half-integral relaxations and relaxations based on the roof duality.