Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

A Reactive Search for the Quadratic Knapsack Problem

Abstract : In this paper, we propose an reactive method to solve the Quadratic Knapsack Problem (noted QKP). The quadratic knapsack problem is a well-studied combinatorial optimisation problem. In all variants of the quadratic knapsack problems, for a set of given items, profits are not only assigned to individual items but also to pairs of them. The pairwise profit is added to the quadratic objective value only when the two corresponding items are both included in the same knapsack. We let a knapsack with a capacity C and a set of candidate objects (or items), each item has a positive weight w(i) , and profit p(i), if selected, generates an object profit p(i), and a pairwise profit p(ij), with any other selected object j. The objective of the QKP is to select a subset of objects to fill the knapsack so as to maximize the overall profit P,while the overall weight does not exceed the knapsack capacity C. This problem is known as quadratic knapsack problem and has been shown strongly NP-hard and it has been applied with a variety of important applications, such as, in the location of satellites, airports, railway stations or freight terminals. The proposed method is mainly based on two complementary phases.In the first phase we use a greedy algorithm for provide the starting solution. In the second phase we improved the quality of the starting solutions based on a reactive search with applying a destroy and repair process, the reactive phase is based both diversification and intensification strategy. The obtained results are compared to those reached by the Cplex solverl and literature. Consequently, the experimental results show the effectiveness of the proposed approach, and the computational results show that the algorithm is capable of solving instances of the QKP that cannot be solved by other methods.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03617900
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:17
Dernière modification le : vendredi 5 août 2022 - 11:25:00

Identifiants

  • HAL Id : hal-03617900, version 1

Collections

Citation

Najat Al-Iedani, Mhand Hifi, Toufik Saadi. A Reactive Search for the Quadratic Knapsack Problem. 2017 4TH INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Apr 2017, Barcelone, Spain. pp.495-499. ⟨hal-03617900⟩

Partager

Métriques

Consultations de la notice

5