 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
MVA-shaped linear-reduction bound for a closed network of M - 1 exponential queues and ONE MAP queue. More...
#include <cstddef>#include <string>#include <vector>#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"Go to the source code of this file.
Classes | |
| struct | line::mapqn::LrMvaParams< T > |
| Parameters of the MVA-shaped LR bound, mirroring the reference's params. More... | |
| struct | line::mapqn::MapqnBndLrMvaResult< T > |
| Result of an MVA-shaped LR bound solve. More... | |
| struct | line::mapqn::LrMvaIndex |
| Variable layout: UN, then QN, then B, in the reference's declaration order. More... | |
Namespaces | |
| namespace | line |
| namespace | line::mapqn |
Enumerations | |
| enum class | line::mapqn::MapqnObjectiveVar { line::mapqn::UN , line::mapqn::QN } |
| The variable family the objective is taken over. More... | |
Functions | |
| 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. | |
MVA-shaped linear-reduction bound for a closed network of M - 1 exponential queues and ONE MAP queue.
Templated port of matlab/lib/qrf/mapqn_bnd_lr_mva.m (ground truth), cross-checked against python/line_solver/api/mapqn/bnd_lr_mva.py.
A DIFFERENT MODEL, NOT A VARIANT. mapqn_bnd_lr relaxes onto the marginal probabilities p1(j,k,i,ni,h) and reads utilizations out of them. This one never introduces a probability variable at all: it works directly on the mean-value quantities UN(i,k), QN(i,k) and the conditional length B(j,k,i), in the manner of an MVA recursion turned into a relaxation. The consequence is a model of 2 M K + M^2 K columns instead of one quadratic in (N+1) sum_i K(i), so it is by far the cheapest bound in the family and the only one that stays small as the population grows. Nothing here is shared with mapqn_p1_common.h, and it deliberately does not use MapqnParams: the network shape is different (see LrMvaParams).
NETWORK SHAPE. Queues 1..M-1 are exponential with scalar rates muM(i), and queue M is the MAP, whose K levels are the phase process. That asymmetry is carried entirely by q(i,j,k,h) below and by nothing else, which is why the families read uniformly over i even though the stations are not alike.
THE FAILURE MODE OF THIS FAMILY IS A VACUOUS BOUND, NOT A CRASH. FLOW, UBAL, QBAL, MCC and MCC2 are the families that read the rates; the rest are structural. Drop the rate-bearing ones and UN = 0 stays feasible while every subscript remains internally consistent. Each family is emitted by a function named after the reference's own numbered section, so the inventory is diffable; do not inline them.
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 defaults to linprog's 'interior-point-legacy' here, which on these badly scaled instances is markedly more accurate than plain 'interior-point'.
Definition in file mapqn_bnd_lr_mva.h.
1.18.0