mapqn_bnd_qr_ld.h File Reference

Quadratic-reduction bound on a marginal of a load-dependent MAP queueing network. More...

#include "line/api/mapqn/mapqn_params.h"
#include "line/api/mapqn/mapqn_qr_common.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/simplex.h"

Include dependency graph for mapqn_bnd_qr_ld.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::mapqn

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

Detailed Description

Quadratic-reduction bound on a marginal of a load-dependent MAP queueing network.

Templated port of matlab/lib/qrf/mapqn_bnd_qr_ld.m (ground truth) and of jar/src/main/java/jline/api/mapqn/Mapqn_bnd_qr_ld.java.

What it computes: the exact stationary distribution of a MAP queueing network is intractable, so the quadratic reduction keeps only the PAIRWISE joint distribution p2(j,nj,k,i,ni,h) – the probability that queue j holds nj jobs in phase k while queue i holds ni jobs in phase h – and imposes every linear relation the true distribution must satisfy: normalization (ONE), the states that cannot occur (ZERO1/2/3), symmetry of the pair, consistency of the pairwise law with its own marginal (MARGINALS), Little's law (THM1, THM1c), the second moment of the population (PC2), phase balance (THM2), population flow balance (THM3a, THM3b), queue balance (QBAL), the order-1 correlation cuts (COR1a, COR1b) and the QMIN inequality (THM4). The true distribution is feasible for that polytope, so maximizing or minimizing one coordinate over it BOUNDS the corresponding true probability. The bound is a relaxation, not an approximation: it is valid, not merely close.

The objective coordinate is the diagonal entry p2(objective_queue, objective_n, objective_phase, same, same, same), which is P(queue j holds n jobs in phase k). Summing the bound over n >= 1 and k is how the reference obtains a utilization bound.

Arithmetic: the whole assembly is +, -, * and / on the model data, and the LP is solved by line::lp::simplex_solve, which uses Bland's rule and no tolerance. At T = line::Rational the returned bound is therefore the EXACT optimum of the exact polytope, with no LP tolerance at all – unlike the MATLAB reference, which reaches it with interior-point linprog and lands a few digits short (its own comment records ~1e-7 residual error on the paper's BAS instance), and unlike the JAR, which uses a double-precision Apache Commons simplex.

Variable bounds: 0 <= p2 <= 1 with the ZERO states pinned to 0 are passed to the solver as bounds. They do NOT become rows the way the JAR needs them to, because Apache SimplexSolver does not box variables and the maximization is unbounded without them; LpModel boxes natively, substitutes out the pinned variables entirely, and materializes at most one row per genuinely upper-bounded variable.

Cost: the model has ((N+1) sum_i K(i))^2 variables, so it grows as the fourth power of the population. The tableau here is dense, which confines the port to small and medium instances; the reference's large blocking instances need a sparse revised simplex.

Definition in file mapqn_bnd_qr_ld.h.