mapqn_bnd_lr_pf.h File Reference

Linear-reduction (LR) bound on the utilization of one station of a closed product-form network. More...

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

Include dependency graph for mapqn_bnd_lr_pf.h:

Go to the source code of this file.

Classes
struct	line::mapqn::LrPfParams< T >
	Product-form parameters of the LR bound, mirroring MATLAB's params. More...
struct	line::mapqn::LrPfResult< T >
	Return value of mapqn_bnd_lr_pf, mirroring the MATLAB result struct. More...

Namespaces
namespace	line
namespace	line::mapqn

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

Detailed Description

Linear-reduction (LR) bound on the utilization of one station of a closed product-form network.

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

WHAT MAKES IT A BOUND. The exact stationary distribution satisfies every constraint assembled below – normalization, the utilization and queue-length definitions, population conservation, the global flow balance of Gordon-Newell and the joint-marginal identities – but those constraints do not pin it down. The feasible set is therefore a POLYTOPE CONTAINING the exact solution, so minimizing U_i over it cannot exceed the true utilization and maximizing it cannot fall short. Both senses are valid bounds, which is why one routine serves lr.lower and lr.upper.

NOT TO BE CONFUSED WITH qrf.mmi.linear, whose name refers only to its explicit Aeq/beq constraint representation: its OBJECTIVE is the nonlinear MEM entropy and it needs fmincon. This method is an LP end to end, which is exactly why it ports and the rest of the QRF family does not.

ARITHMETIC. Assembly is additions and multiplications, and the optimum is a vertex of a rational polytope, so at Rational the bound is EXACT and is deliberately left ungated: lp::simplex_solve uses Bland's rule with no tolerance under exact arithmetic. MATLAB reaches the same vertex through linprog's interior-point method, which approaches it from the interior and stops a few digits short; a deviation against MATLAB is therefore expected to be MATLAB's convergence gap and not this port's error.

COST. The variable count is 2M + M^2 + 2 M^2 (N+1) and the row count is O(M^2 + M N), so the LP grows quadratically in the station count and linearly in the population. It is a bound, not a cheap one.

Definition in file mapqn_bnd_lr_pf.h.