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

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TidsskriftOperations Research
Vol/bind51
Udgave nummer6
Sider (fra-til)922-939
ISSN0030-364X
DOI
StatusUdgivet - 2003
Udgivet eksterntJa

Emneord

  • Production/distribution: integrating production distribution and inventory
  • Integer programming: Branch-and-price algorithm and penalized knapsack problem

Citer dette

Freling, Richard ; Romeijn, H. Edwin ; Romero Morales, Dolores ; Wagelmans, Albert P. M. / A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem. I: Operations Research. 2003 ; Bind 51, Nr. 6. s. 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 {Romero Morales}, Dolores 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; Romero Morales, Dolores ; Wagelmans, Albert P. M.

I: Operations Research, Bind 51, Nr. 6, 2003, s. 922-939.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

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

AU - Freling, Richard

AU - Romeijn, H. Edwin

AU - Romero Morales, Dolores

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

JF - Operations Research

SN - 0030-364X

IS - 6

ER -