I am trying to efficiently solve the following optimization problem: \begin{align}\max_{b \in \mathbb{R}_+^D}&\quad\sum_{n=1}^{N}\operatorname H(b^T w^{(n)} - c^{(n)}) \\\text{s.t.}&\quad\sum_{d=1}^D b_d \leq B,\end{align} where $\operatorname H$ is the Heaviside step function, $b \in \mathbb{R}_+^D$ is a real-valued vector with positive values, $\forall n \in \{1, \dots, N\} : w^{(n)} \in \mathbb{R}_+^D$, and the $c^{(n)}$ are non-negative parameters.
I am aware that this sort of problem can be solved via mixed-integer linear programming (see, for example, the discussion of a more general optimization problem involving step functions in this post).
Given the particularly simple form of this problem, I wonder:
- Is there an efficient method for solving this problem that does not require optimization?
- If not: Do you know whether this problem has been discussed in literature / whether this problem has a particular name?
- If this is a well-studied problem: Is there some specialized solver that is more efficient than using a generic MILP solver (similar to how there are specialized solvers for flow problems)?