Quadratic assignment problem
ಕ್ವಾಡ್ರಾಟಿಕ್ ಅಸೈನ್ಮೆಂಟ್ ಪ್ರಾಬ್ಲಮ್ (ಕ್ಯೂಎಪಿ) ಎಂಬುದು ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅಥವಾ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಶೋಧನೆಯ ಶಾಖೆಯಲ್ಲಿನ ಮೂಲಭೂತ ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ, ಇದು ಕೂಪ್ಮನ್ಸ್ ಮತ್ತು ಬೆಕ್ಮನ್ ಅವರು ಮೊದಲು ಪರಿಚಯಿಸಿದ ಸೌಲಭ್ಯಗಳ ಸ್ಥಳ ಸಮಸ್ಯೆಗಳ ವರ್ಗದಿಂದ. ಸಮಸ್ಯೆಯು ಈ ಕೆಳಗಿನ ನಿಜ ಜೀವನದ ಸಮಸ್ಯೆಯನ್ನು ರೂಪಿಸುತ್ತದೆಃ n ಸೌಲಭ್ಯಗಳ ಒಂದು ಸೆಟ್ ಮತ್ತು n ಸ್ಥಳಗಳ ಒಂದು ಸೆಟ್ ಇದೆ. ಪ್ರತಿ ಜೋಡಿ ಸ್ಥಳಗಳಿಗೆ, ದೂರವನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಜೋಡಿ ಸೌಲಭ್ಯಗಳಿಗೆ ತೂಕ ಅಥವಾ ಹರಿವನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸಲಾಗುತ್ತದೆ (ಉದಾಹರಣೆಗೆ, ಎರಡು ಸೌಲಭ್ಯಗಳ ನಡುವೆ ಸಾಗಿಸಲಾದ ಸರಬರಾಜುಗಳ ಪ್ರಮಾಣ). ಸಂಬಂಧಿತ ಹರಿವುಗಳಿಂದ ಗುಣಿಸಲಾದ ದೂರಗಳ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಗುರಿಯೊಂದಿಗೆ ವಿವಿಧ ಸ್ಥಳಗಳಿಗೆ ಎಲ್ಲಾ ಸೌಲಭ್ಯಗಳನ್ನು ನಿಯೋಜಿಸುವುದು ಸಮಸ್ಯೆಯಾಗಿದೆ. ಅಂತರ್ಬೋಧೆಯಿಂದ, ವೆಚ್ಚದ ಕಾರ್ಯವು ಪರಸ್ಪರರ ನಡುವೆ ಹೆಚ್ಚಿನ ಹರಿವನ್ನು ಹೊಂದಿರುವ ಸೌಲಭ್ಯಗಳನ್ನು ಒಟ್ಟಿಗೆ ಇರಿಸಲು ಪ್ರೋತ್ಸಾಹಿಸುತ್ತದೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ನಿಯೋಜನೆಯ ಸಮಸ್ಯೆಯನ್ನು ಹೋಲುತ್ತದೆ, ವೆಚ್ಚದ ಕಾರ್ಯವನ್ನು ಚತುರ್ಭುಜ ಅಸಮಾನತೆಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ವ್ಯಕ್ತಪಡಿಸಲಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ಈ ಹೆಸರು ಬಂದಿದೆ. ಔಪಚಾರಿಕ ಗಣಿತದ ವ್ಯಾಖ್ಯಾನ ಚತುರ್ಭುಜ ನಿಯೋಜನೆ ಸಮಸ್ಯೆಯ ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನವು ಈ ಕೆಳಗಿನಂತಿದೆಃ ಸಮಾನ ಗಾತ್ರದ ಎರಡು ಸೆಟ್ಗಳಾದ ಪಿ ("ಸೌಲಭ್ಯಗಳು") ಮತ್ತು ಎಲ್ ("ಸ್ಥಳಗಳು"), ತೂಕದ ಕಾರ್ಯದೊಂದಿಗೆ ಡಬ್ಲ್ಯೂಃ ಪಿ × ಪಿ → ಆರ್ ಮತ್ತು ದೂರ ಕಾರ್ಯ ಡಿಃ ಎಲ್ × ಎಲ್ → ಆರ್. ಸಾಮಾನ್ಯವಾಗಿ ತೂಕ ಮತ್ತು ದೂರ ಕಾರ್ಯಗಳನ್ನು ಚದರ ನೈಜ-ಮೌಲ್ಯದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳಾಗಿ ನೋಡಲಾಗುತ್ತದೆ, ಆದ್ದರಿಂದ ವೆಚ್ಚ ಕಾರ್ಯವನ್ನು ಹೀಗೆ ಬರೆಯಲಾಗುತ್ತದೆಃ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಸಂಕೇತದಲ್ಲಿಃ ಕ್ರಮಪಲ್ಲಟನೆ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳ ಸೆಟ್ ಎಲ್ಲಿದೆ, ಇದು ತೂಕದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಮತ್ತು ದೂರ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ, ಆದ್ದರಿಂದ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಯಾವುದೇ ಅಲ್ಗಾರಿದಮ್ ತಿಳಿದಿಲ್ಲ, ಮತ್ತು ಸಣ್ಣ ನಿದರ್ಶನಗಳಿಗೆ ಸಹ ದೀರ್ಘ ಗಣನೆಯ ಸಮಯ ಬೇಕಾಗಬಹುದು. ಪಿ = ಎನ್ಪಿ ಹೊರತುಪಡಿಸಿದರೆ, ಸಮಸ್ಯೆಯು ಯಾವುದೇ (ಸ್ಥಿರ) ಅಂಶಕ್ಕೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಚಾಲನೆಯಲ್ಲಿರುವ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಹೊಂದಿಲ್ಲ ಎಂದು ಸಹ ಸಾಬೀತಾಗಿದೆ. ಹರಿವುಗಳು ಒಂದೇ ವೃತ್ತದ ಉದ್ದಕ್ಕೂ ಎಲ್ಲಾ ಸೌಲಭ್ಯಗಳನ್ನು ಸಂಪರ್ಕಿಸುತ್ತವೆ, ಎಲ್ಲಾ ಹರಿವುಗಳು ಒಂದೇ ಶೂನ್ಯವಲ್ಲದ (ಸ್ಥಿರ) ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಎಲ್ಲಾ ದೂರಗಳು ಟಿಎಸ್ಪಿ ನಿದರ್ಶನದ ಆಯಾ ದೂರಗಳಿಗೆ ಸಮಾನವಾಗಿರುತ್ತವೆ ಎಂದು ಭಾವಿಸಿದರೆ ಟ್ರಾವೆಲಿಂಗ್ ಸೇಲ್ಸ್ಮ್ಯಾನ್ ಪ್ರಾಬ್ಲೆಮ್ (ಟಿಎಸ್ಪಿ) ಅನ್ನು ಕ್ಯೂಎಪಿಯ ವಿಶೇಷ ಪ್ರಕರಣವೆಂದು ಪರಿಗಣಿಸಬಹುದು. ಸ್ಟ್ಯಾಂಡರ್ಡ್ ಕಾಂಬಿನೇಟೋರಿಯಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳ ಇತರ ಅನೇಕ ಸಮಸ್ಯೆಗಳನ್ನು ಈ ರೂಪದಲ್ಲಿ ಬರೆಯಬಹುದು. ಮೂಲ ಸ್ಥಾವರ ಸ್ಥಳ ಸೂತ್ರೀಕರಣದ ಜೊತೆಗೆ, ಕ್ಯೂ. ಎ. ಪಿ. ಯು ಎಲೆಕ್ಟ್ರಾನಿಕ್ಸ್ ಉದ್ಯಮದಲ್ಲಿ ಕಂಪ್ಯೂಟರ್ ನೆರವಿನ ವಿನ್ಯಾಸದ ಸ್ಥಳ ಮತ್ತು ಮಾರ್ಗ ಹಂತದ ಭಾಗವಾಗಿರುವ ಮುದ್ರಿತ ಸರ್ಕ್ಯೂಟ್ ಬೋರ್ಡ್ ಅಥವಾ ಮೈಕ್ರೋಚಿಪ್ನಲ್ಲಿ ಪರಸ್ಪರ ಸಂಪರ್ಕಿತ ಎಲೆಕ್ಟ್ರಾನಿಕ್ ಘಟಕಗಳನ್ನು ಇರಿಸುವ ಸಮಸ್ಯೆಯ ಗಣಿತದ ಮಾದರಿಯಾಗಿದೆ. ಕ್ವಾಡ್ರಾಟಿಕ್ ಬಾಟಲ್ನೆಕ್ ಅಸೈನ್ಮೆಂಟ್ ಸಮಸ್ಯೆಯ ಉಲ್ಲೇಖಗಳು ಟಿಪ್ಪಣಿಗಳ ಮೂಲಗಳು A2.5: ND43, pg.218 ಅನ್ನು ಸಹ ನೋಡಿ. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು https://www.opt.math.tugraz.at/qaplib QAPLIB-ಕ್ವಾಡ್ರಾಟಿಕ್ ಅಸೈನ್ಮೆಂಟ್ ಪ್ರಾಬ್ಲಮ್ ಲೈಬ್ರರಿ http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal MAOS-QAP-ಜಾವಾ ಆಧಾರಿತ ಕ್ವಾಡ್ರಾಟಿಕ್ ಅಸೈನ್ಮೆಂಟ್ ಪ್ರಾಬ್ಲಮ್ ಸಾಲ್ವರ್ https://CRAN.R-project.org/package=qap-R ಪ್ಯಾಕೇಜ್ qAP: ಕ್ವಾಡ್ರಾಟಿಕ್ ಅಸೈನ್ಮೆಂಟ್ ಪ್ರಾಬ್ಲಮ್ಗಾಗಿ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ-ವಿಂಡೋಸ್ಗಾಗಿ ಮೆಟಾಹೆರಿಯಿಸ್ಟಿಕ್ QAP ಸಾಲ್ವರ್ 10/11 NP-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಗಳ ಸಂಯೋಜನೆಯ ಆಪ್ಟಿಮೈಸೇಶನ್