0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Jun 22 at 2:16

1 Answer 1

Reset to default
1
$\begingroup$

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 $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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.$ $\endgroup$
    – prubin ♦
    Jun 22 at 2:13
  • $\begingroup$ @prubin Thank you for your corrections. $\endgroup$
    – Mason
    Jun 22 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.