From: len@airgun.wg.waii.com (Lennert den Boer)
Newsgroups: sci.math
Subject: Re: Need fast C implementation of Simplex Method
Date: 1 Mar 1996 09:35:54 GMT

Antonio Iglesias (open58@redestb.es) wrote:
: I am looking for a fast implementation of the Simplex Method, in C if
: possible.
: Our optimization problem is fairly simple (100 constraints,150
: variables aprox.).
: Does anyone know where I can find it?  I am sure there must be
: zillions of implementations of the Simplex Method and many people who
: will not mind sharing them.

: Antonio Iglesias


You might wish to investigate an implementation by Barrodale & Roberts,
published by ACM:

	"Solution to the Constrained L1 Linear Approximation Problem",
	ACM Vol. 6, No. 2, Algorithm 552, 1980.

You might also wish to refer to 2 papers published by B&R:

	"An efficent Algorithm for Discrete L1 Linear Approximation with
	Linear Constraints", Society for Industrial and Applied Mathematics
	(SIAM) Vol. 15, No. 3, June 1978

	"An improved Algorithm for Discret L1 Linear Approximation", SIAM
	Vol. 10, No. 5, October 1973

Their approach owes its efficiency to a clever method for bypassing vertices
on the simplex, thereby improving the rate of convergence as compared to
algorithms like Karmarkar's.

Hope this is of some assistance,
Lennert den Boer