# Knapsack Problem with Multiple Properties

## Problem Description

I have many examples (say $$N$$) to choose from to train my machine learning model. However, I could only select $$n \ll N$$ based on a set of $$K$$ attributes $$\{a_1, a_2, \cdots, a_k\}$$ already measured for the dataset.

Now I would like to find these $$n$$ samples so that some measure (for example, sum) of the each of the $$K$$ columns are maximized.

## What I Tried

This looks like a knapsack problem but with multiple attributes. However, direct Google search does not seem to give me a lot of relevant results as I am looking for an existing software package that could solve this problem (or perhaps its relaxed version).

## Note

Cross-posted at Math.SE with 200 bounty points.

• Maximizing the sum of each attribute (column) is not possible (barring a major coincidence where the solution maximizing one attribute maximizes all of them). You have a multiobjective problem. I added the tag "multi-objective-optimization". Search for posts with that tag to get some idea of the range of possibilities.
– prubin
Jun 22 at 2:16

First, let $$x_i=1$$ if the $$i$$th example is picked, where $$i \in \{1, 2, …, N\}$$, and $$x_i=0$$ otherwise.

If you want to maximize the sum of ALL the elements, simply a knapsack problem with non-varying weights suffices.

$$max \sum_i (\sum_k a_{ki}) x_i$$

Subject to

$$\sum_i x_i \leq n$$

This can trivially solved by picking the first $$n$$ elements ranked by the sum of its attributes.

If instead you want to maximize the minimum of the sum of each attribute, you can introduce integer variable $$z$$ to solve

$$max \; z$$

Subject to

$$\sum_i x_i \leq n$$

$$\sum_i a_{ki} x_i \geq z, \; \forall k$$

• In both models, I think $a$ should have both $i$ and $k$ as subscripts. In the second model, you do not need the $y_k$ variables. You can just require $\sum_i a_{k,i} x_i \ge z.$
– prubin
Jun 22 at 2:13
• @prubin Thank you for your corrections. Jun 22 at 2:25