A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem

Richard Freling, H. Edwin Romeijn, Dolores Romero Morales, Albert P. M. Wagelmans

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

In this paper, we propose a multiperiod single-sourcing problem (MPSSP), which takes both transportation and inventory into consideration, suitable for evaluating the performance of a logistics distribution network in a dynamic environment. We reformulate the MPSSP as a Generalized Assignment Problem (GAP) with a convex objective function. We then extend a branch-and-price algorithm that was developed for the GAP to this problem. The pricing problem is a so-called Penalized Knapsack Problem (PKP), which is a knapsack problem where the objective function includes an additional convex term penalizing the total use of capacity of the knapsack. The optimal solution of the relaxation of the integrality constraints in the PKP shows a similar structure to the optimal solution of the knapsack problem, that allows for an efficient solution procedure for the pricing problem. We perform an extensive numerical study of the branch-and-price algorithm.
In this paper, we propose a multiperiod single-sourcing problem (MPSSP), which takes both transportation and inventory into consideration, suitable for evaluating the performance of a logistics distribution network in a dynamic environment. We reformulate the MPSSP as a Generalized Assignment Problem (GAP) with a convex objective function. We then extend a branch-and-price algorithm that was developed for the GAP to this problem. The pricing problem is a so-called Penalized Knapsack Problem (PKP), which is a knapsack problem where the objective function includes an additional convex term penalizing the total use of capacity of the knapsack. The optimal solution of the relaxation of the integrality constraints in the PKP shows a similar structure to the optimal solution of the knapsack problem, that allows for an efficient solution procedure for the pricing problem. We perform an extensive numerical study of the branch-and-price algorithm.
LanguageEnglish
JournalOperations Research
Volume51
Issue number6
Pages922-939
ISSN0030-364X
DOIs
StatePublished - 2003
Externally publishedYes

Keywords

    Cite this

    Freling, Richard ; Romeijn, H. Edwin ; Morales, Dolores Romero ; Wagelmans, Albert P. M./ A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem. In: Operations Research. 2003 ; Vol. 51, No. 6. pp. 922-939
    @article{d61459794b10479db5c7b5be5318dc9a,
    title = "A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem",
    abstract = "In this paper, we propose a multiperiod single-sourcing problem (MPSSP), which takes both transportation and inventory into consideration, suitable for evaluating the performance of a logistics distribution network in a dynamic environment. We reformulate the MPSSP as a Generalized Assignment Problem (GAP) with a convex objective function. We then extend a branch-and-price algorithm that was developed for the GAP to this problem. The pricing problem is a so-called Penalized Knapsack Problem (PKP), which is a knapsack problem where the objective function includes an additional convex term penalizing the total use of capacity of the knapsack. The optimal solution of the relaxation of the integrality constraints in the PKP shows a similar structure to the optimal solution of the knapsack problem, that allows for an efficient solution procedure for the pricing problem. We perform an extensive numerical study of the branch-and-price algorithm.",
    keywords = "Production/distribution: integrating production distribution and inventory, Integer programming: Branch-and-price algorithm and penalized knapsack problem",
    author = "Richard Freling and Romeijn, {H. Edwin} and Morales, {Dolores Romero} and Wagelmans, {Albert P. M.}",
    year = "2003",
    doi = "10.1287/opre.51.6.922.24914",
    language = "English",
    volume = "51",
    pages = "922--939",
    journal = "Operations Research",
    issn = "0030-364X",
    publisher = "Institute for Operations Research and the Management Sciences",
    number = "6",

    }

    A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem. / Freling, Richard; Romeijn, H. Edwin; Morales, Dolores Romero; Wagelmans, Albert P. M.

    In: Operations Research, Vol. 51, No. 6, 2003, p. 922-939.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem

    AU - Freling,Richard

    AU - Romeijn,H. Edwin

    AU - Morales,Dolores Romero

    AU - Wagelmans,Albert P. M.

    PY - 2003

    Y1 - 2003

    N2 - In this paper, we propose a multiperiod single-sourcing problem (MPSSP), which takes both transportation and inventory into consideration, suitable for evaluating the performance of a logistics distribution network in a dynamic environment. We reformulate the MPSSP as a Generalized Assignment Problem (GAP) with a convex objective function. We then extend a branch-and-price algorithm that was developed for the GAP to this problem. The pricing problem is a so-called Penalized Knapsack Problem (PKP), which is a knapsack problem where the objective function includes an additional convex term penalizing the total use of capacity of the knapsack. The optimal solution of the relaxation of the integrality constraints in the PKP shows a similar structure to the optimal solution of the knapsack problem, that allows for an efficient solution procedure for the pricing problem. We perform an extensive numerical study of the branch-and-price algorithm.

    AB - In this paper, we propose a multiperiod single-sourcing problem (MPSSP), which takes both transportation and inventory into consideration, suitable for evaluating the performance of a logistics distribution network in a dynamic environment. We reformulate the MPSSP as a Generalized Assignment Problem (GAP) with a convex objective function. We then extend a branch-and-price algorithm that was developed for the GAP to this problem. The pricing problem is a so-called Penalized Knapsack Problem (PKP), which is a knapsack problem where the objective function includes an additional convex term penalizing the total use of capacity of the knapsack. The optimal solution of the relaxation of the integrality constraints in the PKP shows a similar structure to the optimal solution of the knapsack problem, that allows for an efficient solution procedure for the pricing problem. We perform an extensive numerical study of the branch-and-price algorithm.

    KW - Production/distribution: integrating production distribution and inventory

    KW - Integer programming: Branch-and-price algorithm and penalized knapsack problem

    U2 - 10.1287/opre.51.6.922.24914

    DO - 10.1287/opre.51.6.922.24914

    M3 - Journal article

    VL - 51

    SP - 922

    EP - 939

    JO - Operations Research

    T2 - Operations Research

    JF - Operations Research

    SN - 0030-364X

    IS - 6

    ER -