Seminars & Events

Mathematics and Computer Science Division
"Continuous Edge-Concave Quadratic Programming Formulations of Discrete Optimization Problems"

DATE: April 11, 2013
TIME: 10:30 AM - 11:30 AM
SPEAKER: James Hungerford, Postdoc Interviewee
LOCATION: Building 240, Seminar Room 4301, Argonne National Laboratory
HOST: Mihai Anitescu

Description:
In 1990, Tardella showed that a sufficient condition for a function to attain its minimum over a polyhedron is that the function is concave along the edges of the polyhedron. We show how this result can be used to formulate two important discrete optimization problems as continuous quadratic programs. These programs possess the beautiful property that local optimality of a feasible point can be checked in polynomial time. Algorithms for solving these these programs will also be discussed.

Save the event to your calendar [schedule.ics]