This chapter introduces Integer Linear Programming (ILP) approaches for solving efficiently a ðnancial portfolio design problem. The authors proposed a matricial model in Chapter 3, which is a mathematical quadratic model. A linearization step is considered necessary to apply linear programming techniques. The corresponding matricial model shows clearly that the problem is strongly symmetrical. The row and column symmetries are easily handled by adding a negligible number of new constraints. The authors propose two linear models, which are given in detail and proven. These models represent the problem as linear constraint systems with 0-1 variables, which will be implemented in ILP solver. Experimental results in non-trivial instances of portfolio design problem are given.
TopBackground
Linear Programming was used implicitly by Fourier in the early 1800s. However, it was at first formalized and applied to economic problems, by Leonid Kantorovich in the 1930s. Later, it was rediscovered and applied by Tjalling Koopmans, by tackling shipping problems in the 1940s. The first complete algorithm to solve linear programming problems was published by George Dantzig in 1947. Nevertheless, Koopmans was the one who proposed the name “Linear Programming” in discussion with Dantzig in 1948. Kantorovich and Koopmans shared the 1975 Nobel Prize in Economics for their contributions to the theory of optimum allocation of resources (Erickson, 2015). Whereas George Dantiz, who is the recognized inventor of the Simplex algorithm, was simply passed over by the Nobel awards committee, an act of stunning omission. Dantzig, the inventor of Linear Programming, was honored with the National Medal of Science in 1975. (Erickson, 2015; Nahin, 2007)
To apply linear programming techniques to solve a specific problem, we should model it in a Linear Program (LP) which is based on a linear function (Definition 4.1) and linear inequations (Definition 4.2) (Winston, 2004).
Definition-4.1 (Linear-Function)
A function f(x1,x2,…,xn) of x1,x2,…,xnis a linear function if and only if for some set of constants c1,c2,…,cn, f(x1,x2,…,xn) = c1x1,c2x2,…,cnxn.