[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1288.0. "redundant inequality constraints" by CURIE::RICARD () Sun Aug 19 1990 20:22


Given the set of inequalities Ax <= b (A is an m x n matrix, b is an m vector),
does anyone know of an efficient way of finding the redundant inequalities?

I know they can be found by adding another m vector y (y >= 0) so that

Ax + y = b 

and then solving the linear program:

min y[i]
st  Ax + y = b

for each i.  If the minimum value of any y[i] is greater than zero, than the
ith inequality is redundant.  This involves solving m linear programs, however, 
and I need to do this for large values of m and n.

Does anyone know of a way to do this more efficiently? Perhaps by solving fewer 
than m LPs?


Thanks in advance,

Mike
T.RTitleUserPersonal
Name
DateLines
1288.1LP A-teamHERON::BUCHANANcombinatorial bomb squadMon Aug 20 1990 18:169
>Given the set of inequalities Ax <= b (A is an m x n matrix, b is an m vector),
>does anyone know of an efficient way of finding the redundant inequalities?

	If this is a work-related question, then I know that Tim Cannon of
the Mobil account team is generally interested in helping out in linear
programming issues, although he doesn't scan this notesfile frequently.

Regards,
Andrew.