A pseudo boolean function f:{0,1}^n-> R is defined as f(x)= x^tQx +cx where Q is a symmetric matrix with null elements in the diagonal. Finding the minimum of this function is solvable in polynomial time if all entries are non - positive.My question is: Remains the problem of finding the minimum polynomial, if we add linear constraints which themselves decribe a flow. More exactly: Each variable in the constraints occurs in exactly two different equalities and one time its coefficient is 1 and one time its coefficient is -1.Many thanks for response beforehand!
Polynomial cases of 0 1 quadratic programm with linear constraints
optimization;integer programming;flow problems;quadratic