The optimal diversity management problem (ODMP) arises in many application fields when a company, producing a good and/or a service customizable with options, has to satisfy many different client demands with various subset of options, but only a limited number of option combinations can be produced. ODMP can be represented by a disconnected network and formulated as a large-scale p-median problem (PMP). In this paper we improve a known decomposition approach where smaller PMPs, related to the network components, can be solved instead of the initial large problem. The proposed method is structured in three stages and it combines Lagrangian relaxation-based techniques, variable fixing and reduction tests, and a dynamic programming algorithm. It drastically reduces the number and the dimensions of the p-median subproblems to be solved to optimality by a MIP solver and to be combined to determine the optimal solution of the original PMP by a multiple choice knapsack problem. A sequential and a parallel implementation of the method are provided and tested. Obtained results on known and new test instances show that our approach considerably outperforms state-of-the-art algorithms for large-scale ODMPs.

A three-stage p-median based exact method for the Optimal Diversity Management Problem / Sterle, C.; Masone, A.; Ushakov, A.; Vasilyev, I.. - In: NETWORKS. - ISSN 1097-0037. - 74:2(2019), pp. 174-189. [10.1002/net.21821]

A three-stage p-median based exact method for the Optimal Diversity Management Problem

Sterle C.;Masone A.;
2019

Abstract

The optimal diversity management problem (ODMP) arises in many application fields when a company, producing a good and/or a service customizable with options, has to satisfy many different client demands with various subset of options, but only a limited number of option combinations can be produced. ODMP can be represented by a disconnected network and formulated as a large-scale p-median problem (PMP). In this paper we improve a known decomposition approach where smaller PMPs, related to the network components, can be solved instead of the initial large problem. The proposed method is structured in three stages and it combines Lagrangian relaxation-based techniques, variable fixing and reduction tests, and a dynamic programming algorithm. It drastically reduces the number and the dimensions of the p-median subproblems to be solved to optimality by a MIP solver and to be combined to determine the optimal solution of the original PMP by a multiple choice knapsack problem. A sequential and a parallel implementation of the method are provided and tested. Obtained results on known and new test instances show that our approach considerably outperforms state-of-the-art algorithms for large-scale ODMPs.
2019
A three-stage p-median based exact method for the Optimal Diversity Management Problem / Sterle, C.; Masone, A.; Ushakov, A.; Vasilyev, I.. - In: NETWORKS. - ISSN 1097-0037. - 74:2(2019), pp. 174-189. [10.1002/net.21821]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/707434
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 8
social impact