A new algorithm for solving linear programming problems
Un nuevo algoritmo para la solución de problemas de programación lineal
A. L. Ramírez1, O. Buitrago2, R. A. Britto3, A. Fedossova4
1 Andrés Leonardo Ramírez Leal. Affiliation: Universidad de La Salle. MSc in mathematics, Universidad Nacional de Colombia. BSc. in Chemistry Universidad Nacional de Colombia. E-mail: andres1729@yahoo.com
2 Oscar Yecid Buitrago Suescún. Affiliation: Universidad Militar Nueva Granada, Colombia. MSc in Industrial engineering, Universidad de los Andes, Colombia. BSc. in Chemical Engineering, Universidad Nacional de Colombia. E-mail: oscar.buitrago@unimilitar.edu.co
3 Rodrigo Alberto Britto Agudelo. Affiliation: Universidad de Los Andes, Colombia. PHD in Logistics, Maryland University, United States. MSc in Industrial engineering, Universidad de los Andes, Colombia. BSc. in Chemical engineering, Universidad Nacional de Colombia. E-mail: rab@adm.uniandes.edu.co
4 Alina Fedossova. Affiliation: Universidad Nacional de Colombia. PhD in Mathematics, Moscú State University Lomonosov. BSc. in Mathematics, Moscú State University Lomonosov. E-mail: afedosova@unal.edu.co
ABSTRACT
Linear programming (LP) is one of the most widely-applied techniques in operations research. Many methods have been developed and several others are being proposed for solving LP problems, including the famous simplex method and interior point algorithms. This study was aimed at introducing a new method for solving LP problems. The proposed algorithm starts from an interior point and then carries out orthogonal projections using parametric straight lines to move between the interior and polyhedron frontier defining the feasible region until reaching the extreme optimal point.
Keywords: linear programming, optimisation, orthogonal projection, parametric equation.
RESUMEN
La programación lineal (PL) es una de las herramientas de mayor aplicación en la investigación de operaciones. Se han desarrollado y se siguen proponiendo varios métodos para la resolución de problemas de este tipo, desde el famoso simplex hasta los algoritmos de punto interior. Este trabajo tiene como propósito principal presentar la propuesta de un nuevo procedimiento para la solución de problemas PL que, partiendo de un punto interior, realiza proyecciones ortogonales mediante rectas paramétricas y se mueve iterativamente entre el interior y la frontera del poliedro que define la región factible hasta llegar al punto extremo óptimo.
Palabras clave: programación lineal, optimización, proyecciones ortogonales, ecuaciones paramétricas.
Received: June 21th 2011 Accepted: May 20th 2012
Introduction
Linear programming (LP) dates from 1939 when Leonid Kan-tarovich first expressed a problem in economics in linear form (Bazaraa et al., 1998). However, LP as an area of study has been attributed to George Dantzig who also developed the simplex method in 1947 (Cottle, 2006). LP has been widely studied in engineering programmes, management, mathematics and other fields due to its applicability.
Since its publication, the simplex method (and its variants) was the main tool for solving linear problems until 1980 when Kha-chiyan proposed an ellipsoidal algorithm (Khachiyan, 1982). Although its practical implementation was not very efficient, nevertheless it served as the basis for designing Karmarkar's interior point algorithm (IPA), which is computationally efficient for solving large-sized problems (Karmarkar, 1984) and computationally less complex than the simplex method (Powell, 1993); many additional contributions have been made since then, for example, a primal-dual simplex algorithm (Norman and Curet, 1993) which uses less basis than the original simplex primal-dual, another solves the primal-dual starting from an infeasible interior point (Mizuno, 1994), a projective simplex algorithm using LU decomposition (Pan, 2000), an extension of Karmarkar's IPA having higher convergence speed (Naseri and Valinejad, 2007) and an adaptive primal-dual IPA (Kim, Lee and Cho, 2009). More recently, a proposed IPA based on a new search direction (Zhang and Xu, 2011) and another method based on a new barrier function (Cho, 2011) have been developed.
Considering the large number of areas where LP can be applied and the importance of having efficient algorithms for solving LP problems, any contribution made to LP is very relevant. Consequently, a new method for solving LP problems is presented in this paper.
Formulating the problem
An LP problem's general structure is well-known:
dj being the coefficients of the objective function, xj decision variables, aij the coefficient of the j-th variable in the i-th constraint and bi the right side of the i-th constraint.
An LP problem can also be written in a compact form as follows:
where d denotes the objective function coefficients' vector, A the matrix of constraint coefficients, x a variable vector, b the vector of variables and 0 a vector made up only of zeros.
A maximisation problem will be used from now on as the basis; non-negative constraints have not included since the algorithm did not require them (if required they could have been added as additional constraints). If fj were to represent the j-th row of matrix A in (1), the LP problem could have been rewritten as: max z = dx, subject to: fjx ≤ bj j j=1,2,...,m and hyperplane fjx = bj would have been symbolised as πj
Describing the proposed algorithm
The proposed algorithm had two components: an initialisation stage (non-iterative) and the main cycle (iterative).
Initialisation stage
N-1 orthogonal vectors to objective function gradient ( z = b) were defined. n-1 parametric straight lines from any interior point were also defined during this stage (see Winston, 2005, pp 597-604, explaining how to obtain an interior point with Kar-markar's algorithm). The 2(n-1) intersections of these straight lines were found with faces of a polyhedron defined by the prob-lem's feasible region. The respective centroid C0 was calculated, from which gradient d was projected. This projection's intersec-tion with one of the faces of the polyhedron ended the algo-rithm's initialisation. The steps involved in this stage were.
from where the value of t for straight line πj intersection with hyperplane could be cleared:
to construct straight line:
and intersections with m hyperplanes were found . Substi-tuting the values of obtained from (4) in the respective hy-perplane equations, led to:
Main cycle (iterative)
n-1 orthogonal vectors to objective function gradient ( ) were defined. n-1 parametric straight lines from any interior point were also defined during this stage
Once an algorithm has been initialised, iterative calculations must be made to find an optimal solution. Orthogonal projections were performed from F1, and both its intersections on the faces of the polyhedron and the centroid of these intersections were obtained. From the centroid, the gradient of the objective function was projected and the intersection on one of the faces of the polyhedron was calculated. Repeating this procedure led to coming close to an optimal solution for the required level of precision. The steps in the iterative cycle were:
1. Finding n-1 orthogonal vectors to d so that:
sign ( Fi Ci-1 • fk = or zero
where k was the index of the face on which the last projection was done.
2. Finding the intersections of each straight line Fi + Olt,t ε R with every m hyperplane (note that plane πK could have been excluded):
substituting and clearing led to:
3. Choosing minimum positive value of t for each straight line:
4. Calculating each straight line's (each minimum value of t) points of intersection with the faces of the polyhedron using:
5. Calculating the value of new centroid:
6. Constructing straight line Ci + dt and finding its intersection with m hyperplanes πj
substituting values of xi (5) in the in the respective hyperplane equations, led to:
7. Defining . If the solution was unbounded, this condition was not necessarily detectable in the initialisation stage. This condition was still indicated by the non-existence of at least one positive value of t, in which case the algorithm had terminated.
8. Calculating the coordinates for point Fi on the k-th face of the polyhedron:
9. Comparing the coordinates for Fi+1 with Fi. This was finished if the established precision criterion was satisfied, otherwise one had to return to step 1 and perform another iteration.
Application example
A problem in R2 is presented to illustrate each step in the algo-rithm and graphically visualise it.
The following problem was considered:
Figure 1 shows the feasible region, the objective function gradi-ent and the optimal solution (x1 = 12 x2 = 6).
Initialisation
• Interior point (1 1) was used as P0 so that P0 ε AX < B
• Gradient vector d was = (3 1) and n-1 orthogonal vectors to d had to be defined. O1 (-1 3) was chosen in this case.
• n-1 parametric straight lines were defined. The equation for the straight line was:
• The n-1 parametric straight lines' intersection with hyperplanes πj. was found corresponding values of were calculated:
• Values of t were chosen as follows:
• The coordinates of the intersections with the hyperplanes of the polyhedron were:
• The centroid was calculated as:
its location is shown in Figure 2.
• Straight line was constructed and the intersection with the five hyperplanes t πj was found by calculating:
led to:
Coordinates F1 of the straight line with tmin on the k-th of the polyhedron were calculated:
As seen in Figure 3, point F1 was located on one of the faces of polyhedron and it came close to the optimal point; the main cycle (iterative) then began.
Main cycle
A problem in R2 is presented to illustrate each step in the algorithm and graphically visualise Point F1 was located on face . The first step was to find n-1 vectors
so that:
They were orthogonal to the gradient of objective function d The sign (FC0 • f2) or zero.
The intersection of each straight line FI + OIt with each hyper-plane was found (excluding the plane π2 ).
• The t values indicated that the intersections of straight line
• The minimum positive value for t was chosen:
• Corresponding coordinates of intersection were calculated using t 1min, as seen in Figure 4:
The new centroid value was calculated: (Figure 5).
• The straight line was constructed and its intersection with the five hyperplanes was found from
by calculating:
• Defining
• Calculating the coordinates of point F2 (shown in Figure 6) on the k-th face of the polyhedron:
• Comparing the coordinates of Fi-1 with Fi.
The Euclidean distance of points F1 and F2 to the optimal solu-tion were 0.3063 and 0.2797, respectively. This iterative procedure was repeated until the established precision criterion be-came satisfied.
Conclusions and future research
A new algorithm for solving linear programming problems which does not require slack or excess variables, inverting matrices and the non-negativity of the variables has been presented. The algorithm's complexity and comparison with other methods are important topics for future research currently being investigated by the authors, as well as variations in the algorithm, such as transformation of variables and alternative ways of projection to increase convergence speed.
References
Bazaraa, M. Jarvis, J. & Sherali, H. Programación lineal y flujo en redes, 2 ed en español, México, Limusa, 1998.
Cho, G. An interior-point algorithm for linear optimization based on a new barrier function. Applied Mathematics and Computation, Vol 218, No 2, 2011, pp. 386-395.
Cottle, R W. George B. Dantzig: a legendary life in mathematical programming. Mathematical Programming, Vol 105, No 1, 2006, pp. 1-8.
Karmarkar, N. New Poynomial-Time algorithm for linear program-ming. Combinatorica, Vol 4, No 4, 1984, pp. 373-395.
Khachiyan, L. On the exact solution of systems of linear inequalities and linear programming problems. URSS Computational mathematics and Mathematical Physics, Vol 22, No 4, 1982, pp. 239-242.
Kim, M. Lee, Y. Cho, G. An adaptive-step primaldual interior point algorithm for linear optimization. Nonlinear Analysis, Vol 71, 2009, pp. 2305-2315.
Mizuno, S. A predictor-corrector infeasible-interior-point algorithm for linear programming. Operations Research Letters, Vol 16, No 2, 1994, pp. 61-66.
Naseri, R. Valinejad, A. An extended variant of Karmarkar's interior point algorithm. Applied Mathematics and Computation, Vol 184, 2007, pp. 737-742.
Norman D. Curet, N. A primal-dual simplex method for linear programs. Operations Research Letters, Vol 13, No 4, 1993, pp. 233-237.
Pan, P. A projective Simplex algorithm using LU descomposition. Computers and mathematics with applications, Vol 39, 2000, pp. 187-208.
Powell, M.J.D. On the number of iterations of Karmarkar's algorithm for linear programming. Mathematical Programming, Vol 62, 1993, pp. 153-197.
Winston, W. Investigación de Operaciones, aplicaciones y algoritmos, 4 ed en español, México, Thompson, 2005, pp. 597-604.
Zhang, L. Xu, Y. A full-Newton step interior-point algorithm based on modified Newton direction. Operations Research Letters, Vol 39, 2011, pp. 318-322.