M. Ruthmair, G. Raidl:

"An Adaptive Layers Framework for Resource-Constrained Network Design Problems";

Talk: INFORMS Telecommunications Conference, Boca Raton, Florida, USA; 2012-03-15 - 2012-03-17.

Network design problems with resource constraints defined on paths often can be efficiently modeled by using a layered graph approach, in which the original graph is duplicated for each achievable resource value and a resource-indexed mixed integer programming formulation is used. Such formulations are known to have typically tight linear programming relaxation bounds. However, as the number of variables strongly depends on the actual resource bounds, such models may contain huge numbers of variables. We propose a general framework for approximating the linear programming relaxation value of a resource-indexed formulation by a sequence of usually much smaller models. The framework starts with a strongly reduced node set in the layered graph redirecting arcs in a way to provide lower and upper bounds to the linear programming relaxation value of the complete resource-indexed formulation. According to the obtained solutions the layered graph is iteratively extended, decreasing the gap. Additionally, during this approximation procedure the framework can optionally provide a sequence of improving primal solutions. After certain stopping criteria are met the final formulation extended by valid inequalities necessary for guaranteeing feasibility is solved in the usual branch-and-cut way supported by the best obtained primal bound.

Created from the Publication Database of the Vienna University of Technology.