An Equivalent Model for Exactly Solving the Multiple-choice Multidimensional Knapsack Problem
Fuente:
Redalyc
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Artículo científico |
| Lenguaje: | en |
| Publicado: |
International Journal of Combinatorial Optimization Problems and Informatics
2012
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1876452133284347904 |
|---|---|
| author | Mhand Hifi |
| author_facet | Mhand Hifi |
| contents | An Equivalent Model for Exactly Solving the Multiple-choice Multidimensional Knapsack Problem Mhand Hifi Lei Wu Computación Knapsack Heuristic Optimality Lagrangian relaxation The Multiple-choice Multi-dimensional Knapsack Problem (MMKP) is a problem which can be encountered in real-world applications, such as service level agreement, model of allocation resources, or as a dynamic adaptation of system of resources for multimedia multi-sessions. In this paper, we investigate the use of a new model-based Lagrangian relaxation for optimally solving the MMKP. In order to tackle large-scale problem instances, we curtail the search process for providing approximate solutions. We then apply the Cplex solver using both original and equivalent models. In this case, the Cplex solver becomes more efficient when the new model is used. Also, when the proposed method is considered as a heuristic, then it outperforms the Cplex solver using the original model: new solution values are obtained. 2012 artículo científico 2007-1558 https://www.redalyc.org/articulo.oa?id=265224452004 en http://www.redalyc.org/revista.oa?id=2652 International Journal of Combinatorial Optimization Problems and Informatics application/pdf International Journal of Combinatorial Optimization Problems and Informatics International Journal of Combinatorial Optimization Problems and Informatics (México) Num.3 Vol.3 |
| format | Artículo científico |
| id | redalyc_265224452004 |
| institution | Redalyc |
| language | en |
| publishDate | 2012 |
| publisher | International Journal of Combinatorial Optimization Problems and Informatics |
| spellingShingle | An Equivalent Model for Exactly Solving the Multiple-choice Multidimensional Knapsack Problem Mhand Hifi Computación Knapsack Heuristic Optimality Lagrangian relaxation An Equivalent Model for Exactly Solving the Multiple-choice Multidimensional Knapsack Problem Mhand Hifi Lei Wu Computación Knapsack Heuristic Optimality Lagrangian relaxation The Multiple-choice Multi-dimensional Knapsack Problem (MMKP) is a problem which can be encountered in real-world applications, such as service level agreement, model of allocation resources, or as a dynamic adaptation of system of resources for multimedia multi-sessions. In this paper, we investigate the use of a new model-based Lagrangian relaxation for optimally solving the MMKP. In order to tackle large-scale problem instances, we curtail the search process for providing approximate solutions. We then apply the Cplex solver using both original and equivalent models. In this case, the Cplex solver becomes more efficient when the new model is used. Also, when the proposed method is considered as a heuristic, then it outperforms the Cplex solver using the original model: new solution values are obtained. 2012 artículo científico 2007-1558 https://www.redalyc.org/articulo.oa?id=265224452004 en http://www.redalyc.org/revista.oa?id=2652 International Journal of Combinatorial Optimization Problems and Informatics application/pdf International Journal of Combinatorial Optimization Problems and Informatics International Journal of Combinatorial Optimization Problems and Informatics (México) Num.3 Vol.3 |
| title | An Equivalent Model for Exactly Solving the Multiple-choice Multidimensional Knapsack Problem |
| topic | Computación Knapsack Heuristic Optimality Lagrangian relaxation |
| url | https://www.redalyc.org/articulo.oa?id=265224452004 |