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

ISBN-13: 9783540115526 / Angielski / Miękka / 1983 / 290 str.

Mark H. Karwan;Vahid Lotfi;J. Telgen

Opis

During the Spring of 1979 one of us (Zionts) was invited to visit Erasmus University in Rotterdam, The Netherlands. It was there that Zionts met another of us (Telgen) who was then in the process of completing a dissertation on redundancy in linear programming. At that time, Telgen proposed an extended visit to Buffalo, during which time he and Zionts would do an extensive study on redundancy. Redundancy, hardly an exciting or new topic, does have numerous applications. Telgen and Zionts planned the project for the Summer of 1980, and enlisted the support of all the contributors as well as the other two members of our team (Karwan and Lotfi). Lotfi was then a Ph. D. student in Industrial Engineering searching for a thesis topic. Redundancy became his topic. Karwan and Zionts served as his thesis co-chairmen, with Telgen serving as an outside reader of the thesis. We initially had hoped to complete the study during Telgen's stay in Buffalo, but that was far too optimistic. Lotfi completed his dissertation during the late Spring-early Summer of 1981. As the project took shape, we decided that we had more than enough for an article, or even several articles. Accordingly, not wanting to produce redundant papers, we decided to produce this volume --- a state-of-the-art review of methods for handling redundancy and comprehensive tests of the various methods, together with extensions and further developments of the most promising methods.

Spis treści

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.