Objective function and constraint satisfaction over a set of multi-attributes elements
I don't see any problem with modeling this as an integer linear program, for example:

maximize V.x
st:
1) s.x &lt; 80
2) 20 &lt;= e.x &lt;= 35
3) FR.x &gt;= 5
4a) Wood.x + 2 - 2W &gt;= 2
4b) Stone.x + 2W &gt;= 2
5) Gold.x - Stone.x &lt; 0
6) Size10p.x &lt;= 5
x[i] ∈ {0, 1}
W ∈ {0, 1}


Where . is the dot product, x is a binary vector indicating which items to take, e is the vector of all-ones, FR is a boolean vector where an element is 1 iff the corresponding item is from France, Wood is a boolean vector that indicates that the material wood, etc. Size10p indicates that the item has a size higher than 10.

I've made all the left-hand sides of dot products the constant vector, so you can easily see that there are no sneaky quadratic constraints.

Most of the constraints are obvious, but constraint 4 is a bit trickier. It involves a disjunction, and uses an extra binary variable to choose which "side" of the disjunction to take. The other half is then trivially satisfied, by either adding 2 and not also subtracting 2 (W = 0, not taking the wood-side of the disjunction) or by just adding 2 (W = 1, taking the wood-side).


  here we're not dealing with the full space of Integers, but instead only with the values found in the bag


This is usually not a problem, since you can binarize constraints of the form v ∈ some enum to v1 = [v == item1], v2 = [v == item2] etc combined with v1 + v2 + ... = 1. But I did not even need that here, the decision is just "do I take this item or not", and things such as "item has property 'Gold'" are just constant booleans.

More tricks are available in other answers, for example Express boolean logic operations in zero-one integer linear programming (ILP).