Following problem: I have a vector of n different lenghts. I want to minimize the number of different/unique lenghts in that vector. To do so, I can change those numbers - I know the upper and lower bound of each length even. A specific restriction for my particular problem is that the lengths can only be increased and not decreased. I want to do change the lengths in a way so that the overall change is minimal.
So for examaple I have the numbers 1.5, 2.0 and 3.0. Bounds for each x are [x, x+1.1] (can only be increased). So n=3 and let's say I want to know if I can reduce that to 2 unique numbers and if so - how would be the optimal way. For this example, two possible results would be
2.0, 2.0, 3.0 or
1.5, 3.0, 3.0
Both would reduce the number of different lengths to 2, but the second would be better since I would only need to add 0.5 versus 1.0 in the second example.
Is that a known problem? Any pointers? Sorry if this is the wrong place to ask - wasn't sure where to start.
You could formulate this as a Linear Program (LP). Let $\mathbf x$ be your vector of original numbers, and $\mathbf u$ be the vector of corresponding upper bounds. Let $\mathbf y$ be the amount by which you increase each number. Then, we can write the following optimization problem.
\begin{equation} \begin{aligned} p = &\min_{\mathbf y} &&\sum_{i<j}|(x_i+y_i) -(x_j+y_j)| +\alpha\sum_i y_i \\ &\ \ \text{s.t.} && \mathbf x+\mathbf y\leq \mathbf u, \\ &&& \mathbf y \geq \mathbf 0. \end{aligned} \end{equation}
The first part of the objective function measures the difference between each pair of adjusted numbers. The second part penalizes the overall change, so long as $\alpha > 0$.
This can be recast as an LP by introducing an auxiliary variable $z_{ij}$ for each absolute value:
\begin{equation} \begin{aligned} p = &\min_{\mathbf y, \mathbf z} &&\sum_{i<j}z_{ij}+\alpha\sum_i y_i \\ &\ \ \text{s.t.} && \mathbf x+\mathbf y\leq \mathbf u, \\ &&& \mathbf y \geq \mathbf 0, \\ &&& z_{ij} \geq (x_i+y_i) -(x_j+y_j), \\ &&& z_{ij} \geq -\left ( (x_i+y_i) -(x_j+y_j)\right ), \ \ \ \forall i < j. \end{aligned} \end{equation}