I think this is a take on a knapsack problem but I'm struggling to find an example similar:
Say I have various tubes filled with red balls and black balls. The balls are contained in the tubes so that they cant move around and to remove a ball you need to remove the ball in front. Each ball has a different weight and value, I know each ball's characteristics and position beforehand. I'm trying to make a selection of the balls to fulfil a required batch, the batch would need to meet various constraints around the mean batch weight & mean value, batch size etc. The objective is to meet these constraints by removing the minimum number of balls from the tubes.
I can only select the red balls for the batch. The black balls are randomly interspaced within the tube, meaning these balls would have to be removed from the tube in order to reach the red ball behind it, but would not be included in the batch and therefore it's characteristics would not contribute to the batch constraints. Also, not every red ball that is removed from the tubes must be placed on the batch - similar to the black balls, these could just be removed to reach another red ball. So I think I need to have a few decisions - one would be to take the ball and place it in the batch, one would be to remove the ball but don't put it in the batch, and lastly don't touch the ball.
Here is a bit of a pictorial example, with two tubes:
1: R R R R B B B R B R
2: B B B B R R B R R B
As we cannot place the black balls in the batch, we could remove the requirement to make a decision on them, but still consider the placements of the red balls.
For the cost I'm thinking I could assign a cost of: for the 1st red ball in the tube: the cost would be the number of black balls in front of it +1 for the red ball itself. For remaining red balls in each tube: the number of black balls between that red ball and the n-1 red ball + 1 for the red ball itself.
1: R R R R B B B R B R
C: 1 1 1 1 - - - 4 - 2
2: B B B B R R B R R B
C: - - - - 5 1 - 2 1 -
Then, I would have a constraint that forces you to also select the n-1 ball when you select the nth ball for moving - but the n-1th ball can either be put on the batch or just removed.
I'm really struggling to formularise/conceptualise the cost of moves on each ball, does anyone know if any classic optimisation problems fit this scenario or could point me in the right direction?
Any suggestions would be appreciated. :)
