Data Science Python 4

import%20marimo%0A%0A__generated_with%20%3D%20%220.17.6%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20return%20mo%2C%20np%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20nav_menu%20%3D%20mo.nav_menu(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%2Findex.html%22%3A%20f%22%7Bmo.icon('lucide%3Ahome')%7D%20Home%22%2C%0A%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20orientation%3D%22vertical%22%2C%0A%20%20%20%20)%0A%20%20%20%20nav_menu%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%2F%2F%2F%20attention%20%7C%20Attention!%0A%0A%20%20%20%20Code%20in%20this%20notebook%20involving%20AMPL%20**WOULD%20NOT**%20run%20directly%20as%20Marimo%20does%20not%20include%20AMPL%20package%20(it%20needs%20registration%20anyway).%20Check%20AMPL%20%5Bofficial%20website%5D(https%3A%2F%2Fampl.com)%20for%20more%20info.%0A%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Optimization%2C%20Part%202%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Goal%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20This%20set%20develops%20modeling%20and%20solution%20skills%20for%20optimization%20problems.%20Topics%20include%20feasibility%20recovery%20in%20LPs%2C%20formulation%20strength%20in%20integer%20programming%2C%20branch-and-bound%20for%20knapsack%2C%20heuristic%20methods%20(greedy%2C%20local%2C%20tabu%2C%20annealing)%2C%20and%20inventory%20control%20under%20uncertainty.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Problem%201%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Assume%20we%20are%20given%20an%20LP%20in%20standard%20form%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%20%5Cmax_%7Bx%7D(c%5ETx)%20%26%5Ctext%7B%20s.t.%7D%20%5C%5C%20Ax%20%26%5Cle%20b%20%5C%5C%20x%20%26%5Cge%200%20%5Cend%7Baligned%7D%24%24%0A%0A%20%20%20%20where%20%24b%24%20may%20contain%20some%20negative%20components%2C%20in%20which%20case%20it%20is%20not%20clear%20if%20there%20is%20even%20a%20feasible%20solution.%20Formulate%20a%20new%20LP%20such%20that%3A%0A%0A%20%20%20%20-%20The%20new%20LP%20always%20has%20a%20feasible%20solution%20which%20has%20a%20simple%2C%20closed%20form%0A%20%20%20%20-%20The%20new%20LP%20takes%20an%20objective%20value%20of%200%20if%20the%20original%20LP%20is%20feasible%0A%20%20%20%20-%20The%20new%20LP%20takes%20an%20objective%20value%20of%20greater%20than%200%20if%20the%20orginal%20LP%20is%20infeasible%0A%20%20%20%20-%20Given%20a%20solution%20to%20the%20new%20LP%20with%20objective%20value%20of%200%2C%20one%20can%20construct%20a%20feasible%20solution%20to%20the%20original%20LP%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Form%20a%20new%20LP%20by%20introducing%20variables%20%24y_i%20%5Cge%200%24%20(one%20for%20each%20constraint).%20Consider%20the%20LP%3A%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%20%5Cmin_%7Bx%2C%20y%7D%5Csum%20y%20%26%5Ctext%7B%20s.t.%7D%20%5C%5C%20Ax%20-%20y%20%26%5Cle%20b%20%5C%5C%20x%20%26%5Cge%200%20%5C%5C%20y%20%26%5Cge%200%5Cend%7Baligned%7D%24%24%0A%0A%20%20%20%20-%20It%20is%20always%20feasible%3A%20let%20%24x%20%3D%200%24%20and%20%24y_i%20%3D%20-%5Cmin(0%2C%20b_i)%24%0A%20%20%20%20-%20If%20the%20original%20LP%20is%20feasible%2C%20then%20%24y%20%3D%200%24%20is%20a%20feasible%20solution%20and%20is%20clearly%20minimizing%20%241%5ETy%24%0A%20%20%20%20-%20If%20the%20original%20LP%20is%20infeasible%2C%20then%20some%20%24(Ax)_i%24%20exceeds%20%24b_i%24%2C%20forcing%20%24y_i%24%20to%20be%20greater%20than%200%2C%20making%20the%20new%20LP%20takes%20an%20objective%20value%20greater%20than%200%0A%20%20%20%20-%20We%20can%20get%20a%20feasible%20solution%20by%20simply%20extracting%20the%20%24x%24%20part%20of%20optimal%20solution%20of%20the%20new%20LP.%20Notice%20this%20does%20not%20necessarily%20give%20an%20optimal%20solution%20of%20the%20original%20LP%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Problem%202%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Formulation%20A%20has%20the%20following%20constraints%3A%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%5Csum_%7Bj%3D1%7D%5Enx_%7Bij%7D%20%26%3D1%2C%5Cforall%20i%20%5C%5C%20x_%7Bij%7D%20%26%5Cle%20y_j%2C%20%5Cforall%20i%2C%20j%20%5C%5C%20x%2C%20y%20%26%5Cge%200%20%5C%5C%20x_%7Bij%7D%2C%20y_j%20%26%20%5Cin%20%5Cmathbb%7BZ%7D%2C%20%5Cforall%20i%2C%20j%5Cend%7Baligned%7D%24%24%0A%0A%20%20%20%20Formulation%20B%20has%20the%20following%20constraints%3A%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%5Csum_%7Bj%3D1%7D%5Enx_%7Bij%7D%20%26%3D1%2C%5Cforall%20i%20%5C%5C%20%5Csum_%7Bi%3D1%7D%5Emx_%7Bij%7D%20%26%5Cle%20my_j%2C%20%5Cforall%20j%20%5C%5C%20x%2C%20y%20%26%5Cge%200%20%5C%5C%20x_%7Bij%7D%2C%20y_j%20%26%20%5Cin%20%5Cmathbb%7BZ%7D%2C%20%5Cforall%20i%2C%20j%5Cend%7Baligned%7D%24%24%0A%0A%20%20%20%20Which%20formulation%20is%20stronger%3F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Formulation%20A%20is%20stronger.%20The%20second%20constraint%20in%20Formulation%20B%20just%20gives%20a%20total%20cap%20of%20%24x_%7Bij%7D%24%20in%20a%20row%2C%20but%20the%20second%20constraint%20in%20Formulation%20A%20gives%20a%20cap%20to%20them%20individually.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Problem%203%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Solve%20the%20following%20problem%20by%20branch-and-bound.%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%20%5Cmax_%7Bx%7D17x_1%20%2B%2010x_2%20%2B%2025x_3%20%2B%2017x_4%20%26%5Ctext%7B%20s.t.%7D%20%5C%5C%205x_1%20%2B%203x_2%20%2B%208x_3%20%2B%207x_4%20%26%5Cle%2012%20%5C%5C%20x_i%20%26%5Cin%20%5Clbrace%200%2C%201%20%5Crbrace%20%5Cend%7Baligned%7D%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20First%20solve%20the%20LP%3A%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%20%5Cmax_%7Bx%7D17x_1%20%2B%2010x_2%20%2B%2025x_3%20%2B%2017x_4%20%26%5Ctext%7B%20s.t.%7D%20%5C%5C%205x_1%20%2B%203x_2%20%2B%208x_3%20%2B%207x_4%20%26%5Cle%2012%20%5C%5C%20x_i%20%26%5Cin%20%5B0%2C%201%5D%20%5Cend%7Baligned%7D%24%24%0A%0A%20%20%20%20Do%20a%20quick%20value%20per%20weight%2C%20we%20see%20%24w_1%20%3D%2017%2F5%20%3E%20w_2%20%3D%2010%2F3%20%3E%20w_3%20%3D%2025%2F8%20%3E%20w_4%20%3D%2017%2F7%24%20so%20the%20optimal%20solution%20is%20%24x_1%20%3D%201%2C%20x_2%20%3D%201%24%20and%20leaves%20%24x_3%20%3D%200.5%24.%20Now%20we%20do%20branch-and-cut.%0A%0A%20%20%20%20First%2C%20%24x_3%20%3D%200%24%2C%20we%20get%20the%20LP%3A%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%20%5Cmax_%7Bx%7D17x_1%20%2B%2010x_2%20%2B%2017x_4%20%26%5Ctext%7B%20s.t.%7D%20%5C%5C%205x_1%20%2B%203x_2%20%2B%207x_4%20%26%5Cle%2012%20%5C%5C%20x_i%20%26%5Cin%20%5Clbrace%200%2C%201%20%5Crbrace%20%5Cend%7Baligned%7D%24%24%0A%0A%20%20%20%20Apparently%20the%20optimal%20solution%20here%20is%20%24x_1%20%3D%201%2C%20x_4%20%3D%201%20%5Cimplies%24%20object%20%24%3D%2017%2B17%20%3D%2034%24.%0A%0A%20%20%20%20Next%2C%20%24x_3%20%3D%201%24%2C%20we%20get%20the%20LP%3A%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%20%5Cmax_%7Bx%7D17x_1%20%2B%2010x_2%20%2B%2025%20%2B%2017x_4%20%26%5Ctext%7B%20s.t.%7D%20%5C%5C%205x_1%20%2B%203x_2%20%2B%207x_4%20%26%5Cle%204%20%5C%5C%20x_i%20%26%5Cin%20%5Clbrace%200%2C%201%20%5Crbrace%20%5Cend%7Baligned%7D%24%24%0A%0A%20%20%20%20Apparently%20the%20optimal%20solution%20here%20is%20%24x_2%20%3D%201%20%5Cimplies%24%20object%20%24%3D%2010%2B25%20%3D%2035%24.%20Combine%20things%20together%2C%20optimal%20solution%20for%20the%20original%20program%20is%20%24x_2%20%3D%201%2C%20x_3%20%3D%201%24%20gives%20%2417x_1%20%2B%2010x_2%20%2B%2025x_3%20%2B%2017x_4%20%3D%2035%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Problem%204%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Consider%20a%20general%20binary%20knapsack%20problem%0A%0A%20%20%20%20%24%24%5Cbegin%7Baligned%7D%20%5Cmax_%7Bx%7D%5Csum_%7Bi%3D1%7D%5Enc_ix_i%20%26%5Ctext%7B%20s.t.%7D%20%5C%5C%20%5Csum_%7Bi%3D1%7D%5En%20a_ix_i%20%26%5Cle%20B%20%5C%5C%20x_i%20%26%5Cin%20%5Clbrace%200%2C%201%20%5Crbrace%20%5Cend%7Baligned%7D%24%24%0A%0A%20%20%20%201.%20Describe%20a%20greedy%20heuristic%20for%20constructing%20a%20solution%20to%20this%20problem.%0A%20%20%20%202.%20Implement%20local%20search%20heuristic%20for%20this%20problem.%0A%20%20%20%203.%20Extend%20your%20local%20search%20heuristic%20to%20a%20tabu%20search%20heuristic.%0A%20%20%20%204.%20Extend%20your%20local%20search%20heuristic%20to%20a%20simulated%20annealing%20heuristic.%0A%20%20%20%205.%20Run%20each%20of%20your%20heuristics%20on%20some%20randomly%20generated%20problem%20instances.%20Solve%20these%20instances%20with%20Gurobi.%20How%20close%20to%20the%20optimal%20solution%20do%20your%20heuristics%20achieve%3F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%201.%20See%20above%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%202.%20Python%20implement%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20knapsack_local_search(c%2C%20a%2C%20B%2C%20max_iter%3D1000)%3A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(c)%0A%20%20%20%20%20%20%20%20c%20%3D%20np.array(c)%0A%20%20%20%20%20%20%20%20a%20%3D%20np.array(a)%0A%0A%20%20%20%20%20%20%20%20ratio%20%3D%20c%20%2F%20a%0A%20%20%20%20%20%20%20%20order%20%3D%20np.argsort(-ratio)%0A%20%20%20%20%20%20%20%20x%20%3D%20np.zeros(n%2C%20dtype%3Dint)%0A%20%20%20%20%20%20%20%20total_weight%20%3D%200%0A%0A%20%20%20%20%20%20%20%20for%20i%20in%20order%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20total_weight%20%2B%20a%5Bi%5D%20%3C%3D%20B%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%5Bi%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20total_weight%20%2B%3D%20a%5Bi%5D%0A%0A%20%20%20%20%20%20%20%20best_x%20%3D%20x.copy()%0A%20%20%20%20%20%20%20%20best_value%20%3D%20np.dot(c%2C%20x)%0A%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(max_iter)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20improved%20%3D%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x_new%20%3D%20best_x.copy()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x_new%5Bi%5D%20%3D%201%20-%20x_new%5Bi%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20new_weight%20%3D%20np.dot(a%2C%20x_new)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20new_weight%20%3E%20B%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20new_value%20%3D%20np.dot(c%2C%20x_new)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20new_value%20%3E%20best_value%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_x%20%3D%20x_new%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_value%20%3D%20new_value%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20improved%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20improved%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%0A%20%20%20%20%20%20%20%20return%20best_x%2C%20best_value%0A%20%20%20%20return%20(knapsack_local_search%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%203.%20Python%20implement%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20knapsack_tabu_search(c%2C%20a%2C%20B%2C%20max_iter%3D500%2C%20tabu_tenure%3D5)%3A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(c)%0A%20%20%20%20%20%20%20%20c%20%3D%20np.array(c)%0A%20%20%20%20%20%20%20%20a%20%3D%20np.array(a)%0A%0A%20%20%20%20%20%20%20%20ratio%20%3D%20c%20%2F%20a%0A%20%20%20%20%20%20%20%20order%20%3D%20np.argsort(-ratio)%0A%20%20%20%20%20%20%20%20x%20%3D%20np.zeros(n%2C%20dtype%3Dint)%0A%20%20%20%20%20%20%20%20total_weight%20%3D%200%0A%0A%20%20%20%20%20%20%20%20for%20i%20in%20order%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20total_weight%20%2B%20a%5Bi%5D%20%3C%3D%20B%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%5Bi%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20total_weight%20%2B%3D%20a%5Bi%5D%0A%0A%20%20%20%20%20%20%20%20best_x%20%3D%20x.copy()%0A%20%20%20%20%20%20%20%20best_value%20%3D%20np.dot(c%2C%20x)%0A%0A%20%20%20%20%20%20%20%20tabu_list%20%3D%20%7B%7D%0A%0A%20%20%20%20%20%20%20%20for%20iteration%20in%20range(max_iter)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20best_neighbor%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20best_neighbor_value%20%3D%20-np.inf%0A%20%20%20%20%20%20%20%20%20%20%20%20move_to_make%20%3D%20None%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x_candidate%20%3D%20x.copy()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x_candidate%5Bi%5D%20%3D%201%20-%20x_candidate%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20weight_candidate%20%3D%20np.dot(a%2C%20x_candidate)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20weight_candidate%20%3E%20B%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20value_candidate%20%3D%20np.dot(c%2C%20x_candidate)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20is_tabu%20%3D%20i%20in%20tabu_list%20and%20tabu_list%5Bi%5D%20%3E%20iteration%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20aspiration%20%3D%20value_candidate%20%3E%20best_value%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20is_tabu%20or%20aspiration%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20value_candidate%20%3E%20best_neighbor_value%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_neighbor%20%3D%20x_candidate%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_neighbor_value%20%3D%20value_candidate%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20move_to_make%20%3D%20i%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20best_neighbor%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20x%20%3D%20best_neighbor%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20best_neighbor_value%20%3E%20best_value%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_value%20%3D%20best_neighbor_value%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_x%20%3D%20best_neighbor%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20tabu_list%5Bmove_to_make%5D%20%3D%20iteration%20%2B%20tabu_tenure%0A%0A%20%20%20%20%20%20%20%20return%20best_x%2C%20best_value%0A%20%20%20%20return%20(knapsack_tabu_search%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%204.%20Python%20implement%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20knapsack_simulated_annealing(c%2C%20a%2C%20B%2C%20T_init%3D100.0%2C%20T_min%3D1e-3%2C%20alpha%3D0.95%2C%20max_iter%3D1000)%3A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(c)%0A%20%20%20%20%20%20%20%20c%20%3D%20np.array(c)%0A%20%20%20%20%20%20%20%20a%20%3D%20np.array(a)%0A%0A%20%20%20%20%20%20%20%20ratio%20%3D%20c%20%2F%20a%0A%20%20%20%20%20%20%20%20order%20%3D%20np.argsort(-ratio)%0A%20%20%20%20%20%20%20%20x%20%3D%20np.zeros(n%2C%20dtype%3Dint)%0A%20%20%20%20%20%20%20%20total_weight%20%3D%200%0A%0A%20%20%20%20%20%20%20%20for%20i%20in%20order%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20total_weight%20%2B%20a%5Bi%5D%20%3C%3D%20B%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%5Bi%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20total_weight%20%2B%3D%20a%5Bi%5D%0A%0A%20%20%20%20%20%20%20%20best_x%20%3D%20x.copy()%0A%20%20%20%20%20%20%20%20best_value%20%3D%20np.dot(c%2C%20x)%0A%0A%20%20%20%20%20%20%20%20T%20%3D%20T_init%0A%0A%20%20%20%20%20%20%20%20for%20step%20in%20range(max_iter)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20np.random.randint(0%2C%20n)%0A%20%20%20%20%20%20%20%20%20%20%20%20x_new%20%3D%20x.copy()%0A%20%20%20%20%20%20%20%20%20%20%20%20x_new%5Bi%5D%20%3D%201%20-%20x_new%5Bi%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20weight_new%20%3D%20np.dot(a%2C%20x_new)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20weight_new%20%3E%20B%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20value_old%20%3D%20np.dot(c%2C%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20value_new%20%3D%20np.dot(c%2C%20x_new)%0A%20%20%20%20%20%20%20%20%20%20%20%20delta%20%3D%20value_new%20-%20value_old%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20delta%20%3E%200%20or%20np.random.rand()%20%3C%20np.exp(delta%20%2F%20T)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%20%3D%20x_new%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20value_new%20%3E%20best_value%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_x%20%3D%20x_new%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_value%20%3D%20value_new%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20T%20*%3D%20alpha%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20T%20%3C%20T_min%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%0A%20%20%20%20%20%20%20%20return%20best_x%2C%20best_value%0A%20%20%20%20return%20(knapsack_simulated_annealing%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%205.%20AMPL%20Python%20API%20implement%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20%22%22%22%0A%20%20%20%20from%20amplpy%20import%20AMPL%0A%0A%0A%20%20%20%20def%20solve_knapsack_ampl(c%2C%20a%2C%20B)%3A%0A%0A%20%20%20%20%20%20%20%20ampl%20%3D%20AMPL()%0A%20%20%20%20%20%20%20%20ampl.set_option(%22solver%22%2C%20%22gurobi%22)%0A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(c)%0A%0A%20%20%20%20%20%20%20%20%23%20AMPL%20model%0A%20%20%20%20%20%20%20%20ampl.eval(%0A%20%20%20%20%20%20%20%20%20%20%20%20'''%0A%20%20%20%20%20%20%20%20%20%20%20%20set%20ITEMS%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20param%20c%20%7BITEMS%7D%3B%20%20%23%20value%0A%20%20%20%20%20%20%20%20%20%20%20%20param%20a%20%7BITEMS%7D%3B%20%20%23%20weight%0A%20%20%20%20%20%20%20%20%20%20%20%20param%20B%3B%20%20%20%20%20%20%20%20%20%20%23%20capacity%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20var%20x%20%7Bi%20in%20ITEMS%7D%20binary%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20maximize%20TotalValue%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum%20%7Bi%20in%20ITEMS%7D%20c%5Bi%5D%20*%20x%5Bi%5D%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20subject%20to%20Capacity%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sum%20%7Bi%20in%20ITEMS%7D%20a%5Bi%5D%20*%20x%5Bi%5D%20%3C%3D%20B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20'''%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20items%20%3D%20list(range(1%2C%20n%20%2B%201))%0A%20%20%20%20%20%20%20%20ampl.set%5B%22ITEMS%22%5D.set_values(items)%0A%20%20%20%20%20%20%20%20ampl.param%5B%22c%22%5D.set_values(dict(zip(items%2C%20c)))%0A%20%20%20%20%20%20%20%20ampl.param%5B%22a%22%5D.set_values(dict(zip(items%2C%20a)))%0A%20%20%20%20%20%20%20%20ampl.param%5B%22B%22%5D%20%3D%20B%0A%0A%20%20%20%20%20%20%20%20ampl.solve()%0A%0A%20%20%20%20%20%20%20%20x%20%3D%20ampl.get_variable(%22x%22)%0A%20%20%20%20%20%20%20%20best_x%20%3D%20np.array(%5Bint(round(x%5Bi%5D.value()))%20for%20i%20in%20items%5D)%0A%20%20%20%20%20%20%20%20best_value%20%3D%20ampl.get_objective(%22TotalValue%22).value()%0A%0A%20%20%20%20%20%20%20%20return%20best_x%2C%20best_value%0A%20%20%20%20%22%22%22%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20generate_knapsack_instance(n%3D50%2C%20seed%3DNone)%3A%0A%20%20%20%20%20%20%20%20if%20seed%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20np.random.seed(seed)%0A%0A%20%20%20%20%20%20%20%20c%20%3D%20np.random.randint(10%2C%20100%2C%20size%3Dn)%20%20%23%20values%20between%2010%20and%20100%0A%20%20%20%20%20%20%20%20a%20%3D%20np.random.randint(5%2C%2050%2C%20size%3Dn)%20%20%23%20weights%20between%205%20and%2050%0A%20%20%20%20%20%20%20%20B%20%3D%20int(np.random.uniform(0.5%2C%200.7)%20*%20np.sum(a))%20%20%23%2050%E2%80%9370%25%20of%20total%20weight%0A%0A%20%20%20%20%20%20%20%20return%20c.tolist()%2C%20a.tolist()%2C%20B%0A%0A%20%20%20%20c%2C%20a%2C%20B%20%3D%20generate_knapsack_instance(n%3D30)%0A%20%20%20%20return%20B%2C%20a%2C%20c%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20B%2C%0A%20%20%20%20a%2C%0A%20%20%20%20c%2C%0A%20%20%20%20knapsack_local_search%2C%0A%20%20%20%20knapsack_simulated_annealing%2C%0A%20%20%20%20knapsack_tabu_search%2C%0A)%3A%0A%20%20%20%20x_best%2C%20val_best%20%3D%20knapsack_local_search(c%2C%20a%2C%20B)%0A%20%20%20%20print(%22Local%20search%3A%22)%0A%20%20%20%20print(%22Selected%3A%22%2C%20x_best)%0A%20%20%20%20print(%22Total%20value%3A%22%2C%20val_best)%0A%0A%20%20%20%20x_best%2C%20val_best%20%3D%20knapsack_tabu_search(c%2C%20a%2C%20B)%0A%20%20%20%20print(%22Tabu%20search%3A%22)%0A%20%20%20%20print(%22Best%20solution%3A%22%2C%20x_best)%0A%20%20%20%20print(%22Total%20value%3A%22%2C%20val_best)%0A%0A%20%20%20%20x_best%2C%20val_best%20%3D%20knapsack_simulated_annealing(c%2C%20a%2C%20B)%0A%20%20%20%20print(%22Simulated%20Annealing%3A%22)%0A%20%20%20%20print(%22Best%20solution%3A%22%2C%20x_best)%0A%20%20%20%20print(%22Total%20value%3A%22%2C%20val_best)%0A%0A%20%20%20%20%22%22%22%0A%20%20%20%20x_best%2C%20val_best%20%3D%20solve_knapsack_ampl(c%2C%20a%2C%20B)%0A%20%20%20%20print(%22Gurobi%3A%22)%0A%20%20%20%20print(%22Selected%3A%22%2C%20x_best)%0A%20%20%20%20print(%22Total%20Value%3A%22%2C%20val_best)%0A%20%20%20%20%22%22%22%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Problem%205%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Consider%20the%20dynamic%20single%20item%20inventory%20problem.%20Your%20company%20sells%20a%20single%20item.%20Right%20now%2C%20you%20have%20%24x_0%24%20units%20of%20the%20item.%20In%20each%20day%20%24t%24%2C%20some%20number%20%24d_t%24%20of%20customers%20arrive%20and%20attempt%20to%20buy%20the%20product.%20Each%20unit%20sold%20produces%20%5C%24r%20of%20revenue.%20If%20you%20have%20more%20customers%20than%20demand%20in%20any%20day%2C%20you%20lose%20the%20excess%20customers%2C%20and%20do%20not%20sell%20anything%20to%20them.%20At%20the%20end%20of%20each%20day%2C%20you%20can%20choose%20to%20order%20more%20product%2C%20which%20will%20arrive%20%24L%24%20days%20later.%20If%20you%20order%20%24k%24%20units%20of%20products%2C%20you%20must%20pay%20%5C%24%20%24%5Calpha%20%2B%5Cbeta%20k%24%2C%20where%20%24%5Calpha%24%20is%20a%20flat%20delivery%20fee%2C%20and%20%24%5Cbeta%24%20is%20the%20per-unit%20cost.%20If%20we%20let%20%24z_t%24%20be%20the%20amount%20ordered%20at%20end%20of%20day%20%24t%24%2C%20then%20the%20amount%20of%20inventory%20%24x_t%24%20available%20at%20the%20beginning%20of%20each%20day%20t%20can%20be%20calculated%20recursively%20by%3A%0A%0A%20%20%20%20%24%24x_t%20%3D%20%5Cbegin%7Bcases%7D%20z_%7Bt%20-%20L%7D%20%26%2C%20d_%7Bt-1%7D%20%5Cge%20x_%7Bt-1%7D%2C%20%5C%5C%20x_%7Bt%20-%201%7D%20-%20d_%7Bt%20-%201%7D%20%2B%20z_%7Bt%20-%20L%7D%20%26%2C%20d_%7Bt-1%7D%20%3C%20x_%7Bt-1%7D.%5Cend%7Bcases%7D%24%24%0A%0A%20%20%20%20Suppose%20that%20you%20have%20some%20method%20for%20producing%20an%20estimate%20%24%5Chat%7Bd%7D_t%24%20for%20the%20value%20%24d_t%24.%20Describe%2C%20in%20detail%2C%20a%20method%20that%20you%20could%20use%20to%20decide%20at%20the%20end%20of%20each%20day%20how%20much%20inventory%20to%20order.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Assume%20expectation%20of%20%24d_t%24%20is%20positive%2C%20suppose%20%24%5Calpha%20%3D%200%24%20then%20we%20should%20always%20just%20order%20any%20many%20as%20we%20can%20because%20there%20is%20no%20penalties%20on%20overstocking%20(can%20introduce%20penalty%20by%20adding%20storage%20fee%20or%20spoilage).%20With%20a%20positive%20%24%5Calpha%24%2C%20ordering%20too%20often%20becomes%20expensive.%20The%20general%20idea%20is%20to%20wait%20until%20a%20*projected*%20shortfall%20is%20large%20enough%20that%20is%20worth%20paying%20the%20flat%20fee%20%24%5Calpha%24.%0A%0A%20%20%20%201.%20Step%201%3A%20Simulate%20inventory%20over%20days%20%24t%2C%20%5Cdots%2C%20t%2BL%24%20using%20the%20formula%20and%20the%20demand%20estimation%0A%20%20%20%202.%20Step%202%3A%20Forecast%20demand%20over%20window%20starting%20at%20%24t%2BL%24%3A%0A%20%20%20%20%20%20%20%20Choose%20a%20short%20forecast%20horizon%20%24H'%24%20and%20compute%3A%20%24D%20%3D%20%5Csum_%7Bs%3Dt%2BL%7D%5E%7Bt%2BL%2BH'%7D%20%5Chat%7Bd%7D_s%24%0A%20%20%20%203.%20Step%203%3A%20Compute%20projected%20shortfall%20%24k%20%3D%20%5Cmax(0%2C%20D%20-%20x_%7Bt%2BL%7D)%24%3A%20the%20number%20of%20units%20needed%20(beyond%20what%20you%20expect%20to%20have)%20to%20meet%20projected%20demand%0A%20%20%20%204.%20Step%204%3A%20Compute%20gain%20from%20selling%3A%20%24G%20%3D%20(r%20-%20%5Cbeta)%20%5Ccdot%20k%24%2C%20place%20the%20order%20if%20%24G%20%3E%20%5Calpha%24%0A%20%20%20%205.%20Step%205%3A%20Main%20records%20and%20proceed%20to%20next%20day%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A