| 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 |
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.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1288.1 | LP A-team | HERON::BUCHANAN | combinatorial bomb squad | Mon Aug 20 1990 15:16 | 9 |
>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. | |||||