Efficient flow problem for a complex integer program

Question

I have a bunch of marbles each with some weight (they can also have negative weights). I want to pick the nodes such that the weight is maximized. The only rule is that if I pick X1 and X2 I have to pick X1,2 as well. Also if I pick X1,X2,X3 then I have to pick not only X1,2 and X2,3 and X1,3 but also X1,2,3. The other thing is that I cannot pick X1,2 unless I pick both X1 and X2.

It is easily solvable by integer programming but I am wondering if there is any network flow solution that is more efficient?

Some clarification: for every X1 and X2 there is always a X1,2 marble (but may have 0 or negative weight).

The input is just the list of marbles and their weights [(X1:W1), (X2:W2), (X1,2:W1,2),...]

More Updates Suresh pointed out that the input size is very large and I agree. In the problem that I am solving I only have 4 layers. I mean I have up to X(i,j,k,l) and everything above it with 5 or more subscripts has a weight 0.

• Suresh Venkat: There's something strange here; are you given a weight for any possible subset ? If so, then your input size is very large.
• Mark: @SureshVenkat thanks for pointing that out. Added a clarification.

Answer 1

Isn't this problem NP-complete?

Start with a graph $G$. Make $x_i = 1 \ \ \forall i,ドル where $i$ is a vertex of $G$. Now, for each edge $(i,j)$ of $G,ドル make $x_{i,j} = -3$. Otherwise, make $x_{i,j}=0$. Give weight 0 to all three- and four-level marbles. To maximize your objective function, you want to pick as many marbles as you can so long as you don't take two marbles connected by an edge. This is the maximum independent set problem, which is NP-complete.