# A Simple Approach to Dynamic Optimisation of Flexible Optical Networks with Practical Application
## 7 Extensions and Generalisations
The new optimisation problem 'Generalised Dynamically Powered Relays for a Flexible Optical Network' (GDRP-FON) is, thus, defined as:  
```
GDRP-FON: MinimiseC(r[objective function] s.t.M,W[constraint]
```  
**Theorem. **_GDRP-FON is NP-complete._  
**Proof. ** (_informal_) Intuitively, by direct reduction to DPR-FON and the demonstration of polynomial certification (the full version follows). \(\square\)  
We now proceed to build a revised fast heuristic for GDRP-FON as follows:  
Once again, define the _hop matrix_, \(H\), as \(H\) = (\(h_{ij}\)) where \(\forall ij\), \(h_{ij}=\) 1_(a: link a is in the shortest path between \(i\) and \(j\))_. However, now for the extended GDRP-FON problem, these hop counts have to take into account link weights, \(W\) = (\(w_{ij}\)). Consequently, the first extended subroutine, AlgGH, again using _[PERSON]'s Shortest Path Algorithm_ becomes:  
```
AlgGH(Calculate hop matrix): \(\forall ij\), \(\overline{\forall ij}\), \(\overline{\text{\small{\sf{un}}}}\)\(DSPA\) to calculate\(H\) = (\(h_{ij}\)) using the weightings, \(W\) = (\(w_{ij}\)) as SPA edge costs (\(W\): input; \(H\): output) (note that DSPA still only runs _once_ to calculate each row of the matrix, \(H\), _not_ individually for each element, \(h_{ij}\). Additionally, although the \(w_{ij}\) values define actual weightings, the shortest path (the _result_), in each case, need only be recorded in hops, \(h_{ij}\)). The second subroutine, AlgGV, calculates the _viability matrix_, \(V\) = (\(v_{ij}\)), which now has to be extended in two respects. In defining the existence of a path between each node pair \(ij\), satisfying \(m_{ij}\) (now a local value), it must also take into account whether a relay is _present_ or _permitted_ at each node \(k\). For each _ij_ node pair, then, \(v_{ij}\) = \(T\) if the hop count between \(i\) and \(j\) is at most \(m_{ij}\) or a sequence of _permitted_ relays can be found between \(i\) and \(j\) with the hop count of each step between relays \(k\) and \(l\) at most \(m_{kl}\) (the limit is applied independently for each relay pair). ``` AlgGV(calculatetheviabilitymatrix): \(\forall ij\), \(\underline{\text{\small{\sf{setv}}}}_{ij}\)=Tif(\(h_{ij}\leq\)\(m_{ij}\)) \(\vee\)(\(\exists k\)\(\ldots\)\(\downarrow\), \(\ldots\) s.t. (\(p_{k}\)\(\wedge\)\(\ldots\)\(\wedge\)\(p_{1}\)\(\wedge\)\(r_{k}\)\(\wedge\)\(\ldots\)\(\wedge\)\(r_{1}\)=\(T\)) \(\wedge\)(\(h_{ik}\leq\)\(m_{ik}\)\(\wedge\)\(\ldots\)\(\wedge\)\(h_{lj}\leq\)\(m_{lj}\))); \(\forall ij\)=Fotherwise ```
This now allows us to reconsider the NP-completeness proof:  
**Theorem. **_GDRP-FON is NP-complete._  
**Proof. ** GDRP-FON is NP-hard since, for \(p_{k}\) = \(T\)\(\forall k\), \(d_{ij}\) = \(h_{ij}\)\(\forall ij\) and \(w_{ij}\) = \(m_{ij}\) = _constant_\(\forall ij\),  
DRP-FON reduces to it. As before, a certificate for GDRP-FON can be verified in polynomial time by the following algorithm:
``` runAlgGH runAlgGV if\(v_{ij}\)=T\(\forall ij\)then certificatevalid else certificateinvalid SinceGDRP-FON is NP-Hard and has polynomial time certificate verifiability, it is NP-complete. \(\square\)Again we return to the development of an equivalent fast heuristic for GDRP-FON, combining the newly-extended AlgGH and AlgGV subroutines. Once again, the complete algorithm starts by initialising all relays to be switched off, then uses a greedy heuristic to switch on _permitted_ relays, one at a time. The relay to be newly-powered is that which (is permitted and) has viable paths to the largest number of other nodes, _not_ currently acting as relays--thus maximising the number of _new_ nodes that are'reached/spanned' by the extra relay. Again, the algorithm terminates when the overall solution becomes viable, i.e., when paths between all node pairs (with or without intermediate relays) are viable. ```
AlgR(Optimiserelayarray)://-GDRP-FON-heuristic set\(r_{k}\)=F\(\forall\)K//Allrelaysswitchedoff runAlgGH//Calculatehoplengths runAlgGV//Calculateviablepaths while\(\exists ij\)s.t. \(\
u_{ij}\)=Fdo//ifmorerelaysneeded {find\(k\)s.t.