A branch-and-cut algorithm for the capacitated profitable tour problem

Mads Kehlet Jepsen, Bjørn Petersen, Simon Spoorendonk, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved through dynamic programming. In this paper we present an alternative framework based on a formulation for the undirected CPTP and solved through branch-and-cut. Valid inequalities are presented among which we introduce a new family of inequalities for the CPTP denoted rounded multistar inequalities and we prove their validity. Computational experiments are performed on a set of instances known from the literature and a set of newly generated instances. The results indicate that the presented algorithm is highly competitive with the dynamic programming algorithms. In particular, we are able to solve instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to serve as a platform for further development of branch-and-cut algorithms for CPTP hence also acting as a survey/tutorial.
    Original languageEnglish
    JournalDiscrete Optimization
    Volume14
    Pages (from-to)78-96
    ISSN1572-5286
    DOIs
    Publication statusPublished - 2014

    Keywords

    • Branch-and-cut algorithm
    • Valid inequalities
    • Profitable tour problem
    • Capacitated shortest path problem
    • Traveling salesman problem

    Cite this

    Jepsen, Mads Kehlet ; Petersen, Bjørn ; Spoorendonk, Simon ; Pisinger, David. / A branch-and-cut algorithm for the capacitated profitable tour problem. In: Discrete Optimization. 2014 ; Vol. 14. pp. 78-96.
    @article{e8a2e68191ce44efa74698b4295e264a,
    title = "A branch-and-cut algorithm for the capacitated profitable tour problem",
    abstract = "This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved through dynamic programming. In this paper we present an alternative framework based on a formulation for the undirected CPTP and solved through branch-and-cut. Valid inequalities are presented among which we introduce a new family of inequalities for the CPTP denoted rounded multistar inequalities and we prove their validity. Computational experiments are performed on a set of instances known from the literature and a set of newly generated instances. The results indicate that the presented algorithm is highly competitive with the dynamic programming algorithms. In particular, we are able to solve instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to serve as a platform for further development of branch-and-cut algorithms for CPTP hence also acting as a survey/tutorial.",
    keywords = "Branch-and-cut algorithm, Valid inequalities, Profitable tour problem, Capacitated shortest path problem, Traveling salesman problem",
    author = "Jepsen, {Mads Kehlet} and Bj{\o}rn Petersen and Simon Spoorendonk and David Pisinger",
    year = "2014",
    doi = "10.1016/j.disopt.2014.08.001",
    language = "English",
    volume = "14",
    pages = "78--96",
    journal = "Discrete Optimization",
    issn = "1572-5286",
    publisher = "Elsevier",

    }

    A branch-and-cut algorithm for the capacitated profitable tour problem. / Jepsen, Mads Kehlet; Petersen, Bjørn; Spoorendonk, Simon; Pisinger, David.

    In: Discrete Optimization, Vol. 14, 2014, p. 78-96.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - A branch-and-cut algorithm for the capacitated profitable tour problem

    AU - Jepsen, Mads Kehlet

    AU - Petersen, Bjørn

    AU - Spoorendonk, Simon

    AU - Pisinger, David

    PY - 2014

    Y1 - 2014

    N2 - This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved through dynamic programming. In this paper we present an alternative framework based on a formulation for the undirected CPTP and solved through branch-and-cut. Valid inequalities are presented among which we introduce a new family of inequalities for the CPTP denoted rounded multistar inequalities and we prove their validity. Computational experiments are performed on a set of instances known from the literature and a set of newly generated instances. The results indicate that the presented algorithm is highly competitive with the dynamic programming algorithms. In particular, we are able to solve instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to serve as a platform for further development of branch-and-cut algorithms for CPTP hence also acting as a survey/tutorial.

    AB - This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved through dynamic programming. In this paper we present an alternative framework based on a formulation for the undirected CPTP and solved through branch-and-cut. Valid inequalities are presented among which we introduce a new family of inequalities for the CPTP denoted rounded multistar inequalities and we prove their validity. Computational experiments are performed on a set of instances known from the literature and a set of newly generated instances. The results indicate that the presented algorithm is highly competitive with the dynamic programming algorithms. In particular, we are able to solve instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to serve as a platform for further development of branch-and-cut algorithms for CPTP hence also acting as a survey/tutorial.

    KW - Branch-and-cut algorithm

    KW - Valid inequalities

    KW - Profitable tour problem

    KW - Capacitated shortest path problem

    KW - Traveling salesman problem

    U2 - 10.1016/j.disopt.2014.08.001

    DO - 10.1016/j.disopt.2014.08.001

    M3 - Journal article

    VL - 14

    SP - 78

    EP - 96

    JO - Discrete Optimization

    JF - Discrete Optimization

    SN - 1572-5286

    ER -