Redundancy in Mathematical Programming : A State-of-the-Art Survey

1. An Introduction to Redundancy -- 1.1 Redundancy -- 1.2 Causes of Redundancy -- 1.3 Consequences of Redundancy -- 1.4 Dealing with Redundancy -- 1.5 A Survey of the Literature -- 1.6 Objective and Plan of the Study -- 2. Mathematical Foundations and Notation -- 2.1 Notation -- 2.2 Terminology -- 2.3 A Categorization of Methods -- 2.4 Some Common Theory -- 3. A Method for Identifying Redundant Constraints and Extraneous Variables in Linear Programming -- 3.1 An Intuitive Exposition of the Approach -- 3.2 The Algorithm -- 3.3 Theory -- 3.4 An Example -- 3.5 Conclusion -- 4. A Method for Determining Redundant Constraints -- 4.1 An Intuitive Exposition of the Method -- 4.2 The Algorithm -- 4.3 Theoretical Background -- 4.4 An Illustrative Example -- 4.5 Conclusion -- 5. Identifying Redundancy in Systems of Linear Constraints -- 5.1 Introduction -- 5.2 Intuitive Exposition of the Approach -- 5.3 Description of the Algorithm -- 5.4 Mathematical Theory -- 5.5 Special Aspects of the Approach -- 5.6 Example -- 6. Finding Redundant Constraints in Sets of Linear Inequalities -- 6.1 Introduction -- 6.2 Intuitive Exposition of the Approach -- 6.3 The Algorithm -- 6.4 Mathematical Theory -- 6.5 Special Aspects of the Approach -- 6.6 An Example -- 6.7 Conclusion -- 7. A Method for Finding Redundant Constraints of a System of Linear Inequalities -- 7.1 An Intuitive Exposition of the Approach -- 7.2 Description of the Algorithm -- 7.3 Mathematical Theory -- 7.4 Special Aspects of the Approach -- 7.5 An Example -- 7.6 Conclusion -- 8. Some Reduction of Linear Programs Using Bounds on Problem Variables -- 8.1 Introduction -- 8.2 An Intuitive Exposition of the Approach -- 8.3 Description of the Algorithm -- 8.4 Mathematical Theory -- 8.5 Special Aspects of the Approach -- 8.6 An Example -- 8.7 Conclusion -- 9. A Reduction Procedure for Linear and Integer Programming Models -- 9.1 Introduction -- 9.2 Primal and Dual Observations -- 9.3 The Tests -- 9.4 Applying the Tests -- 9.5 Implementation Considerations -- 9.6 Numerical Examples -- 9.7 Conclusions -- 10. Preduce — A Probabilistic Algorithm Identifying Redundancy by a Random Feasible Point Generator (RFPG) -- 10.1 Introduction -- 10.2 An Intuitive Exposition of Algorithm PREDUCE -- 10.3 Description of Algorithm PREDUCE -- 10.4 Mathematical Theory -- 10.5 Special Aspects of PREDUCE -- 10.6 A Numerical Example -- 11. The Noncandidate Constraint Method -- 11.1 Introduction -- 11.2 An Intuitive Explanation of the Method -- 11.3 Description of the Algorithm -- 11.4 Special Aspects of the Noncandidate Method -- 11.5 Solution of an Example -- 11.6 Conclusions -- 12. Structural Redundancy in Large-Scale Optimization Models -- 12.1 Introduction -- 12.2 Overview of the Analysis -- 12.3 Details of the Analysis -- 12.4 Extensions to Mixed Integer and Nonlinear Models -- 12.5 Conclusion -- 12.6 Acknowledgments -- 13. Programming the Methods and Experimental Design -- 13.1 Programming the Methods -- 13.2 Performance Monitoring -- 13.3 Test Problems -- 13.4 Summary -- 14. Results of the Sign Test Methods -- 14.1 Results for the Randomly Generated Problems -- 14.2 Problem Differences -- 14.3 Method Efficiencies Versus Time -- 14.4 Efficiency of the Various Tests -- 14.5 Results for the Structured Problems -- 15. Results of the Other Methods -- 15.1 Boneh’s Method -- 15.2 Mattheiss’ Method -- 15.3 Klein and Holm’s Method -- 15.4 Williams’ Method -- 15.5 The Method of Sethi and Thompson -- 15.6 Summary -- 16. Improvements and Extensions -- 16.1 The Extended Sign Test Method -- 16.2 The Hybrid Method -- 16.3 The Reduce Method -- 17. Results of the Improvements and Extensions -- 17.1 The Extended Sign Test Method -- 17.2 The Hybrid Method -- 17.3 The Reduce Method -- 18. Conclusions -- 18.1 Summary of the Test Results -- 18.2 Other Developments and Conclusions -- References.