Note on the dominance rules in the exact algorithm for the container pre-marshalling problem by Tanaka & Tierney (2018)

Bo Jin and Mingzhu Yu

European Journal of Operational Research, 2021, vol. 293, issue 2, 802-807

Abstract: In this note, we identify an over-pruning issue that occurs in the iterative deepening branch-and-bound algorithm by Tanaka and Tierney (2018). We show that this over-pruning issue is caused by an inconsistency between two dominance rules, namely, the transitive move rule and the empty stack rule, and it will in turn cause the exact algorithm to produce incorrect optimal solutions. To address this issue, we propose a new concept termed the lexicographic dominance principle, and prove that all dominance rules under the lexicographic dominance principle are mutually consistent. Finally, we re-examine all the dominance rules described in the referred paper, and present a compatible set of dominance rules to guarantee mutual consistency.

Keywords: Container pre-marshalling problem; Dominance rules; Mutual consistency (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720310870
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:293:y:2021:i:2:p:802-807

DOI: 10.1016/j.ejor.2020.12.041

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().