Knapsack: how to add item type to existing solution

Question

I've been working with this variation of dynamic programming to solve a knapsack problem:

KnapsackItem = Struct.new(:name, :cost, :value)
KnapsackProblem = Struct.new(:items, :max_cost)


def dynamic_programming_knapsack(problem)
  num_items = problem.items.size
  items = problem.items
  max_cost = problem.max_cost

  cost_matrix = zeros(num_items, max_cost+1)

  num_items.times do |i|
    (max_cost + 1).times do |j|
      if(items[i].cost > j)
        cost_matrix[i][j] = cost_matrix[i-1][j]
      else
        cost_matrix[i][j] = [cost_matrix[i-1][j], items[i].value + cost_matrix[i-1][j-items[i].cost]].max
      end
    end
  end

  cost_matrix
end

def get_used_items(problem, cost_matrix)
  i = cost_matrix.size - 1
  currentCost = cost_matrix[0].size - 1
  marked = Array.new(cost_matrix.size, 0) 

  while(i >= 0 && currentCost >= 0)
    if(i == 0 && cost_matrix[i][currentCost] > 0 ) || (cost_matrix[i][currentCost] != cost_matrix[i-1][currentCost])
      marked[i] = 1
      currentCost -= problem.items[i].cost
    end
    i -= 1
  end
  marked
end

This has worked great for the structure above where you simply provide a name, cost and value. Items can be created like the following:

 items = [
      KnapsackItem.new('david lee', 8000, 30) , 
      KnapsackItem.new('kevin love', 12000, 50), 
      KnapsackItem.new('kemba walker', 7300, 10),
      KnapsackItem.new('jrue holiday', 12300, 30),
      KnapsackItem.new('stephen curry', 10300, 80),
      KnapsackItem.new('lebron james', 5300, 90),
      KnapsackItem.new('kevin durant', 2300, 30),
      KnapsackItem.new('russell westbrook', 9300, 30),
      KnapsackItem.new('kevin martin', 8300, 15),
      KnapsackItem.new('steve nash', 4300, 15),
      KnapsackItem.new('kyle lowry', 6300, 20),
      KnapsackItem.new('monta ellis', 8300, 30),
      KnapsackItem.new('dirk nowitzki', 7300, 25),
      KnapsackItem.new('david lee', 9500, 35),
      KnapsackItem.new('klay thompson', 6800, 28)
    ]

  problem = KnapsackProblem.new(items, 65000)

Now, the problem I'm having is that I need to add a position for each of these players and I have to let the knapsack algorithm know that it still needs to maximize value across all players, except there is a new restriction and that restriction is each player has a position and each position can only be selected a certain amount of times. Some positions can be selected twice, others once. Items would ideally become this:

KnapsackItem = Struct.new(:name, :cost, :position, :value)

Positions would have a restriction such as the following:

PositionLimits = Struct.new(:position, :max)

Limits would be instantiated perhaps like the following:

limits = [Struct.new('PG', 2), Struct.new('C', 1), Struct.new('SF', 2), Struct.new('PF', 2), Struct.new('Util', 2)]

What makes this a little more tricky is every player can be in the Util position. If we want to disable the Util position, we will just set the 2 to 0.

Our original items array would look something like the following:

items = [
          KnapsackItem.new('david lee', 'PF', 8000, 30) , 
          KnapsackItem.new('kevin love', 'C', 12000, 50), 
          KnapsackItem.new('kemba walker', 'PG', 7300, 10),
          ... etc ...
        ]

How can position restrictions be added to the knapsack algorithm in order to still retain max value for the provided player pool provided?

Answer 1

As I understand, the additional constraint that you are specifying is as following:

There shall be a set of elements, out which only at most k (k = 1 or 2) elements can be selected in the solution. There shall be multiple such sets.

There are two approaches that come to my mind, neither of which are efficient enough.

Approach 1:

1. Divide the elements into groups of positions. So if there are 5 positions, then each element shall be assigned to one of 5 groups.

2. Iterate (or recur) through all the combinations by selecting 1 (or 2) element from each group and checking the total value and cost. There are ways in which you can fathom some combinations. For example, in a group if there are two elements in which one gives more value at lesser cost, then the other can be rejected from all solutions.

Approach 2:

Mixed Integer Linear Programming Approach.

Formulate the problem as follows:

Maximize summation (ViXi) {i = 1 to N} 
where Vi is value and 
Xi is a 1/0 variable denoting presence/absence of an element from the solution.

Subject to constraints:
summation (ciXi) <= C_MAX {total cost}
And for each group:
summation (Xj) <= 1 (or 2 depending on position)
All Xi = 0 or 1.

And then you will have to find a solver to solve the above MILP.

Answer 2

There are some efficient libraries available in ruby which could suit your task , Its clear that you are looking for some constrain based optimization , there are some libraries in ruby which are a opensource so, free to use , Just include them in you project. All you need to do is generate Linear programming model objective function out of your constrains and library's optimizer would generate Solution which satisfy all your constrains , or says no solution exists if nothing can be concluded out of the given constrains .

Some such libraries available in ruby are

• RGLPK
• OPL
• LP Solve

OPL follows the LP syntax similar to IBM CPLEX , which is widely used Optimization software, So you could get good references on how to model the LP using this , Moreover this is build on top of the RGLPK.

Answer 3

This problem is similar to a constraint vehicle routing problem. You can try a heuristic like the saving algorithm from Clarke&Wright. You can also try a brute-force algorithm with less players.