<<<<<<<<Please help on the assignment below>>>>>>>

Santa has overslept and now is not able to bring presents to all children. However, he wants to make the most of the remaining time budget B he has available, and thus wants to find the optimal solution to the following problem: He a list C of children, where each child c C has a niceness-score nc 0. Moreover, he knows the travel durations tcd > 0 between all the places children c, d C live. He also knows the travel durations tnc > 0 from his house n on the north-pole to all children, and tcs > 0 from all children to his other house s on the south-pole. He wants to find a path from the north-pole to the south-pole respecting the available time budget B which maximizes the sum of the niceness-scores of the children he visits on the path.

(a) Can you help Santa by formulating an integer linear programming problem for above problem? (2 pts)

(b) Can you implement and solve above problem in Python for the instance santa.py given in Moodle? What is the optimal solution and what is the optimal solution value? (2 pts)

The file santa.py as below:

#!/usr/bin/env python3 # -*- coding: utf-8 -*- #import docplex from docplex.mp.model import Model # travel times T = [[0.0, 93740.71739324437, 28303.294494800404, 60573.9953659828, 67432.25806126697, 9609.884087792136, 15158.967367868438, 3866.9323280606077, 8062.9660755642635, 25387.483511596794, 61192.85976834963, 27300.045969547366, 53273.121321185965, 28466.428454135228, 55479.749623127354, 7250.619066052229, 9362.892067913592, 25084.440993462475, 82238.06803012642, 17685.389349856006, 49404.09705487389, 57546.2357182414], [93740.71739324437, 0.0, 111911.5857375299, 66114.85381872521, 73736.92584238783, 91438.606347486, 106411.95586699838, 90484.96348455526, 89463.28055468683, 118617.4912712611, 33399.54791761412, 98377.1485053135, 57130.353702242246, 105312.59259840159, 67218.96751545358, 88320.78429685112, 101874.6458729104, 73557.0114231363, 73689.1000657669, 79882.92917785693, 65521.592378409914, 53192.15208104017], [28303.294494800404, 111911.5857375299, 0.0, 88468.47310912801, 95657.61445134676, 37603.527198828044, 32607.664934191438, 31864.95175169735, 36365.9586955122, 30650.580555522916, 82084.66837469774, 52998.57643191935, 80061.10080015135, 51484.894773766384, 83415.92231268139, 35321.76889641286, 20241.257193287187, 52145.19076233301, 110364.22367707617, 45225.53816256695, 77100.83898800061, 83961.65361544519], [60573.9953659828, 66114.85381872521, 88468.47310912801, 0.0, 10170.18091687654, 52345.16898963365, 64857.841494081564, 56806.378292041314, 52689.1686955868, 77219.7029116255, 40584.33940608126, 46474.3484699087, 13480.11059414947, 53305.13098468201, 5115.15397963742, 53348.47826620085, 69711.45537716238, 36572.68637068929, 22322.30267781527, 43243.42260256123, 11551.900891130488, 14534.786497795534], [67432.25806126697, 73736.92584238783, 95657.61445134676, 10170.18091687654, 0.0, 58627.517437378345, 69860.38186221005, 63796.18968412221, 59397.57892088534, 81705.70334480514, 50246.768822128244, 49838.20875409252, 23649.960829407326, 56126.415469036554, 13702.462927116454, 60336.47201668741, 76284.47076335327, 44635.66681238224, 15122.05354833791, 50715.76758719227, 20559.265857294162, 24337.961062802664], [9609.884087792136, 91438.606347486, 37603.527198828044, 52345.16898963365, 58627.517437378345, 0.0, 15072.339580785068, 7171.667911343953, 3082.6107371025755, 27728.735140694727, 58212.42803385633, 18429.55379191256, 46339.14876031495, 21064.54099286284, 47230.02250502214, 5313.410855580463, 17701.286283459725, 19012.815919313485, 73585.51931805944, 11771.332588080253, 41541.2379145759, 50876.15067908539], [15158.967367868438, 106411.95586699838, 32607.664934191438, 64857.841494081564, 69860.38186221005, 15072.339580785068, 0.0, 17003.27561587183, 16969.834287423088, 12832.996300307226, 73249.13910257924, 21738.702454573962, 60406.651924529804, 18974.719315365382, 59801.71074512502, 18329.596444627485, 14344.562402210104, 33940.31618908996, 84982.02672282301, 26833.571491668805, 54777.004217376656, 65086.113649414525], [3866.9323280606077, 90484.96348455526, 31864.95175169735, 56806.378292041314, 63796.18968412221, 7171.667911343953, 17003.27561587183, 0.0, 4788.074099186445, 28255.304348631624, 57752.84909951108, 25562.89690453725, 49407.023914520454, 27667.290961845203, 51720.08699360914, 3465.7695664887906, 13229.459814535126, 21217.630746351, 78547.50182198858, 13824.820812097327, 45594.773978959434, 53680.26511456513], [8062.9660755642635, 89463.28055468683, 36365.9586955122, 52689.1686955868, 59397.57892088534, 3082.6107371025755, 16969.834287423088, 4788.074099186445, 0.0, 29282.68556656132, 56370.12741149343, 21287.546021599082, 45939.5811305164, 24139.94187110854, 47583.12199530626, 2242.9996166072046, 17022.56016668759, 18039.920447651657, 74239.29884151655, 10555.053538912061, 41639.74071343983, 50358.94457360778], [25387.483511596794, 118617.4912712611, 30650.580555522916, 77219.7029116255, 81705.70334480514, 27728.735140694727, 12832.996300307226, 28255.304348631624, 29282.68556656132, 0.0, 85633.84068168903, 32256.156113997793, 73193.32384775126, 27374.73547112369, 72207.92954996352, 30300.83107071816, 19760.320405018752, 46703.7640244306, 96806.84927506986, 39490.333086551684, 67397.14749337241, 77890.50649899895], [61192.85976834963, 33399.54791761412, 82084.66837469774, 40584.33940608126, 50246.768822128244, 58212.42803385633, 73249.13910257924, 57752.84909951108, 56370.12741149343, 85633.84068168903, 0.0, 65224.7402317104, 28259.80775290058, 72071.02273021595, 39686.6747043614, 55366.68135920467, 69766.17697514532, 40157.64943314288, 56419.328079409104, 46570.139383498754, 35836.98494338634, 26049.6996659098], [27300.045969547366, 98377.1485053135, 52998.57643191935, 46474.3484699087, 49838.20875409252, 18429.55379191256, 21738.702454573962, 25562.89690453725, 21287.546021599082, 32256.156113997793, 65224.7402317104, 0.0, 45412.3407891071, 7188.207101204034, 41721.40149888664, 23482.08314033488, 32928.3530404847, 26276.924628237983, 64853.828860458976, 22980.043894601236, 38158.77380948712, 50264.2437095198], [53273.121321185965, 57130.353702242246, 80061.10080015135, 13480.11059414947, 23649.960829407326, 46339.14876031495, 60406.651924529804, 49407.023914520454, 45939.5811305164, 73193.32384775126, 28259.80775290058, 45412.3407891071, 0.0, 52593.87788516265, 11489.794344047237, 46084.549987625986, 62630.756871894766, 28206.366024578543, 34216.298838759605, 35600.21355698023, 8422.283230953466, 4853.056249828562], [28466.428454135228, 105312.59259840159, 51484.894773766384, 53305.13098468201, 56126.415469036554, 21064.54099286284, 18974.719315365382, 27667.290961845203, 24139.94187110854, 27374.73547112369, 72071.02273021595, 7188.207101204034, 52593.87788516265, 0.0, 48640.41887788489, 26377.44176977366, 32162.539108798588, 32582.63399087466, 71007.3700715954, 28298.11764710862, 45279.701014712984, 57445.030725188066], [55479.749623127354, 67218.96751545358, 83415.92231268139, 5115.15397963742, 13702.462927116454, 47230.02250502214, 59801.71074512502, 51720.08699360914, 47583.12199530626, 72207.92954996352, 39686.6747043614, 41721.40149888664, 11489.794344047237, 48640.41887788489, 0.0, 48259.99643682642, 64604.6847993866, 31629.80963662283, 27152.79818103838, 38198.142761732524, 6883.985805425523, 14203.103796821986], [7250.619066052229, 88320.78429685112, 35321.76889641286, 53348.47826620085, 60336.47201668741, 5313.410855580463, 18329.596444627485, 3465.7695664887906, 2242.9996166072046, 30300.83107071816, 55366.68135920467, 23482.08314033488, 46084.549987625986, 26377.44176977366, 48259.99643682642, 0.0, 16562.503395767166, 17946.514991844524, 75081.93064848626, 10485.495263162346, 42155.97420756871, 50405.81695236771], [9362.892067913592, 101874.6458729104, 20241.257193287187, 69711.45537716238, 76284.47076335327, 17701.286283459725, 14344.562402210104, 13229.459814535126, 17022.56016668759, 19760.320405018752, 69766.17697514532, 32928.3530404847, 62630.756871894766, 32162.539108798588, 64604.6847993866, 16562.503395767166, 0.0, 34447.05600795659, 91193.18282926908, 27034.523410827835, 58636.43109044746, 66909.01817062328], [25084.440993462475, 73557.0114231363, 52145.19076233301, 36572.68637068929, 44635.66681238224, 19012.815919313485, 33940.31618908996, 21217.630746351, 18039.920447651657, 46703.7640244306, 40157.64943314288, 26276.924628237983, 28206.366024578543, 32582.63399087466, 31629.80963662283, 17946.514991844524, 34447.05600795659, 0.0, 58778.958315893964, 7499.302119484193, 25071.096363495923, 32466.298324941516], [82238.06803012642, 73689.1000657669, 110364.22367707617, 22322.30267781527, 15122.05354833791, 73585.51931805944, 84982.02672282301, 78547.50182198858, 74239.29884151655, 96806.84927506986, 56419.328079409104, 64853.828860458976, 34216.298838759605, 71007.3700715954, 27152.79818103838, 75081.93064848626, 91193.18282926908, 58778.958315893964, 0.0, 65223.976175707816, 33863.848577893536, 32910.80924692827], [17685.389349856006, 79882.92917785693, 45225.53816256695, 43243.42260256123, 50715.76758719227, 11771.332588080253, 26833.571491668805, 13824.820812097327, 10555.053538912061, 39490.333086551684, 46570.139383498754, 22980.043894601236, 35600.21355698023, 28298.11764710862, 38198.142761732524, 10485.495263162346, 27034.523410827835, 7499.302119484193, 65223.976175707816, 0.0, 31900.8959926363, 39927.42741281738], [49404.09705487389, 65521.592378409914, 77100.83898800061, 11551.900891130488, 20559.265857294162, 41541.2379145759, 54777.004217376656, 45594.773978959434, 41639.74071343983, 67397.14749337241, 35836.98494338634, 38158.77380948712, 8422.283230953466, 45279.701014712984, 6883.985805425523, 42155.97420756871, 58636.43109044746, 25071.096363495923, 33863.848577893536, 31900.8959926363, 0.0, 12882.449351485913], [57546.2357182414, 53192.15208104017, 83961.65361544519, 14534.786497795534, 24337.961062802664, 50876.15067908539, 65086.113649414525, 53680.26511456513, 50358.94457360778, 77890.50649899895, 26049.6996659098, 50264.2437095198, 4853.056249828562, 57445.030725188066, 14203.103796821986, 50405.81695236771, 66909.01817062328, 32466.298324941516, 32910.80924692827, 39927.42741281738, 12882.449351485913, 0.0]]; nC=len(T) #index of the north-pole house (i.e., first row/column in T) n=0 #index of the south-pole house (i.e., last row/column in T) s=nC-1 #time budget B = 100000 #to keep indexing simple, the north-pole house and south-pole house is also included in the niceness-list and given a value of zero. niceness=[0, 88, 47, 86, 2, 77, 20, 56, 49, 62, 75, 50, 19, 60, 85, 64, 8, 77, 39, 41, 59, 0] m = Model(name='santa', log_output=True) m.export_as_lp("santa.lp") m.solve() m.print_solution()