Finding an optimal solution that minimizes a constraint?

Question

Let us call this problem the Slinger-Bird problem (actually the Slinger is analogous to a server and the bird to a request but I was having a nervous breakdown thinking about it so I changed them hoping to get a different perspective!).

• There are S stone throwers (slingers) and B birds.
• The slingers are not within the range of each other.
• Slinging once can kill all birds within the sight of a slinger and will consume one shot and one time unit

I am trying to figure out the optimal solution that minimizes the time and the number of shots it takes to kill the birds given a particular arrival pattern of birds. Let me give an example with absolute numbers: 3 Slingers and 4 birds.

        Time        1            2            3           4             5
Slinger
S1                B1, B2     B1, B2, B3       B4
S2                               B1         B1, B2      B3,B4     
S3                  B1         B3, B4                 B1,B2,B3,B4

and my data looks like this:

>> print t
[
  {
    1: {S1: [B1, B2], S2: [], S3: [B1]}, 
    2: {S1: [B1, B2, B3], S2: [B1], S3: [B3, B4]},
    3: {S1: [B4], S2: [B1,B2], S3: []},
    4: {S1: [], S2: [B3, B4], S3: [B1, B2, B3, B4]}
  }
]

There are a number of solutions I could think of (Sx at t=k implies that slinger Sx takes a shot at time k):

1. S1 at t=1, S1 at t=2, S1 at t=3 <- Cost: 3 shots + 3 time units = 6
2. S1 at t=2, S1 at t=3 <- Cost: 2 shots + 3 time units = 5
3. S1 at t=1, S3 at t=2 <- Cost: 2 shots + 2 time units = 4
4. S3 at t=4 <- Cost: 1 shot + 4 time units = 5

To me it appears that solution 3 is the optimal one in this. Of course, I did this by hand (so there is a possibility I may have missed something) but I cannot think of a scalable way of doing this. Also, I am worried there are corner cases because the decision of one shooter might alter the decision of others but because I have the global view, may be it does not matter.

What is a fast and good way to solving this problem in python? I am having a hard time coming up with a good data structure to do this leave alone the algorithm to do it. I am thinking of using dynamic programming because this seems to involve state space exploration but am a bit confused on how to proceed. Any suggestions?

Answer 1

This is not an optimal assignment problem, because slingers kill all birds in view.

You have a two-dimensional objective function, so there can be a number of tradeoffs between shots and time. Determining the minimum number of shots for a particular time limit is exactly the set cover problem (as mhum suggests). The set cover problem is NP-hard and hard to approximate, but in practice, branch and bound using the dual of the linear programming formulation is quite effective in finding the optimum.

Answer 2

I suggest using bitmaps for the slingers and birds, i.e.

S1 = B1 = 1, S2 = B2 = 2, S3 = B3 = 4, B4 = 8

Then the input data can be written as

bird_data = [[3, 0, 1], [7, 1, 12], [8, 3, 0], [0, 12, 15]]

The cost function can now be written like this:

def cost(shots):
    hit = units = 0
    for show, shot in zip(bird_data, shots):
        units += 1
        for n, birds in enumerate(show):
            if shot & 1:
                units += 1
                hit |= birds
                if hit == 15: # all are hit
                    return units
            shot >>= 1
    return 99 # penalty when not all are hit

Now it's easy to find the optimal shots by calculating the minimum of the cost function:

from itertools import product

shot_sequences = product(*([range(7)]*len(bird_data)))

print min((cost(shots), shots) for shots in shot_sequences)

This prints

(4, (0, 5, 0, 0))

which means the optimum is 4 units, when S1 and S3 (5 = 1 + 4) fire at t=2. Of course your solution is also possible, where S1 fires at t=1 and S3 at t=2, both have the same cost.

However, since the algorithm is using brute force, running over all possible shot sequences, it is only fast and feasible when the data sets are very small, like in your example.