Heuristic analysis of a near optimal approximation algorithm for the determination of investment options

Abstract

When cash becomes available in a company, there are several strategies that allowus to benefit from it. The problem is how much to invest, for how long, and using whichof the investment options in order to get the maximum profit out of it. A commonproblem in business administration is that we do not want to keep the money idle inthe checking account, neither to over-invest. When the cash function becomes negativean analogous scheme is used as we want to pay as little interests as possible. In thispaper we are reporting the experiments and implementation of several heuristics thatcan be used with the greedy algorithm and how well they behave. Finally we developa hybrid algorithm that takes the best of the greedy algorithm and performs a verylimited search. We find in this work that with the greedy algorithm we use, in generalis not possible to optimize the profit for a given function; nevertheless the algorithmwe use can find profits that are very close to the optimum and in some cases it getsthe optimum. The proposed algorithm use a heuristic search based on the greedyscheme and greedy selection criteria to find profits close to the optimum. A softwareapplication was developed in order to show that the proposed strategy really works.Although this algorithm is suboptimal, it is very efficient in terms of time.Keywords: Common sense reasoning, knowledge representation,soft decision making,greedy algorithms, financial analysis.

Cuando se tiene disponibilidad de dinero en efectivo en una compa˜n´?a, existenvarias estrategias que nos permiten obtener beneficios de ´este. El problema es determinarcuanto invertir, por cuanto tiempo y que opciones de inversi´on usar para obtenerla m´axima utilidad. Un problema com´un en la administraci´on de negocios es que no sequiere mantener el efectivo ocioso en la cuenta de cheques, ni tampoco sobre invertir.Cuando la funci´on de dinero disponible es negativa, se utiliza un esquema an´alogo, eneste caso se busca pagar la menor cantidad de dinero por intereses generados. En esteart´?culo estamos reportando los experimentos e implementaci´on de varias heur´?sticasque pueden ser usadas con el algoritmo voraz, donde analizamos su desempe˜no. Finalmentese desarrolla un algoritmo h´?brido que toma el mejor resultado de variasheur´?sticas utilizando el algoritmo voraz y hace una b´usqueda muy limitada. En estetrabajo encontramos que con el algoritmo voraz utilizado, no es posible optimizar engeneral la utilidad para un problema dado; sin embargo, el procedimiento utilizadopuede encontrar utilidades muy cercanas al ´optimo y en ocasiones conseguir el ´optimo.Se desarroll´o una aplicaci´on computacional para mostrar que la estrategia propuestarealmente funciona. Aunque el algoritmo propuesto es sub´optimo, es muy eficiente entiempo de procesamiento.Palabras clave: Razonamiento de sentido com´un, representaci