tailieunhanh - A primal-dual exterior point algorithm for linear programming problems

The aim of this paper is to present a new simplex-type algorithm for the Linear Programming Problem. The Primal-Dual method is a Simplex-type pivoting algorithm that generates two paths in order to converge to the optimal solution. | Yugoslav Journal of Operations Research Vol 19 (2009), Number 1, 123-132 DOI: A PRIMAL-DUAL EXTERIOR POINT ALGORITHM FOR LINEAR PROGRAMMING PROBLEMS Nikolaos SAMARAS Angelo SIFELARAS Charalampos TRIANTAFYLLIDIS Department of Applied Informatics, University of Macedonia Greece, Thessaloniki samaras,sifalera,mai0629@ Received: December 2007 / Accepted: June 2009 Abstract: The aim of this paper is to present a new simplex type algorithm for the Linear Programming Problem. The Primal - Dual method is a Simplex - type pivoting algorithm that generates two paths in order to converge to the optimal solution. The first path is primal feasible while the second one is dual feasible for the original problem. Specifically, we use a three-phase-implementation. The first two phases construct the required primal and dual feasible solutions, using the Primal Simplex algorithm. Finally, in the third phase the Primal - Dual algorithm is applied. Moreover, a computational study has been carried out, using randomly generated sparse optimal linear problems, to compare its computational efficiency with the Primal Simplex algorithm and also with MATLAB’s Interior Point Method implementation. The algorithm appears to be very promising since it clearly shows its superiority to the Primal Simplex algorithm as well as its robustness over the IPM algorithm. Keywords: Linear optimization, simplex-type algorithms, primal-dual exterior point algorithm, computational study. 1. INTRODUCTION Linear Programming (LP) is perhaps the most important and best-studied optimization problem. A lot of real world problems can be formulated as linear problems [1], [2] and [4]. The simplex algorithm developed by Dantzig, starts with a primal 124 N. Samaras, A. Sifaleras, C. Triantafyllidis / A Primal Dual Exterior Point feasible basis and uses pivot operations in order to preserve the feasibility of the basis and guarantee monotonicity of the objective value. Many pivot rules .

• Cơ sở dữ liệu
• Linear optimization
• Simplex type algorithms
• Primal dual exterior point algorithm
• Computational study
• Linear Programming Problem
• Ebook Linear optimization
• Linear extensions
• The linear programming problem
• Simplex algorithms
• Primal dual pairs
• Projective algorithms
• Ellipsoid algorithms
• Combinatorial optimization
• Backtracking Search Optimization Algorithm
• Unconstrained non linear function optimization
• BSA and Quadratic approximation
• Non differentiable optimization problem
• Continuous function optimization
• Linear primal dual problems
• Fuzzy environment
• Non linear membership function
• Numerical problem
• Non–linear model
• Kernel function
• Interior point algorithm
• Polynomial complexity
• Primal dual method
• Inventory classification
• Weighted linear optimization
• Multi criteria decision making
• Extended models
• Cross efficiency technique
• Engineering optimization theory
• Classical optimization techniques
• One dimensional minimization methods
• Linear programming I Simplex method
• Additional topics and extensions
• Numerical Method
• Mathematical optimization
• Numerical solutions
• Numerical Method for unconstrained optimization
• Newton's method for nonlinear equations
• Numerical linear algebra background
• Secant methods
• Minimum linear arrangement problem
• Variable neighborhood search
• Solving minimum linear arrangement problem
• Recent optimization problems
• Art heuristic
• Business analytics
• Regression analysis
• forecasting techniques
• Ebook Linear Programming
• Linear Programming
• The Simplex Method
• Sensitivity and Parametric Analyses
• Structural Optimization
• The Affine Scaling Method
• Data mining
• Spreadsheet modeling
• Monte carlo simulation
• Risk analysis
• Integer optimization
• Decision analysis
• Vietnam Journal of Mechanics
• Reservoir optimization with differential evolution
• Non linear Programming
• Undifferential optimal function
• DE to Pleikrong
• The genetic algorithm
• The consequential convex approximation programming
• Composite structure optimization
• Linear elastic fiber reinforced composite laminate
• Differential evolution
• Directed mutation
• Global optimization
• Modified BGA mutation
• Dynamic non linear crossover
• Optimal design
• Derivative free optimization
• Trust region
• Quadratic surrogate model
• Linear accelerator
• Multi Objective Optimization
• Non Dominated Sorting Algorithm II (NSGA II)
• Active Disturbance Rejection Control (ADRC)
• Active disturbance rejection control
• The non linear ALSTOM gasifier
• Performance tests
• Trapezoidal fuzzy number
• Penalty method
• Stochastic methods
• Optimization methods
• Fuzzy Goal Programming
• α Cut Analysis
• Supply Chain Master Planning
• Possibilistic Linear Programming
• Fuzzy multi objective linear model
• Project scheduling with cost minimization
• Construction management
• Project schedule optimization
• Time cost analysis
• Nuclear engineering and technology
• Optimization of operation parameters of 80 kev electron gun
• 80 kev electron gun
• Electron linear accelerator
• The electron generator
• Optimal cropping
• Coastal areas of Odisha
• Maximizing crop production
• Optimization of water resource
• office
• tin học
• pioneering discovery
• combat infections
• genes including Toll
• different non linear
• optimization techniques
• illegal adulterant