A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints.
Hanif D. SheraliSubhash C. SarinPei-Fang TsaiPublished in: Discret. Optim. (2006)
Keyphrases
- precedence constraints
- branch and bound algorithm
- scheduling problem
- lower bound
- branch and bound
- partially ordered sets
- vertex cover
- np hard
- maximum lateness
- unit length
- upper bound
- release dates
- graphical models
- sequence dependent setup times
- series parallel
- single machine scheduling problem
- precedence relations
- parallel processors
- combinatorial optimization problems
- partially ordered
- parallel machines
- global constraints
- image segmentation
- probabilistic inference
- message passing
- combinatorial optimization
- belief propagation
- shortest path
- optimal solution