The constraint families of the quadratic-reduction (QR) polytope. More...

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

Include dependency graph for mapqn_qr_common.h:

Namespaces
namespace	line
namespace	line::mapqn

Functions
template<class T>
std::vector< char >	line::mapqn::qr_zero_bounds (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	ZERO1/2/3: states that carry no probability mass, imposed as ub = 0.
template<class T>
void	line::mapqn::qr_one (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	ONE: sum over (nj,k) of p2(j,nj,k,j,nj,k) = 1, per queue j.
template<class T>
void	line::mapqn::qr_symmetry (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m, const std::vector< char > &is_zero)
	SYMMETRY: p2(i,ni,h,j,nj,k) = p2(j,nj,k,i,ni,h), emitted once per pair.
template<class T>
void	line::mapqn::qr_marginals (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	MARGINALS: p2(j,nj,k,j,nj,k) = sum over (ni <= N-nj, h) of p2(j,nj,k,i,ni,h) for every i != j.
template<class T>
void	line::mapqn::qr_thm1 (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	THM1 (Little's law in probability form): for each (j,k), sum_{i,nj>=1,ni>=1,h} ni p2(j,nj,k,i,ni,h) = N sum_{nj>=1} p2(j,nj,k,j,nj,k).
template<class T>
void	line::mapqn::qr_thm1c (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	THM1c: the nj = 0 companion of THM1, conditioning on queue j being empty.
template<class T>
void	line::mapqn::qr_pc2 (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	PC2 (second moment): sum_{i,j,ni>=1,nj>=1,h,k} nj ni p2(j,nj,k,i,ni,h) = N^2.
template<class T>
void	line::mapqn::qr_xz (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	XZ (delay model only): the think-time balance sum_{ni>=1,k} ni p2(M,ni,k,M,ni,k) = (Z/D1) sum_{k,nj>=1} p2(1,nj,k,1,nj,k), i.e.
template<class T>
void	line::mapqn::qr_thm2 (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	THM2 (phase balance): for each (i,k) the total rate out of phase k at queue i equals the total rate into it, summed over populations ni >= 1.
template<class T>
void	line::mapqn::qr_thm3a (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	THM3a (population flow balance, 1 <= ni <= N-1): the rate at which queue i is entered while holding ni jobs equals the rate at which it is left while holding ni+1.
template<class T>
void	line::mapqn::qr_thm3b (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	THM3b: the ni = 0 boundary case of THM3a, resolved per arrival phase u.
template<class T>
void	line::mapqn::qr_qbal (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	QBAL (queue balance): LHS1 + LHS2 = RHS1 + RHS2 for each (i,k).
template<class T>
void	line::mapqn::qr_cor1a (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	COR1a: the order-1 correlation cut, for each (i, kstar, ni = 0..N-2).
template<class T>
void	line::mapqn::qr_cor1b (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	COR1b: the ni = N-1 boundary of COR1a (blocks A', C', D', E', H').
template<class T>
void	line::mapqn::qr_thm4 (const MapqnParams< T > &p, const P2Index &idx, lp::LpModel< T > &m)
	THM4 (QMIN): for each (j,k,i), sum_{t,h,nj,nt} nt p2(j,nj,k,t,nt,h) >= N sum_{h,nj,ni} p2(j,nj,k,i,ni,h), the only inequality family.

Detailed Description

The constraint families of the quadratic-reduction (QR) polytope.

mapqn_bnd_qr_ld and mapqn_bnd_qr_delay are the same polytope up to one family: the delay model adds XZ, the think-time balance between the delay station M and the throughput at queue 1. MATLAB keeps two nearly identical 800-line files (mapqn_bnd_qr_ld.m and mapqn_bnd_qr_delay.m differ only in XZ, the order in which PC2 is emitted, and the shape of the returned marginals); the JAR duplicates them again. Here each family is emitted by one function and each entry point calls the families it needs, so a fix to a family cannot land in one entry point and miss the other.

Emitting the families BY NAME is deliberate. The recurring failure mode in this domain is an inventory gap: a file whose every subscript is internally consistent but which omits a whole family, producing a vacuous [0,1] bound that reads as "loose but valid" (see the mapqn notes in _kb/03-api-layer.md). Naming the families makes the inventory diffable against the reference.

Sign convention: every family is assembled as a single accumulated row and emitted as row = 0 or row >= 0, with the reference's right-hand terms carried across with a negative sign rather than dropped. QBAL in particular is LHS1 + LHS2 = RHS1 + RHS2; dropping the RHS terms would force-zero the variables they carry and silently tighten the polytope.

Variable bounds. The reference sets lb = 0, ub = 1 on every variable and ub = 0 on the states the ZERO families exclude. Those are passed to the solver as bounds, not as rows: line::lp::LpModel takes explicit per-variable bounds, substitutes out any variable with lb == ub (which is every ZERO state, the bulk of the model) and materializes a row only for a finite upper bound that is not also a lower bound. The JAR has to add ~2 nVars explicit rows instead, because Apache Commons SimplexSolver does not box variables and the maximization is otherwise unbounded.

Definition in file mapqn_qr_common.h.

Namespaces

Functions

Detailed Description