A First-order e-approximation algorithm for linear programs and a second-order implementation

This article presents an algorithm that finds an e-feasible solution relatively to some constraints of a linear program. The algorithm is a first-order feasible directions method with constant stepsize that attempts to find the minimizer of an exponential penalty function. When embedded with bisecti...

Full description

Bibliographic Details
Main Author: Rocha, Ana Maria A. C. (author)
Other Authors: Fernandes, Edite Manuela da G. P. (author), Soares, João L. (author)
Format: conferencePaper
Language:eng
Published: 2005
Subjects:
Linear programs
First-order algorithm
Exponential penalty function
Science & Technology
Online Access:http://hdl.handle.net/1822/5414
Country:Portugal
Oai:oai:repositorium.sdum.uminho.pt:1822/5414
Description
Summary:This article presents an algorithm that finds an e-feasible solution relatively to some constraints of a linear program. The algorithm is a first-order feasible directions method with constant stepsize that attempts to find the minimizer of an exponential penalty function. When embedded with bisection search, the algorithm allows for the approximated solution of linear programs. We present applications of this framework to set-partitioning problems and report some computational results with first-order and second-order implementations.

Similar Items