Sökning: WFRF:(Quttineh Nils Hassan) >
A theoretical justi...
A theoretical justification of the set covering greedy heuristic of Caprara et al
-
- Larsson, Torbjörn (författare)
- Linköpings universitet,Tillämpad matematik,Tekniska fakulteten
-
- Quttineh, Nils-Hassan (författare)
- Linköpings universitet,Tillämpad matematik,Tekniska fakulteten
-
(creator_code:org_t)
- Elsevier, 2022
- 2022
- Engelska.
-
Ingår i: Discrete Optimization. - : Elsevier. - 1572-5286 .- 1873-636X. ; 45
- Relaterad länk:
-
https://liu.diva-por... (primary) (Raw object)
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Large scale set covering problems have often been approached by constructive greedy heuristics, and much research has been devoted to the design and evaluation of various greedy criteria for such heuristics. A criterion proposed by Caprara et al. (1999) is based on reduced costs with respect to the yet unfulfilled constraints, and the resulting greedy heuristic is reported to be superior to those based on original costs or ordinary reduced costs. We give a theoretical justification of the greedy criterion proposed by Caprara et al. by deriving it from a global optimality condition for general nonconvex optimisation problems. It is shown that this criterion is in fact greedy with respect to incremental contributions to a quantity which at termination coincides with the deviation between a Lagrangian dual bound and the objective value of the feasible solution found.
Ämnesord
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Nyckelord
- Set covering problem; Greedy heuristics; Lagrangian relaxation; Global optimality conditions
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas