Package jline.api.spn

Class Spn_lpbnd

java.lang.Object
jline.api.spn.Spn_lpbnd
public class Spn_lpbnd extends Object
Linear-programming bounds on the mean marking and the throughputs of a stochastic timed Petri net.

The stationary chain is relaxed to a MOMENT POLYTOPE: the uniformized evolution equation is written for E[X_p], E[X_p^2] and E[X_p1 X_p2], which gives linear equalities among the mean marking x, the enabling probabilities q and the products y(p,t) = E[X_p e_t]; behavioural and probabilistic inequalities are added on top; and every reported measure is then obtained by minimising and maximising its linear form over that polytope. Any stationary point of the true chain satisfies every row, so the two optima BRACKET the exact value whatever the polytope leaves out.

This is the Petri-net sibling of the QRF bounds in SolverBA: same technique, a different index space, and a LINEAR objective, so there is no stationary point to escape from and the answer is a property of the model alone.

VARIABLES, over place levels l = 0..L-1 and modes e = 0..E-1: x(l) the mean tokens, q(e) the probability that mode e is enabled, th(e) its throughput, u(e) the state-equation firing counts, and y(l,e) = E[X_l e_e] on the Markovian side only. u is EXISTENTIAL and is not reported: E[X] is a convex combination of reachable markings, each of which is m0 + C h for some nonnegative integer h, so the mean satisfies m0 + C u for some nonnegative real u.

LEVELS ARE (place, class) PAIRS, PLACE-MAJOR, level pp*R + k, the same coordinates Spn_mdd, Spn_sinvariants and Spn_conv use. MODES are (transition, mode) pairs in node order.

THE TOKEN COUNTS CREATED BY A FIRING ARE DETERMINISTIC IN LINE, which removes a whole branch of the reference: it allows sigma_(t,p)(n) to be random and splits the covariance family into an independent case (its eq. 7) and a selective one (its eq. 8). setFiringOutcome takes an integer weight, so E[sigma^2] = sigma^2 and E[sigma_p1 sigma_p2] = sigma_p1 sigma_p2 hold exactly and eq. (7) is the correct form. Eq. (8) has no LINE model behind it and is deliberately absent.

LIVENESS IS OFF BY DEFAULT, AND THAT IS DELIBERATE. The reference's two liveness rows (sum_t q_t >= 1 and x_p <= sum_t y_(p,t)) hold only on a live net, and liveness is not something this class can cheaply certify -- an inhibitor arc alone is enough to deadlock a net that looks well formed. A bound that silently assumed it would be wrong rather than loose on exactly the models where a bound is most wanted, so the rows are opt-in.

WHAT THE ROWS ARE WORTH, MEASURED. They are the whole of the lower side. On the reference's own Table 2 (its Fig. 2b production line, five rate vectors) assumelive reproduces its published l.b. column to four decimals -- 1.1653 against 1.165, 1.8288 against 1.829, 1.5814 against 1.581, 1.3592 against 1.359, 1.3497 against 1.350 -- while without them the Markovian lower bound collapses onto the OPERATIONAL one on four of the five. The upper side needs neither row and matches the published u.b.2 either way.

THE APACHE SIMPLEX SOLVER ASSUMES ONLY NON-NEGATIVITY, so every variable upper bound (q <= 1, x <= B, y <= B) is materialised as an explicit LEQ row, the same workaround Mapqn_bnd_lr_pf carries. The constraint set is built ONCE and reused across the one solve per reported cell; only the objective vector changes.

Reference: Z. Liu, "Performance Analysis of Stochastic Timed Petri Nets Using Linear Programming Approach", IEEE Trans. Software Engineering 24(11), 1998, 1014-1030. The constraint families are its Table 1, p. 1022; the bracket statement is its Theorem 3, p. 1021.

MATLAB twin: spn_lpbnd.m. Python twin: api/spn/lpbnd.py.

  • Method Details

    • spn_lpbnd

      public static Spn_lpbnd.SpnLpBounds spn_lpbnd(NetworkStruct sn)
      Bracket the mean tokens and the throughputs, with the default options.

    • spn_lpbnd

      public static Spn_lpbnd.SpnLpBounds spn_lpbnd(NetworkStruct sn, Spn_lpbnd.SpnLpOptions opt)
      Bracket the mean tokens and the throughputs of a stochastic Petri net.
      Parameters:
      sn - a NetworkStruct holding Places and Transitions
      opt - the relaxation options; null takes the defaults
      Returns:
      the brackets, per place level and per mode