REDUNDANCY IN LINEAR PROGRAMMING PROBLEMS

Abstract

Linear Programming (LP) gives a strong structure to make different real-life problems better. Yet, LP models sometimes show too much repetition. This means that some constraints or variables don’t add much value in the space of solutions, affecting how fast they can be computed and understood as answers. Finding the redundancies helps in understanding the underlying problem and can greatly improve the running time of subsequent computations. Intuitively, we are provided with a problem described by a set of constraints, but only some of them are needed to describe any of its solutions. The constraints that are not needed for this description are redundant. More specifically, we consider the setting of linear programs (LP) in n-variables, given by a linear function that has to be maximized subject to a system of m inequalities. An inequality of this system is called redundant, if after removing it the LP still has the same feasible region, otherwise it is called non-redundant. The main goal of this study is creating a methodical way to find and handle redundancy in LP models. For this, the research initially examines the theoretical basis related to redundancy in LP, including meanings, kinds and consequences. The investigation moves on from theory into real methods used for recognizing redundancy in LPs by looking at methods for constraint and variable redundancy detection. The methods used for constraint redundancy detection are the Bounds method, linear programming method and deterministic method. These techniques attempt to reveal constraints that have no impact on the best possible solution. For finishing the project, a structured methodology is planned to be used. It will have these main stages: reviewing literature, creating LP problem instances that show different application areas, applying redundancy analysis methods, confirming through experiments and case studies, as well as writing down discoveries and suggested actions. Within these stages there are also important elements of testing and validation which guarantee the efficiency and dependability of suggested methods for identifying and handling redundancy in LP models. To end, this project wants to improve how we use and comprehend redundancy analysis in linear programming problems. Through the organized study of redundancy across various constraint types, along with the creation of efficient methods for analysis, our goal is to help enhance optimization for decision-making procedures and resource usage in different situations in real life.