[Acpc-l] Erinnerung:10.12.2001 17h00 Manfred Padberg: Cutting Plane Methods for Mixed-Integer Programming

[Therese Schwarz]

Der Fachbereich Informatik und die Österreichische Computer Gesellschaft
laden zu folgendem Vortrag ein:

****************************************************************************
Cutting Plane Methods for Mixed-Integer Programming
Manfred Padberg
New York University


Zeit: 10.Dezember 2001, 17:00 Uhr ct.
Ort: Zemanek Hörsaal, Favoritenstraße 11/Erdgeschoß/roter Bereich


ABSTRACT: Combinatorial and mixed-integer optimization problems are 
omnipresent in todays
high-technology society. Research over the last 20 to 30 years, of both 
theoretical and numerical
nature, has shown that the most successful technique to solve such problems 
exactly is based
on "cutting planes methods" using embedded linear programs. After defining 
mixed-integer
programs (MIPs) and indicating their relevance to contemporary problem 
solving, we discuss in
this talk cutting plane methods for their resolution. Rules for deriving 
valid inequalities and the
classical (Gomory) cutting planes are surveyed next, including some results 
on recent new cutting
planes (the MIR inequalities). We then relate MIPs with rational data to 
the linear optimization
problem over rational polyhedra and discuss the polynomial-time equivalence 
of optimization and
separation. We conclude with a discussion of branch-and-cut algorithms and 
address the question
of how to integrate classical cutting planes in such a framework.

Short Biography: Manfred Padberg ist Professor of Operations Management an 
der Stern School
of Business an der New York University. Er ist einer der führenden 
Wissenschaftler für die exakte
Lösung NP-schwieriger Optimierungsprobleme, wie z.B. beim crew Scheduling 
oder für das Travelling-
Salesman Instanzen. Dort war er mehrere Male "Weltmeister", d.h. er löste 
eine bis dahin grösste
noch ungelöste TSP-Instanz beweisbar optimal.

Manfred Padberg erhielt zahlreiche Auszeichnungen und Preise. Die 
wichtigsten sind der Lanchester
Prize der Operations Research Society of America (1983), der Dantzig Prize 
der Mathematical
Programming Society and Society for Industrial and Applied Mathematics 
(1985), der Senior U.S.
Scientist Research Award der Alexander von Humboldt-Stiftung (1989), sowie 
der John von Neumann
Theory Prize des Institute for Operations Research and the Management 
Sciences (2000).

Weiterhin ist er Autor der folgenden Bücher:
-- Linear Optimization and Extensions, Springer-Verlag, Berlin, 1995, 
revised and expanded
second edition, 1999.
-- Location, Scheduling, Design and Integer Programming, (with M. Rijal), 
Kluwer Academic
Publishers, Boston, 1996.
-- Linear Optimization and Extensions: Problems and Solutions, (with D. 
Alevras), Springer-
Verlag, Berlin, 2001.



--
Schwarz Therese
Vienna University of Technology - Database & AI Group
A-1040 Vienna, Favoritenstr. 9-11/Stg.2/3. Stock/1842
Tel.: ++43(1)58801-18404, Fax: ++43(1)58801-18492
http://www.dbai.tuwien.ac.at/staff/sek