Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth.
David CoudertDorian MazauricNicolas NissePublished in: ACM J. Exp. Algorithmics (2016)
Keyphrases
- branch and bound algorithm
- experimental evaluation
- lower bound
- branch and bound
- upper bound
- optimal solution
- bounded treewidth
- np hard
- test problems
- search tree
- combinatorial optimization
- randomly generated problems
- precedence constraints
- lower bounding
- single machine scheduling problem
- upper bounding
- finding an optimal solution
- variable ordering
- search algorithm
- max sat
- mixed integer linear programming
- lagrangian relaxation
- lower and upper bounds
- branch and bound method
- maximum clique
- np complete
- dynamic programming