Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


On Describing the Value Function of a Linear Program by a Reverse Search of Bases

The value function of a linear program gives the optimal objective value as a function of the right-hand-side vector. For minimization problems in standard form the value function is convex and piecewise linear. More precisely, if we denote by $b$ the right-hand-side vector and by $varphi$ the value function then $varphi(b) = max{y^Tb : y in Y}$ where $Y$ is the set of extreme points of the dual polyhedron. In some applications, an analytical description of the value function is needed, where each $y in Y$ is associated with a minimal description of the region of the right-hand-side vectors where $varphi(b) = y^Tb$ (critical region). Such a region turns out to be the polar set of the cone described by the dual constraints active at $y$. The problem of building up an analytical description of the value function and the problem of finding all vertices of a given polyhedron are then strictly related. Several algorithms have been proposed for the solution of the vertex enumeration problem. Among them, the reverse search method proposed by D. Avis and K. Fukuda is particularly appealing for its simplicity and its efficiency. In this talk we discuss how to adapt the reverse search algorithm in order to describe the value function of a linear program, and we suggest different algorithmic approaches. Some computational results on a particular application are reported.

Type of Seminar:
Public Seminar
Dr. Carlo Filippi
Department of Pure and Applied Mathematics - University of Padova Via Belzoni 7 - 35131 Padova - Italy
Mar 08, 2000   17:00

ETH zentrum, Physikstr. 3, 8006 Zurich, ETL K 25
Contact Person:

Dr. Alberto Bemporad
No downloadable files available.
Biographical Sketch:
Carlo Filippi received his Laurea in Statistics from University of Padova in 1988. He did post-lauream studies in computer science from 1989 to 1992. From 1992 he is research associate of operations research at the Science Faculty of the University of Padova. He has taught courses in operations research and optimization, at different student levels. His research interests include sensitivity analysis and parametric programming, network flows optimization and some combinatorial optimization problems arising from scheduling and location. He has published on European Journal of Operational Research,Transportation Science, Operations Research Letters and Ricerca Operativa. He is happily married with Elisabetta and they have two sons, Anna and Gabriele.