On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem.
Naveen GargRohit KhandekarGoran KonjevodR. RaviF. Sibel SalmanAmitabh Sinha IIPublished in: IPCO (2001)
Keyphrases
- network design problem
- valid inequalities
- lp relaxation
- mixed integer
- approximation algorithms
- linear programming
- integer programming
- traveling salesman problem
- linear program
- linear programming relaxation
- mixed integer programming
- network design
- integer programming formulation
- integer program
- lagrangian relaxation
- lower and upper bounds
- cutting plane
- branch and bound
- convex hull
- feasible solution
- special case
- column generation
- transportation networks
- genetic algorithm