Resumen

El problema de empaquetamiento de conjuntos (SPP) es un importante problema de optimización combinatoria NP-duro con amplias aplicaciones. En este trabajo, codificamos el problema de empaquetamiento de conjuntos como el problema del conjunto independiente ponderado máximo (MWIS) y resolvemos el problema codificado con un algoritmo eficiente diseñado para el problema MWIS. Comparamos el método basado en conjuntos independientes con los algoritmos más avanzados para el problema de empaquetamiento de conjuntos en 64 instancias de referencia estándar. Los resultados experimentales muestran que el método basado en conjuntos independientes es superior a los algoritmos existentes en términos de calidad de las soluciones y tiempo de ejecución obtenido las soluciones.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:problema de empaquetamiento de conjuntos, conjunto independiente, problema de optimización combinatoria difícil, conjunto independiente ponderado máximo, instancias de referencia estándar, método, problema, soluciones, problema mwis, algoritmos artísticos
• Keywords:set packing problem, independent set, hard combinatorial optimization problem, maximum weighted independent set, standard benchmark instances, method, problem, solutions, mwis problem, art algorithms