Publicación: THE QUADRATIC KNAPSACK PROBLEM WITH SETUP
Fecha
2024
Autores
Título de la revista
ISSN de la revista
Título del volumen
Editor
COMPUTERS AND OPERATIONS RESEARCH
Resumen
THE QUADRATIC KNAPSACK PROBLEM IS A WELL-KNOWN GENERALIZATION OF THE CLASSICAL 0-1 KNAPSACK PROBLEM, IN
WHICH ANY PAIR OF ITEMS PRODUCES A PAIRWISE PROFIT IF BOTH ARE SELECTED. ANOTHER RELEVANT GENERALIZATION OF THE
KNAPSACK PROBLEM IS THE KNAPSACK PROBLEM WITH SETUP, IN WHICH THE ITEMS ARE PARTITIONED INTO CLASSES, THE
ITEMS OF A CLASS CAN ONLY BE INSERTED INTO THE KNAPSACK IF THE CORRESPONDING CLASS IS ACTIVATED, AND ACTIVATING
A CLASS INVOLVES A SETUP COST AND A SETUP CAPACITY REDUCTION.
DESPITE A RICH LITERATURE ON THESE TWO PROBLEMS, THEIR OBVIOUS GENERALIZATION, I.E., THE QUADRATIC KNAPSACK
PROBLEM WITH SETUP, WAS NEVER INVESTIGATED SO FAR. WE DISCUSS APPLICATIONS, MATHEMATICAL MODELS, DETERMINISTIC
MATHEURISTIC ALGORITHMS, AND COMPUTATIONALLY EVALUATE THEIR PERFORMANCE.
Descripción
Palabras clave
Setup constraints, Quadratic knapsack problem, Matheuristic algorithms, Local search
