Grouping of a list of elements in fixed order to maximize the total return of all the groups

Question

I'd like to ask about if there's an existing type of problems that fits to my question. (Searching it for a while but cannot get to the point)

Basic Problem Description:

Given a sequenced list (order fixed) of elements: [4,5,10,5,2,4,5,3...]

I need to group them into several bins (like the img below) so that the sum of each group fits in certain constraints -- i.e. lower, upper bound

The objective is to maximize the total return V = SUM(v_i) of all groups -- each group will have value v_i depends on the sum of all its sub-elements.

Question:

1. Since the total number of groups is undefined, how to formulate this problem?
2. Is there an existing type of OP or MIP problem like this to refer to?

Advanced Version:

An additional requirement for the basic version of the question is, the center of some bins/groups need to locate at a serious of fixed location -- say, one need to center at the 5th element, another need to center at the 30th element, etc.

Question

1. Is there a proper way to formulate it?
2. Again, references will be appreciated.

Answer 1

You can formulate this as a shortest path problem in a directed acyclic network. Each node corresponds to the start of a new bin. The first element is the source node, and you will introduce a dummy sink node. Each arc from $i$ to $j$ (with $i<j$) corresponds to a bin with items $\{i,i+1,\dots,j-1\}$, and the arc weight is $-v\left(\sum_{k=i}^{j-1} a_k\right)$, where $a_k$ is the value of element $k$ in your input list; the minus sign is because your original problem is maximization. The presence or absence of an arc in the network is determined by the lower and upper bounds on the sum of a group. The problem is to find a shortest path from source to sink. The additional requirement in the advanced version can be enforced by omitting some arcs.