Quadratic-reduction bound on the utilization of one queue of a closed MAP queueing network with a FINITE-CAPACITY station under blocking-after-service. 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_bas.h:

Classes
struct	line::mapqn::QrBasParams< T >
	Parameters of the BAS bound, mirroring the reference's params. More...
struct	line::mapqn::QrBasResult< T >
	Result of a BAS bound solve. More...
struct	line::mapqn::QrBasIndex
	Variable layout: p2(j,nj,kj,i,ni,hi,m) then e(i,ki). More...

Namespaces
namespace	line
namespace	line::mapqn

Functions
template<class T>
QrBasResult< T >	line::mapqn::mapqn_qr_bounds_bas (const QrBasParams< T > &p, int objective_queue, MapqnSense sense=MapqnSense::Min)
	Bound the utilization of one queue over the BAS polytope.

Detailed Description

Quadratic-reduction bound on the utilization of one queue of a closed MAP queueing network with a FINITE-CAPACITY station under blocking-after-service.

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

WHAT BAS MEANS HERE. Station f has capacity F(f). A job completing at station j and routed to a full f cannot move, so j is BLOCKED: it holds the completed job and serves nothing until f frees a slot. The set of currently blocked stations, and the order in which they blocked, is the blocking configuration m in 0..MR-1. Every probability variable carries it, which is what separates this model from mapqn_bnd_qr_ld: the state is (pairwise occupancy, blocking configuration), not occupancy alone.

THE BLOCKING TABLES ARE SUPPLIED, NOT DERIVED. BB, MM, ZZ, ZM and MM1 are caller data here exactly as they are in the reference, where example_bas_small.m writes them out literally. Deriving them from (M, f) would be a different routine and is deliberately not attempted.

FAMILY-BY-FAMILY TRAPS, all verified against the reference and recorded in _kb/03-api-layer.md. Read them before editing any family below:

THM30 and THM3 do NOT share a loop nest. THM30's RHS sums over hj with a coefficient independent of hj (a pure multiplicity); THM3's sums over hi with a coefficient that depends on it. Copying one into the other scales the row by K and still solves.
THM3f is pinned to configuration 0, not looped over m: below capacity there is no blocking, so only the unblocked configuration contributes.
THM3L couples TWO configurations through mp = MM1(m,j), and its RHS variable is the diagonal in mp, not in m.
THM4 is accumulated as (sum nt p2 - N sum p2) and then NEGATED, giving N P(j at (nj,kj), i nonempty) <= sum_t E[n_t ...].
SYMMETRY skips pairs both of whose members are already pinned to zero, so it must run AFTER the ZERO pass. The emission order below is load bearing.

UPPER BOUNDS ARE INFINITE, unlike every other bound in this family. The reference initializes ub = inf and only the ZERO families pin anything; the variables are bounded above through ONE instead. lp::LpModel's default is exactly lb = 0 with a free upper bound, so nothing is set here beyond the ZERO pins.

COST. MR * B^2 + sum_i K(i) columns with B = (N+1) sum_i K(i), so the model is MR times the load-dependent one. The tableau here is dense, which confines the port to small instances; the reference's own paper instance is ~6e4 columns and needs a sparse revised simplex.

Definition in file mapqn_qr_bounds_bas.h.

Classes

Namespaces

Functions

Detailed Description