Excess information in parametric linear optimization

Abstract

We consider a parameteric linear optimization problem (called primal) and its corresponding dual problem, where the parameters are the cost vector and the right-hand-side vector, respectively. This article characterizes those constraints of the primal problem (variables of the dual problem, respectively) which can be eliminated without modifying its feasible set mapping its optimal set mapping, and its value mapping. Superfluity relative to the primal feasible set is nothing else than redundancy in its constraints system, whereas superfluity relative to the dual optimal set is closely related with another well-known phenomenon of excess of information in linear optimization: strong strangeness. The relationships between all these phenomena are also analyzed.

Keywords:

• Linear inequality systems
• Linear programming
• Linear semi-infinite programming
• Excess of information
• Redundancy

Keywords:

• Mathematics Subject Classifications 2000
• 90C34
• 90C05

Acknowledgement

This work was supported by the DGES of Spain, Grant PB98-0975.