Ellipsoid method
ಗಣಿತದ ಆಪ್ಟಿಮೈಸೇಶನ್ನಲ್ಲಿ, ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನವು ಕನ್ವೆಕ್ಸ್ ಕಾರ್ಯಗಳನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಒಂದು ಪುನರಾವರ್ತಿತ ವಿಧಾನವಾಗಿದೆ. ತರ್ಕಬದ್ಧ ದತ್ತಾಂಶದೊಂದಿಗೆ ಕಾರ್ಯಸಾಧ್ಯವಾದ ರೇಖೀಯ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಪರಿಣತಿ ಪಡೆದಾಗ, ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನವು ಇನ್ಪುಟ್ ಗಾತ್ರದಲ್ಲಿ ಬಹುಪದವಾಗಿರುವ ಹಲವಾರು ಹಂತಗಳಲ್ಲಿ ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುವ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನವು ಎಲಿಪ್ಸೋಯಿಡ್ಗಳ ಅನುಕ್ರಮವನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ, ಅದರ ಪರಿಮಾಣವು ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಏಕರೂಪವಾಗಿ ಕಡಿಮೆಯಾಗುತ್ತದೆ, ಹೀಗಾಗಿ ಕನ್ವೆಕ್ಸ್ ಕಾರ್ಯದ ಮಿನಿಮೈಸರ್ ಅನ್ನು ಸುತ್ತುವರೆದಿರುತ್ತದೆ. ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಿಧಾನವು ಸುದೀರ್ಘ ಇತಿಹಾಸವನ್ನು ಹೊಂದಿದೆ. ಪುನರಾವರ್ತಿತ ವಿಧಾನವಾಗಿ, ಪ್ರಾಥಮಿಕ ಆವೃತ್ತಿಯನ್ನು ನೌಮ್ ಝಡ್. ಶೋರ್ ಪರಿಚಯಿಸಿದರು. 1972ರಲ್ಲಿ, ಅರ್ಕಡಿ ನೆಮಿರೋವ್ಸ್ಕಿ ಮತ್ತು ಡೇವಿಡ್ ಬಿ. ಯುಡಿನ್ (ಜುಡಿನ್) ಅವರು ನೈಜ ಕನ್ವೆಕ್ಸ್ ಕನಿಷ್ಠೀಕರಣಕ್ಕಾಗಿ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅಧ್ಯಯನ ಮಾಡಿದರು. ತರ್ಕಬದ್ಧ ದತ್ತಾಂಶದೊಂದಿಗೆ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಆಗಿ, ಎಲಿಪ್ಸೋಯಿಡ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಲಿಯೊನಿಡ್ ಖಾಚಿಯಾನ್ ಅಧ್ಯಯನ ಮಾಡಿದರು; ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂಗಳ ಬಹುಪದ-ಸಮಯದ ಪರಿಹಾರವನ್ನು ಸಾಬೀತುಪಡಿಸುವುದು ಖಾಚಿಯಾನ್ನ ಸಾಧನೆಯಾಗಿದೆ. ಇದು ಸೈದ್ಧಾಂತಿಕ ದೃಷ್ಟಿಕೋನದಿಂದ ಒಂದು ಗಮನಾರ್ಹ ಹಂತವಾಗಿದೆಃ ಆ ಸಮಯದಲ್ಲಿ ರೇಖೀಯ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವ ಪ್ರಮಾಣಿತ ಕ್ರಮಾವಳಿಯು ಸಿಂಪ್ಲೆಕ್ಸ್ ಕ್ರಮಾವಳಿಯಾಗಿತ್ತು, ಇದು ಸಮಸ್ಯೆಯ ಗಾತ್ರದಲ್ಲಿ ಸಾಮಾನ್ಯವಾಗಿ ರೇಖೀಯವಾಗಿರುವ ರನ್ ಟೈಮ್ ಅನ್ನು ಹೊಂದಿದೆ, ಆದರೆ ಯಾವ ಉದಾಹರಣೆಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿವೆ ಎಂಬುದಕ್ಕೆ ಇದು ಸಮಸ್ಯೆಯ ಗಾತ್ರದಲ್ಲಿ ಘಾತೀಯವಾಗಿದೆ. ಅಂತೆಯೇ, ಎಲ್ಲಾ ಪ್ರಕರಣಗಳಿಗೆ ಬಹುಪದವೆಂದು ಖಾತರಿಪಡಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಹೊಂದಿರುವುದು ಸೈದ್ಧಾಂತಿಕ ಪ್ರಗತಿಯಂತೆ ತೋರುತ್ತದೆ. ಮೊದಲ ಬಾರಿಗೆ, ರನ್ ಟೈಮ್ ಅನ್ನು ಬಹುಪದವೆಂದು ಸಾಬೀತುಪಡಿಸಬಹುದಾದ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಂಗಳನ್ನು ಪರಿಹರಿಸಲು ಕ್ರಮಾವಳಿಗಳಿರಬಹುದು ಎಂದು ಖಾಚಿಯಾನ್ ಅವರ ಕೆಲಸವು ತೋರಿಸಿದೆ. ಆದಾಗ್ಯೂ, ಆಚರಣೆಯಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ ಸಾಕಷ್ಟು ನಿಧಾನವಾಗಿದೆ ಮತ್ತು ಕಡಿಮೆ ಪ್ರಾಯೋಗಿಕ ಆಸಕ್ತಿಯನ್ನು ಹೊಂದಿದೆ, ಆದರೂ ಇದು ನಂತರದ ಕೆಲಸಕ್ಕೆ ಸ್ಫೂರ್ತಿಯನ್ನು ಒದಗಿಸಿತು, ಅದು ಹೆಚ್ಚು ಪ್ರಾಯೋಗಿಕ ಬಳಕೆಯಾಗಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಕರ್ಮಾರ್ಕರ್ ಅವರ ಅಲ್ಗಾರಿದಮ್, ಒಂದು ಆಂತರಿಕ-ಬಿಂದು ವಿಧಾನವಾಗಿದ್ದು, ಆಚರಣೆಯಲ್ಲಿ ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಿಧಾನಕ್ಕಿಂತ ಹೆಚ್ಚು ವೇಗವಾಗಿರುತ್ತದೆ. ಕರ್ಮಾರ್ಕರ್ ಅವರ ಅಲ್ಗಾರಿದಮ್ ಕೂಡ ಅತ್ಯಂತ ಕೆಟ್ಟ ಪರಿಸ್ಥಿತಿಯಲ್ಲಿ ವೇಗವಾಗಿರುತ್ತದೆ. ದೀರ್ಘವೃತ್ತಾಕಾರದ ಕ್ರಮಾವಳಿಯು ಸಂಕೀರ್ಣತೆಯ ಸಿದ್ಧಾಂತಕಾರರಿಗೆ ಸಮಸ್ಯೆಯ ಆಯಾಮ ಮತ್ತು ದತ್ತಾಂಶದ ಗಾತ್ರವನ್ನು ಅವಲಂಬಿಸಿರುವ (ಕೆಟ್ಟ-ಪ್ರಕರಣ) ಮಿತಿಗಳನ್ನು ಸಾಧಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ, ಆದರೆ ಸಾಲುಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಅಲ್ಲ, ಆದ್ದರಿಂದ ಇದು ಅನೇಕ ವರ್ಷಗಳವರೆಗೆ ಸಂಯೋಜನೆಯ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಮುಖ್ಯವಾಗಿತ್ತು. 21ನೇ ಶತಮಾನದಲ್ಲಿ ಮಾತ್ರ ಇದೇ ರೀತಿಯ ಸಂಕೀರ್ಣತೆಯ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿರುವ ಆಂತರಿಕ-ಬಿಂದು ಕ್ರಮಾವಳಿಗಳು ಕಾಣಿಸಿಕೊಂಡಿವೆ. ವಿವರಣೆ ಕನ್ವೆಕ್ಸ್ ಮಿನಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯು ಈ ಕೆಳಗಿನ ಅಂಶಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ವಾಹಕದ ಮೇಲೆ ಕನಿಷ್ಠಗೊಳಿಸಬೇಕಾದ ಕನ್ವೆಕ್ಸ್ ಕಾರ್ಯ (n ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿರುವ); ರೂಪದ ಕನ್ವೆಕ್ಸ್ ಅಸಮಾನತೆಯ ನಿರ್ಬಂಧಗಳು, ಅಲ್ಲಿ ಕಾರ್ಯಗಳು ಕನ್ವೆಕ್ಸ್ ಆಗಿರುತ್ತವೆ; ಈ ನಿರ್ಬಂಧಗಳು ಕನ್ವೆಕ್ಸ್ ಸೆಟ್ ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತವೆ. ರೂಪದ ರೇಖೀಯ ಸಮಾನತೆಯ ನಿರ್ಬಂಧಗಳು. ಕನಿಷ್ಠಕಾರಕವನ್ನು ಹೊಂದಿರುವಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಆರಂಭಿಕ ದೀರ್ಘವೃತ್ತವನ್ನು ಸಹ ನಮಗೆ ನೀಡಲಾಗಿದೆ, ಎಲ್ಲಿ ಮತ್ತು ಅದರ ಕೇಂದ್ರವಾಗಿದೆ. ಅಂತಿಮವಾಗಿ, ಕನ್ವೆಕ್ಸ್ ಸೆಟ್ಗೆ ಬೇರ್ಪಡಿಸುವ ಒರಾಕಲ್ನ ಅಸ್ತಿತ್ವವು ನಮಗೆ ಬೇಕಾಗುತ್ತದೆ. ಒಂದು ಬಿಂದುವನ್ನು ನೀಡಿದರೆ, ಒರಾಕಲ್ ಎರಡು ಉತ್ತರಗಳಲ್ಲಿ ಒಂದನ್ನು ಹಿಂದಿರುಗಿಸಬೇಕುಃ "ಬಿಂದುವು ಒಳಗೆ ಇದೆ", ಅಥವಾ-"ಬಿಂದುವು ಒಳಗೆ ಇಲ್ಲ, ಮತ್ತು ಮೇಲಾಗಿ, ಇಲ್ಲಿ ಬೇರ್ಪಡಿಸುವ ಹೈಪರ್ ಪ್ಲೇನ್ ಇದೆ", ಅಂದರೆ, ಎಲ್ಲರಿಗೂ ಅಂತಹ ವೆಕ್ಟರ್. ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನದ ಔಟ್ಪುಟ್ ಒಂದೋಃ ಪಾಲಿಟೋಪ್ನಲ್ಲಿನ ಯಾವುದೇ ಬಿಂದು (ಅಂದರೆ, ಯಾವುದೇ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಬಿಂದು), ಅಥವಾ-ಖಾಲಿಯಾಗಿರುವ ಪುರಾವೆ. ಎಲ್ಲೆಡೆ ಶೂನ್ಯವಾಗಿರುವ ಕಾರ್ಯದ ಅಸಮಾನತೆ-ನಿರ್ಬಂಧಿತ ಕನಿಷ್ಠೀಕರಣವು ಯಾವುದೇ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಬಿಂದುವನ್ನು ಸರಳವಾಗಿ ಗುರುತಿಸುವ ಸಮಸ್ಯೆಗೆ ಅನುರೂಪವಾಗಿದೆ. ಯಾವುದೇ ರೇಖೀಯ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯನ್ನು ರೇಖೀಯ ಕಾರ್ಯಸಾಧ್ಯತೆಯ ಸಮಸ್ಯೆಯಾಗಿ ಕಡಿಮೆ ಮಾಡಬಹುದು (ಉದಾಹರಣೆಗೆ. ಕೆಲವು ರೇಖೀಯ ಅಸಮಾನತೆ ಮತ್ತು ಸಮಾನತೆಯ ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟು ಶೂನ್ಯ ಕಾರ್ಯವನ್ನು ಕಡಿಮೆ ಮಾಡಿ). ಇದನ್ನು ಮಾಡಲು ಒಂದು ಮಾರ್ಗವೆಂದರೆ ಪ್ರೈಮಲ್ ಮತ್ತು ಡ್ಯುಯಲ್ ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಂಗಳನ್ನು ಒಟ್ಟಿಗೆ ಒಂದು ಪ್ರೋಗ್ರಾಂನಲ್ಲಿ ಸಂಯೋಜಿಸುವುದು ಮತ್ತು ಪ್ರೈಮಲ್ ದ್ರಾವಣದ ಮೌಲ್ಯವು ಡ್ಯುಯಲ್ ದ್ರಾವಣದ ಮೌಲ್ಯಕ್ಕಿಂತ ಕೆಟ್ಟದ್ದಲ್ಲ ಎಂಬ ಹೆಚ್ಚುವರಿ (ರೇಖೀಯ) ನಿರ್ಬಂಧವನ್ನು ಸೇರಿಸುವುದು. ರೇಖೀಯ ಕಾರ್ಯಕ್ರಮದ ಉದ್ದೇಶವನ್ನು ಹೆಚ್ಚುವರಿ ನಿರ್ಬಂಧವೆಂದು ಪರಿಗಣಿಸುವುದು ಮತ್ತು ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಬಳಸುವುದು ಮತ್ತೊಂದು ಮಾರ್ಗವಾಗಿದೆ. ಅನಿಯಂತ್ರಿತ ಕನಿಷ್ಠೀಕರಣ ಅಲ್ಗಾರಿದಮ್ನ k-th ಪುನರಾವರ್ತನೆಯಲ್ಲಿ, ನಾವು ದೀರ್ಘವೃತ್ತಾಕಾರದ ಮಧ್ಯಭಾಗದಲ್ಲಿ ಒಂದು ಬಿಂದುವನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಅಸಮತ್ವ-ನಿರ್ಬಂಧಿತ ಕನಿಷ್ಠೀಕರಣದ ಗುಣಲಕ್ಷಣದಿಂದ ನಿಲ್ಲಿಸುವ ಮಾನದಂಡವನ್ನು ಎಲ್ಲಿ ನೀಡಲಾಗುತ್ತದೆ ಎಂಬುದರ ಮೂಲಕ ನವೀಕರಣವನ್ನು ನೀಡಲಾಗುತ್ತದೆ ನಿರ್ಬಂಧಿತ ಕನಿಷ್ಠೀಕರಣಕ್ಕಾಗಿ ಅಲ್ಗಾರಿದಮ್ನ k-th ಪುನರಾವರ್ತನೆಯಲ್ಲಿ, ನಾವು ಮೊದಲಿನಂತೆ ದೀರ್ಘವೃತ್ತದ ಕೇಂದ್ರದಲ್ಲಿ ಒಂದು ಬಿಂದುವನ್ನು ಹೊಂದಿದ್ದೇವೆ. ನಾವು ಇಲ್ಲಿಯವರೆಗೆ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪುನರಾವರ್ತನೆಗಳ ಚಿಕ್ಕ ವಸ್ತುನಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ದಾಖಲಿಸುವ ಮೌಲ್ಯಗಳ ಪಟ್ಟಿಯನ್ನು ಸಹ ನಿರ್ವಹಿಸಬೇಕು. ಬಿಂದುವು ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದರ ಆಧಾರದ ಮೇಲೆ, ನಾವು ಎರಡು ಕಾರ್ಯಗಳಲ್ಲಿ ಒಂದನ್ನು ನಿರ್ವಹಿಸುತ್ತೇವೆಃ ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದ್ದರೆ, ನಿರ್ಬಂಧವಿಲ್ಲದ ಸಂದರ್ಭದಲ್ಲಿ ಅದೇ ನವೀಕರಣವನ್ನು ಮಾಡಿ, ತೃಪ್ತಿಪಡಿಸುವ ಉಪವಿಭಾಗವನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ. ನಮ್ಮ ಕಾರ್ಯಸಾಧ್ಯತೆಯ ಕಡಿತವು ಎಲ್ಲಾ ಕಾರ್ಯಸಾಧ್ಯವಾದ z ಗೆ ತೃಪ್ತಿಪಡಿಸಬೇಕಾದ ಉಪವಿಭಾಗವಾಗಿರಬಹುದು. ಕಾರ್ಯಕ್ಷಮತೆ ಎಲಿಪ್ಸೋಯಿಡ್ ವಿಧಾನವನ್ನು ಕಡಿಮೆ-ಆಯಾಮದ ಸಮಸ್ಯೆಗಳಿಗೆ ಬಳಸಲಾಗುತ್ತದೆ, ಉದಾಹರಣೆಗೆ ಸಮತಟ್ಟಾದ ಸ್ಥಳದ ಸಮಸ್ಯೆಗಳು, ಅಲ್ಲಿ ಅದು ಸಂಖ್ಯಾತ್ಮಕವಾಗಿ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ. "ಸಣ್ಣ" ಗಾತ್ರದ ಸಮಸ್ಯೆಗಳಲ್ಲಿಯೂ ಸಹ, ಇದು ಸಂಖ್ಯಾತ್ಮಕ ಅಸ್ಥಿರತೆ ಮತ್ತು ಆಚರಣೆಯಲ್ಲಿ ಕಳಪೆ ಕಾರ್ಯಕ್ಷಮತೆಯಿಂದ ಬಳಲುತ್ತದೆ. ಆದಾಗ್ಯೂ, ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಿಧಾನವು ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ನಲ್ಲಿ ಒಂದು ಪ್ರಮುಖ ಸೈದ್ಧಾಂತಿಕ ತಂತ್ರವಾಗಿದೆ. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಎಲಿಪ್ಸೋಯಿಡ್ ಅಲ್ಗಾರಿದಮ್ ಆಕರ್ಷಕವಾಗಿದೆ ಏಕೆಂದರೆ ಅದರ ಸಂಕೀರ್ಣತೆಯು ಕಾಲಮ್ಗಳ ಸಂಖ್ಯೆ ಮತ್ತು ಗುಣಾಂಕಗಳ ಡಿಜಿಟಲ್ ಗಾತ್ರವನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ, ಆದರೆ ಸಾಲುಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಅಲ್ಲ. 21ನೇ ಶತಮಾನದಲ್ಲಿ, ಅಂತಹುದೇ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿರುವ ಆಂತರಿಕ-ಬಿಂದು ಕ್ರಮಾವಳಿಗಳು ಕಾಣಿಸಿಕೊಂಡಿವೆ. ಡಿಮಿಟ್ರಿಸ್ ಅಲೆವ್ರಾಸ್ ಮತ್ತು ಮ್ಯಾನ್ಫ್ರೆಡ್ ಡಬ್ಲ್ಯೂ. ಪ್ಯಾಡ್ಬರ್ಗ್, ಲೀನಿಯರ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅಂಡ್ ಎಕ್ಸ್ಟೆನ್ಷನ್ಸ್ಃ ಪ್ರಾಬ್ಲಮ್ಸ್ ಅಂಡ್ ಎಕ್ಸ್ಟೆನ್ಷನ್ಸ್, ಯೂನಿವರ್ಸಿಟೆಕ್ಸ್ಟ್, ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್, 2001. (ಪ್ಯಾಡ್ಬರ್ಗ್ನಿಂದ ಪರಿಹಾರಗಳೊಂದಿಗೆ ಸಮಸ್ಯೆಗಳು.) ವಿ. ಚಂದ್ರು ಮತ್ತು M.R.Rao, ಲೀನಿಯರ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್, ಅಧ್ಯಾಯ 31 ಅಲ್ಗಾರಿದಮ್ಸ್ ಮತ್ತು ಥಿಯರಿ ಆಫ್ ಕಂಪ್ಯೂಟೇಶನ್ ಹ್ಯಾಂಡ್ಬುಕ್, M.J.Atallah, ಸಿಆರ್ಸಿ ಪ್ರೆಸ್ 1999,31-1 ನಿಂದ 31-37. ವಿ. ಚಂದ್ರು ಮತ್ತು M.R.Rao, ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್, ಅಧ್ಯಾಯ 32 ಅಲ್ಗಾರಿದಮ್ಸ್ ಮತ್ತು ಥಿಯರಿ ಆಫ್ ಕಂಪ್ಯೂಟೇಶನ್ ಹ್ಯಾಂಡ್ಬುಕ್, M.J.Atallah, ಸಿಆರ್ಸಿ ಪ್ರೆಸ್ 1999,32-1 ನಿಂದ 32-45. ಜಾರ್ಜ್ ಬಿ. ಡಾಂಟ್ಜಿಗ್ ಮತ್ತು ಮುಕುಂದ್ ಎನ್. ಥಾಪಾ. 1997 ರಲ್ಲಿ. ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ 1: ಪರಿಚಯ. ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್. ಜಾರ್ಜ್ ಬಿ. ಡಾಂಟ್ಜಿಗ್ ಮತ್ತು ಮುಕುಂದ್ ಎನ್. ಥಾಪಾ. 2003 ರಲ್ಲಿ. ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ 2: ಸಿದ್ಧಾಂತ ಮತ್ತು ವಿಸ್ತರಣೆಗಳು. ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್. ಎಲ್. ಲೊವಾಸ್ಜ್ಃ ಆನ್ ಅಲ್ಗಾರಿದಮಿಕ್ ಥಿಯರಿ ಆಫ್ ನಂಬರ್ಸ್, ಗ್ರಾಫ್ಸ್, ಅಂಡ್ ಕನ್ವೆಕ್ಸಿಟಿ, ಸಿಬಿಎಂಎಸ್-ಎನ್ಎಸ್ಎಫ್ ರೀಜನಲ್ ಕಾನ್ಫರೆನ್ಸ್ ಸೀರೀಸ್ ಇನ್ ಅಪ್ಲೈಡ್ ಮ್ಯಾಥಮ್ಯಾಟಿಕ್ಸ್ 50, ಎಸ್ಐಎಎಂ, ಫಿಲಡೆಲ್ಫಿಯಾ, ಪೆನ್ಸಿಲ್ವೇನಿಯಾ, 1986 ಕಟ್ಟ ಜಿ. ಮೂರ್ತಿ, ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್, ವಿಲೇ, 1983. ಎಮ್. ಪ್ಯಾಡ್ಬರ್ಗ್, ಲೀನಿಯರ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅಂಡ್ ಎಕ್ಸ್ಟೆನ್ಷನ್ಸ್, ಎರಡನೇ ಆವೃತ್ತಿ, ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್, 1999. ಕ್ರಿಸ್ಟೋಸ್ ಎಚ್. ಪಾಪಾಡಿಮಿಟ್ರಿಯು ಮತ್ತು ಕೆನ್ನೆತ್ ಸ್ಟೀಗ್ಲಿಟ್ಜ್, ಕಾಂಬಿನೇಟೋರಿಯಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ಃ ಅಲ್ಗಾರಿದಮ್ಸ್ ಅಂಡ್ ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ, ಕರೆಕ್ಟೆಡ್ ರಿಪಬ್ಲಿಕೇಶನ್ ವಿತ್ ಎ ನ್ಯೂ ಪ್ರೀಫೇಸ್, ಡೋವರ್. ಅಲೆಕ್ಸಾಂಡರ್ ಶ್ರೈಜ್ವರ್, ಥಿಯರಿ ಆಫ್ ಲೀನಿಯರ್ ಅಂಡ್ ಇಂಟಿಜರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್. ಜಾನ್ ವಿಲೇ & ಸನ್ಸ್, 1998, ಎಕ್ಸ್ಟರ್ನಲ್ ಲಿಂಕ್ಸ್ EE364b, ಸ್ಟ್ಯಾನ್ಫೋರ್ಡ್ ಕೋರ್ಸ್ನ ಮುಖಪುಟ ಕಾಂಬಿನೇಟೋರಿಯಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಕನ್ವೆಕ್ಸ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಲೀನಿಯರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್