mapqn_qr_bounds_rsrd.h File Reference

Quadratic-reduction bound on the utilization of one queue of a closed MAP queueing network under RS-RD blocking (repetitive service, random destination). More...

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

Include dependency graph for mapqn_qr_bounds_rsrd.h:

Go to the source code of this file.

Classes
struct	line::mapqn::QrRsrdParams< T >
	Parameters of the RS-RD bound, mirroring the reference's params. More...
struct	line::mapqn::QrRsrdResult< T >
	Result of an RS-RD bound solve. More...
struct	line::mapqn::QrRsrdIndex
	Variable layout: p2(j,nj,kj,i,ni,hi), then U(i,k,n) and Ueff(i,k,n) for n >= 1, then pb(i). More...

Namespaces
namespace	line
namespace	line::mapqn

Functions
template<class T>
QrRsrdResult< T >	line::mapqn::mapqn_qr_bounds_rsrd (const QrRsrdParams< T > &p, int objective_queue, MapqnSense sense=MapqnSense::Min)
	Bound the utilization of one queue over the RS-RD polytope.

Detailed Description

Quadratic-reduction bound on the utilization of one queue of a closed MAP queueing network under RS-RD blocking (repetitive service, random destination).

Templated port of matlab/lib/qrf/qrf_rsrd.m (ground truth), whose own origin is the AMPL model qrboundsrsrd_skel.mod.

WHAT RS-RD MEANS HERE. A job completing at i and routed to a FULL destination is not held: service is repeated at i and a fresh destination drawn. Nothing is blocked in the BAS sense, so unlike mapqn_qr_bounds_bas there is no blocking-configuration index and the model is far narrower. What the blocking costs instead is EFFECTIVE service: Ueff(i,k,n) subtracts the mass whose chosen destination was full, and pb(i) accumulates the difference.

ITS HALF-INDEX IS NOT THE FAMILY'S. Populations run 0..F(i), not 0..N, so the pairwise half-index is built on F(i)+1 and this model cannot share a layout with any other mapqn bound. Every population loop below is capped by F, and that is deliberate, not an optimization.

THE ONE TRAP, and it is invisible in the output. THM1 is AGGREGATED over nj >= 1: ONE row per (j,kj), not one per (j,kj,nj). The per-nj form is strictly stronger, solves cleanly, and over-tightens the polytope – on the paper's M = 5, N = 20 instance it returns U1min = 0.92508 against the published 0.87058. THM1c is the separate nj = 0 row and is NOT part of that aggregation. The reference carries this warning in its own comment; it is repeated here because a porter reading only the loop nest would not see it.

LOAD DEPENDENCE IS LIVE. Unlike qrf_bas, q here carries alpha(i,n), so the rate depends on the population at the departing queue. The reference indexes it as q{i,j}(k,h,n+1), a 1-based population axis whose first slot is population 0; rsrd_rate below takes the population directly.

ARITHMETIC. Assembly is +, -, * on the model data and lp::simplex_solve uses Bland's rule with no tolerance, so at T = line::Rational the returned bound is the EXACT optimum of the exact polytope.

COST. B^2 + 2 sum_i K(i) F(i) + M columns with B = sum_i (F(i)+1) K(i). No MR factor, so it is much smaller than the BAS model at equal size, but the tableau is still dense: see the ceiling recorded in _kb/03-api-layer.md.

Definition in file mapqn_qr_bounds_rsrd.h.