Submodular flow
ಕಾಂಬಿನೇಟೋರಿಯಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸಬ್ ಮಾಡ್ಯುಲರ್ ಫ್ಲೋ ಎಂಬುದು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳ ಸಾಮಾನ್ಯ ವರ್ಗವಾಗಿದ್ದು, ವಿಶೇಷ ಸಂದರ್ಭಗಳಲ್ಲಿ ಕನಿಷ್ಠ-ವೆಚ್ಚದ ಹರಿವಿನ ಸಮಸ್ಯೆ, ಮ್ಯಾಟ್ರಾಯಿಡ್ ಇಂಟರ್ಸೆಕ್ಷನ್ ಮತ್ತು ತೂಕದ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ನಲ್ಲಿ ಕನಿಷ್ಠ-ತೂಕದ ಡೈಜೋಯಿನ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಸಮಸ್ಯೆಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಇದನ್ನು ಮೂಲತಃ ಜ್ಯಾಕ್ ಎಡ್ಮಂಡ್ಸ್ ಮತ್ತು ರಿಕ್ ಗೈಲ್ಸ್ ಅವರು ರೂಪಿಸಿದರು ಮತ್ತು ಇದನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಶಾಸ್ತ್ರೀಯ ಕನಿಷ್ಠ-ವೆಚ್ಚದ ಹರಿವಿನ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಇನ್ಪುಟ್ ಒಂದು ಹರಿವಿನ ಜಾಲವಾಗಿದ್ದು, ಪ್ರತಿ ಅಂಚಿನ ಹರಿವಿನ ಪ್ರಮಾಣ ಮತ್ತು ಪ್ರತಿ ಅಂಚಿನ ಉದ್ದಕ್ಕೂ ಪ್ರತಿ ಘಟಕದ ಹರಿವಿನ ವೆಚ್ಚಗಳ ಮೇಲೆ ಕಡಿಮೆ ಮತ್ತು ಮೇಲಿನ ಮಿತಿಗಳನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುವ ನಿರ್ದಿಷ್ಟ ಸಾಮರ್ಥ್ಯಗಳನ್ನು ಹೊಂದಿದೆ. ಪ್ರತಿ ತುದಿಯಲ್ಲಿರುವ ಸಾಮರ್ಥ್ಯಗಳನ್ನು ಪಾಲಿಸುವ ಹರಿವಿನ ಪ್ರಮಾಣಗಳ ವ್ಯವಸ್ಥೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ ಒಟ್ಟು ಹರಿವಿನ ಪ್ರಮಾಣವು ಒಟ್ಟು ಹರಿವಿನ ಪ್ರಮಾಣಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ ಮತ್ತು ಕನಿಷ್ಠ ಒಟ್ಟು ವೆಚ್ಚವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂಬ ಕಿರ್ಚಾಫ್ನ ನಿಯಮವನ್ನು ಪಾಲಿಸುವುದು ಇದರ ಗುರಿಯಾಗಿದೆ. ಸಬ್ ಮಾಡ್ಯುಲರ್ ಹರಿವಿನಲ್ಲಿ, ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಸೆಟ್ಗಳಲ್ಲಿ ಸಬ್ ಮಾಡ್ಯುಲರ್ ಸೆಟ್ ಕಾರ್ಯವನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ಕಿರ್ಚಾಫ್ನ ನಿಯಮವನ್ನು ಪಾಲಿಸುವ ಬದಲು, ಪ್ರತಿ ಶೃಂಗದ ಸೆಟ್ಗೆ, ಹೆಚ್ಚುವರಿ ಹರಿವು (ಫ್ಲೋ ಇನ್ ಮತ್ತು ಫ್ಲೋ ಔಟ್ ನಡುವಿನ ವ್ಯತ್ಯಾಸಕ್ಕೆ ಸೆಟ್ ಅನ್ನು ಮ್ಯಾಪಿಂಗ್ ಮಾಡುವ ಕಾರ್ಯ) ಸಬ್ ಮಾಡ್ಯುಲರ್ ಕಾರ್ಯದಿಂದ ನೀಡಲಾದ ಮೌಲ್ಯವಾಗಿರಬಹುದು. ಉಲ್ಲೇಖಗಳ ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್