I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints.
To illustrate my point, I'll try to come up with an example.
A bag contains several items with the following attributes:
- Value (Int)
- Size (Int)
- Material (Enum)
- Origin (Enum)
As an example, we can imagine a bag consisting of the following items:
value size material origin 4 1 wood FR 4 2 stone US 3 3 gold JP 2 2 wood FR ... ... ... ...
The goal is to maximize the total Value, while at the same time respecting a set of constraints. An example set of constraints would be:
total size < 80 between 20 and 35 items in total at least five elements with origin FR at least two elements with material wood OR at least two elements with material stone strictly less elements with material gold than elements of material stone no more than 5 elements with size > 10
Below are some approaches I've thought about, and the reason why I can't use them directly:
- (Integer) Linear Programming: here we're not dealing with the full space of Integers, but instead only with the values found in the bag (and tied to the other properties for each item)
- Stochastic Constraint Satisfaction: it would be easy to stochastically come up with a selection of Items which respects the constraints, but here we're not looking for any solution, instead we're looking for the solution which yields the highest total Value, which would need us to exhaustively list all possible satisfying solutions before picking the one with highest value (which may be a very inefficient approach)
- SMT solver: I think it could be the way to go, but so far I can't see how to model the link between the constraints, the objective function and the bag of elements
Can you think of an approach to solve this kind of problems?