Namespaces
namespace	qrfbas

Classes
struct	LrMvaIndex
	Variable layout: UN, then QN, then B, in the reference's declaration order. More...
struct	LrMvaParams
	Parameters of the MVA-shaped LR bound, mirroring the reference's params. More...
struct	LrPfParams
	Product-form parameters of the LR bound, mirroring MATLAB's params. More...
struct	LrPfResult
	Return value of mapqn_bnd_lr_pf, mirroring the MATLAB result struct. More...
struct	MapqnAmvaResult
	X: class throughputs; Qq: mean queue lengths at the MAP station (job in service included); U: busy probability per class, X E[S]; ES: mean service times; pi: joint phase law at N (class R fastest). More...
struct	MapqnBndLrMvaResult
	Result of an MVA-shaped LR bound solve. More...
struct	MapqnBndLrResult
	Result of a general LR bound solve. More...
struct	MapqnBndQrResult
	Result of a general QR bound solve. More...
struct	MapqnP1Index
	Variable layout of the p1-level models. More...
struct	MapqnParams
	Parameters of a MAP queueing network for the QR bounds. More...
struct	MapqnQrResult
	Result of a QR bound solve. More...
struct	MapqnSolution
	Objective value and the name-keyed variable table of one bound program. More...
struct	P2Index
	Flat index of the joint variable p2(j,nj,k,i,ni,h). More...
struct	QrBasIndex
	Variable layout: p2(j,nj,kj,i,ni,hi,m) then e(i,ki). More...
struct	QrBasParams
	Parameters of the BAS bound, mirroring the reference's params. More...
struct	QrBasResult
	Result of a BAS bound solve. More...
struct	QrfAffine
	An affine residual map recovered as (A, b) with fn(x) = A x - b. More...
struct	QrfConstraints
	The two constraint blocks: g(x) <= 0 and h(x) = 0. More...
struct	QrfMetrics
	The utilizations and queue lengths read off an optimal pair tensor. More...
struct	QrfRates
	The transition rates the constraint inventory reads. More...
struct	QrfReduced
	The equality block with its dependent rows dropped. More...
struct	QrfVars
	The unflattened decision vector: the pair tensor and the effective rates. More...
struct	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...
struct	QrRsrdParams
	Parameters of the RS-RD bound, mirroring the reference's params. More...
struct	QrRsrdResult
	Result of an RS-RD bound solve. More...

Typedefs
using	LrIndex = MapqnP1Index
	Variable layout of the LR model: the shared p1-level blocks and nothing else.
using	QrIndex = MapqnP1Index
	Variable layout of the general QR model: the shared p1-level blocks plus the joint p2 block.

Enumerations
enum class	MapqnObjectiveVar { UN , QN }
	The variable family the objective is taken over. More...
enum class	MapqnSense { Max , Min }
	Which direction the bound is taken in. More...

Functions
template<class T>
MapqnAmvaResult< T >	mapqn_amva (const std::vector< T > &mu_in, const std::vector< Matrix< T > > &D0s, const std::vector< Matrix< T > > &D1s, const std::vector< int > &N)
template<class T>
MapqnBndLrResult< T >	mapqn_bnd_lr (const MapqnParams< T > &p, int objective_queue, int objective_phase, MapqnSense sense=MapqnSense::Max)
	Bound U(objective_queue, objective_phase) over the linear-reduction polytope.
template<class T>
MapqnBndLrMvaResult< T >	mapqn_bnd_lr_mva (const LrMvaParams< T > &p, int objective_queue, int objective_level, MapqnSense sense=MapqnSense::Max, MapqnObjectiveVar objective_var=MapqnObjectiveVar::UN)
	Bound UN or QN at (objective_queue, objective_level) over the MVA-shaped LR polytope.
template<class T>
LrPfResult< T >	mapqn_bnd_lr_pf (const LrPfParams< T > &p, int objective_queue, MapqnSense sense)
	Port of mapqn_bnd_lr_pf.
template<class T>
MapqnBndQrResult< T >	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.
template<class T>
MapqnQrResult< T >	mapqn_bnd_qr_delay (const MapqnParams< T > &p, int objective_queue, int objective_phase, int objective_n, MapqnSense sense=MapqnSense::Max)
	Bound P(queue objective_queue holds objective_n jobs in phase objective_phase) for a network with a delay station at queue M.
template<class T>
MapqnQrResult< T >	mapqn_bnd_qr_ld (const MapqnParams< T > &p, int objective_queue, int objective_phase, int objective_n, MapqnSense sense=MapqnSense::Max)
	Bound P(queue objective_queue holds objective_n jobs in phase objective_phase), in the requested direction.
template<class T>
T	mapqn_q (const MapqnParams< T > &p, int i, int j, int k, int h, int n)
	q(i,j,k,h,n): rate at which queue i, holding n jobs and in phase k, moves to phase h while routing a job to queue j.
template<class T>
QrBasResult< T >	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.
template<class T>
QrRsrdResult< T >	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.
template<class T>
std::vector< char >	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	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	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	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	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	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	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	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	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	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	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	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	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	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	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.
template<class T>
QrfMetrics< T >	mapqn_qrf_bas (const QrBasParams< T > &p, qrfbas::Objective obj, unsigned max_iter=200)
	Solve one BAS-blocking NLP bound.
template<class T>
QrfMetrics< T >	mapqn_qrf_bas_mmi (const QrBasParams< T > &p, unsigned max_iter=200)
	Minimum-mutual-information bound on the BAS-blocking polytope.
template<class T>
QrfMetrics< T >	mapqn_qrf_bas_mem (const QrBasParams< T > &p, unsigned max_iter=200)
	Maximum-entropy bound on the BAS-blocking polytope.
template<class T>
QrfMetrics< T >	mapqn_qrf_bas_bethe (const QrBasParams< T > &p, unsigned max_iter=200)
	Tree-reweighted (Bethe) free entropy bound on the BAS-blocking polytope.
template<class T>
T	qrf_log (const T &v)
	log() in the working arithmetic.
template<class T>
T	qrf_logtol ()
	The reference's LOGTOL: the shift that keeps log() off zero.
std::size_t	qrf_num_vars (std::size_t M, std::size_t N, const std::vector< int > &K, std::size_t MR)
	Number of decision variables the layout actually USES.
std::vector< long >	qrf_index_map (std::size_t M, std::size_t N, const std::vector< int > &K, std::size_t MR)
	Flat position of every p2 entry, in the FILL ORDER of sub_qrfvar.
template<class T>
QrfVars< T >	sub_qrfvar (const std::vector< T > &x, std::size_t M, std::size_t N, const std::vector< int > &K, std::size_t MR)
	Unflatten x into the pair tensor and the effective rates.
template<class T>
T	mmi_objective (const std::vector< T > &x, std::size_t M, std::size_t N, const std::vector< int > &K, const std::vector< int > &F, std::size_t MR)
	Mutual-information objective.
template<class T>
T	mem_objective (const std::vector< T > &x, std::size_t M, std::size_t N, const std::vector< int > &K, const std::vector< int > &F, std::size_t MR)
	Maximum-entropy objective, returned as the NEGATIVE entropy +sum p log p over the diagonal entries, because the solver MINIMIZES and the AMPL model states this objective as maximize H.
template<class T>
std::vector< T >	mmi_gradient (const std::vector< T > &x, std::size_t M, std::size_t N, const std::vector< int > &K, const std::vector< int > &F, std::size_t MR, const std::vector< long > &idx)
	Gradient of mmi_objective.
template<class T>
std::vector< T >	mem_gradient (const std::vector< T > &x, std::size_t M, std::size_t N, const std::vector< int > &K, const std::vector< int > &F, std::size_t MR, const std::vector< long > &idx)
	Gradient of mem_objective: d/dp of p log(p') is log p' + p/p'.
template<class T>
T	bethe_objective (const std::vector< T > &x, std::size_t M, std::size_t N, const std::vector< int > &K, const std::vector< int > &F, std::size_t MR)
	Tree-reweighted (Bethe) free entropy at the uniform spanning-tree weight, the objective of qrf.bethe.
template<class T>
std::vector< T >	bethe_gradient (const std::vector< T > &x, std::size_t M, std::size_t N, const std::vector< int > &K, const std::vector< int > &F, std::size_t MR, const std::vector< long > &idx)
	Gradient of bethe_objective.
template<class T>
QrfMetrics< T >	qrf_extract_results (const QrfVars< T > &v, std::size_t M, const std::vector< int > &K, const std::vector< int > &F, std::size_t MR, const Matrix< T > *alpha=nullptr)
	extract_results: the diagonal marginals of the optimal tensor, plus the alpha-weighted mean BN.
template<class T>
std::vector< std::size_t >	qrf_independent_rows (const Matrix< T > &A, double tol=-1.0)
	Rows of a maximal linearly independent subset of A, by pivoted Gram-Schmidt.
template<class T, class Fn>
QrfAffine< T >	qrf_affine_matrices (Fn fn, std::size_t n)
	Recover (A, b) from an affine residual map.
template<class T>
QrfReduced< T >	qrf_reduce_equalities (const Matrix< T > &A, const std::vector< T > &b)
	Drop the linearly dependent equality rows, keeping the feasible set exact.
template<class T>
lp::LpModel< T >	qrf_polytope (const Matrix< T > &Aeq, const std::vector< T > &beq, const Matrix< T > &Aub, const std::vector< T > &bub, std::size_t n)
	The polytope of a QRF instance, as an LpModel over the box [0,1]^n.
template<class T>
Matrix< T >	qrf_null_space (const Matrix< T > &A, std::size_t n)
	Orthonormal basis of null(A), as an (n x d) matrix.
template<class T, class Obj, class Grad>
std::vector< T >	solve_qrf_nlp_lp (Obj objective, Grad gradient, const std::vector< T > &x0, const lp::LpModel< T > &polytope, const std::string &name, unsigned max_iter=200, double gap_tol=1e-10)
	Minimize a convex objective over {Aeq x = beq, Aub x <= bub, 0 <= x <= 1}, starting from a feasible point, by FRANK-WOLFE.
template<class T, class Obj, class Grad>
std::vector< T >	solve_qrf_nlp (Obj objective, Grad gradient, const std::vector< T > &x0, const Matrix< T > &Aeq, const std::vector< T > &beq, const Matrix< T > &Aub, const std::vector< T > &bub, const std::string &name, unsigned max_iter=200, double gap_tol=1e-10)
	The same, with the polytope given as matrices rather than as an LpModel.
template<class T>
std::vector< T >	qrf_min_norm_point (const lp::LpModel< T > &polytope, const std::vector< T > &x0, const std::string &name)
	The minimum-norm point of the polytope, from any feasible point of it.
template<class T>
std::vector< T >	qrf_feasible_start_lp (const lp::LpModel< T > &polytope, const std::string &name)
	A feasible point of an LpModel polytope: the MINIMUM-NORM one.
template<class T>
std::vector< T >	qrf_feasible_start (const Matrix< T > &Aeq, const std::vector< T > &beq, const Matrix< T > &Aub, const std::vector< T > &bub, std::size_t n)
	A point of the polytope, as the phase 1 of qrf_noblo_start.m.
template<class T>
QrfRates< T >	qrf_build_q (std::size_t M, const std::vector< int > &K, const Matrix< T > &mu, const Matrix< T > &v, const Matrix< T > &rt)
	build_q_from_mu_v_rt: the population-free rates.
template<class T>
QrfRates< T >	qrf_build_q_ld (std::size_t M, const std::vector< int > &K, const Matrix< T > &mu, const Matrix< T > &v, const Matrix< T > &rt, std::size_t N, const Matrix< T > &alpha)
	build_q_ld: the load-dependent rates.
template<class T>
void	qrf_extract_mu_v (const std::vector< std::pair< Matrix< T >, Matrix< T > > > &MAPs, std::size_t M, const std::vector< int > &K, Matrix< T > mu, Matrix< T > v)
	extract_mu_v_from_maps: the completion and background rates of each MAP.
template<class T>
QrfConstraints< T >	sub_qrfcon_noblo (const std::vector< T > &x, const QrfRates< T > &q, std::size_t M, std::size_t MR, const Matrix< int > &BB, const std::vector< int > &F, std::size_t N, const std::vector< int > &K)
	The full no-blocking constraint inventory, sub_qrfcon_noblo.
template<class T>
QrfMetrics< T >	qrf_noblo_mmi (std::size_t M, const std::vector< int > &K, std::size_t N, const Matrix< T > &mu, const Matrix< T > &v, const Matrix< T > &rt)
	qrf_noblo_mmi: the no-blocking bound under mutual-information minimization.
template<class T>
QrfMetrics< T >	qrf_noblo_bethe (std::size_t M, const std::vector< int > &K, std::size_t N, const Matrix< T > &mu, const Matrix< T > &v, const Matrix< T > &rt)
	qrf_noblo_bethe: the same polytope under the tree-reweighted free entropy.
template<class T>
QrfMetrics< T >	qrf_noblo_mem (const std::vector< std::pair< Matrix< T >, Matrix< T > > > &MAPs, std::size_t N, const Matrix< T > &rt)
	qrf_noblo_mem: the same polytope under maximum entropy.
template<class T>
QrfMetrics< T >	qrf_noblo_mmi_ld (std::size_t M, const std::vector< int > &K, std::size_t N, const Matrix< T > &mu, const Matrix< T > &v, const Matrix< T > &rt, const Matrix< T > &alpha)
	qrf_noblo_mmi_ld: MMI on the LOAD-DEPENDENT polytope.
template<class T>
QrfMetrics< T >	qrf_noblo_mmi_linear (const std::vector< std::pair< Matrix< T >, Matrix< T > > > &MAPs, std::size_t N, const Matrix< T > &rt, const Matrix< T > &alpha)
	qrf_noblo_mmi_linear: the load-dependent no-blocking bound, under MMI.

Typedef Documentation

◆ LrIndex

using line::mapqn::LrIndex = MapqnP1Index

Variable layout of the LR model: the shared p1-level blocks and nothing else.

Defined in mapqn_p1_common.h, constructed here with the joint block switched off.

Definition at line 86 of file mapqn_bnd_lr.h.

◆ QrIndex

using line::mapqn::QrIndex = MapqnP1Index

Variable layout of the general QR model: the shared p1-level blocks plus the joint p2 block.

Defined in mapqn_p1_common.h, which the linear reduction shares; the alias keeps the name this model is documented and tested under.

Definition at line 100 of file mapqn_bnd_qr.h.

Enumeration Type Documentation

◆ MapqnObjectiveVar

enum class line::mapqn::MapqnObjectiveVar

strong

The variable family the objective is taken over.

The paper states its bounds on the AGGREGATE over levels: U_i(N) = sum_k U_i^k(N) is the utilization of station i, while U_i^k alone is its utilization while the MAP sits in phase k. Pass objective_level = -1 for that aggregate; optimizing the K terms separately and adding them is also a bound but a strictly looser one, since the phases cannot all peak at once.

Enumerator
UN
QN

Definition at line 102 of file mapqn_bnd_lr_mva.h.

◆ MapqnSense

enum class line::mapqn::MapqnSense

strong

Which direction the bound is taken in.

Enumerator
Max
Min

Definition at line 154 of file mapqn_params.h.

Function Documentation

◆ bethe_gradient()

template<class T>

std::vector< T > line::mapqn::bethe_gradient	(	const std::vector< T > &	x,
		std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		const std::vector< int > &	F,
		std::size_t	MR,
		const std::vector< long > &	idx )

Gradient of bethe_objective.

df/dp_ij = lambda*(log p_ij' + p_ij/p_ij' - log p_ii' - log p_jj') for i != j, and df/dp_ii = log p_ii' + p_ii/p_ii'

(lambda/p_ii')*sum_{j!=i,kj,nj}(p_ij + p_ji), a primed denominator standing for the shifted value. The second sum is accumulated by the scatter below, which visits both orderings of every pair.

Definition at line 425 of file mapqn_qrf_common.h.

References bethe_gradient(), line::mapqn::QrfVars< T >::p(), line::mapqn::QrfVars< T >::p2_at(), qrf_log(), qrf_logtol(), and sub_qrfvar().

Referenced by bethe_gradient(), and qrf_noblo_bethe().

◆ bethe_objective()

template<class T>

T line::mapqn::bethe_objective	(	const std::vector< T > &	x,
		std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		const std::vector< int > &	F,
		std::size_t	MR )

Tree-reweighted (Bethe) free entropy at the uniform spanning-tree weight, the objective of qrf.bethe.

With lambda = 1/M this is lambda*sum_{i!=j} I(n_i;n_j) - sum_i H(n_i), the NEGATIVE of a tree-reweighted entropy with uniform edge weight rho_ij = 2*lambda on the complete station graph. H_rho is a convex combination of tree entropies – hence concave on the local marginal polytope – exactly when rho lies in the spanning tree polytope of K_M, whose uniform point is rho_ij = 2/M. So lambda = 1/M is the LARGEST uniform weight for which minimising this is a CONVEX program: every local optimum is global and the answer stops depending on the start point. The Bethe weight lambda = 1/2 (total edge mass C(M,2) against the M-1 a spanning tree can carry) is outside that polytope for every M > 2 and coincides with 1/M at M = 2.

TWO DIFFERENCES FROM mmi_objective, BOTH DELIBERATE. The population loops start at n = 0, the range the AMPL source states (ni, nj in 0..F) and the one mmi_objective does not use, so the idle/idle cell – the strongest correlation in a closed chain – is inside the sum; and the entropy term is mem_objective's body over the same restored range, which already carries the sign a minimiser needs. Neither repair touches qrf.mmi or qrf.mem, whose values are pinned by tests.

NUMERICAL NOTE. The restored n = 0 cells are structurally zero: they contribute 0*log(tol) = 0 to the VALUE but log(tol) ~ -13.8 to the GRADIENT, so the value is insensitive to the shift while the descent direction is not.

Definition at line 383 of file mapqn_qrf_common.h.

References bethe_objective(), line::mapqn::QrfVars< T >::p(), qrf_log(), qrf_logtol(), and sub_qrfvar().

Referenced by bethe_objective(), and qrf_noblo_bethe().

◆ mapqn_amva()

template<class T>

MapqnAmvaResult< T > line::mapqn::mapqn_amva	(	const std::vector< T > &	mu_in,
		const std::vector< Matrix< T > > &	D0s,
		const std::vector< Matrix< T > > &	D1s,
		const std::vector< int > &	N )

Definition at line 108 of file mapqn_amva.h.

References line::mapqn::MapqnAmvaResult< T >::ES, line::InputError::InputError(), line::inverse(), mapqn_amva(), line::mapqn::MapqnAmvaResult< T >::pi, line::mapqn::MapqnAmvaResult< T >::Qq, line::mapqn::MapqnAmvaResult< T >::U, and line::mapqn::MapqnAmvaResult< T >::X.

Referenced by mapqn_amva(), and line::mva::solver_mapqn().

◆ mapqn_bnd_lr()

template<class T>

MapqnBndLrResult< T > line::mapqn::mapqn_bnd_lr	(	const MapqnParams< T > &	p,
		int	objective_queue,
		int	objective_phase,
		MapqnSense	sense = MapqnSense::Max )

Bound U(objective_queue, objective_phase) over the linear-reduction polytope.

Parameters

p	network parameters; queues and phases are 0-based. alpha is IGNORED: this model has no load dependence.
objective_queue	queue index, 0..M-1
objective_phase	phase index, 0..K(objective_queue)-1
sense	Max for an upper bound, Min for a lower bound

Definition at line 220 of file mapqn_bnd_lr.h.

Referenced by mapqn_bnd_lr().

◆ mapqn_bnd_lr_mva()

template<class T>

MapqnBndLrMvaResult< T > line::mapqn::mapqn_bnd_lr_mva	(	const LrMvaParams< T > &	p,
		int	objective_queue,
		int	objective_level,
		MapqnSense	sense = MapqnSense::Max,
		MapqnObjectiveVar	objective_var = MapqnObjectiveVar::UN )

Bound UN or QN at (objective_queue, objective_level) over the MVA-shaped LR polytope.

Parameters

p	network parameters; queues and levels are 0-based, and the MAP queue is index M - 1
objective_queue	queue index, 0..M-1
objective_level	level index, 0..K-1, or -1 for the SUM over levels
sense	Max for an upper bound, Min for a lower bound
objective_var	UN (default) or QN, the variable family optimized over

Definition at line 367 of file mapqn_bnd_lr_mva.h.

Referenced by mapqn_bnd_lr_mva(), and line::ba::solver_ba_analyzer().

◆ mapqn_bnd_lr_pf()

template<class T>

LrPfResult< T > line::mapqn::mapqn_bnd_lr_pf	(	const LrPfParams< T > &	p,
		int	objective_queue,
		MapqnSense	sense )

Port of mapqn_bnd_lr_pf.

Parameters

p	station count, population, rates and routing
objective_queue	1-BASED station whose utilization is bounded, as in the reference
sense	Min for the lr.lower bound, Max for lr.upper

Definition at line 133 of file mapqn_bnd_lr_pf.h.

Referenced by mapqn_bnd_lr_pf(), and line::ba::solver_ba_analyzer().

◆ mapqn_bnd_qr()

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.

Parameters

p	network parameters; queues and phases are 0-based. alpha is IGNORED: this model has no load dependence, use mapqn_bnd_qr_ld for that.
objective_queue	queue index, 0..M-1
objective_phase	phase index, 0..K(objective_queue)-1
sense	Max for an upper bound, Min for a lower bound

Definition at line 380 of file mapqn_bnd_qr.h.

Referenced by mapqn_bnd_qr().

◆ mapqn_bnd_qr_delay()

template<class T>

MapqnQrResult< T > line::mapqn::mapqn_bnd_qr_delay	(	const MapqnParams< T > &	p,
		int	objective_queue,
		int	objective_phase,
		int	objective_n,
		MapqnSense	sense = MapqnSense::Max )

Bound P(queue objective_queue holds objective_n jobs in phase objective_phase) for a network with a delay station at queue M.

p.Z is the think time and p.D1 the service demand at queue 1; both enter only through the XZ family.

Definition at line 52 of file mapqn_bnd_qr_delay.h.

References line::InputError::InputError(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, mapqn_bnd_qr_delay(), Max, line::mapqn::MapqnParams< T >::N, line::mapqn::P2Index::num_vars(), qr_cor1a(), qr_cor1b(), qr_marginals(), qr_one(), qr_pc2(), qr_qbal(), qr_symmetry(), qr_thm1(), qr_thm1c(), qr_thm2(), qr_thm3a(), qr_thm3b(), qr_thm4(), qr_xz(), qr_zero_bounds(), line::lp::LpModel< T >::set_bounds(), and line::mapqn::MapqnParams< T >::validate().

Referenced by mapqn_bnd_qr_delay().

◆ mapqn_bnd_qr_ld()

template<class T>

MapqnQrResult< T > line::mapqn::mapqn_bnd_qr_ld	(	const MapqnParams< T > &	p,
		int	objective_queue,
		int	objective_phase,
		int	objective_n,
		MapqnSense	sense = MapqnSense::Max )

Bound P(queue objective_queue holds objective_n jobs in phase objective_phase), in the requested direction.

Parameters

p	network parameters; queues and phases are 0-based
objective_queue	queue index, 0..M-1
objective_phase	phase index, 0..K(objective_queue)-1
objective_n	population level, 0..N
sense	Max for an upper bound, Min for a lower bound

Definition at line 78 of file mapqn_bnd_qr_ld.h.

References line::InputError::InputError(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, mapqn_bnd_qr_ld(), Max, line::mapqn::MapqnParams< T >::N, line::mapqn::P2Index::num_vars(), qr_cor1a(), qr_cor1b(), qr_marginals(), qr_one(), qr_pc2(), qr_qbal(), qr_symmetry(), qr_thm1(), qr_thm1c(), qr_thm2(), qr_thm3a(), qr_thm3b(), qr_thm4(), qr_zero_bounds(), line::lp::LpModel< T >::set_bounds(), and line::mapqn::MapqnParams< T >::validate().

Referenced by mapqn_bnd_qr_ld().

◆ mapqn_q()

template<class T>

T line::mapqn::mapqn_q	(	const MapqnParams< T > &	p,
		int	i,
		int	j,
		int	k,
		int	h,
		int	n )

q(i,j,k,h,n): rate at which queue i, holding n jobs and in phase k, moves to phase h while routing a job to queue j.

Port of the local q_func in mapqn_bnd_qr_ld.m. n == 0 returns 0 (an empty queue completes nothing); the load-dependent factor alpha(i,n) is 1 beyond the width of the alpha table, exactly as MATLAB's if n <= size(alpha,2) guard does. The i == j branch adds the background rate v, because a self-routing completion and a phase change without completion are indistinguishable in the marginal process.

Definition at line 89 of file mapqn_params.h.

References line::mapqn::MapqnParams< T >::alpha, mapqn_q(), line::mapqn::MapqnParams< T >::mu, line::mapqn::MapqnParams< T >::r, and line::mapqn::MapqnParams< T >::v.

Referenced by mapqn_q(), qr_cor1a(), qr_cor1b(), qr_qbal(), qr_thm2(), qr_thm3a(), and qr_thm3b().

◆ mapqn_qr_bounds_bas()

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.

The utilization is sum over m, k and n >= 1 of p2(i,n,k,i,n,k,m), i.e. the probability that queue i holds at least one job, in ANY blocking configuration. That is the raw utilization; the per-phase EFFECTIVE utilization, which excludes the blocked configurations, is returned in e.

Parameters

p	network and blocking parameters, all 0-based
objective_queue	queue index, 0..M-1
sense	Max for an upper bound, Min for a lower bound

Definition at line 682 of file mapqn_qr_bounds_bas.h.

References line::mapqn::QrBasIndex::e(), line::mapqn::QrBasResult< T >::e, line::mapqn::QrBasParams< T >::F, line::InputError::InputError(), line::lp::LpSolution< T >::iterations, line::mapqn::QrBasResult< T >::iterations, line::mapqn::QrBasParams< T >::K, line::lp::lp_solve(), line::lp::lp_status_name(), line::mapqn::QrBasParams< T >::M, mapqn_qr_bounds_bas(), line::Matrix< T >::Matrix(), Max, Min, line::mapqn::QrBasParams< T >::MR, line::mapqn::QrBasParams< T >::N, line::lp::LpModel< T >::num_rows(), line::mapqn::QrBasResult< T >::num_rows, line::lp::LpModel< T >::num_vars(), line::mapqn::QrBasIndex::num_vars(), line::mapqn::QrBasResult< T >::num_vars, line::lp::LpSolution< T >::objective, line::mapqn::QrBasResult< T >::objective, line::mapqn::QrBasResult< T >::occupancy, line::lp::LpSolution< T >::ok(), line::mapqn::QrBasResult< T >::ok, line::mapqn::QrBasIndex::p2(), line::lp::LpModel< T >::set_cost(), line::lp::LpModel< T >::set_maximize(), line::lp::LpSolution< T >::status, line::mapqn::QrBasResult< T >::status, line::mapqn::QrBasResult< T >::U, line::mapqn::QrBasParams< T >::validate(), line::lp::LpSolution< T >::x, and line::mapqn::QrBasResult< T >::x.

Referenced by mapqn_qr_bounds_bas().

◆ mapqn_qr_bounds_rsrd()

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.

Parameters

p	network parameters, all 0-based
objective_queue	queue index, 0..M-1
sense	Max for an upper bound, Min for a lower bound

Definition at line 565 of file mapqn_qr_bounds_rsrd.h.

Referenced by mapqn_qr_bounds_rsrd().

◆ mapqn_qrf_bas()

template<class T>

QrfMetrics< T > line::mapqn::mapqn_qrf_bas	(	const QrBasParams< T > &	p,
		qrfbas::Objective	obj,
		unsigned	max_iter = 200 )

Solve one BAS-blocking NLP bound.

Parameters

p	the same parameters the LP token qrf.bas takes
obj	which functional to minimize over the polytope
max_iter	Frank-Wolfe iteration cap. EVERY ITERATE IS FEASIBLE, since each step is a convex combination of two points of the polytope, so a truncated run returns a worse bound but never an invalid one. That is what makes a small cap a legitimate way to keep a test cheap: the BAS polytope has hundreds of columns and each iteration costs one LP plus a line search.

Definition at line 156 of file mapqn_qrf_bas_nlp.h.

References line::mapqn::qrfbas::bas_polytope(), line::mapqn::qrfbas::Bethe, line::mapqn::QrBasIndex::e(), line::mapqn::QrBasParams< T >::F, line::InputError::InputError(), line::mapqn::QrBasParams< T >::K, line::mapqn::QrBasParams< T >::M, mapqn_qrf_bas(), line::mapqn::qrfbas::Mem, line::mapqn::qrfbas::mem_terms(), line::mapqn::qrfbas::mmi_terms(), line::mapqn::QrBasParams< T >::MR, line::mapqn::QrBasParams< T >::N, line::mapqn::QrBasIndex::p2(), line::mapqn::QrfMetrics< T >::QN, qrf_feasible_start_lp(), qrf_log(), qrf_logtol(), solve_qrf_nlp_lp(), line::mapqn::QrfMetrics< T >::UN, and line::mapqn::QrBasParams< T >::validate().

Referenced by mapqn_qrf_bas(), mapqn_qrf_bas_bethe(), mapqn_qrf_bas_mem(), and mapqn_qrf_bas_mmi().

◆ mapqn_qrf_bas_bethe()

template<class T>

QrfMetrics< T > line::mapqn::mapqn_qrf_bas_bethe	(	const QrBasParams< T > &	p,
		unsigned	max_iter = 200 )

Tree-reweighted (Bethe) free entropy bound on the BAS-blocking polytope.

lambda*sum_{i!=j} I(n_i;n_j) - sum_i H(n_i) at lambda = 1/M, the objective of qrf_noblo_bethe evaluated over the BAS decision vector: the blocking configurations and the per-station capacities enter through the ranges alone.

Definition at line 276 of file mapqn_qrf_bas_nlp.h.

References line::mapqn::qrfbas::Bethe, mapqn_qrf_bas(), and mapqn_qrf_bas_bethe().

Referenced by mapqn_qrf_bas_bethe(), and line::ba::solver_ba_qrf_analyzer().

◆ mapqn_qrf_bas_mem()

template<class T>

QrfMetrics< T > line::mapqn::mapqn_qrf_bas_mem	(	const QrBasParams< T > &	p,
		unsigned	max_iter = 200 )

Maximum-entropy bound on the BAS-blocking polytope.

Definition at line 264 of file mapqn_qrf_bas_nlp.h.

References mapqn_qrf_bas(), mapqn_qrf_bas_mem(), and line::mapqn::qrfbas::Mem.

Referenced by mapqn_qrf_bas_mem(), and line::ba::solver_ba_qrf_analyzer().

◆ mapqn_qrf_bas_mmi()

template<class T>

QrfMetrics< T > line::mapqn::mapqn_qrf_bas_mmi	(	const QrBasParams< T > &	p,
		unsigned	max_iter = 200 )

Minimum-mutual-information bound on the BAS-blocking polytope.

Definition at line 258 of file mapqn_qrf_bas_nlp.h.

References mapqn_qrf_bas(), mapqn_qrf_bas_mmi(), and line::mapqn::qrfbas::Mmi.

Referenced by mapqn_qrf_bas_mmi(), and line::ba::solver_ba_qrf_analyzer().

◆ mem_gradient()

template<class T>

std::vector< T > line::mapqn::mem_gradient	(	const std::vector< T > &	x,
		std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		const std::vector< int > &	F,
		std::size_t	MR,
		const std::vector< long > &	idx )

Gradient of mem_objective: d/dp of p log(p') is log p' + p/p'.

Definition at line 336 of file mapqn_qrf_common.h.

References mem_gradient(), line::mapqn::QrfVars< T >::p(), line::mapqn::QrfVars< T >::p2_at(), qrf_log(), qrf_logtol(), and sub_qrfvar().

Referenced by mem_gradient(), and qrf_noblo_mem().

◆ mem_objective()

template<class T>

T line::mapqn::mem_objective	(	const std::vector< T > &	x,
		std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		const std::vector< int > &	F,
		std::size_t	MR )

Maximum-entropy objective, returned as the NEGATIVE entropy +sum p log p over the diagonal entries, because the solver MINIMIZES and the AMPL model states this objective as maximize H.

Returning +H (as every port did until 2026-08-29) selects the minimum-entropy face of the polytope instead, under a method documented as maximum-entropy.

Definition at line 278 of file mapqn_qrf_common.h.

References mem_objective(), line::mapqn::QrfVars< T >::p(), qrf_log(), qrf_logtol(), and sub_qrfvar().

Referenced by mem_objective(), and qrf_noblo_mem().

◆ mmi_gradient()

template<class T>

std::vector< T > line::mapqn::mmi_gradient	(	const std::vector< T > &	x,
		std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		const std::vector< int > &	F,
		std::size_t	MR,
		const std::vector< long > &	idx )

Gradient of mmi_objective.

For t = p_ij (log p_ij - log p_ii - log p_jj) the three partials are dt/dp_ij = log p_ij - log p_ii - log p_jj + p_ij/p_ij', dt/dp_ii = -p_ij/p_ii' and dt/dp_jj = -p_ij/p_jj', a primed denominator standing for the shifted value. i != j throughout, so no term aliases its own partials.

Definition at line 302 of file mapqn_qrf_common.h.

References mmi_gradient(), line::mapqn::QrfVars< T >::p(), line::mapqn::QrfVars< T >::p2_at(), qrf_log(), qrf_logtol(), and sub_qrfvar().

Referenced by mmi_gradient(), qrf_noblo_mmi(), qrf_noblo_mmi_ld(), and qrf_noblo_mmi_linear().

◆ mmi_objective()

template<class T>

T line::mapqn::mmi_objective	(	const std::vector< T > &	x,
		std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		const std::vector< int > &	F,
		std::size_t	MR )

Mutual-information objective.

sum over i != j of p_ij (log p_ij - log p_ii - log p_jj), each log taken on the LOGTOL-shifted value so the sweep can visit the boundary.

Definition at line 246 of file mapqn_qrf_common.h.

References mmi_objective(), line::mapqn::QrfVars< T >::p(), qrf_log(), qrf_logtol(), and sub_qrfvar().

Referenced by mmi_objective(), qrf_noblo_mmi(), qrf_noblo_mmi_ld(), and qrf_noblo_mmi_linear().

◆ qr_cor1a()

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).

Blocks A..H follow the reference letter for letter; A and B are the arrival terms, C..H the departure and phase-change terms at populations ni+1 and ni+2.

Definition at line 363 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, mapqn_q(), line::mapqn::MapqnParams< T >::N, qr_cor1a(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_cor1a().

◆ qr_cor1b()

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').

Definition at line 447 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, mapqn_q(), line::mapqn::MapqnParams< T >::N, qr_cor1b(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_cor1b().

◆ qr_marginals()

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.

The diagonal entry is the marginal of queue j, so the joint over the pair (j,i) must sum back to it.

Definition at line 125 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, qr_marginals(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_marginals().

◆ qr_one()

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.

Definition at line 85 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, qr_one(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_one().

◆ qr_pc2()

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.

Definition at line 176 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, qr_pc2(), and line::lp::LpModel< T >::row_add_int().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_pc2().

◆ qr_qbal()

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).

This is the family the reference warns about. The right-hand side carries two distinct blocks – the arrival flow into queue i (RHS1, itself in two pieces, the ni = 0 term and the ni >= 1 term) and the population-weighted phase inflow (RHS2). Dropping either would leave the variables they touch with no other constraint mentioning them and force them to zero.

Definition at line 298 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, mapqn_q(), line::mapqn::MapqnParams< T >::N, qr_qbal(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_qbal().

◆ qr_symmetry()

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.

Definition at line 96 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, qr_symmetry(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_symmetry().

◆ qr_thm1()

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).

Definition at line 146 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, qr_thm1(), and line::lp::LpModel< T >::row_add_int().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_thm1().

◆ qr_thm1c()

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.

Definition at line 162 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, qr_thm1c(), and line::lp::LpModel< T >::row_add_int().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_thm1c().

◆ qr_thm2()

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.

Definition at line 213 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, mapqn_q(), line::mapqn::MapqnParams< T >::N, qr_thm2(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_thm2().

◆ qr_thm3a()

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.

Definition at line 238 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, mapqn_q(), line::mapqn::MapqnParams< T >::N, qr_thm3a(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_thm3a().

◆ qr_thm3b()

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.

Definition at line 265 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_eq(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, mapqn_q(), line::mapqn::MapqnParams< T >::N, qr_thm3b(), and line::lp::LpModel< T >::row_add().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_thm3b().

◆ qr_thm4()

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.

The reference passes it to linprog as -row * x <= 0; here it is emitted directly as row >= 0.

Definition at line 507 of file mapqn_qr_common.h.

References line::lp::LpModel< T >::emit_ge(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, qr_thm4(), and line::lp::LpModel< T >::row_add_int().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_thm4().

◆ qr_xz()

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.

the mean population at the delay station equals Z times the throughput of queue 1, whose service demand is D1.

Definition at line 195 of file mapqn_qr_common.h.

References line::mapqn::MapqnParams< T >::D1, line::lp::LpModel< T >::emit_eq(), line::InputError::InputError(), line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, qr_xz(), line::lp::LpModel< T >::row_add(), line::lp::LpModel< T >::row_add_int(), and line::mapqn::MapqnParams< T >::Z.

Referenced by mapqn_bnd_qr_delay(), and qr_xz().

◆ qr_zero_bounds()

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.

ZERO1 i == j, nj == ni, h != k (one queue cannot be in two phases) ZERO2 i == j, nj != ni (one queue cannot hold two populations) ZERO3 i != j, nj + ni > N (more jobs than the network holds) Returns the indicator so SYMMETRY can skip pairs that are both zeroed, as the reference does.

Definition at line 63 of file mapqn_qr_common.h.

References line::mapqn::MapqnParams< T >::K, line::mapqn::MapqnParams< T >::M, line::mapqn::MapqnParams< T >::N, line::mapqn::P2Index::num_vars(), qr_zero_bounds(), and line::lp::LpModel< T >::set_upper().

Referenced by mapqn_bnd_qr_delay(), mapqn_bnd_qr_ld(), and qr_zero_bounds().

◆ qrf_affine_matrices()

template<class T, class Fn>

QrfAffine< T > line::mapqn::qrf_affine_matrices	(	Fn	fn,
		std::size_t	n )

Recover (A, b) from an affine residual map.

Every constraint of the QRF inventory is LINEAR in the decision vector – only the objectives are nonlinear – so the matrix form is exact, not a linearization. Affinity is VERIFIED at a probe point and a violation is raised rather than tolerated, because a silently non-affine callback would make the recovered matrix wrong everywhere except at the probe.

Definition at line 595 of file mapqn_qrf_common.h.

References line::mapqn::QrfAffine< T >::A, line::mapqn::QrfAffine< T >::b, line::InputError::InputError(), line::Matrix< T >::Matrix(), and qrf_affine_matrices().

Referenced by qrf_affine_matrices().

◆ qrf_build_q()

template<class T>

QrfRates< T > line::mapqn::qrf_build_q	(	std::size_t	M,
		const std::vector< int > &	K,
		const Matrix< T > &	mu,
		const Matrix< T > &	v,
		const Matrix< T > &	rt )

build_q_from_mu_v_rt: the population-free rates.

Definition at line 80 of file mapqn_qrf_noblo.h.

References line::mapqn::QrfRates< T >::Kmax, line::mapqn::QrfRates< T >::load_dependent, line::mapqn::QrfRates< T >::M, line::mapqn::QrfRates< T >::q4, and qrf_build_q().

Referenced by qrf_build_q(), qrf_noblo_bethe(), qrf_noblo_mem(), and qrf_noblo_mmi().

◆ qrf_build_q_ld()

template<class T>

QrfRates< T > line::mapqn::qrf_build_q_ld	(	std::size_t	M,
		const std::vector< int > &	K,
		const Matrix< T > &	mu,
		const Matrix< T > &	v,
		const Matrix< T > &	rt,
		std::size_t	N,
		const Matrix< T > &	alpha )

build_q_ld: the load-dependent rates.

qrboundsrsrd_skel.mod:11 declares q with FIVE indices, the fifth being the population n of the EMITTING station, with q[...,0] = 0, and the scaling alpha[i,n] multiplying BOTH the background term v and the completion term rt[i,i] mu. Dropping alpha from the v term is as wrong as dropping the index.

Parameters

alpha (M x N), 0-based in the population, so alpha(i, n-1) is the AMPL alpha[i,n]; an empty matrix means all ones

Definition at line 112 of file mapqn_qrf_noblo.h.

References line::Matrix< T >::cols(), line::InputError::InputError(), line::mapqn::QrfRates< T >::Kmax, line::mapqn::QrfRates< T >::load_dependent, line::mapqn::QrfRates< T >::M, line::mapqn::QrfRates< T >::N, line::mapqn::QrfRates< T >::q5, qrf_build_q_ld(), and line::Matrix< T >::rows().

Referenced by qrf_build_q_ld(), qrf_noblo_mmi_ld(), and qrf_noblo_mmi_linear().

◆ qrf_extract_mu_v()

template<class T>

void line::mapqn::qrf_extract_mu_v	(	const std::vector< std::pair< Matrix< T >, Matrix< T > > > &	MAPs,
		std::size_t	M,
		const std::vector< int > &	K,
		Matrix< T > *	mu,
		Matrix< T > *	v )

extract_mu_v_from_maps: the completion and background rates of each MAP.

Definition at line 143 of file mapqn_qrf_noblo.h.

References line::Matrix< T >::Matrix(), and qrf_extract_mu_v().

Referenced by qrf_extract_mu_v(), qrf_noblo_mem(), qrf_noblo_mmi_linear(), and line::ba::solver_ba_qrf_analyzer().

◆ qrf_extract_results()

template<class T>

QrfMetrics< T > line::mapqn::qrf_extract_results	(	const QrfVars< T > &	v,
		std::size_t	M,
		const std::vector< int > &	K,
		const std::vector< int > &	F,
		std::size_t	MR,
		const Matrix< T > *	alpha = nullptr )

extract_results: the diagonal marginals of the optimal tensor, plus the alpha-weighted mean BN.

alpha may be empty, meaning load independent.

Definition at line 487 of file mapqn_qrf_common.h.

References line::mapqn::QrfMetrics< T >::BN, line::mapqn::QrfVars< T >::p(), line::mapqn::QrfMetrics< T >::QN, qrf_extract_results(), and line::mapqn::QrfMetrics< T >::UN.

Referenced by qrf_extract_results().

◆ qrf_feasible_start()

template<class T>

std::vector< T > line::mapqn::qrf_feasible_start	(	const Matrix< T > &	Aeq,
		const std::vector< T > &	beq,
		const Matrix< T > &	Aub,
		const std::vector< T > &	bub,
		std::size_t	n )

A point of the polytope, as the phase 1 of qrf_noblo_start.m.

The all-zero vector violates normalization by a full unit and COR1 by N^2, and from there a local method terminates AT the start point. Every constraint here is linear, so an LP lands on the polytope exactly; the minimum-norm refinement above is what keeps it off a vertex.

Definition at line 975 of file mapqn_qrf_common.h.

References line::InputError::InputError(), line::lp::Optimal, qrf_feasible_start(), qrf_min_norm_point(), qrf_polytope(), line::lp::simplex_solve(), line::lp::LpSolution< T >::status, and line::lp::LpSolution< T >::x.

Referenced by qrf_feasible_start().

◆ qrf_feasible_start_lp()

template<class T>

std::vector< T > line::mapqn::qrf_feasible_start_lp	(	const lp::LpModel< T > &	polytope,
		const std::string &	name )

A feasible point of an LpModel polytope: the MINIMUM-NORM one.

THE START IS PART OF THE ANSWER HERE, and a vertex is the wrong one. Neither MEM nor MMI is a convex program as the reference states them – the MEM objective is -sum p log p, which is CONCAVE, and it is MINIMIZED – so every method reports a stationary point fixed by where it started. A zero-cost phase-1 LP lands on an arbitrary VERTEX, and a vertex is already a local minimum of a concave objective: conditional gradient reports a zero gap and hands the vertex straight back. Measured on the two-phase / one-phase pair at N = 2: f(x0) = f(xopt) = 1.0397 and a utilization of exactly 1 against the references' 0.8.

qrf_noblo_start.m minimizes 0.5||x||^2 over the same rows for exactly this reason ("so the returned point is the unique minimum-norm feasible point instead of an arbitrary vertex"), and native Python does the same. That objective IS strongly convex, so conditional gradient solves it to optimality over the polytope and needs no QP backend. From that start the port returns [0.8, 0.4] / [1.4, 0.6], which is native Python to the last digit printed and MATLAB to 1e-3 – MATLAB's fmincon stops on its own MaxIter = 100 slightly short of it.

Definition at line 953 of file mapqn_qrf_common.h.

References line::InputError::InputError(), line::lp::lp_solve(), line::lp::LpModel< T >::num_vars(), line::lp::Optimal, qrf_feasible_start_lp(), qrf_min_norm_point(), line::lp::LpModel< T >::set_cost(), line::lp::LpModel< T >::set_maximize(), line::lp::LpSolution< T >::status, and line::lp::LpSolution< T >::x.

Referenced by mapqn_qrf_bas(), and qrf_feasible_start_lp().

◆ qrf_independent_rows()

template<class T>

std::vector< std::size_t > line::mapqn::qrf_independent_rows	(	const Matrix< T > &	A,
		double	tol = -1.0 )

Rows of a maximal linearly independent subset of A, by pivoted Gram-Schmidt.

The reference uses column-pivoted QR of A^T, which at each step retains the remaining column of largest residual norm; this is the same greedy selection written out, and only the index SET is used downstream. Selecting by conditioning rather than by first-encountered matters: the QRF equality block is heavily redundant (SYMMETRY states every pair twice, ZERO / MARGINALS / UEFF overlap), carrying roughly twice as many rows as its rank.

Definition at line 523 of file mapqn_qrf_common.h.

References line::Matrix< T >::cols(), qrf_independent_rows(), and line::Matrix< T >::rows().

Referenced by qrf_independent_rows(), and qrf_reduce_equalities().

◆ qrf_index_map()

std::vector< long > line::mapqn::qrf_index_map	(	std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		std::size_t	MR )

inline

Flat position of every p2 entry, in the FILL ORDER of sub_qrfvar.

The layout is not a plain strided tensor: the phase loops run over K[j] and K[i], not over Kmax, so a station with fewer phases leaves GAPS. An entry that carries no variable keeps -1, and every gradient scatter must skip it.

Definition at line 183 of file mapqn_qrf_common.h.

References line::mapqn::QrfVars< T >::Kmax, line::mapqn::QrfVars< T >::M, line::mapqn::QrfVars< T >::MR, line::mapqn::QrfVars< T >::N, line::mapqn::QrfVars< T >::p2_at(), and qrf_index_map().

Referenced by qrf_index_map(), qrf_noblo_bethe(), qrf_noblo_mem(), qrf_noblo_mmi(), qrf_noblo_mmi_ld(), and qrf_noblo_mmi_linear().

◆ qrf_log()

template<class T>

T line::mapqn::qrf_log ( const T & v )

log() in the working arithmetic.

num_traits exposes the logarithm only as a double (log_as_double), which is enough here: every consumer of this file is gated on has_transcendental, so T is a floating type and the round trip loses nothing it did not already lose.

Definition at line 112 of file mapqn_qrf_common.h.

References qrf_log().

Referenced by bethe_gradient(), bethe_objective(), mapqn_qrf_bas(), mem_gradient(), mem_objective(), mmi_gradient(), mmi_objective(), and qrf_log().

◆ qrf_logtol()

template<class T>

T line::mapqn::qrf_logtol ( )

The reference's LOGTOL: the shift that keeps log() off zero.

Definition at line 118 of file mapqn_qrf_common.h.

References qrf_logtol().

Referenced by bethe_gradient(), bethe_objective(), mapqn_qrf_bas(), mem_gradient(), mem_objective(), mmi_gradient(), mmi_objective(), and qrf_logtol().

◆ qrf_min_norm_point()

template<class T>

std::vector< T > line::mapqn::qrf_min_norm_point	(	const lp::LpModel< T > &	polytope,
		const std::vector< T > &	x0,
		const std::string &	name )

The minimum-norm point of the polytope, from any feasible point of it.

0.5||x||^2 is strongly convex, so the Frank-Wolfe gap is a true bound on the optimality gap and the loop terminates on it rather than on its budget.

Definition at line 918 of file mapqn_qrf_common.h.

References qrf_min_norm_point(), and solve_qrf_nlp_lp().

Referenced by qrf_feasible_start(), qrf_feasible_start_lp(), and qrf_min_norm_point().

◆ qrf_noblo_bethe()

template<class T>

QrfMetrics< T > line::mapqn::qrf_noblo_bethe	(	std::size_t	M,
		const std::vector< int > &	K,
		std::size_t	N,
		const Matrix< T > &	mu,
		const Matrix< T > &	v,
		const Matrix< T > &	rt )

qrf_noblo_bethe: the same polytope under the tree-reweighted free entropy.

The polytope, the phase-1 feasible start and the NLP call are exactly those of qrf_noblo_mmi; the objective is the only difference. See bethe_objective in mapqn_qrf_common.h for what it is and why the uniform edge weight is lambda = 1/M.

ONE SOLVE, NO RESTARTS. The objective is convex on this polytope, so there is no second local minimum for a restart to find; the single solve from the phase-1 point returns the global optimum.

Parameters

M	number of queues
K	phases per queue
N	total population
mu	(M x Kmax*Kmax) completion rates
v	(M x Kmax*Kmax) background rates
rt	(M x M) routing matrix

Definition at line 494 of file mapqn_qrf_noblo.h.

References bethe_gradient(), bethe_objective(), qrf_build_q(), qrf_index_map(), and qrf_noblo_bethe().

Referenced by qrf_noblo_bethe(), and line::ba::solver_ba_qrf_analyzer().

◆ qrf_noblo_mem()

template<class T>

QrfMetrics< T > line::mapqn::qrf_noblo_mem	(	const std::vector< std::pair< Matrix< T >, Matrix< T > > > &	MAPs,
		std::size_t	N,
		const Matrix< T > &	rt )

qrf_noblo_mem: the same polytope under maximum entropy.

Definition at line 510 of file mapqn_qrf_noblo.h.

References mem_gradient(), mem_objective(), qrf_build_q(), qrf_extract_mu_v(), qrf_index_map(), and qrf_noblo_mem().

Referenced by qrf_noblo_mem(), and line::ba::solver_ba_qrf_analyzer().

◆ qrf_noblo_mmi()

template<class T>

QrfMetrics< T > line::mapqn::qrf_noblo_mmi	(	std::size_t	M,
		const std::vector< int > &	K,
		std::size_t	N,
		const Matrix< T > &	mu,
		const Matrix< T > &	v,
		const Matrix< T > &	rt )

qrf_noblo_mmi: the no-blocking bound under mutual-information minimization.

Parameters

M	number of queues
K	phases per queue
N	total population
mu	(M x Kmax*Kmax) completion rates
v	(M x Kmax*Kmax) background rates
rt	(M x M) routing matrix

Definition at line 460 of file mapqn_qrf_noblo.h.

References mmi_gradient(), mmi_objective(), qrf_build_q(), qrf_index_map(), and qrf_noblo_mmi().

Referenced by qrf_noblo_mmi(), and line::ba::solver_ba_qrf_analyzer().

◆ qrf_noblo_mmi_ld()

template<class T>

QrfMetrics< T > line::mapqn::qrf_noblo_mmi_ld	(	std::size_t	M,
		const std::vector< int > &	K,
		std::size_t	N,
		const Matrix< T > &	mu,
		const Matrix< T > &	v,
		const Matrix< T > &	rt,
		const Matrix< T > &	alpha )

qrf_noblo_mmi_ld: MMI on the LOAD-DEPENDENT polytope.

The only difference from qrf_noblo_mmi is the arity of q, and that is the whole point: with a population-free q the balance families cannot tell the rate at which a station empties at population n from the rate at n', so the polytope stops pinning the utilization.

Parameters

alpha (M x N) load-dependent scaling, alpha(i, n-1) being the AMPL alpha[i,n]; an empty matrix means all ones

Definition at line 542 of file mapqn_qrf_noblo.h.

References mmi_gradient(), mmi_objective(), qrf_build_q_ld(), qrf_index_map(), and qrf_noblo_mmi_ld().

Referenced by qrf_noblo_mmi_ld(), and line::ba::solver_ba_qrf_analyzer().

◆ qrf_noblo_mmi_linear()

template<class T>

QrfMetrics< T > line::mapqn::qrf_noblo_mmi_linear	(	const std::vector< std::pair< Matrix< T >, Matrix< T > > > &	MAPs,
		std::size_t	N,
		const Matrix< T > &	rt,
		const Matrix< T > &	alpha )

qrf_noblo_mmi_linear: the load-dependent no-blocking bound, under MMI.

The linear in the name is about HOW the reference builds its constraints, not about which constraints they are and not about the objective: it emits the same inventory directly as sparse matrices instead of recovering it from a residual callback, because scipy's SLSQP under-allocates its Fortran workspace when the equality block outnumbers the variables and corrupts the heap rather than refusing. This port recovers the matrices affinely for every entry point and reduces the equality block before it reaches the optimizer, so the distinction does not arise and the two spellings are one function here. It is verified, not assumed: test_mapqn_qrf_noblo.cpp checks this against the reference.

Until 2026-08-29 the MATLAB reference called its own mem() here, with mmi() surviving only in a commented-out line, and this port mirrored that: the entry point named for mutual-information minimisation returned an entropy extremum. The objective is now MMI in all four ports. MMI is not convex, so unlike the MEM it replaces this entry point has no unique optimum and agrees with the reference only where the polytope pins the answer.

Definition at line 579 of file mapqn_qrf_noblo.h.

References mmi_gradient(), mmi_objective(), qrf_build_q_ld(), qrf_extract_mu_v(), qrf_index_map(), and qrf_noblo_mmi_linear().

Referenced by qrf_noblo_mmi_linear(), and line::ba::solver_ba_qrf_analyzer().

◆ qrf_null_space()

template<class T>

Matrix< T > line::mapqn::qrf_null_space	(	const Matrix< T > &	A,
		std::size_t	n )

Orthonormal basis of null(A), as an (n x d) matrix.

The reference calls scipy.linalg.null_space, an SVD; this builds the same space by modified Gram-Schmidt – orthonormalize the rows of A, then sweep the canonical directions and keep each one whose residual against the row space and the basis so far is nontrivial. The basis is not the SVD's, but the SPACE is, and the caller only ever uses the space: x0 + Z t ranges over the same affine set whichever orthonormal basis Z carries. Gram-Schmidt is used rather than util/svd.h because that header needs LAPACK, which this call path must not require.

Definition at line 716 of file mapqn_qrf_common.h.

References qrf_null_space(), and line::Matrix< T >::rows().

Referenced by qrf_null_space().

◆ qrf_num_vars()

std::size_t line::mapqn::qrf_num_vars	(	std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		std::size_t	MR )

inline

Number of decision variables the layout actually USES.

THIS IS DELIBERATELY SMALLER THAN THE REFERENCE'S compute_num_vars, which returns the full M (N+1) Kmax M (N+1) Kmax MR + M Kmax tensor. The fill loops of sub_qrfvar run over K[j] and K[i], not over Kmax, so with heterogeneous phase counts the tail of that vector is never written, never read by a constraint, and never read by an objective – and, being unread, it has an all-zero column in Aeq, so every one of those coordinates lands in null(Aeq) as a FLAT direction of the reduced problem.

The reference's gradient-based SLSQP shrugs that off (a flat direction has zero gradient). The augmented-Lagrangian inner solve here is Nelder-Mead, which degrades sharply with dimension, and the padding is not a rounding detail: on a two-phase / one-phase pair at N = 2 it is 64 flat directions against 20 real ones, and the solve returns a utilization of exactly 1 against the reference's 0.8. Dropping the dead coordinates is EXACT, not an approximation – nothing reads them – and it is what makes the port agree.

The live coordinates are a PREFIX of the reference's vector, since the fill order is consecutive, so the two layouts agree wherever both are defined.

Definition at line 166 of file mapqn_qrf_common.h.

References qrf_num_vars().

Referenced by qrf_num_vars().

◆ qrf_polytope()

template<class T>

lp::LpModel< T > line::mapqn::qrf_polytope	(	const Matrix< T > &	Aeq,
		const std::vector< T > &	beq,
		const Matrix< T > &	Aub,
		const std::vector< T > &	bub,
		std::size_t	n )

The polytope of a QRF instance, as an LpModel over the box [0,1]^n.

Shared by the phase 1 and by the conditional-gradient loop, so the two can never disagree about which set they are working over.

Definition at line 679 of file mapqn_qrf_common.h.

References line::lp::LpModel< T >::emit_eq(), line::lp::LpModel< T >::emit_le(), qrf_polytope(), line::lp::LpModel< T >::row_add(), line::lp::LpModel< T >::row_clear(), line::Matrix< T >::rows(), line::lp::LpModel< T >::set_bounds(), line::lp::LpModel< T >::set_cost(), and line::lp::LpModel< T >::set_maximize().

Referenced by qrf_feasible_start(), and qrf_polytope().

◆ qrf_reduce_equalities()

template<class T>

QrfReduced< T > line::mapqn::qrf_reduce_equalities	(	const Matrix< T > &	A,
		const std::vector< T > &	b )

Drop the linearly dependent equality rows, keeping the feasible set exact.

An INCONSISTENT system is refused rather than reduced: rank([A|b]) above rank(A) means the polytope is empty, which is a modelling error, and discarding the offending rows would return numbers for a model nobody wrote.

Definition at line 646 of file mapqn_qrf_common.h.

References line::mapqn::QrfReduced< T >::A, line::mapqn::QrfReduced< T >::b, line::Matrix< T >::cols(), line::InputError::InputError(), line::mapqn::QrfReduced< T >::keep, line::Matrix< T >::Matrix(), qrf_independent_rows(), qrf_reduce_equalities(), and line::Matrix< T >::rows().

Referenced by qrf_reduce_equalities().

◆ solve_qrf_nlp()

template<class T, class Obj, class Grad>

std::vector< T > line::mapqn::solve_qrf_nlp	(	Obj	objective,
		Grad	gradient,
		const std::vector< T > &	x0,
		const Matrix< T > &	Aeq,
		const std::vector< T > &	beq,
		const Matrix< T > &	Aub,
		const std::vector< T > &	bub,
		const std::string &	name,
		unsigned	max_iter = 200,
		double	gap_tol = 1e-10 )

The same, with the polytope given as matrices rather than as an LpModel.

Definition at line 886 of file mapqn_qrf_common.h.

References line::lp::LpModel< T >::emit_eq(), line::lp::LpModel< T >::emit_le(), line::lp::LpModel< T >::row_add(), line::lp::LpModel< T >::row_clear(), line::Matrix< T >::rows(), line::lp::LpModel< T >::set_bounds(), line::lp::LpModel< T >::set_maximize(), solve_qrf_nlp(), and solve_qrf_nlp_lp().

Referenced by solve_qrf_nlp().

◆ solve_qrf_nlp_lp()

template<class T, class Obj, class Grad>

std::vector< T > line::mapqn::solve_qrf_nlp_lp	(	Obj	objective,
		Grad	gradient,
		const std::vector< T > &	x0,
		const lp::LpModel< T > &	polytope,
		const std::string &	name,
		unsigned	max_iter = 200,
		double	gap_tol = 1e-10 )

Minimize a convex objective over {Aeq x = beq, Aub x <= bub, 0 <= x <= 1}, starting from a feasible point, by FRANK-WOLFE.

THIS IS A DELIBERATE SUBSTITUTION FOR THE REFERENCE'S SLSQP, and it is the one place in this port where a different algorithm is the right answer rather than a compromise. The reference eliminates the equalities with a null-space basis and runs SLSQP on the reduced problem. That works because SLSQP is gradient-based; the augmented-Lagrangian path available here has a derivative-free Nelder-Mead inner solve, and started AT A VERTEX of the polytope – which is exactly what the phase-1 LP returns – its first simplex steps leave the feasible set, are penalized, and it does not move at all. Measured on a two-phase / one-phase pair at N = 2: it returned its start point, an objective of 0.6931 against the reference's 0.6438, and a utilization of 1.0 against 0.8.

The feasible set is a polytope, so conditional gradient applies directly and gives more than convergence: at each step the linear minimization over the SAME polytope yields the FRANK-WOLFE GAP <grad f(x), x - s>, which is the exact stationarity measure – zero iff no feasible descent direction exists at x. On MEM, which is convex, it is additionally an upper bound on f(x) - f(x*). It subsumes the reference's one-shot "did a feasible descent direction exist at the start?" probe: the same question is asked at every iterate, and the answer is what terminates the loop.

No null-space reduction is needed, since the LP carries the equalities itself.

Parameters

objective	convex objective
gradient	its gradient
x0	a feasible point, from qrf_feasible_start

Definition at line 795 of file mapqn_qrf_common.h.

References line::InputError::InputError(), line::lp::lp_solve(), line::lp::Optimal, line::lp::LpModel< T >::set_cost(), line::lp::LpModel< T >::set_maximize(), solve_qrf_nlp_lp(), line::lp::LpSolution< T >::status, and line::lp::LpSolution< T >::x.

Referenced by mapqn_qrf_bas(), qrf_min_norm_point(), solve_qrf_nlp(), and solve_qrf_nlp_lp().

◆ sub_qrfcon_noblo()

template<class T>

QrfConstraints< T > line::mapqn::sub_qrfcon_noblo	(	const std::vector< T > &	x,
		const QrfRates< T > &	q,
		std::size_t	M,
		std::size_t	MR,
		const Matrix< int > &	BB,
		const std::vector< int > &	F,
		std::size_t	N,
		const std::vector< int > &	K )

The full no-blocking constraint inventory, sub_qrfcon_noblo.

Parameters

x	decision vector
q	the rates, whose arity selects the model
BB	(MR x M) blocking-state matrix
F	(M) capacity per queue

Definition at line 179 of file mapqn_qrf_noblo.h.

References line::mapqn::QrfRates< T >::at(), line::mapqn::QrfRates< T >::at4(), line::mapqn::QrfVars< T >::e, line::mapqn::QrfConstraints< T >::eq, line::mapqn::QrfConstraints< T >::ineq, line::mapqn::QrfVars< T >::Kmax, line::mapqn::QrfRates< T >::load_dependent, line::mapqn::QrfVars< T >::p(), sub_qrfcon_noblo(), and sub_qrfvar().

Referenced by sub_qrfcon_noblo().

◆ sub_qrfvar()

template<class T>

QrfVars< T > line::mapqn::sub_qrfvar	(	const std::vector< T > &	x,
		std::size_t	M,
		std::size_t	N,
		const std::vector< int > &	K,
		std::size_t	MR )

Unflatten x into the pair tensor and the effective rates.

Definition at line 206 of file mapqn_qrf_common.h.

References line::mapqn::QrfVars< T >::e, line::InputError::InputError(), line::mapqn::QrfVars< T >::Kmax, line::mapqn::QrfVars< T >::M, line::mapqn::QrfVars< T >::MR, line::mapqn::QrfVars< T >::N, line::mapqn::QrfVars< T >::p(), line::mapqn::QrfVars< T >::p2, and sub_qrfvar().

Referenced by bethe_gradient(), bethe_objective(), mem_gradient(), mem_objective(), mmi_gradient(), mmi_objective(), sub_qrfcon_noblo(), and sub_qrfvar().

Namespaces

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ LrIndex

◆ QrIndex

Enumeration Type Documentation

◆ MapqnObjectiveVar

◆ MapqnSense

Function Documentation

◆ bethe_gradient()

◆ bethe_objective()

◆ mapqn_amva()

◆ mapqn_bnd_lr()

◆ mapqn_bnd_lr_mva()

◆ mapqn_bnd_lr_pf()

◆ mapqn_bnd_qr()

◆ mapqn_bnd_qr_delay()

◆ mapqn_bnd_qr_ld()

◆ mapqn_q()

◆ mapqn_qr_bounds_bas()

◆ mapqn_qr_bounds_rsrd()

◆ mapqn_qrf_bas()

◆ mapqn_qrf_bas_bethe()

◆ mapqn_qrf_bas_mem()

◆ mapqn_qrf_bas_mmi()

◆ mem_gradient()

◆ mem_objective()

◆ mmi_gradient()

◆ mmi_objective()

◆ qr_cor1a()

◆ qr_cor1b()

◆ qr_marginals()

◆ qr_one()

◆ qr_pc2()

◆ qr_qbal()

◆ qr_symmetry()

◆ qr_thm1()

◆ qr_thm1c()

◆ qr_thm2()

◆ qr_thm3a()

◆ qr_thm3b()

◆ qr_thm4()

◆ qr_xz()

◆ qr_zero_bounds()

◆ qrf_affine_matrices()

◆ qrf_build_q()

◆ qrf_build_q_ld()

◆ qrf_extract_mu_v()

◆ qrf_extract_results()

◆ qrf_feasible_start()

◆ qrf_feasible_start_lp()

◆ qrf_independent_rows()

◆ qrf_index_map()

◆ qrf_log()

◆ qrf_logtol()

◆ qrf_min_norm_point()

◆ qrf_noblo_bethe()

◆ qrf_noblo_mem()

◆ qrf_noblo_mmi()

◆ qrf_noblo_mmi_ld()

◆ qrf_noblo_mmi_linear()

◆ qrf_null_space()

◆ qrf_num_vars()

◆ qrf_polytope()

◆ qrf_reduce_equalities()

◆ solve_qrf_nlp()

◆ solve_qrf_nlp_lp()

◆ sub_qrfcon_noblo()

◆ sub_qrfvar()