A layered queueing network as ONE nonlinear program: linear constraints over the flows, the service-time composition and the closures, plus a nonlinear objective that is the sum of squares of the QD-AMVA congestion and Little laws (Casale, Perez and Wang, PERFORMANCE 2015). More...

#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <map>
#include <memory>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
#include "line/api/lqn/lqn_balance_equations.h"
#include "line/lang/lqn/lqn_struct.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for lqn_export_nlp.h:

Classes
struct	line::lqn::NlpLld
	A declared queue-dependent rate multiplier of one station: an expression in n, or a tabulated lldscaling row, which is refused because its interpolant has a corner at every knot. More...
struct	line::lqn::NlpOptions
	Options of the program: python export_nlp(lld=, alpha=, fork=). More...
struct	line::lqn::nlp_detail::LldEvalError
	An evaluation failure, carrying the python exception name the message reports. More...
struct	line::lqn::nlp_detail::LldSyntaxError
	A parse failure: the text is not an expression of the grammar. More...
class	line::lqn::nlp_detail::LldExpr
	An lld expression, parsed once and evaluated over std::complex<double>. More...
struct	line::lqn::NlpRate
	The queue-dependent rate of one station, r(n) = softmin(n, m) [* lld(n)], or n at a delay. More...
struct	line::lqn::NlpSolveResult
	What NlpProgram::solve returns: python's Result. More...
class	line::lqn::NlpProgram
	The program of one layered model. More...
struct	line::lqn::NlpProgram::Bil
struct	line::lqn::NlpProgram::Nlt
struct	line::lqn::NlpProgram::Mnl
struct	line::lqn::NlpProgram::Sweep
struct	line::lqn::nlp_detail::ForkBlock
	One AND-fork/join block, in absolute LQN indices. More...

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
namespace	line::lqn
namespace	line::lqn::nlp_detail

Typedefs
using	line::lqn::nlp_detail::cplx = std::complex<double>

Functions
std::string	line::lqn::nlp_detail::fmt (const char *f, double v)
std::string	line::lqn::nlp_detail::py_repr (double v)
	Python's repr of a float: the shortest round-tripping digits, in python's layout.
std::string	line::lqn::nlp_detail::py_repr (const cplx &z)
	Python's repr of a value that may be complex.
double	line::lqn::nlp_detail::re (double x)
double	line::lqn::nlp_detail::re (const cplx &z)
template<class S>
S	line::lqn::nlp_detail::softmin (const S &a, const S &b, double alpha)
	Smooth stand-in for min(a, b), verbatim python _SOFTMIN_SRC; real or complex.
std::string	line::lqn::nlp_detail::check_lld (const std::string &src, std::shared_ptr< const LldExpr > &out)
	Why an lld expression cannot be used, or empty: python _check_lld verbatim.
std::vector< double >	line::lqn::nlp_detail::lstsq_min_norm (const Matrix< double > &A, const std::vector< double > &b)
	One-sided Jacobi SVD of A (m x n), returning the min-norm least-squares solution of A x = b.
double	line::lqn::nlp_detail::norm2 (const std::vector< double > &v)
template<class S>
S	line::lqn::fj_max_exp (const std::vector< S > &m)
	E[max] of K independent EXPONENTIAL branch completion times of means m, with the reciprocals cleared so a branch of zero mean contributes zero: sum over nonempty S of (-1)^(\|S\|+1) prod_{i in S} m_i / sum_{i in S} prod_{j in S, j != i} m_j.
std::vector< double >	line::lqn::fj_max_exp_grad (const std::vector< double > &u)
	Gradient of fj_max_exp by complex step, one coordinate at a time.
UnsupportedError	line::lqn::nlp_detail::nlp_error (const std::string &msg)
template<class T>
std::string	line::lqn::nlp_detail::elem (const LqnStruct< T > &lqn, std::size_t idx)
template<class T>
std::string	line::lqn::nlp_detail::callnm (const LqnStruct< T > &lqn, std::size_t c)
template<class T>
double	line::lqn::nlp_detail::hostdem_mean (const LqnStruct< T > &lqn, std::size_t a)
template<class T>
bool	line::lqn::nlp_detail::is_post_and (const LqnStruct< T > &lqn, std::size_t a)
template<class T>
bool	line::lqn::nlp_detail::is_pre_and (const LqnStruct< T > &lqn, std::size_t a)
template<class T>
std::size_t	line::lqn::nlp_detail::quorum_of (const LqnStruct< T > &lqn, std::size_t a)
template<class T>
std::string	line::lqn::nlp_detail::read_block (const LqnStruct< T > &lqn, const std::vector< std::size_t > &A, const std::vector< std::size_t > &H, const std::vector< std::size_t > &srcs, const std::map< std::size_t, std::vector< std::size_t > > &succ, const std::map< std::size_t, std::vector< std::size_t > > &prd, ForkBlock &blk)
	python _read_block: one candidate block, or the reason it is not one.
template<class T>
std::vector< ForkBlock >	line::lqn::nlp_detail::fork_blocks (const LqnStruct< T > &lqn, const std::string &fork, std::vector< std::string > &bad)
	python _fork_blocks: the well-formed blocks, and every AND marking outside one.
template<class T>
std::vector< ForkBlock >	line::lqn::nlp_detail::scope_check (const LqnStruct< T > &lqn, const std::string &fork)
	python _scope_check: the blocks, or LINE:unsupported:NlpExport naming every offender.
double	line::lqn::nlp_detail::tot (const std::vector< double > &pops)
double	line::lqn::nlp_detail::delta (double t)
std::string	line::lqn::nlp_detail::strip (const std::string &s)
template<class T>
NlpProgram	line::lqn::lqn_nlp_program (const LqnStruct< T > &lqn, const NlpOptions &opt=NlpOptions(), const std::string &name="")
	Build the nonlinear program of a layered model: python export_nlp without the emission, i.e.

Detailed Description

A layered queueing network as ONE nonlinear program: linear constraints over the flows, the service-time composition and the closures, plus a nonlinear objective that is the sum of squares of the QD-AMVA congestion and Little laws (Casale, Perez and Wang, PERFORMANCE 2015).

Twin of python line_solver.api.lqn.lqn_export_nlp. The python exporter EMITS a self-contained script; that emission is python-only by design. What is ported is the PROGRAM the script builds, constructed in memory: the same element numbering, the same variable layout

Xe(NE) Xa(NA) Xc(NC) W(NA) S(NE) R(NC) Q(NA) Qt(NC) BC(NC) BR(NR) GH(NGH) GT(NGT) SA(NE if forking)

the same row order of AEQ/AUB, the same residual order, the same refusals (LINE:unsupported:NlpExport) and the same solve: Newton on the square system with a minimum-norm least-squares step, escalating the warm-start sweeps 0, 5, 20, 100 before falling back to a constrained descent.

THE FALLBACK DIFFERS FROM PYTHON. Python falls back to scipy's trust-constr; this port runs a projected Levenberg-Marquardt on the merit ||r||^2 + ||AEQ x - BEQ||^2 + ||max(0, AUB x - BUB)||^2 over x >= 0, identical in MATLAB, the JAR and C++. Every model the reference suite solves is rooted by the Newton ladder, which reaches the same root in every codebase.

Rate functions r_i(n) = softmin(n, m_i) [* lld_i(n)] and the AND-fork closure are differentiated by COMPLEX STEP, as in python. A declared lld multiplier is an expression in n over a small grammar shared by the four codebases:

expr  := term (('+'|'-') term)*        term  := unary (('*'|'/') unary)*
unary := ('+'|'-') unary | power       power := atom ('**' unary)?
atom  := NUMBER | 'n' | FUNC '(' expr {',' expr} ')' | '(' expr ')'
FUNC  := exp | log | sqrt | sin | cos | tanh | abs | min | max, optionally np. or math.

abs is the real modulus and min/max reject a complex argument, so both are caught by the analyticity check exactly as python catches them.

Definition in file lqn_export_nlp.h.

Classes

Namespaces

Typedefs

Functions

Detailed Description