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

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?

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) 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.