Connectedness and Local Search for Bicriteria Knapsack Problems
Identifieur interne : 003509 ( Istex/Curation ); précédent : 003508; suivant : 003510Connectedness and Local Search for Bicriteria Knapsack Problems
Auteurs : Arnaud Liefooghe [France] ; Luís Paquete [Portugal] ; Marco Sim Es [Portugal] ; José R. Figueira [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: This article reports an experimental study on a given structural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal solutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.
Url:
DOI: 10.1007/978-3-642-20364-0_5
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003551
Links to Exploration step
ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5DLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Connectedness and Local Search for Bicriteria Knapsack Problems</title>
<author><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
<affiliation wicri:level="1"><mods:affiliation>LIFL – CNRS – INRIA Lille-Nord Europe, Université Lille 1, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIFL – CNRS – INRIA Lille-Nord Europe, Université Lille 1</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: arnaud.liefooghe@univ-lille1.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luís" last="Paquete">Luís Paquete</name>
<affiliation wicri:level="1"><mods:affiliation>CISUC, Department of Informatics Engineering, University of Coimbra, Portugal</mods:affiliation>
<country xml:lang="fr">Portugal</country>
<wicri:regionArea>CISUC, Department of Informatics Engineering, University of Coimbra</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: paquete@dei.uc.pt</mods:affiliation>
<country wicri:rule="url">Portugal</country>
</affiliation>
</author>
<author><name sortKey="Sim Es, Marco" sort="Sim Es, Marco" uniqKey="Sim Es M" first="Marco" last="Sim Es">Marco Sim Es</name>
<affiliation wicri:level="1"><mods:affiliation>CISUC, Department of Informatics Engineering, University of Coimbra, Portugal</mods:affiliation>
<country xml:lang="fr">Portugal</country>
<wicri:regionArea>CISUC, Department of Informatics Engineering, University of Coimbra</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: msimoes@student.dei.uc.pt</mods:affiliation>
<country wicri:rule="url">Portugal</country>
</affiliation>
</author>
<author><name sortKey="Figueira, Jose R" sort="Figueira, Jose R" uniqKey="Figueira J" first="José R." last="Figueira">José R. Figueira</name>
<affiliation wicri:level="1"><mods:affiliation>INPL, École des Mines de Nancy, Laboratoire LORIA, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>INPL, École des Mines de Nancy, Laboratoire LORIA</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: jose.figueira@mines.inpl-nancy.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5D</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-20364-0_5</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-SFW4H26L-1/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">003551</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003551</idno>
<idno type="wicri:Area/Istex/Curation">003509</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Connectedness and Local Search for Bicriteria Knapsack Problems</title>
<author><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
<affiliation wicri:level="1"><mods:affiliation>LIFL – CNRS – INRIA Lille-Nord Europe, Université Lille 1, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIFL – CNRS – INRIA Lille-Nord Europe, Université Lille 1</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: arnaud.liefooghe@univ-lille1.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luís" last="Paquete">Luís Paquete</name>
<affiliation wicri:level="1"><mods:affiliation>CISUC, Department of Informatics Engineering, University of Coimbra, Portugal</mods:affiliation>
<country xml:lang="fr">Portugal</country>
<wicri:regionArea>CISUC, Department of Informatics Engineering, University of Coimbra</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: paquete@dei.uc.pt</mods:affiliation>
<country wicri:rule="url">Portugal</country>
</affiliation>
</author>
<author><name sortKey="Sim Es, Marco" sort="Sim Es, Marco" uniqKey="Sim Es M" first="Marco" last="Sim Es">Marco Sim Es</name>
<affiliation wicri:level="1"><mods:affiliation>CISUC, Department of Informatics Engineering, University of Coimbra, Portugal</mods:affiliation>
<country xml:lang="fr">Portugal</country>
<wicri:regionArea>CISUC, Department of Informatics Engineering, University of Coimbra</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: msimoes@student.dei.uc.pt</mods:affiliation>
<country wicri:rule="url">Portugal</country>
</affiliation>
</author>
<author><name sortKey="Figueira, Jose R" sort="Figueira, Jose R" uniqKey="Figueira J" first="José R." last="Figueira">José R. Figueira</name>
<affiliation wicri:level="1"><mods:affiliation>INPL, École des Mines de Nancy, Laboratoire LORIA, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>INPL, École des Mines de Nancy, Laboratoire LORIA</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: jose.figueira@mines.inpl-nancy.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: This article reports an experimental study on a given structural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal solutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003509 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 003509 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5D |texte= Connectedness and Local Search for Bicriteria Knapsack Problems }}
This area was generated with Dilib version V0.6.33. |