Sökning: L773:0305 0548 OR L773:1873 765X >
A*-based constructi...
A*-based construction of decision diagrams for a prize-collecting scheduling problem
-
- Horn, Matthias (författare)
- Institute of Logic and Computation, TU Wien
-
- Maschler, Johannes (författare)
- Institute of Logic and Computation, TU Wien
-
- Raidl, Günther R. (författare)
- Institute of Logic and Computation, TU Wien
-
visa fler...
-
- Rönnberg, Elina, 1981- (författare)
- Linköpings universitet,Optimeringslära,Tekniska fakulteten
-
visa färre...
-
(creator_code:org_t)
- Elsevier, 2021
- 2021
- Engelska.
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 126
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://liu.diva-por... (primary) (Raw object)
-
https://doi.org/10.1...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Decision diagrams (DDs) have proven to be useful tools in combinatorial optimization. Relaxed DDs represent discrete relaxations of problems, can encode essential structural information in a compact form, and may yield strong dual bounds. We propose a novel construction scheme for relaxed multi-valued DDs for a scheduling problem in which a subset of elements has to be selected from a ground set and the selected elements need to be sequenced. The proposed construction scheme builds upon A search guided by a fast-to-calculate problem-specific dual bound heuristic. In contrast to traditional DD compilation methods, the new approach does not rely on a correspondence of DD layers to decision variables. For the considered kind of problem, this implies that multiple nodes representing the same state at different layers can be avoided, and consequently also many redundant isomorphic substructures. For keeping the relaxed DD compact, a new mechanism for merging nodes in a layer-independent way is suggested. For our prize-collecting job sequencing problem, experimental results show that the DDs from our A -based approach provide substantially better bounds while frequently being an order-ofmagnitude smaller than DDs obtained from traditional compilation methods, given about the same time. To obtain a heuristic solution and a corresponding lower bound, we further propose to construct a restricted DD based on the relaxed one, thereby substantially exploiting already gained information. This approach outperforms a standalone restricted DD construction, basic constraint programming and mixed integer linear programming approaches, and a variable neighborhood search in terms of solution quality on most of our benchmark instances.
Ämnesord
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Nyckelord
- Decision diagrams
- A* search
- Scheduling
- Sequencing
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas