npfqn_bnd_bpt.h File Reference

First-order linear-programming relaxation of the achievable region of a multiclass open Markovian queueing network. More...

#include <cstddef>
#include <string>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/linalg.h"
#include "line/util/lp_highs.h"
#include "line/util/matrix.h"
#include "line/util/simplex.h"

Include dependency graph for npfqn_bnd_bpt.h:

Go to the source code of this file.

Classes
struct	line::npfqn::BndBpt< T >

Namespaces
namespace	line
namespace	line::npfqn

Functions
template<class T>
BndBpt< T >	line::npfqn::npfqn_bnd_bpt (const std::vector< T > &lambda0, const std::vector< T > &mu, const Matrix< T > &P, const std::vector< std::size_t > &stationOf, const std::vector< T > &c)
	First-order linear-programming relaxation of the achievable region of a multiclass open Markovian queueing network.

Detailed Description

First-order linear-programming relaxation of the achievable region of a multiclass open Markovian queueing network.

Templated port of matlab/src/api/npfqn/npfqn_bnd_bpt.m, cross-checked against jar/src/main/java/jline/api/npfqn/Npfqn_bnd_bpt.java.

Returns a LOWER bound on sum_r c_r x_r, where x_r is the mean sojourn time of class r, valid for EVERY non-idling scheduling policy. A "class" here is a buffer with its own exponential service rate and its own Markovian routing, so a station serving several customer types owns one class per type. The network is open: class r receives external Poisson arrivals at rate lambda0(r) and, on completing service, becomes class r' with probability P(r,r') or leaves with the row deficit.

METHOD. Uniformize the chain and let R(t) = sum_r f(r) n_r(t) for an arbitrary vector f. The steady-state balance of E[R^2] is an identity quadratic in f; since it holds for every f, the two sides' coefficient matrices agree entrywise. Diagonal entries give one equation per class, off-diagonal entries one per unordered pair, in the variables

x_r = E[T_r], the mean sojourn time of class r, I(r,l) = E[1{server sigma(r) busy with class r} n_l], N(i,l) = E[1{server i idle} n_l].

A third block states that the events "station i serves class r" and "station i idle" are mutually exclusive and exhaustive, so their terms sum to E[n_l] = lambda_l x_l. Minimizing over this polyhedron is a relaxation of the achievable region, hence a lower bound.

EXACT ON M/M/1. The LP reduces to mu*I11 - lambda^2*x = lambda and I11 + N11 = lambda*x with N11 >= 0, whence x >= 1/(mu-lambda) with equality.

NOT INCLUDED, DELIBERATELY. The valid inequality I(r,r) >= rho_r would tighten the relaxation but is not part of the reference's characterization, and reproducing the reference's published bounds is the acceptance test.

ARITHMETIC. Rational-clean: the equations are polynomial in the data and the dense simplex is exact, so at T = line::Rational the returned value is the exact optimum of the exact polytope. Nothing here is transcendental.

Reference: D. Bertsimas, I. Paschalidis, J. Tsitsiklis (1994). Optimization of multiclass queueing networks: polyhedral and nonlinear characterizations of achievable performance. Annals of Applied Probability 4(1), 43-75. See also D. Bertsimas (1995), Queueing Systems 21, 337-389, Theorem 9, which restates the same characterization.

Definition in file npfqn_bnd_bpt.h.