School Seminars and Colloquia

An inclusive cone method for linear programming: theory and algorithms

ORSUM Seminar

by Yanqun Liu


Institution: Math & Geospatial Sciences, RMIT
Date: Fri 4th June 2010
Time: 1:00 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

Abstract: We introduce the concept of extended boundedness, termed inclusiveness, which is fundamental to linear programming but has been absent from the linear programming vocabulary. We present a basic duality principle showing that inclusiveness and feasibility are a pair of coexisting and mutually dual properties in linear programming. This duality principle leads to a duality result called `quadrichotomy theorem' which is an improvement of the well known trichotomy theorem (the strong duality theorem). An application of the new duality theory is given.

In addition, we present a class ``exterior climbing methods" for solving general linear programming problems in canonical form: minimizing a linear objective function subject to inequality constraints. This class of methods does not require the variables be restricted. There is no need for slack or artificial variables. Any equality constraints can be eliminated to reduce the problem size. In a sense, this class of methods includes the dual simplex methods as special cases. We will give example exterior climbing algorithms, present a simple way of dealing with degeneracy, and provide convergence results. Initial numerical tests show that these new algorithms are very efficient.

The theory and methods to be presented are expected to give more insight into and refresh our usual understanding of linear programming.

For More Information: contact: Christina Burt. email: c.burt@ms.unimelb.edu.au