Knapsack Problem Variant - Maximizing Weight and Value Up To Limit

Question

I'm trying to work out an algorithm (likely using OR Tools in Python) for solving a problem that seems to be related to the Knapsack problem.

• I have a set of items at Location A
• I want to get them to Location B
• Each item has a weight and a value
• I can only carry X amount of weight
• I'm afraid of getting robbed along the way, so I only want to carry up to Y amount of value

If I'm trying to plan my first trip from Location A to Location B, how can I select the items such that:

• I maximize the weight that is loaded, up to a limit of X (minimize wasted weight capacity)
• I maximize the value that is loaded, up to a limit of Y (minimize wasted value capacity)

A contrived example:

• My limits are 5kg and $50
• I have 10 of Item C (weight: 0.1kg, value: $10)
• I have 10 of Item D (weight: 1kg, value: $1)

The "easy" solution is to make 4 trips:

• 5x Item C ($50, 0.5kg)
• 5x Item C ($50, 0.5kg)
• 5x Item D ($5, 5kg)
• 5x Item D ($5, 5kg)

But the smarter solution is to make only 3 trips:

• 4x Item C + 4x Item D ($44, 4.4kg)
• 4x Item C + 4x Item D ($44, 4.4kg)
• 2x Item C + 2x Item D ($22, 2.2kg)

I've worked with the OR Tools linear solver, but only with maximizing one value while having multiple constraints. How can I maximize multiple values (loaded weight and loaded value) with multiple constraints?

Answer 1

I believe I found a solution to this. What I did was try to maximize a composite variable that accounts for both weight and value. In Python with OR Tools:

objective = solver.Objective()

for i, item in enumerate(item_list):
    objective.SetCoefficient(x[i], item['mass']/max_volume + item['value']/max_value)

objective.SetMaximization()

This sets the coefficient to account for both mass and value. The important part is that each is normalized against its associated limit. This solution is consistently giving me sets of items that fully use both the weight and value "space" to their full extent.