Department Events

Events

  • Apr
    2

    The traveling salesman problem: postcards from the edge of impossibility

    Department of Industrial Engineering and Management Sciences

    11:00 AM ITW 1.350, Ford Motor Company Engineering Design Center

    EVENT DETAILS

    William Cook, Ph.D.
    University of Waterloo and John Hopkins University

    Abstract: Given a collection of points, the TSP asks for the shortest route to visit them all. Simple enough. But even a whisper of the problem strikes fear in the heart of the computing world. Last year, a Washington Post article reported it would take "1,000 years to compute the most efficient route between 22 cities."
    In an ultimate battle of math+engineering versus the impossible, the impossible wins: it is likely no TSP solution method can have good performance on every data set as the number of points goes off to infinity. That said, the 1,000-year claim ignores over 70 years of intense study. A 22-city TSP can be handled in a snap with modern algorithms, even on an iPhone. Going larger, we describe techniques that have been used to solve to precise optimality examples with nearly 50,000 points and Google Map walking distances. And if we have a couple of million points to visit, say the nearest stars to our sun, then my money is on the math. Indeed, for this particular example, with 2,079,471 stars, we have a route that is guaranteed to be no more than 1.00002 times longer than a shortest possible solution.
    Complexity theory suggests there are limits to the power of general-purpose computational techniques, in engineering, science and elsewhere. But what are these limits and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this context, demonstrating whether or not focused efforts on a single, possibly unsolvable, problem will produce results beyond our expectations.
    Biography: William Cook is a Professor in Applied Mathematics and Statistics at Johns Hopkins University and a University Professor in Combinatorics and Optimization at the University of Waterloo, where he received his Ph.D. in 1983. Bill was elected a SIAM Fellow in 2009, an INFORMS Fellow in 2010, a member of the National Academy of Engineering in 2011, and an American Mathematics Society Fellow in 2012. He is the author of the popular book In Pursuit of the Traveling Saleseman: Mathematics and the Limits of Computation. Bill is a former Editor-in-Chief of the journals Mathematical Programming
    (Series A and B) and Mathematical Programming Computation. He is a past chair of the Mathematical Optimization Society and a past chair of the INFORMS Computing Society.

    more less

    TIME Tuesday, April 2, 2019 at 11:00 AM - 12:00 PM

    LOCATION ITW 1.350, Ford Motor Company Engineering Design Center    map it

    ADD TO CALENDAR SHARE

    CONTACT Agnes Kaminski    a-kaminski@northwestern.edu EMAIL

    CALENDAR Department of Industrial Engineering and Management Sciences

  • Apr
    23

    IEMS Seminar: Open Problems In Contract Theory

    Department of Industrial Engineering and Management Sciences

    11:00 AM M228, Technological Institute

    EVENT DETAILS

    TIME Tuesday, April 23, 2019 at 11:00 AM - 12:00 PM

    LOCATION M228, Technological Institute    map it

    ADD TO CALENDAR SHARE

    CONTACT Agnes Kaminski    a-kaminski@northwestern.edu EMAIL

    CALENDAR Department of Industrial Engineering and Management Sciences

  • May
    1

    Whole-Brain Leadership for PhD Students Seminar Series: Shari Diamond

    McCormick School of Engineering and Applied Science

    12:00 PM ITW classroom, 1-350, Ford Motor Company Engineering Design Center

    EVENT DETAILS

    TIME Wednesday, May 1, 2019 at 12:00 PM - 1:00 PM

    LOCATION ITW classroom, 1-350, Ford Motor Company Engineering Design Center    map it

    ADD TO CALENDAR SHARE

    CONTACT Northwestern Engineering Events    northwestern-engineering-events@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • May
    22

    Whole-Brain Leadership for PhD Students Seminar Series: Todd Rosenthal

    McCormick School of Engineering and Applied Science

    12:00 PM ITW classroom, 1-350, Ford Motor Company Engineering Design Center

    EVENT DETAILS

    TIME Wednesday, May 22, 2019 at 12:00 PM - 1:00 PM

    LOCATION ITW classroom, 1-350, Ford Motor Company Engineering Design Center    map it

    ADD TO CALENDAR SHARE

    CONTACT Northwestern Engineering Events    northwestern-engineering-events@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • May
    31

    Center for Physical Genomics and Engineering Symposium

    McCormick School of Engineering and Applied Science

    9:00 AM Daniel Hale Williams Auditorium, McGaw Pavilion

    EVENT DETAILSmore info

    TIME Friday, May 31, 2019 at 9:00 AM - 5:30 PM

    LOCATION Daniel Hale Williams Auditorium, McGaw Pavilion    map it

    ADD TO CALENDAR SHARE

    CONTACT Ben Keane    b-keane@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Jun
    8

    Spring classes end

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Saturday, June 8, 2019

    ADD TO CALENDAR SHARE

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar