Suppose we have variables such that if and only if and we want maximize the value of . I know that this reduces to the following Integer programming problem:
The linear relaxation of this problem is then given by:
Now in the relaxation we will simply get . I was wondering whether there is some alternative formulation for the Integer Program such that, when we take the linear relaxation of the problem, the solution is stricly smaller than .