I've got a specific problem, but I'm not sure where to look to solve it:
In the context of my application, there are critical services, non-critical services, and agents which provide exactly one critical service and one or more non-critical services. I must choose from the collection of all agents (with replacement) a finite number of agents, such that each critical service is provided by a certain number of agents. This is straightforward. However, I have the secondary objective that I would like the set I choose to also provide as many different non-critical services as possible.
I'm sure this can be done via SAT, but I don't really want to mess around with NP-complete solvers. The goal for either kind (critical or not) of the services could be constructed as a network flow problem and solved in a straightforward way, but I can't seem to merge them, even as a multi-commodity network flow.
Has anyone seen this problem before, or something embarrassingly similar? I'd really appreciate a pointer to where I could start looking for solutions.