solver_ba_spnlp.h File Reference

Linear-programming bounds on the mean marking and the throughputs of a stochastic timed Petri net. More...

#include <cstddef>
#include <string>
#include "line/api/spn/spn_lpbnd.h"
#include "line/lang/qn/network_struct.h"
#include "line/solvers/ba/solver_ba_analyzer.h"
#include "line/util/error.h"

Include dependency graph for solver_ba_spnlp.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::ba

Functions
bool	line::ba::is_spnlp_method (const std::string &method)
	Whether a resolved method name belongs to the Petri-net LP family.
template<class T>
BaSolution< T >	line::ba::solver_ba_spnlp_analyzer (const qn::NetworkStruct< T > &L, const BaOptions &opt)
	Moment-relaxation LP bounds for a stochastic Petri net.

Detailed Description

Linear-programming bounds on the mean marking and the throughputs of a stochastic timed Petri net.

Port of matlab/src/solvers/BA/solver_ba_spnlp_analyzer.m. The polytope and the LP are spn::spn_lpbnd; this analyzer maps the LINE model onto them and reads one side of the bracket back per place.

METHOD NAMES. Four, in two families: spnlp.upper and spnlp.lower are the Markovian LP and need exponential firing times; spnlp.op.upper and spnlp.op.lower drop the second-moment, covariance and Little's-law families and the whole E[X_p e_t] block with them, which is what removes the exponential requirement and admits any phase-type law. The operational pair is much looser, and is the reference's own "without Markovian assumption" column.

BOUND CONVENTION. Q(i,0) is the reported side of the bracket on the mean number of tokens in place i. Tp(i,0) is the same side of the bracket on the token throughput of that place, and R follows by Little's law from the two. U(i,0) = Q(i,0) DELIBERATELY: a Place is an INF station and LINE reports U = Q at an infinite server, which is what SolverCTMC and solver_nc_spn_analyzer both do on the same net. The reference's place utilization 1 - P(m = 0) is a different quantity and is not this column.

SINGLE CLASS ONLY, and column 0 is the only one written, matching solver_nc_spn.h: spn_lpbnd puts one level per place because NetworkStruct::transparam carries no class dimension, and refuses a coloured net rather than collapse it. The MATLAB, JAR and python twins carry the class axis and do not have this restriction.

A TRANSITION GETS NO ROW. It is a stateful node and not a station, so it has no station index; the mode throughputs and enabling probabilities the LP also brackets stay inside spn_lpbnd's return value, the same way spn_metrics keeps mode_tput and mode_util off the table.

HOW TIGHT. The reference's own Table 2 measures it on a four-server production line: the upper side lands 2% to 11% above simulation and the lower side 30% to 40% below it, both comfortably inside the operational bounds it also reports. Expect a usable upper bound and a weak lower one.

Reference: Z. Liu (1998). Performance analysis of stochastic timed Petri nets using linear programming approach. IEEE Transactions on Software Engineering 24(11), 1014-1030.

Definition in file solver_ba_spnlp.h.