The Lagrangian relaxation for the combinatorial integral approximation problem.
Michael N. JungGerhard ReineltSebastian SagerPublished in: Optim. Methods Softw. (2015)
Keyphrases
- lagrangian relaxation
- integer programming
- relaxation algorithm
- lower bound
- feasible solution
- linear programming
- dynamic programming
- np hard
- lower and upper bounds
- column generation
- capacity constraints
- branch and bound algorithm
- mixed integer programming
- approximation algorithms
- dual decomposition
- single machine scheduling problem
- mixed integer program
- shortest path
- valid inequalities
- subgradient method
- lagrangian heuristic
- linear programming relaxation
- network design problem
- linear program
- branch and bound
- upper bound
- lagrangian dual
- mixed integer linear programs