The Sequential Ordering Problem (SOP) is an NP-hard problem with a wide range of applications in the domains of scheduling, logistics and compilers. The development of powerful computers and effective algorithmic techniques has made it possible to devise exact algorithms that can solve larger instances of this problem. In this paper, we present an enhanced exact algorithm for this problem using a branch-and-bound (B&B) approach. The proposed algorithm is based on a new lower-bound technique and a local-search domination technique. The new lower-bound technique uses the dynamic Hungarian algorithm to solve a Minimum-Cost Perfect Matching relaxation of the SOP. The local search domination technique prunes the sub-tree below the current node in the B&B tree if a better partial solution is found. The performance of the proposed algorithm is evaluated experimentally using three different benchmark suites: TSPLIB, SOPLIB and COMPILERS. The results of the experimental evaluation show that the proposed algorithm finds exact solutions considerably faster than previously proposed algorithms. The proposed approach significantly reduces the optimality gap to 0.217, 0.122, and 0.004 for the three respective benchmark sets, and closes five instances that were previously open.

Solving the sequential ordering problem using branch and bound / Jamal, Jafar Mohammad Jehad A R; Shobaki, G; Papapanagiotou, Vassilis; Gambardella Luca, Maria; Montemanni, Roberto. - 2018-:(2017), pp. 3110-3118. (Intervento presentato al convegno 2017 IEEE Symposium Series on Computational Intelligence, SSCI 2017 tenutosi a Honolulu, USA nel 2017) [10.1109/SSCI.2017.8280805].

Solving the sequential ordering problem using branch and bound

JAMAL, JAFAR MOHAMMAD JEHAD A R;Montemanni Roberto
2017

Abstract

The Sequential Ordering Problem (SOP) is an NP-hard problem with a wide range of applications in the domains of scheduling, logistics and compilers. The development of powerful computers and effective algorithmic techniques has made it possible to devise exact algorithms that can solve larger instances of this problem. In this paper, we present an enhanced exact algorithm for this problem using a branch-and-bound (B&B) approach. The proposed algorithm is based on a new lower-bound technique and a local-search domination technique. The new lower-bound technique uses the dynamic Hungarian algorithm to solve a Minimum-Cost Perfect Matching relaxation of the SOP. The local search domination technique prunes the sub-tree below the current node in the B&B tree if a better partial solution is found. The performance of the proposed algorithm is evaluated experimentally using three different benchmark suites: TSPLIB, SOPLIB and COMPILERS. The results of the experimental evaluation show that the proposed algorithm finds exact solutions considerably faster than previously proposed algorithms. The proposed approach significantly reduces the optimality gap to 0.217, 0.122, and 0.004 for the three respective benchmark sets, and closes five instances that were previously open.
2017
2017
2017 IEEE Symposium Series on Computational Intelligence, SSCI 2017
Honolulu, USA
2017
2018-
3110
3118
Jamal, Jafar Mohammad Jehad A R; Shobaki, G; Papapanagiotou, Vassilis; Gambardella Luca, Maria; Montemanni, Roberto
Solving the sequential ordering problem using branch and bound / Jamal, Jafar Mohammad Jehad A R; Shobaki, G; Papapanagiotou, Vassilis; Gambardella Luca, Maria; Montemanni, Roberto. - 2018-:(2017), pp. 3110-3118. (Intervento presentato al convegno 2017 IEEE Symposium Series on Computational Intelligence, SSCI 2017 tenutosi a Honolulu, USA nel 2017) [10.1109/SSCI.2017.8280805].
File in questo prodotto:
File Dimensione Formato  
08280805.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 927.7 kB
Formato Adobe PDF
927.7 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1177202
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 6
social impact