An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers

DOI10.1007/S10589-015-9725-9MaRDI QIDQ2350866zbMATH OpenOpenAlexWikidataFDO

Authors Ghassan Shobaki, Jafar Jamal

Publication date 25 June 2015

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10589-015-9725-9

zbMATH Keywords

branch-and-bound enumerationcompiler optimizationsinstruction schedulinglow energy computinglow power computingNP-complete problemsprecedence-constrained traveling salesman problemsequential ordering problemswitching energy

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Applications of mathematical programming (90C90)

Recommendations

• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• An efficient genetic algorithm for the traveling salesman problem with precedence constraints
• A heuristic manipulation technique for the sequential ordering problem
• On the sequential ordering problems
• scientific article; zbMATH DE number 1538846

Cites work

• A branch \& cut algorithm for the asymmetric traveling salesman problem with precedence constraints
• A hybrid particle swarm optimization approach for the sequential ordering problem
• An inexact algorithm for the sequential ordering problem
• Constrained TSP and low-power computing
• scientific article; zbMATH DE number 1064419 (Why is no real title available?)
• scientific article; zbMATH DE number 2061755 (Why is no real title available?)
• Introduction to algorithms.
• The Traveling-Salesman Problem and Minimum Spanning Trees

Cited in

(6)

• Branch-and-bound for the precedence constrained generalized traveling salesman problem
• Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• Solving the traveling salesperson problem with precedence constraints by deep reinforcement learning
• Precedence-constrained arborescences
• A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem

Describes a project that uses

Uses Software

• MiBench
• Stony Brook
• HAS-SOP

This page was built for publication: An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2350866)