Configuration linear program
ಕಾನ್ಫಿಗರೇಶನ್ ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಂ (ಕಾನ್ಫಿಗರೇಶನ್-ಎಲ್ಪಿ) ಎಂಬುದು ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಬಳಸುವ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ತಂತ್ರವಾಗಿದೆ. ದಾಸ್ತಾನು ಕಡಿತದ ಸಮಸ್ಯೆಯ ಹಿನ್ನೆಲೆಯಲ್ಲಿ ಇದನ್ನು ಪರಿಚಯಿಸಲಾಯಿತು. ನಂತರ, ಇದನ್ನು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಮತ್ತು ಉದ್ಯೋಗ ವೇಳಾಪಟ್ಟಿ ಸಮಸ್ಯೆಗಳಿಗೆ ಅನ್ವಯಿಸಲಾಗಿದೆ. ಕಾನ್ಫಿಗರೇಶನ್-ಎಲ್ಪಿಯಲ್ಲಿ, ಪ್ರತಿಯೊಂದು ಸಂಭವನೀಯ ಸಂರಚನೆಗೆ ಒಂದು ವೇರಿಯೇಬಲ್ ಇರುತ್ತದೆ-ಒಂದೇ ಬಿನ್ನಲ್ಲಿ ಹೊಂದಿಕೊಳ್ಳಬಹುದಾದ ಪ್ರತಿಯೊಂದು ಸಂಭವನೀಯ ಮಲ್ಟಿಸೆಟ್ ಐಟಂಗಳು (ಈ ಸಂರಚನೆಗಳನ್ನು ಮಾದರಿಗಳು ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ). ಸಾಮಾನ್ಯವಾಗಿ, ಸಮಸ್ಯೆಯ ಗಾತ್ರದಲ್ಲಿ ಸಂರಚನೆಗಳ ಸಂಖ್ಯೆಯು ಘಾತೀಯವಾಗಿರುತ್ತದೆ, ಆದರೆ ಕೆಲವು ಸಂದರ್ಭಗಳಲ್ಲಿ ಬಹುಪದೀಯ ಸಂಖ್ಯೆಯ ಸಂರಚನೆಗಳನ್ನು ಮಾತ್ರ ಬಳಸಿಕೊಂಡು ಅಂದಾಜು ಪರಿಹಾರಗಳನ್ನು ಸಾಧಿಸಲು ಸಾಧ್ಯವಿದೆ. ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ನಲ್ಲಿ ಅವಿಭಾಜ್ಯ ಎಲ್ಪಿ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಸಮಸ್ಯೆಯಲ್ಲಿ, ವಿವಿಧ ಗಾತ್ರಗಳ n ವಸ್ತುಗಳು ಇರುತ್ತವೆ. ವಸ್ತುಗಳನ್ನು ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಡಬ್ಬಿಗಳಲ್ಲಿ ಪ್ಯಾಕ್ ಮಾಡುವುದು ಗುರಿಯಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಬಿನ್ ಗರಿಷ್ಠ ಬಿ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಕಾರ್ಯಸಾಧ್ಯವಾದ ಸಂರಚನೆಯು ಗರಿಷ್ಠ ಬಿ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುವ ಗಾತ್ರಗಳ ಗುಂಪಾಗಿದೆ. ಉದಾಹರಣೆಃ ವಸ್ತುವಿನ ಗಾತ್ರಗಳು 3,3,3,3,3,4,4,4,4,4, ಮತ್ತು B = 12 ಎಂದು ಭಾವಿಸೋಣ. ನಂತರ ಸಂಭವನೀಯ ಸಂರಚನೆಗಳುಃ 3333; 333; 33,334,344; 4,44,444. ನಾವು ಗಾತ್ರ 3 ರ ಮೂರು ವಸ್ತುಗಳನ್ನು ಮಾತ್ರ ಹೊಂದಿದ್ದರೆ, ನಾವು 3333 ಸಂರಚನೆಯನ್ನು ಬಳಸಲು ಸಾಧ್ಯವಾಗಲಿಲ್ಲ. ವಿವಿಧ ಗಾತ್ರಗಳ ಗುಂಪನ್ನು (ಮತ್ತು ಅವುಗಳ ಸಂಖ್ಯೆಯನ್ನು) S ನಿಂದ ಸೂಚಿಸಿ. ವಿವಿಧ ಸಂರಚನೆಗಳ ಗುಂಪನ್ನು (ಮತ್ತು ಅವುಗಳ ಸಂಖ್ಯೆಯನ್ನು) C ಯಿಂದ ಸೂಚಿಸಿ. ಎಸ್ನಲ್ಲಿ ಪ್ರತಿ ಗಾತ್ರಕ್ಕೆ ಎಸ್ ಮತ್ತು ಸಿನಲ್ಲಿ ಕಾನ್ಫಿಗರೇಶನ್ ಸಿ, ಸೂಚಿಸುತ್ತದೆಃ ಎನ್ಎಸ್-ಗಾತ್ರದ ವಸ್ತುಗಳ ಸಂಖ್ಯೆ ಎಸ್, ಸಿ-ಸಂರಚನೆಯಲ್ಲಿ ಗಾತ್ರದ ಘಟನೆಗಳ ಸಂಖ್ಯೆ ಸಿ. ಎಕ್ಸ್ಸಿ-ಸಂರಚನೆಯೊಂದಿಗೆ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುವ ವೇರಿಯೇಬಲ್ ಸಿ. ನಂತರ, ಬಿನ್-ಪ್ಯಾಕಿಂಗ್ನ ಕಾನ್ಫಿಗರೇಶನ್ ಎಲ್ಪಿಃ ಎಸ್ನಲ್ಲಿರುವ ಎಲ್ಲಾ ಎಸ್ಗಳಿಗೆ (-ಗಾತ್ರದ ಎಲ್ಲಾ ಎನ್ಎಸ್ ಐಟಂಗಳನ್ನು ಪ್ಯಾಕ್ ಮಾಡಲಾಗಿದೆ). ಸಿ ಯಲ್ಲಿನ ಎಲ್ಲಾ ಸಿ ಗೆ (-ಒಟ್ಟಾರೆಯಾಗಿ ಗರಿಷ್ಠ ಎನ್ ತೊಟ್ಟಿಗಳಿವೆ, ಆದ್ದರಿಂದ ಪ್ರತಿ ಪ್ರತ್ಯೇಕ ಸಂರಚನೆಯ ಗರಿಷ್ಠ ಎನ್). ಸಂರಚನೆ ಎಲ್ಪಿ ಒಂದು ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂ ಆಗಿದೆ, ಆದ್ದರಿಂದ ಸಾಮಾನ್ಯವಾಗಿ ಇದು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದೆ. ಇದಲ್ಲದೆ, ಸಮಸ್ಯೆಯೂ ಸಹ ಸಾಮಾನ್ಯವಾಗಿ ಬಹಳ ದೊಡ್ಡದಾಗಿದೆಃ ಇದು ಸಿ ಅಸ್ಥಿರಗಳು ಮತ್ತು ಎಸ್ ನಿರ್ಬಂಧಗಳನ್ನು ಹೊಂದಿದೆ. ಚಿಕ್ಕ ಐಟಂ ಗಾತ್ರವು ಇಬಿ ಆಗಿದ್ದರೆ (ಕೆಲವು ಭಿನ್ನರಾಶಿ ಇ ಇನ್ (0,1))), ನಂತರ ಪ್ರತಿ ಬಿನ್ನಲ್ಲಿ 1/ಇ ಐಟಂಗಳವರೆಗೆ ಇರಬಹುದು, ಆದ್ದರಿಂದ ಸಂರಚನೆಗಳ ಸಂಖ್ಯೆ ಸಿ ~ ಎಸ್ 1/ಇ, ಇ ಚಿಕ್ಕದಾಗಿದ್ದರೆ ಅದು ತುಂಬಾ ದೊಡ್ಡದಾಗಿರಬಹುದು (ಇ ಅನ್ನು ಸ್ಥಿರವೆಂದು ಪರಿಗಣಿಸಿದರೆ, ನಂತರ ಪೂರ್ಣಾಂಕ ಎಲ್ಪಿಯನ್ನು ಸಮಗ್ರ ಹುಡುಕಾಟದಿಂದ ಪರಿಹರಿಸಬಹುದುಃ ಗರಿಷ್ಠ ಎಸ್ 1/ಇ ಸಂರಚನೆಗಳಿವೆ, ಮತ್ತು ಪ್ರತಿ ಸಂರಚನೆಗೆ ಗರಿಷ್ಠ ಎನ್ ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳಿವೆ, ಆದ್ದರಿಂದ ಪರಿಶೀಲಿಸಲು ಹೆಚ್ಚಿನ ಸಂಯೋಜನೆಗಳಿವೆ. ಪ್ರತಿ ಸಂಯೋಜನೆಗೆ, ನಾವು S ನಿರ್ಬಂಧಗಳನ್ನು ಪರಿಶೀಲಿಸಬೇಕು, ಆದ್ದರಿಂದ ರನ್-ಟೈಮ್, ಇದು S, e ಸ್ಥಿರವಾಗಿದ್ದಾಗ n ನಲ್ಲಿ ಬಹುಪದವಾಗಿದೆ). ಆದಾಗ್ಯೂ, ಈ ಐಎಲ್ಪಿ ಹಲವಾರು ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳಿಗೆ ಆಧಾರವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಈ ಕ್ರಮಾವಳಿಗಳ ಮುಖ್ಯ ಉದ್ದೇಶವು ಮೂಲ ನಿದರ್ಶನವನ್ನು ಹೊಸ ನಿದರ್ಶನವಾಗಿ ಕಡಿಮೆ ಮಾಡುವುದು, ಇದರಲ್ಲಿ ಎಸ್ ಚಿಕ್ಕದಾಗಿದೆ ಮತ್ತು ಇ ದೊಡ್ಡದಾಗಿದೆ, ಆದ್ದರಿಂದ ಸಿ ತುಲನಾತ್ಮಕವಾಗಿ ಚಿಕ್ಕದಾಗಿದೆ. ನಂತರ, ಐ. ಎಲ್. ಪಿ. ಯನ್ನು ಸಂಪೂರ್ಣ ಹುಡುಕಾಟದ ಮೂಲಕ ಪರಿಹರಿಸಬಹುದು (ಎಸ್, ಸಿ ಸಾಕಷ್ಟು ಚಿಕ್ಕದಾಗಿದ್ದರೆ), ಅಥವಾ ಅದನ್ನು ಭಾಗಶಃ ಎಲ್. ಪಿ. ಆಗಿ ಸಡಿಲಗೊಳಿಸಬಹುದು. ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್ಪಿ ಬಿನ್-ಪ್ಯಾಕಿಂಗ್ನ ಫ್ರ್ಯಾಕ್ಷನಲ್ ಕಾನ್ಫಿಗರೇಶನ್ ಎಲ್ಪಿ ಇದು ಮೇಲಿನ ಐಎಲ್ಪಿಯ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಡಿಲಿಕೆಯಾಗಿದೆ. ಇದು ಕೊನೆಯ ನಿರ್ಬಂಧವನ್ನು ನಿರ್ಬಂಧದೊಂದಿಗೆ ಬದಲಾಯಿಸುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಪ್ರತಿ ಸಂರಚನೆಯನ್ನು ಭಾಗಶಃ ಸಂಖ್ಯೆಯ ಬಾರಿ ಬಳಸಬಹುದು. ಈ ವಿಶ್ರಾಂತಿಯನ್ನು ಮೊದಲು ಗಿಲ್ಮೋರ್ ಮತ್ತು ಗೊಮೊರಿ ಪ್ರಸ್ತುತಪಡಿಸಿದರು, ಮತ್ತು ಇದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಗಿಲ್ಮೋರ್-ಗೊಮೊರಿ ರೇಖೀಯ ಕಾರ್ಯಕ್ರಮ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಃ 3 ಗಾತ್ರದ 31 ವಸ್ತುಗಳು ಮತ್ತು 4 ಗಾತ್ರದ 7 ವಸ್ತುಗಳು ಇವೆ ಎಂದು ಭಾವಿಸೋಣ, ಮತ್ತು ಬಿನ್-ಗಾತ್ರವು 10 ಆಗಿದೆ. ಸಂರಚನೆಗಳು ಹೀಗಿವೆಃ 4,44,34,334,33,333. ನಿರ್ಬಂಧಗಳು [0,0,1,2,1,2,3] * x = 31 ಮತ್ತು [1,2,1,1,0,0,0] * x = 7. ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್ಪಿಗೆ ಸೂಕ್ತವಾದ ಪರಿಹಾರವೆಂದರೆ [0,0,0,7,0,0,17/3] ಅಂದರೆಃ 334 ಸಂರಚನೆಯ 7 ತೊಟ್ಟಿಗಳು ಮತ್ತು 333 ಸಂರಚನೆಯ 17/3 ತೊಟ್ಟಿಗಳಿವೆ. ಎರಡು ವಿಭಿನ್ನ ಸಂರಚನೆಗಳು ಮಾತ್ರ ಬೇಕಾಗುತ್ತವೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಸಂಕ್ಷಿಪ್ತವಾಗಿ ಹೇಳುವುದಾದರೆ, ಭಾಗಶಃ LPಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಬರೆಯಬಹುದುಃ 1 ಎಂಬುದು C ಗಾತ್ರದ ವಾಹಕ (1,., 1) ಆಗಿದ್ದರೆ, A ಎಂಬುದು S-by-C ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದ್ದು, ಇದರಲ್ಲಿ ಪ್ರತಿ ಅಂಕಣವು ಒಂದೇ ಸಂರಚನೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ ಮತ್ತು n ಎಂಬುದು ವಾಹಕ (n1,., nS) ಆಗಿದೆ. ಅವಿಭಾಜ್ಯತೆಯ ನಿರ್ಬಂಧಗಳಿಲ್ಲದ ಒಂದು ರೇಖೀಯ ಕ್ರಮಾವಳಿಯನ್ನು ಅಸ್ಥಿರ ಮತ್ತು ನಿರ್ಬಂಧಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ಸಮಯದ ಬಹುಪದದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಸಮಸ್ಯೆಯೆಂದರೆ, ಫ್ರ್ಯಾಕ್ಷನಲ್ ಕಾನ್ಫಿಗರೇಶನ್ ಎಲ್ಪಿಯಲ್ಲಿನ ಅಸ್ಥಿರಗಳ ಸಂಖ್ಯೆಯು ಸಂಭವನೀಯ ಸಂರಚನೆಗಳ ಸಂಖ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ, ಇದು ದೊಡ್ಡದಾಗಿರಬಹುದು. ಕರ್ಮಾರ್ಕರ್ ಮತ್ತು ಕಾರ್ಪ್ ಈ ಸಮಸ್ಯೆಯನ್ನು ನಿವಾರಿಸುವ ಕ್ರಮಾವಳಿಯನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಮೊದಲನೆಯದಾಗಿ, ಅವರು ಫ್ರ್ಯಾಕ್ಷನಲ್ ಎಲ್ಪಿಯ ಡ್ಯುಯಲ್ ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ನಿರ್ಮಿಸುತ್ತಾರೆಃ ಇದು ಎಸ್ ವೇರಿಯೇಬಲ್ಗಳಾದ y1,.., yS, ಮತ್ತು C ನಿರ್ಬಂಧಗಳನ್ನು ಹೊಂದಿದೆಃ ಪ್ರತಿ ಕಾನ್ಫಿಗರೇಶನ್ c ಗೆ, ಒಂದು ನಿರ್ಬಂಧವಿದೆ, ಅಲ್ಲಿ ಕಾನ್ಫಿಗರೇಶನ್ c ಅನ್ನು ಪ್ರತಿನಿಧಿಸುವ A ನ ಕಾಲಮ್ ಇದೆ. ಪ್ರತಿ ಗಾತ್ರಕ್ಕೆ, ನಾವು ಋಣಾತ್ಮಕವಲ್ಲದ ಬೆಲೆಯನ್ನು ನಿರ್ಧರಿಸಬೇಕು. ನಮ್ಮ ಲಾಭವು ಎಲ್ಲಾ ವಸ್ತುಗಳ ಒಟ್ಟು ಬೆಲೆಯಾಗಿದೆ. ಪ್ರತಿ ಸಂರಚನೆಯಲ್ಲಿನ ವಸ್ತುಗಳ ಒಟ್ಟು ಬೆಲೆ ಗರಿಷ್ಠ 1 ಆಗಿರುತ್ತದೆ ಎಂಬ ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟು ನಾವು ಲಾಭವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು ಬಯಸುತ್ತೇವೆ. ಎರಡನೆಯದಾಗಿ, ಅವರು ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನದ ರೂಪಾಂತರವನ್ನು ಅನ್ವಯಿಸುತ್ತಾರೆ, ಇದು ಎಲ್ಲಾ ನಿರ್ಬಂಧಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡುವ ಅಗತ್ಯವಿಲ್ಲ-ಇದಕ್ಕೆ ಕೇವಲ ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ ಅಗತ್ಯವಿದೆ. ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ ಒಂದು ವೆಕ್ಟರ್ y ಅನ್ನು ನೀಡಿದ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು, ಅದು ಕಾರ್ಯಸಾಧ್ಯವೆಂದು ಪ್ರತಿಪಾದಿಸುತ್ತದೆ, ಅಥವಾ ಅದು ಉಲ್ಲಂಘಿಸುವ ನಿರ್ಬಂಧವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಯನ್ನು s ಗಾತ್ರಗಳು ಮತ್ತು y ಮೌಲ್ಯಗಳೊಂದಿಗೆ ಪರಿಹರಿಸುವ ಮೂಲಕ ಡ್ಯುಯಲ್ ಎಲ್ಪಿಗಾಗಿ ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದುಃ ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಯ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವು ಗರಿಷ್ಠ 1 ಒಟ್ಟು ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದ್ದರೆ, ನಂತರ y ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದೆ; ಅದು 1 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ, y ಗಿಂತ ಕಾರ್ಯಸಾಧ್ಯವಲ್ಲ, ಮತ್ತು ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಯ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವು ನಿರ್ಬಂಧವನ್ನು ಉಲ್ಲಂಘಿಸುವ ಸಂರಚನೆಯನ್ನು ಗುರುತಿಸುತ್ತದೆ. ಮೂರನೆಯದಾಗಿ, ನಾಪ್ಸ್ಯಾಕ್ ಸಮಸ್ಯೆಗೆ ಅಂದಾಜು ಪರಿಹಾರದೊಂದಿಗೆ, ಡ್ಯುಯಲ್ ಎಲ್ಪಿಗೆ ಅಂದಾಜು ಪರಿಹಾರವನ್ನು ಪಡೆಯಬಹುದು ಮತ್ತು ಇದರಿಂದ, ಪ್ರೈಮಲ್ ಎಲ್ಪಿಗೆ ಅಂದಾಜು ಪರಿಹಾರವನ್ನು ಪಡೆಯಬಹುದು ಎಂದು ಅವರು ತೋರಿಸುತ್ತಾರೆ; ಕರ್ಮಾರ್ಕರ್-ಕಾರ್ಪ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಕ್ರಮಾವಳಿಗಳನ್ನು ನೋಡಿ. ಒಟ್ಟಾರೆಯಾಗಿ, ಯಾವುದೇ ಸಹಿಷ್ಣುತೆಯ ಅಂಶವಾದ ಎಚ್ ಗೆ, ಗರಿಷ್ಠ ಎಲ್ಓಪಿಟಿ (ಐ) + ಎಚ್ ನಲ್ಲಿ ವೆಚ್ಚದ ಮೂಲಭೂತ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ, ಮತ್ತು ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಚಲಿಸುತ್ತದೆಃ, ಇಲ್ಲಿ ಎಸ್ ವಿವಿಧ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆ, ಎನ್ ವಿವಿಧ ವಸ್ತುಗಳ ಸಂಖ್ಯೆ, ಮತ್ತು ಚಿಕ್ಕ ವಸ್ತುವಿನ ಗಾತ್ರ ಇಬಿ ಆಗಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, e ≤1/n ಮತ್ತು h = 1 ಆಗಿದ್ದರೆ, ಅಲ್ಗಾರಿದಮ್ ಹೆಚ್ಚಿನ LOPT + 1 ಡಬ್ಬಿಗಳೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆಃ ಈ ಅಲ್ಗಾರಿದಮ್ನ ಯಾದೃಚ್ಛಿಕ ರೂಪಾಂತರವು ನಿರೀಕ್ಷಿತ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಃ ಅಪೂರ್ಣಾಂಕದ ಎಲ್. ಪಿ. ಯನ್ನು ಪೂರ್ಣಾಂಕಗೊಳಿಸಿದಾಗ ಕರ್ಮಾರ್ಕರ್ ಮತ್ತು ಕಾರ್ಪ್ ಅಪೂರ್ಣಾಂಕದ ಎಲ್. ಪಿ. ಯನ್ನು ಸಮಗ್ರ ಎಲ್. ಪಿ. ಗೆ ಅಂದಾಜು ಪರಿಹಾರವಾಗಿ ಪೂರ್ಣಾಂಕಗೊಳಿಸುವ ಮಾರ್ಗವನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಿದರು; ಕರ್ಮಾರ್ಕರ್-ಕಾರ್ಪ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಕ್ರಮಾವಳಿಗಳನ್ನು ನೋಡಿ. ಈ ಎಲ್ಪಿಯ ಸಂಯೋಜಕ ಸಮಗ್ರತೆಯ ಅಂತರವು ಒ (ಲಾಗ್ 2 (ಎನ್)) ನಲ್ಲಿದೆ ಎಂದು ಅವರ ಪುರಾವೆಗಳು ತೋರಿಸುತ್ತವೆ. ನಂತರ, ಹೋಬರ್ಗ್ ಮತ್ತು ರಾಥ್ವೋಸ್ ತಮ್ಮ ಫಲಿತಾಂಶವನ್ನು ಸುಧಾರಿಸಿದರು ಮತ್ತು ಅವಿಭಾಜ್ಯ ಅಂತರವು ಒ (ಲಾಗ್ (ಎನ್)) ನಲ್ಲಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸಿದರು. ಅವಿಭಾಜ್ಯ ಅಂತರದ ಮೇಲೆ ಅತ್ಯಂತ ಪ್ರಸಿದ್ಧವಾದ ಕೆಳ ಮಿತಿಯು ಸ್ಥಿರ ω (1) ಆಗಿದೆ. ನಿಖರವಾದ ಸಮಗ್ರತೆಯ ಅಂತರವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಒಂದು ಮುಕ್ತ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಬಿನ್ ಹೊದಿಕೆಯಲ್ಲಿ ಬಿನ್ ಹೊದಿಕೆಯ ಸಮಸ್ಯೆಯಲ್ಲಿ, ವಿವಿಧ ಗಾತ್ರಗಳ n ವಸ್ತುಗಳು ಇರುತ್ತವೆ. ವಸ್ತುಗಳನ್ನು ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಡಬ್ಬಿಗಳಲ್ಲಿ ಪ್ಯಾಕ್ ಮಾಡುವುದು ಗುರಿಯಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಬಿನ್ ಕನಿಷ್ಠ ಬಿ ಅನ್ನು ಹೊಂದಿರಬೇಕು. ಈ ಸಮಸ್ಯೆಯ ನೈಸರ್ಗಿಕ ಸಂರಚನೆಯು ಎಲ್ಪಿ ಆಗಿರಬಹುದುಃ ಅಲ್ಲಿ ಎ ಕನಿಷ್ಠ ಬಿ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುವ ವಸ್ತುಗಳ ಎಲ್ಲಾ ಸಂರಚನೆಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ (ಒಬ್ಬರು ಸೇರ್ಪಡೆ-ಕನಿಷ್ಠ ಸಂರಚನೆಗಳನ್ನು ಮಾತ್ರ ತೆಗೆದುಕೊಳ್ಳಬಹುದು). ಈ ಎಲ್ಪಿ ಯೊಂದಿಗಿನ ಸಮಸ್ಯೆಯೆಂದರೆ, ಡಬ್ಬಿಯನ್ನು ಮುಚ್ಚುವ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ನಿರ್ವಹಿಸುವುದು ಸಮಸ್ಯಾತ್ಮಕವಾಗಿದೆ, ಏಕೆಂದರೆ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರಕ್ಕೆ ಸಣ್ಣ ವಸ್ತುಗಳು ಅಗತ್ಯವಾಗಬಹುದು. ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಅನುಮತಿಸಲಾಗಿರುವುದರಿಂದ, ಕರ್ಮಾರ್ಕರ್ ಮತ್ತು ಕಾರ್ಪ್ ತಂತ್ರಕ್ಕೂ ಸಹ ಸಂರಚನೆಗಳ ಸಂಖ್ಯೆಯು ತುಂಬಾ ದೊಡ್ಡದಾಗಿರಬಹುದು. ಸಿರಿಕ್, ಜಾನ್ಸನ್ ಮತ್ತು ಕೆನ್ಯಾನ್ ಪರ್ಯಾಯ ಎಲ್ಪಿಯನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಮೊದಲಿಗೆ, ಅವರು ಸಣ್ಣ ಎಂದು ಕರೆಯಲ್ಪಡುವ ವಸ್ತುಗಳ ಗುಂಪನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತಾರೆ. ಟಿ ಎಲ್ಲಾ ಸಣ್ಣ ವಸ್ತುಗಳ ಒಟ್ಟು ಗಾತ್ರವಾಗಿರಲಿ. ನಂತರ, ಅವರು ಮೊತ್ತ <2 ರೊಂದಿಗೆ ಎಲ್ಲಾ ಸಂರಚನೆಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎ ಅನ್ನು ನಿರ್ಮಿಸುತ್ತಾರೆ. ನಂತರ, ಅವರು ಮೇಲಿನ ಎಲ್ಪಿಯನ್ನು ಒಂದು ಹೆಚ್ಚುವರಿ ನಿರ್ಬಂಧದೊಂದಿಗೆ ಪರಿಗಣಿಸುತ್ತಾರೆಃ ಹೆಚ್ಚುವರಿ ನಿರ್ಬಂಧವು ಡಬ್ಬಿಯಲ್ಲಿನ "ಖಾಲಿ ಜಾಗ" ವನ್ನು ಸಣ್ಣ ವಸ್ತುಗಳಿಂದ ತುಂಬಬಹುದು ಎಂದು ಖಾತರಿಪಡಿಸುತ್ತದೆ. ಈ ಎಲ್ಪಿಯ ಡ್ಯುಯಲ್ ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾಗಿದೆ ಮತ್ತು ಸರಳವಾದ ನಾಪ್ಸ್ಯಾಕ್-ಪ್ರಾಬ್ಲಮ್ ಸೆಪರೇಷನ್ ಒರಾಕಲ್ನಿಂದ ಪರಿಹರಿಸಲಾಗುವುದಿಲ್ಲ. ಸಿರಿಕ್, ಜಾನ್ಸನ್ ಮತ್ತು ಕೆನ್ಯಾನ್ ಇದನ್ನು ಸುಮಾರು 1/ಎಪ್ಸಿಲಾನ್ನಲ್ಲಿ ಸಮಯದ ಘಾತಾಂಕದಲ್ಲಿ ಪರಿಹರಿಸಲು ವಿಭಿನ್ನ ವಿಧಾನವನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಜಾನ್ಸೆನ್ ಮತ್ತು ಸೋಲಿಸ್-ಒಬಾ ಇದನ್ನು 1/ಎಪ್ಸಿಲಾನ್ನಲ್ಲಿ ಅಂದಾಜು ಸಮಯ ಘಾತಾಂಕದಲ್ಲಿ ಪರಿಹರಿಸಲು ಸುಧಾರಿತ ವಿಧಾನವನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಯಂತ್ರ ವೇಳಾಪಟ್ಟಿಯಲ್ಲಿ ಸಂಬಂಧವಿಲ್ಲದ-ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿಯ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಕೆಲವು ವಿಭಿನ್ನ ಯಂತ್ರಗಳಿವೆ, ಅವು ಕೆಲವು ವಿಭಿನ್ನ ಕಾರ್ಯಗಳನ್ನು ನಿರ್ವಹಿಸುತ್ತವೆ. ಯಂತ್ರವು ಜಾಬ್ ಜೆ ಅನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಿದಾಗ, ಅದು ಪೈ, ಜೆ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಯಂತ್ರದ ಗರಿಷ್ಠ ಪೂರ್ಣಗೊಳಿಸುವ ಸಮಯವು ಸಾಧ್ಯವಾದಷ್ಟು ಕಡಿಮೆಯಾಗುವಂತೆ ಯಂತ್ರಗಳ ನಡುವೆ ಕೆಲಸಗಳನ್ನು ವಿಭಜಿಸುವುದು ಇದರ ಗುರಿಯಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯ ನಿರ್ಧಾರದ ಆವೃತ್ತಿಯೆಂದರೆಃ ಟಿ ಸಮಯವನ್ನು ನೀಡಿದರೆ, ಎಲ್ಲಾ ಯಂತ್ರಗಳ ಪೂರ್ಣಗೊಳಿಸುವ ಸಮಯವು ಗರಿಷ್ಠ ಟಿ ಆಗಿರುವ ವಿಭಾಗವಿದೆಯೇ? ಪ್ರತಿ ಯಂತ್ರಕ್ಕೆ (i), ಯಂತ್ರದಿಂದ ಗರಿಷ್ಠ ಟಿ ಸಮಯದಲ್ಲಿ ಸಂಸ್ಕರಿಸಬಹುದಾದ ಕಾರ್ಯಗಳ ಸೀಮಿತವಾದ ಅನೇಕ ಉಪಗುಂಪುಗಳಿವೆ. ಅಂತಹ ಪ್ರತಿಯೊಂದು ಉಪಗುಂಪನ್ನು ಯಂತ್ರಕ್ಕೆ ಸಂರಚನೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ (i). ಯಂತ್ರಕ್ಕೆ (i) ಎಲ್ಲಾ ಸಂರಚನೆಗಳ ಗುಂಪನ್ನು ಸಿಐ (ಟಿ) ನಿಂದ ಸೂಚಿಸಿ, ಸಮಯ ಟಿ ನೀಡಲಾಗಿದೆ. ಸಿಐ (ಟಿ) ಯಲ್ಲಿ ಪ್ರತಿ ಯಂತ್ರಕ್ಕೆ (i) ಮತ್ತು ಕಾನ್ಫಿಗರೇಶನ್ ಸಿಗೆ, ಯಂತ್ರದಲ್ಲಿ ಬಳಸುವ ನಿಜವಾದ ಸಂರಚನೆಯು (i) ಸಿ, ಮತ್ತು 0 ಆಗಿದ್ದರೆ 1 ಕ್ಕೆ ಸಮನಾಗಿರುವ ವೇರಿಯೇಬಲ್ ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿ. ನಂತರ, ಎಲ್ಪಿ ನಿರ್ಬಂಧಗಳು ಹೀಗಿವೆಃ 1,., m ನಲ್ಲಿ ಪ್ರತಿ ಯಂತ್ರಕ್ಕೆ i; 1,., n ನಲ್ಲಿ ಪ್ರತಿ ಕೆಲಸಕ್ಕೆ j; ಪ್ರತಿ i, j. ಗುಣಲಕ್ಷಣಗಳು ಸಂಬಂಧವಿಲ್ಲದ-ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿಗಾಗಿ ಕಾನ್ಫಿಗರೇಶನ್-ಎಲ್ಪಿಯ ಅವಿಭಾಜ್ಯ ಅಂತರವು 2 ಆಗಿದೆ. ಹೈ-ಮಲ್ಟಿಪ್ಲಿಸಿಟಿ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಉಲ್ಲೇಖಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಸಂಖ್ಯೆ ವಿಭಜನೆ ಜಾಬ್ ಶೆಡ್ಯೂಲಿಂಗ್ ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಸಹ ನೋಡಿ.