Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1983 | Buch

An Introduction to Redundancy Kapitel lesen Erstes Kapitel lesen

Redundancy in Mathematical Programming

A State-of-the-Art Survey

verfasst von: Prof. Mark H. Karwan, Prof. Vahid Lotfi, Prof. Stanley Zionts, Dr. Jan Telgen

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Economics and Mathematical Systems

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter
Chapter 1. An Introduction to Redundancy
Abstract
Redundancy in mathematical programming is common, being generally brought about by the lack of complete knowledge about the system of constraints and the desire on the part of the problem formulator not to omit essential elements of the formulation. Over the past twenty years numerous papers have been written on redundancy. In those papers methods have been presented for identifying redundancies. This volume presents an up-to-date survey of methods for identifying and removing redundancy and presents the results of extensive empirical tests on these methods. Based on the results of these tests, recommendations for improvements to the methods are made and some of the improvements are tested.
Mark H. Karwan, Vahid Lotfi, Stanley Zionts, Jan Telgen
Chapter 2. Mathematical Foundations and Notation
Abstract
In this chapter we present the definitions, notation, and terminology that will be used in the volume. We define numerous concepts of redundancy, and consider their interrelationships. We then attempt to categorize the methods. Finally, we present some theory common to certain of the methods. The emphasis of the chapter is on linear inequalities and linear programming, but many of the results are readily extendable to more general mathematical programming problems.
Mark H. Karwan, Vahid Lotfi, Stanley Zionts, Jan Telgen
Chapter 3. A Method for Identifying Redundant Constraints and Extraneous Variables in Linear Programming
Abstract
This paper presents a method for identifying redundant constraints and extraneous variables in linear programming problems. The method has evolved from the method of Zionts (1965) (see also Thompson, Tonge and Zionts (1966)) which identified redundant constraints and extraneous variables either prior to or during the solution of linear programming problems. In earlier work (Zionts and Wallenius (1976)) we had to solve a problem that is closely related to identifying all redundant constraints and extraneous variables in a linear programming problem. In Zionts and Wallenius (1980) we show that the method can solve five related problems, one of these problems being the redundant constraint problem. This paper develops the method fully for identifying redundant constraints and extraneous variables.
Stanley Zionts, Jyrki Wallenius
Chapter 4. A Method for Determining Redundant Constraints
Abstract
In finding redundant constraints of a set of linear constraints, the most general case is the task of determining redundant constraints in a set of linear inequalities with variables not restricted in sign. A method for the most general case can be used—possibly with slight modifications—for all systems of linear inequalities. As is well known, difficulties in determining redundant constraints may occur in connection with (primal) degeneracy. Degeneracy may be caused by redundancy itself (weakly redundant constraints — cf. Ch. 2) but not exclusively by redundancy. If degeneracy is caused by both reasons at the same time, we shall call such a case combined degeneracy for short. In order to handle combined degeneracy in connection with determining redundant constraints, the results of Gal (1978) can be used. They are incorporated in the algorithm presented in Section 4.3. The polytope in the illustrative example in Section 4.4 is appropriately degenerate.
Tomas Gal
Chapter 5. Identifying Redundancy in Systems of Linear Constraints
Abstract
The method to be described below is designed to detect redundancy, more specifically, redundant constraints, in systems of linear inequalities. Fundamental to the method is the possibility to recognize redundancy of a constraint by determining the minimum value of the associated slack variable. This property was first mentioned by Lisy (1971) and exploited in Gal (1975b). By defining the structural variables as the slack variables of the nonnegativity constraints (Telgen (1977a)), all variables present in a simplex tableau can be considered as slack variables and treated in the same way. Furthermore, the method heavily draws upon the possibility of identifying (non)redundancy by virtue of certain conditions in a simplex tableau. This approach was first utilized in Zionts (1965) and Thompson, Tonge and Zionts (1966).
Jan Telgen
Chapter 6. Finding Redundant Constraints in Sets of Linear Inequalities
Abstract
Consider the polyhedral set S = {x|x ≥ 0, Ax≤ b}, where A is m × n, x is n × 1, and b is m × 1. After we add slack variables, xn+1,..., xn+m, to the structural constraints, Ax ≤ b, we can also consider the polyhedral set SH = {x|Hx = b, x ≥ 0}, where H = (A, I). SH is an embedding of S in Rn+m. Each variable in the definition of SH can be viewed as a slack variable for one of the constraints defining S, since the “structural variables” (x1,...,xn) can be viewed as the slacks of the nonnegativity constraints (x ≥ 0) defining S. Thus there is a one-to-one correspondence between all the constraints defining S and the nonnegativity constraints in the definition of SH. Hence, the statements, “The kth constraint of S is redundant (nonredundant)” and “The constraint xk ≥ 0 is redundant (nonredundant) in defining SH” are equivalent. We let Sk be obtained from S by deleting the kth constraint.
David S. Rubin
Chapter 7. A Method for Finding Redundant Constraints of a System of Linear Inequalities
Abstract
In principle, any vertex finding algorithm can be employed to find redundant constraints in a system of linear inequalities. All that needs to be noted is the set of constraints active at each vertex visited. Assuming nondegeneracy, any constraint which is active at a vertex is not redundant. For a survey of vertex finding algorithms and some computational experience, see Mattheiss and Rubin (1980).
Theodore H. Mattheiss
Chapter 8. Some Reduction of Linear Programs Using Bounds on Problem Variables
Abstract
Consider the linear programming problem (LPP)
$$ \begin{array}{*{20}c} {maximize} \hfill & {{\text{z}} = cx} \hfill \\ {{\text{subject to}}} \hfill & {{\text{Ax}} \leqslant {\text{b}}} \hfill \\ {} \hfill & {{\text{x}} \geqslant {\text{0}}} \hfill \\ \end{array} $$
(8.1)
and its dual
$$ \begin{array}{*{20}c} {maximize} \hfill & {{\text{v}} = yb} \hfill \\ {{\text{subject to}}} \hfill & {{\text{yA}} \geqslant {\text{c}}} \hfill \\ {} \hfill & {{\text{y}} \geqslant {\text{0}}} \hfill \\ \end{array} $$
(8.2)
with A∈Rm×n, b∈Rm, c∈Rn and y∈Rm, x∈Rn. Assume that both (8.1) and (8.2) have optimal solutions.
Dieter Klein, Soren J. Holm
Chapter 9. A Reduction Procedure for Linear and Integer Programming Models
Abstract
A procedure is described for simplifying linear and integer programming models. The procedure performs tests which may:
i
Detect infeasibility or unboundedness;
 
ii
Detect and remove weakly and strongly redundant constraints;
 
iii
Detect strongly binding constraints and remove them by a suitable adjustment of the objective function;
 
iv
Fix variables and remove them;
 
v
Replace constraints by simple bounds;
 
vi
Replace columns by bounds on shadow prices;
 
vii
Tighten (or relax) bounds on variables and shadow prices.
 
H. Paul Williams
Chapter 10. Preduce — A Probabilistic Algorithm Identifying Redundancy by a Random Feasible Point Generator (RFPG)
Abstract
This chapter describes a probabilistic-type algorithm, PREDUCE (Probabilistic REDUCE) capable of detecting (possibly with an error) several general properties of a given feasible region, by performing a random walk through the region. PREDUCE is mainly designed for redundancy identification. PREDUCE also provides information (at little additional cost) concerning the boundedness, convexity and dimensionality of the feasible region as well as some estimate on the size of the facets enclosing the feasible region and bounds on each of the variables. This type of global information is often desirable, especially in a pre-optimization phase, and is rarely provided by standard algorithms.
Arnon Boneh
Chapter 11. The Noncandidate Constraint Method
Abstract
Thompson, Tonge, and Zionts (1966) defined a redundant constraint in a linear programming problem as one which could be dropped without changing the feasible region. Most linear programs have some redundant constraints, and it would be desirable to be able to identify them. However, the discovery of redundant constraints is computationally extremely costly.
Awanti P. Sethi, Gerald L. Thompson
Chapter 12. Structural Redundancy in Large-Scale Optimization Models
Abstract
This paper discusses automatic detection and exploitation of structural redundancy in large-scale mathematical programming models. From our perspective, such redundancy represents embedded special structure which can give significant insight to the model proponent as well as greatly reduce solution effort. We report experiments with real-life linear programming (LP) and mixed-integer (MIP) models in which various methods are developed and tested as integral modules in an optimization system of advanced design. We seek to understand the modeling implications of these embedded redundancies as well as to exploit them during actual optimization. The latter goal places heavy emphasis on efficient, as well as effective, identification techniques for economic application to large models. Several (polynomially bounded) heuristic detection algorithms are presented from our work. In addition, bounds are reported for a maximum row dimension of the more complex structures. These bounds are useful for objectively estimating the quality of heuristically derived assessments of structural redundancy. Finally, some additional suggestions are made for analyzing nonlinear programming (NLP) models.
Gordon H. Bradley, Gerald G. Brown, Glenn W. Graves
Chapter 13. Programming the Methods and Experimental Design
Abstract
Using the size-reduction techniques presented in Chapters 3 through 11 as a base together with the insights presented in Chapter 12, we programmed and tested all the methods on the CDC Cyber-174 computer system at the State University of New York at Buffalo.
Mark H. Karwan, Vahid Lotfi, Stanley Zionts, Jan Telgen
Chapter 14. Results of the Sign Test Methods
Abstract
In this chapter we present the results of the sign test methods on randomly generated problems as well as on structured problems. The results of the remaining methods will be presented in the next chapter.
Mark H. Karwan, Vahid Lotfi, Stanley Zionts, Jan Telgen
Chapter 15. Results of the Other Methods
Abstract
In the previous chapter, we presented the results of the sign test methods. These methods identified constraints as redundant by minimizing the associated slack variables. In this chapter, we present the results for the remaining five methods (presented in Chapters 7–11). The first two of these methods identify redundant constraints in a different way from the sign test methods. The two methods developed by Boneh and by Mattheiss are also quite different from each other.
Mark H. Karwan, Vahid Lotfi, Stanley Zionts, Jan Telgen
Chapter 16. Improvements and Extensions
Abstract
In Chapters 14 and 15 we presented results of size-reduction techniques on sets of randomly generated and structured problems. In presenting the results, we suggested some changes which have promise for improving the performance of these techniques.
Mark H. Karwan, Vahid Lotfi, Stanley Zionts, Jan Telgen
Chapter 17. Results of the Improvements and Extensions
Abstract
In the previous chapter we presented potential improvements on some of the existing size-reduction techniques. We then proposed some new methods for reducing problem size as well as reducing problem size while solving the problem. These extensions consisted of the extended sign test method, the hybrid method and the reduce method.
Mark H. Karwan, Vahid Lotfi, Stanley Zionts, Jan Telgen
Chapter 18. Conclusions
Abstract
The objective of this volume was to consider the problem of redundancy in mathematical programming and various methods for resolving it, and to evaluate the methods in a comprehensive way. We began by introducing redundancy, the causes of redundancy, and its consequences. We then gave a formal definition of the problem in mathematical terms and introduced our notation (see Chapters 1 and 2 ).
Mark H. Karwan, Vahid Lotfi, Stanley Zionts, Jan Telgen
Backmatter
Metadaten
Titel
Redundancy in Mathematical Programming
verfasst von
Prof. Mark H. Karwan
Prof. Vahid Lotfi
Prof. Stanley Zionts
Dr. Jan Telgen
Copyright-Jahr
1983
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-45535-3
Print ISBN
978-3-540-11552-6
DOI
https://doi.org/10.1007/978-3-642-45535-3