PJO: Generic well posedness in linear programming



		Volume 4, Number 3, September 2008, pp. 513-525
		Roberto Lucchetti, Paola Radrizzani and Silvia Villa
		Key words:
		well posedness, linear programming, genericity
	Mathematices Subject Classification: 49K40, 90C05; 90C46, 90C31


	Abstract:
	We consider the following pair of linear programming problems in duality:

		and

	parameterized by the m × n matrix A defining the inequality constraints. The main result of the paper states that in the case m ≥ n the set S of well posed problems in a very strong sense is a generic subset of the set of problems having solution. Generic here means that S is an open and dense set whose complement is contained in a finite union of algebraic surfaces of dimension less than mn.