Maximizing sum of step functions under single linear constraint

Question

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:

1. Is there an efficient method for solving this problem that does not require optimization?
2. If not: Do you know whether this problem has been discussed in literature / whether this problem has a particular name?
3. 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)?

Answer 1

Dynamic Programming is often a good method of choice for solving this class of problems. Chapter 3 of The Art and Theory of Dynamic Programming refers to this class of problems as Resource Allocation problems. There is one constraint restricting the amount of available resource, the parameter $B$, with a linear or nonlinear objective function. An interesting feature of dynamic programming for such problems is that it can sometimes be used to find analytical or closed-form solutions for them.

Dynamic programming is a very reasonable choice, but of course, we need to spend some time to understand the problem better (deriving some properties that allow for an efficient solution). Often we start with the basic case ($N=2$ or $D=2$ or both) and then generalize the results to the more general case. Using proof by induction, we might also be able to derive policies that result in an efficient closed-form solution. An example of this approach with a nonlinear step (ceiling) function can be found here. Another example is the Discrete Budgeting Problem introduced in Section 2.1.2 of Approximate Dynamic Programming.