Consider the following optimization formulation:
$$\max \, c_1x - \sum_{i=1}^{n} c_i \max(x-a_i, 0) \\ x \geq 0 $$
where $a_i$ and $c_i$ are positive parameters.
I know this problem can be reformulated as an MIP. However, the problem seems to have a nice structure. Is there a way to solve it using another approach (e.g., line search) instead of casting the problem as a MIP?
I'll assume that the problem is
$f(x)=\max c_{0}x - \sum_{i=1}^{n} c_{i} \max(x-a_{i},0)$
The special case where $c_{0}=c_{1}$ is handled by the general solution given here.
Assume without loss of generality that the coefficients $a_{i}$ and $c_{i}$ are sorted so that
$0 < a_{1} \leq a_{2} \leq \ldots \leq a_{n}$.
The function $f(x)$ is concave and piecwise linear. The derivative is discontinous at the points $a_{1}$, $a_{2}$, $\ldots$, $a_{n}$.
For $x<a_{1}$, $f(x)=c_{0}x$, and $f'(x)=c_{0}$.
For $a_{1} < x < a_{2}$, $f(x)=c_{0}x-c_{1}(x-a_{1})$, and $f'(x)=c_{0}-c_{1}$.
For $a_{k} < x < a_{k+1}$, $f(x)=c_{0}x-\sum_{i=1}^{k} c_{i}(x-a_{i})$, and $f'(x)=c_{0}-\sum_{i=1}^{k} c_{i}$.
For $a_{n}<x$, $f(x)=c_{0}-\sum_{i=1}^{n}c_{i}(x-a_{i})$, and $f'(x)=c_{0}-\sum_{i=1}^{n}c_{i}$.
If $c_{0}-\sum_{i=1}^{n}c_{i}>0$, then the function is unbounded as $x \rightarrow \infty$.
Otherwise, there is a point $a_{k}$ such that $f'(x)>0$ for $x<a_{k}$ and $f'(x)<0$ for $x>a_{k}$. The maximum occurs at $x=a_{k}$.
Computationally, this problem can be solved by sorting the $a_{i}$, and then computing $c_{0}-\sum_{i=1}^{k} c_{i}$ for $k=1, 2, \ldots, n$.