Operator Calculus Algorithms for Multi-Constrained Paths
Résumé
Classical approaches to multi-constrained routing problems generally require construction of trees and the use of heuristics to prevent combinatorial explosion. Introduced here is the notion of constrained path algebras and their application to multi-constrained path problems. The inherent combinatorial properties of these algebras make them useful for routing problems by implicitly pruning the underlying tree structures. Operator calculus (OC) methods are generalized to multiple non-additive constraints in order to develop algorithms for the multi constrained path problem and multi constrained optimization problem. Theoretical underpinnings are developed first, then algorithms are presented. These algorithms demonstrate the tremendous simplicity, flexibility and speed of the OC approach. Algorithmsare implemented inMathematica and Java and applied to a problem first proposed by Ben Slimane et al. as an example.