News & Events
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

    CONTACT Agnes Kaminski    a-kaminski@northwestern.edu EMAIL

    CALENDAR Department of Industrial Engineering and Management Sciences

  • Apr
    30

    Learning and Information Aggregation in Dynamic Games

    Department of Industrial Engineering and Management Sciences (IEMS)

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

    EVENT DETAILS

    TIME Tuesday, April 30, 2024 at 11:00 AM - 12:00 PM

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

    ADD TO CALENDAR

    CONTACT Kendall Minta    kendall.minta@gmail.com EMAIL

    CALENDAR Department of Industrial Engineering and Management Sciences (IEMS)

  • May
    8

    Extending Care: A Conversation about Conservation and Futurity

    Block Museum of Art

    6:00 PM Block Museum of Art, Mary and Leigh

    EVENT DETAILSmore info

    TIME Wednesday, May 8, 2024 at 6:00 PM - 7:30 PM

    LOCATION Block Museum of Art, Mary and Leigh    map it

    ADD TO CALENDAR

    CONTACT Block Museum of Art    block-museum@northwestern.edu EMAIL

    CALENDAR Block Museum of Art

  • Jun
    10

    Northwestern Engineering PhD Hooding and Master's Degree Recognition Ceremony

    McCormick School of Engineering and Applied Science

    9:00 AM Welsh-Ryan Arena

    EVENT DETAILSmore info

    TIME Monday, June 10, 2024 at 9:00 AM - 11:00 AM

    LOCATION Welsh-Ryan Arena   

    ADD TO CALENDAR

    CONTACT Amy Pokrass    amy.pokrass@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Jun
    10

    Northwestern Engineering Undergraduate Convocation

    McCormick School of Engineering and Applied Science

    2:00 PM Welsh-Ryan Arena

    EVENT DETAILSmore info

    TIME Monday, June 10, 2024 at 2:00 PM - 4:00 PM

    LOCATION Welsh-Ryan Arena   

    ADD TO CALENDAR

    CONTACT Amy Pokrass    amy.pokrass@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Aug
    14

    Undergraduate Quantum Summer School

    McCormick School of Engineering and Applied Science

    All Day Ford Motor Company Engineering Design Center

    EVENT DETAILSmore info

    TIME Wednesday, August 14, 2024

    LOCATION Ford Motor Company Engineering Design Center    map it

    ADD TO CALENDAR

    CONTACT Dongyang Li    lidongyang@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Aug
    15

    Undergraduate Quantum Summer School

    McCormick School of Engineering and Applied Science

    All Day Ford Motor Company Engineering Design Center

    EVENT DETAILSmore info

    TIME Thursday, August 15, 2024

    LOCATION Ford Motor Company Engineering Design Center    map it

    ADD TO CALENDAR

    CONTACT Dongyang Li    lidongyang@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science