A three‐stage p‐median based exact method for the optimal diversity management problem. Issue 2 (26th March 2018)

• Record Type: Journal Article
• Authors: Masone, Adriano; Sterle, Claudio; Vasilyev, Igor; Ushakov, Anton
• Is Part Of: Networks. Volume 74:Issue 2(2019)
• Page Start: 174
• Page End: 189
• Publication Date: 2018-03-26
• Subjects: decomposition -- Lagrangian relaxation -- multiple choice knapsack -- optimal diversity management -- p‐median -- parallel computing; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21821
• Languages: English
• ISSNs: 0028-3045

Abstract

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 article we improve a known decomposition approach where smaller PMP s, 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 ODMP s.