mapqn_bnd_qr.h File Reference

General quadratic-reduction (QR) bound on the utilization of one queue-phase of a closed MAP queueing network. More...

#include <cstddef>
#include <string>
#include <vector>
#include "line/api/mapqn/mapqn_p1_common.h"
#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/simplex.h"

Include dependency graph for mapqn_bnd_qr.h:

Go to the source code of this file.

Classes
struct	line::mapqn::MapqnBndQrResult< T >
	Result of a general QR bound solve. More...

Namespaces
namespace	line
namespace	line::mapqn

Typedefs
using	line::mapqn::QrIndex = MapqnP1Index
	Variable layout of the general QR model: the shared p1-level blocks plus the joint p2 block.

Functions
template<class T>
MapqnBndQrResult< T >	line::mapqn::mapqn_bnd_qr (const MapqnParams< T > &p, int objective_queue, int objective_phase, MapqnSense sense=MapqnSense::Max)
	Bound U(objective_queue, objective_phase) over the general QR polytope.

Detailed Description

General quadratic-reduction (QR) bound on the utilization of one queue-phase of a closed MAP queueing network.

Templated port of matlab/lib/qrf/mapqn_bnd_qr.m (ground truth), cross-checked against python/line_solver/api/mapqn/bnd_qr.py. It is NOT ported from jar/src/main/java/jline/api/mapqn/Mapqn_bnd_qr.java, which hardcodes GoalType.MAXIMIZE and takes no sense argument, so it cannot express the lower bound at all (see _kb/03-api-layer.md).

THIS IS NOT mapqn_bnd_qr_ld AT alpha == 1. The load-dependent model relaxes onto the pairwise law p2 alone and imposes 15 families over it. This model carries the singly-indexed p1 and p1c alongside p2, plus the aggregate U, IT, Q and C, and ties the three levels together with the projection families PI21/PI22/PI23. The extra level buys the aggregate inequalities UUB1, QUB1, CUB1, CUB2 and THM4, which have no expression in a pure p2 model. The two polytopes are different relaxations of the same chain and neither contains the other; keep both.

WHAT MAKES IT A BOUND. Every constraint below is satisfied by the exact stationary distribution, and none of them pins it down, so the feasible set is a polytope CONTAINING the exact solution. Optimizing U(i,k) over it therefore brackets the true utilization from whichever side is asked for. The bound is a relaxation, not an approximation: it is valid, not merely close.

THE FAILURE MODE OF THIS FAMILY IS A VACUOUS BOUND, NOT A CRASH. Omit THM30 and THM3 and no constraint mentions mu at all, so U = 0 and U = 1 are both feasible and the routine returns the [0,1] box while every subscript in the file stays internally consistent. That is exactly how the 2026-07-20 defect in mapqn_bnd_qr.m survived (it carried only SRVB and returned [0,1/3] where the true range is [0.1970, 0.2182]). Each family is therefore emitted by a function named after it, so the inventory is diffable against the reference by name. Do not inline them.

INERT VARIABLES OMITTED. The reference registers UP(j,k,i,h), QP(j,k,i,h) and I(j,k,i) and gives them upper bounds, then references them in no constraint and in no objective (verified: UPidx, QPidx and Iidx appear in mapqn_bnd_qr.m only at their own registration and bounding). A variable with no row and no cost cannot move the optimum, so they are not allocated here. This drops 2 (sum_i K(i))^2 + M sum_i K(i) columns and changes no bound.

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. The MATLAB reference reaches it with linprog's 'interior-point' (its 'interior-point-legacy' declares this system infeasible once the balance families are present) and lands a few digits short, so a deviation against MATLAB is expected to be MATLAB's convergence gap, not this port's error.

COST. (N+1) sum_i K(i) is the pairwise half-index B; the model has B^2 + 2 B sum_i K(i) + (M+3) sum_i K(i) columns, so it grows as the fourth power of the population. The tableau is dense, which confines the port to small and medium instances.

Definition in file mapqn_bnd_qr.h.