Date:	February 2 (Thu), 2006, 15:00-16:00
	Room:	RIMS, Room 009
	Speaker:	Utz-Uwe Haus (Otto-von-Guericke University of Magdeburg GERMANY, Scientific Assistant)
	Title:	The Integral Basis Method in Primal Integer Programming based on joint works with Robert Weismantel, Matthias Koeppe, Giovanni Rinaldi, Claudio Gentile and Raymond Hemmecke
	Abstract:	The Integral Basis Method was proposed as a new algorithm for solving mixed-integer linear programming problems a few years ago. It is a primal algorithm working in the simplex tableau, and does not resort to branching or cutting planes. This talk will present the basic algorithm (simplex-like phase I, augmentation and optimality proofs), a specialization to the stable set problem, and give a perspective on current research.
	Date:	June 21 (Tuesday), 2005, 14:00--15:00
	Room:	RIMS, Room 206
	Speaker:	H. Narayanan (Indian Institute of Technology, Bombay)
	Title:	An Implicit Duality Theorem and Its Applications
	Abstract:	Duality Theorems of the type (V^{\perp \perp}=V) are fundamental to many areas of Mathematics. We present a way to recast such results in an implicit form when the system has, in addition to `manifest' variables, other variables which are `latent'. The aim is to economically (in time and space) build a new system which is `dual' to the original system in its manifest variables. Such ideas are useful whenever we have to build `adjoints' of systems. We also show that `Implicit Duality' gives a fruitful way of looking at the `hybrid rank problem' for graphs and vector spaces.
	Date:	February 17 (Thu), 2005, 16:00-17:30
	Room:	RIMS, Room 202
	Speaker:	Komei Fukuda (Dept. of Mathematics, EPFL, CH-1015 Lausanne, and Institutes for Operations Research and Theoretical Computer Science, ETH Zentrum, CH-8092 Zurich, Switzerland)
	Title:	Generating all vertices in implicitly defined polytopes
	Abstract:	The classical vertex enumeration problem is a representation conversion problem for convex polytopes, that is, to transform a halfspace representation (H-representation) of a convex polytope to its vertex representation (V-representation). In this talk, we present recent algorithmic advances in the vertex enumeration problem for implicitly defined polytopes and polyhedra where neither H- nor V-representation is available. These include (1) the computation of the vertices of the Minkowski addition of several V-polytopes, (2) the enumeration of all Gr\'obner bases of a polynomial ideal and (3) the computation of the convex hull of several convex polytopes, all in general dimensional Euclidean space. We show that the reverse search scheme can be applied to these problems and lead to practical algorithms that are highly parallelizable. Recent implementations of these algorithms are also reported to indicate the power and the limits of these ``super heavy'' computations that require to solve a large number of small scale LPs.

	Last modified: February 7, 2006