Premium
A three‐stage p ‐median based exact method for the optimal diversity management problem
Author(s) -
Masone Adriano,
Sterle Claudio,
Vasilyev Igor,
Ushakov Anton
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21821
Subject(s) - knapsack problem , solver , mathematical optimization , lagrangian relaxation , reduction (mathematics) , computer science , integer programming , benders' decomposition , mathematics , decomposition , relaxation (psychology) , psychology , ecology , social psychology , geometry , biology
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.