Optimization problem: Choose indices to max $A$ under constraint $B$

Question

I have the following data set:

\begin{array}{|c|c|c|} \hline \text{Index}& A & B \\ \hline 0 & a_0 & b_0\\ \hline 1 & a_1 & b_1\\ \hline 2 & a_2 & b_2\\ \hline ... & ... & ...\\ \hline \end{array}

There are $\sim 1300$ indices and from them I need to choose a $100$ such that:

$$ \max(\sum_{i \in I} a_i) $$ $$ s.t. $$ $$ \sum_{i \in I} b_i \ge C $$ Where: $$ I $$ Is the set of chosen indices.

My knowledge in optimization is lacking, is this a problem solvable? Are there any known algorithms for solving this problem? Is there any available Python code for it?

Thank you.

Answer 1

This is a mixed integer linear programming problem.

Reformulate the problem as:

$$\max \sum_{i \in \{1,\ldots n\}}a_iy_i$$

subject to:

$$\sum_{i \in \{1,\ldots n\}} b_iy_i \ge C$$

$$\sum_{i \in \{1,\ldots n\}} y_i=100$$

$$y_i \in \{0,1\},\forall i \in \{1,\ldots n\} $$