Linear programming - constraining on a maximum of distinct values

Question

I'm trying to solve the following linear programming assignment i've been given:

On a set $\{1,….,N\}$ is defined a discrete cumulative distribution function :

$F(i)=y_i,\ \ i=1,...,N$

With $F(i) ≥ F(i − 1),\ \ ∀i = 2,...,N$. Define an other discrete cumulative distribution function $G$, which approximates $F$.

$G$ shall assume $n<N$ values (distinct possibles values of $G(i)$ are $n$), and shall be defined in a way in which the absolute error (the sum of the differences $|F(i) - G(i)|$) is as low as possible.

I can't translate the fact that $G$ have to assume $n$ distinct values into one or more constraints; do i have to introduce logic variables?

Answer 1

A natural approach is to introduce binary decision variable $x_i$ to indicate whether $G(i)>G(i-1)$ and then impose cardinality constraint $\sum_i x_i \le n-1$ to enforce at most $n-1$ jumps, equivalently at most $n$ different values.