say I have $n$ integers which I will denote $i_m$, each integer has a range $r_m$, a cost $C_m(i_m)$, and a value $V_m(i_m)$. There is a maximum total $T$ the sum of the costs must not exceed. What I am trying to do is
\begin{array}{ll} \text{maximize} & \sum_{j=0}^m V_j(i_j) \\ \text{subject to}& \sum_{j=0}^m C_j(i_j) \le T \\ &0\le i_m \le r_m \end{array}
My first instinct was to find continuous approximations for all the costs and values, then use the method of Lagrange multipliers, or something similar.
However, there is a hitch. There are sub-ranges that need to sum to or exceed certain requirements in order for variables further up the line be non-zero.
I'll give an example to illustrate. Say $m=18$, and we are given
$i_{4,5,6}>0 \implies \sum_{j=1}^3i_j \ge20$ and $i_{7,8,9}>0 \implies \sum_{j=1}^6i_j \ge50$ then, furthermore $i_{13,14,15}>0 \implies \sum_{j=10}^{12}i_j \ge20$ and $i_{16,17,18}>0 \implies \sum_{j=1}^{15}i_j \ge50$
I do not know how to handle these requirements, is there any algorithms I can use? I'm looking for an improvement on iterating the greedy algorithm until $T$ is met.
There are two issues. The first is the discrete nature of the problem. The other is added Inequality Constraints. I found This paper which describes adding "slack variables" to handle inequalities. This seems to be what I am looking for. I intend to add these slack variables and solve the problem as a continuous problem. Then, reduce all $i_n$ to $\lfloor i_n \rfloor$ to bring it back to a discrete problem. From there I'll simply use a greedy algorithm to spend the rest of my total $T$.