Multi-Objective Knapsack Problem

This is a Multi-Objective Optimization problem: a variation of uni-objective Knapsack Problem: In this case instead of maximizing profits we look at multiple objectives.

Project Selection Problem

We want to select projects for investing some money

  • the budget is 900k euros (this this the constraint)


  • Maximize expected profits
  • Maximize the number of employees
Projects $\to$ $P_1$ $P_2$ $P_3$ $P_4$
Investment, k-euro 200 300 400 500
# of employees 2 3 5 6
Exp. return, % 2.5 4.5 4 2.5

For example

  • $P_3 + P_4 \leqslant 900$, can employ 11 people


We see that there are only two interesting solutions

  • all other solutions are dominated by these two


Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion