Computer aided discovery of families of valid inequalities

Stefan Røpke, Jean-Francois Cordeau, Gilbert Laporte

    Research output: Contribution to conferenceConference abstract for conferenceResearch

    Abstract

    We present a computer program that helps the user discovering new families of valid inequalities for any integer program. It does so by finding simple valid inequalities that are violated by a fractional solution supplied by the user. It is up to the user to generalize these inequalities further. We present new families of inequalities for the capacitated vehicle routing problem and the traveling salesman problem with pickup and deliveries found using the program.
    Original languageEnglish
    Publication date2009
    Publication statusPublished - 2009
    Event20th International Symposium of Mathematical Programming - Chicago, IL, United States
    Duration: 23 Aug 200928 Aug 2009
    Conference number: 20
    http://ismp2009.eecs.northwestern.edu/

    Conference

    Conference20th International Symposium of Mathematical Programming
    Number20
    CountryUnited States
    CityChicago, IL
    Period23/08/200928/08/2009
    Internet address

    Cite this

    Røpke, S., Cordeau, J-F., & Laporte, G. (2009). Computer aided discovery of families of valid inequalities. Abstract from 20th International Symposium of Mathematical Programming, Chicago, IL, United States.