Approximate linear programming for networks: Average cost bounds

• New approximating functions are proposed to use in approximate dynamic programming for queueing network control.
• Approximate linear programming (ALP) is used to obtain lower bounds on average cost.
• More tractable forms of the linear programs are found using constraint reduction.
• ALPs are solved for a variety of queueing networks with up to 11 buffers.
• Tests on smaller networks achieved an average cost bound within 1–5% of optimal.

This paper uses approximate linear programming (ALP) to compute average cost bounds for queueing network control problems. Like most approximate dynamic programming (ADP) methods, ALP approximates the differential cost by a linear form. New types of approximating functions are identified that offer more accuracy than previous ALP studies or other performance bound methods. The structure of the infinite constraint set is exploited to reduce it to a more manageable set. When needed, constraint sampling and truncation methods are also developed. Numerical experiments show that the LPs using quadratic approximating functions can be easily solved on examples with up to 17 buffers. Using additional functions reduced the error to 1–5% at the cost of larger LPs. These ALPs were solved for systems with up to 6–11 buffers, depending on the functions used. The method computes bounds much faster than value iteration. It also gives some insights into policies. The ALPs do not scale to very large problems, but they offer more accurate bounds than other methods and the simplicity of just solving an LP.