A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem.
Adam KurpiszSamuli LeppänenMonaldo MastrolilliPublished in: CoRR (2015)
Keyphrases
- single machine scheduling problem
- lower bound
- min sum
- branch and bound algorithm
- semidefinite
- lagrangian relaxation
- np hard
- upper bound
- branch and bound
- precedence constraints
- semidefinite programming
- lower and upper bounds
- optimal solution
- single machine
- worst case
- objective function
- sufficient conditions
- np complete
- higher dimensional
- combinatorial optimization
- genetic algorithm
- higher order
- convex relaxation
- interior point methods
- scheduling problem