On matrices with the Edmonds-Johnson property

ARGOMENTI: Convegni Dottorato

Wednesday 26 November 2008 h. 15:00, room 1C/150
Alberto DEL PIA (Ph.D. in Applied Math., Dip. Mat.)
"On matrices with the Edmonds-Johnson property"

Integer programming is the problem of optimizing a linear function over the integral points in a polyhedron P, expressed as a system of linear inequalities. It is known that it is equivalent to optimizing such linear function over the polyhedron P_I, that is the convex hull of the integral points in P. One of the main problems in mathematical programming is to developed tools to get P_I, and one of such methods is the Chvatal-Gomory procedure. This procedure, starting from P, gives a sequence of smaller polyhedra, P', P'', ..., that converges to P_I in a finite number of iterations. The number of iterations needed to get P_I gives an order of complexity to the problems. We survey some old and new results of classes of problems in which P'=P_I.


Seminario Dottorato del Dipartimento di Matematica P&A di Padova
Organization: Corrado Marastoni - Tiziano Vargiolu - Matteo Dalla Riva
Web page:

Download Seminario Dottorato