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.