I do not know such a software - but we can think about the code. There are tow points which you have to define properly:
- which assets (correspondently, payoffs) are you allowed to replicate the complicated option?
- as barrycarter has already asked - what should be the form of the input?
Further procedure should be quite easy. You are trying to find a linear combination $\lambda$ of basic assets $s_1,s2_,...$ (because in practice this is the only possibility for you to "combine" it) which fits the complex payoff $\gamma$. It's just a peace-wise affine optimization problem. Once you minimize the difference $|\lambda - \gamma|$ you have either zero (so you have found the replication formula) or smth greater than zero (which means that there is no replication formula which perfectly covers this complicated payoff).
Once you will determine the points I've mentioned - I believe I will be able to help you to solve this problem.
Edited: Let us call your payoff $P(S)$ and simple payoff functions are $P_1(S,\theta_1),P_2(S,\theta_2),...$, where $\theta$ are parameters, e.g. strike for Call or Put.
Then you would like to check if there exist $a_1,a_2,...$ such that
P(S) = \sum\limits_i a_i P_i(S,\theta_i).
You can solve this problem by defining
J(a,\theta) = ||P(\cdot) - \sum\limits_i a_i P_i(\cdot,\theta_i)||
where you can use any norm - and in fact due to the structure of payoffs, this norm should be defined only on some finite interval $[0,S']$. Then you solve
and if the extremum value is $0$ - you can cover your exotic payoff with simple ones, if non-zero - you cannot cover it perfectly, but the obtained values of $a,\theta$ will be optimal.
If you need more details about the solution of optimization problem -just tell me.
P.S. I think the paper you have refereed to is not correct - the payoff is not peace-wise affine while they plot it (and considered it) as peace-wise affine function.