Heuristics for the 0―1 multidimensional knapsack problem : Cooperative combinatorial optimization

BOYER, V ; ELKIHEL, M ; et al.

In: European journal of operational research, Jg. 199 (2009), Heft 3, S. 658-664

Online academicJournal - print, 20 ref

Zugriff:

View record from ScienceDirect (Volltext)

Two heuristics for the 0-1 multidimensional knapsack problem (MKP) are presented. The first one uses surrogate relaxation, and the relaxed problem is solved via a modified dynamic-programming algorithm. The heuristics provides a feasible solution for (MKP). The second one combines a limited-branch-and-cut-procedure with the previous approach, and tries to improve the bound obtained by exploring some nodes that have been rejected by the modified dynamic-programming algorithm. Computational experiences show that our approaches give better results than the existing heuristics, and thus permit one to obtain a smaller gap between the solution provided and an optimal solution.

Titel:	Heuristics for the 0―1 multidimensional knapsack problem : Cooperative combinatorial optimization
Autor/in / Beteiligte Person:	BOYER, V ; ELKIHEL, M ; EL BAZ, D
Link:	View record from ScienceDirect (Volltext) E-Journal im Bestand der UB Hagen? View record from PASCAL Archive
Zeitschrift:	European journal of operational research, Jg. 199 (2009), Heft 3, S. 658-664
Veröffentlichung:	Amsterdam: Elsevier, 2009
Medientyp:	academicJournal
Umfang:	print, 20 ref
ISSN:	0377-2217 (print)
Schlagwort:	Control theory, operational research Automatique, recherche opérationnelle Sciences exactes et technologie Exact sciences and technology Sciences appliquees Applied sciences Recherche operationnelle. Gestion Operational research. Management science Recherche opérationnelle et modèles formalisés de gestion Operational research and scientific management Programmation mathématique Mathematical programming Flots dans les réseaux. Problèmes combinatoires Flows in networks. Combinatorial problems Méthode heuristique Heuristic method Método heurístico Méthode séparation et coupe Branch and cut method Método branch and cut Problème sac à dos Knapsack problem Problema mochila Programmation dynamique Dynamic programming Programación dinámica Programmation zero un Zero one programming Programmacion cero uno Système n dimensions Multidimensional system Sistema n dimensiones Branch-and-cut Dynamic-programming Heuristics Multidimensional knapsack problem Surrogate relaxation
Sonstiges:	Nachgewiesen in: PASCAL Archive Sprachen: English Original Material: INIST-CNRS Document Type: Article File Description: text Language: English Author Affiliations: LAAS-CNRS, Université de Toulouse, 7 Avenue du Colonel Roche, 31077 Toulouse, France Rights: Copyright 2009 INIST-CNRS ; CC BY 4.0 ; Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS Notes: Operational research. Management

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.