Detection and identification of redundant constraints in a linear program

Date

10-1992

Degree

Bachelor of Science in Applied Mathematics

College

College of Arts and Sciences (CAS)

Adviser/Committee Chair

Norberto R. Navarrete Jr.

Abstract

in many linear programming problems, the system of constraints used to define the feasible set may not be the simplest in the sense that it is possible to find a smaller system that will define the same set. A. common situation is the existence of redundant constraints, that is, constraints of an LP problem that do not affect the feasible set. The identification of such redundant constraints can lead to a significant reduction of the original LP problem. This paper studies different forms of redundancies such as dominant equations, null variables, and nonextremal variables. Moreover, the paper will discuss and illustrate some of the methods for identifying constraints which are actually redundant. These methods involve the identification of dominant equation, null variables, nonextremal variables, and the exploitation of the upper and lower bounding procedure.

Language

English

Location

UPLB Main Library Special Collections Section (USCS)

Call Number

Thesis

Document Type

Thesis

This document is currently not available here.

Share

COinS