import%20marimo%0A%0A__generated_with%20%3D%20%220.15.2%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20!%5BMOSEK%20ApS%5D(https%3A%2F%2Fwww.mosek.com%2Fstatic%2Fimages%2Fbranding%2Fwebgraphmoseklogocolor.png%20)%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Small%20disks%20and%20geometric%20facility%20location%3A%20*a%20mixed%20integer%20conic%20quadratic%20tutorial*%0A%20%20%20%20%20%20%20%20In%20this%20tutorial%20we%20are%20going%20to%3A%0A%20%20%20%20%20%20%20%20*%20show%20examples%20of%20compact%20models%20constructed%20with%20*Fusion*%2C%0A%20%20%20%20%20%20%20%20*%20write%20a%20conic%20model%20with%20binary%20variables%2C%0A%20%20%20%20%20%20%20%20*%20apply%20the%20*Big-M*%20formulation%2C%0A%20%20%20%20%20%20%20%20*%20construct%20a%20base%20model%20and%20use%20its%20various%20extensions%20to%20solve%20a%20number%20of%20different%20problems.%0A%0A%20%20%20%20%20%20%20%20%23%23%23%20Introduction%0A%0A%20%20%20%20%20%20%20%20We%20are%20going%20to%20work%20with%20variations%20of%20the%20following%20geometric%20setup.%20Suppose%20we%20have%20%24n%24%20of%20points%20%24p_1%2C%5Cldots%2Cp_n%5Cin%5Cmathbb%7BR%7D%5Ed%24%20and%20we%20want%20to%20find%20a%20configuration%20of%20%24k%24%20balls%20with%20centers%20%24x_1%2C%5Cldots%2Cx_k%5Cin%5Cmathbb%7BR%7D%5Ed%24%20and%20radii%20%24r_1%2C%5Cldots%2Cr_k%24%2C%20respectively%2C%20which%20covers%20some%2Fall%20of%20the%20points%20%24p_i%24%20and%20satisfies%20additional%20constraints%20depending%20on%20the%20problem.%20For%20visualization%20purposes%20we%20will%20focus%20on%20the%20plane%20and%20disks%2C%20that%20is%20the%20case%20%24d%3D2%24%2C%20but%20the%20code%20and%20mathematical%20formulation%20remain%20valid%20in%20all%20dimensions.%0A%0A%20%20%20%20%20%20%20%20For%20example%2C%20the%20next%20snippet%20displays%20a%20set%20of%20points%20in%20%24%5Cmathbb%7BR%7D%5E2%24.%20Here%20is%20a%20sample%20question%3A%20how%20many%20of%20those%20points%20can%20we%20cover%20with%20three%20disks%20of%20radius%20at%20most%20%240.1%24%20each%3F%0A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20from%20mosek.fusion%20import%20Model%2C%20Domain%2C%20Expr%2C%20ObjectiveSense%2C%20Matrix%2C%20Var%2C%20SolutionStatus%0A%20%20%20%20import%20mosek.fusion.pythonic%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20def%20data(n)%3A%0A%20%20%20%20%20%20%20%20np.random.seed(1236)%0A%20%20%20%20%20%20%20%20return%20%5B%5B_x%2C%20y%5D%20for%20_x%2C%20y%20in%20np.broadcast(np.random.uniform(0.0%2C%201.0%2C%20n)%2C%20np.random.uniform(0.0%2C%200.3%2C%20n))%5D%0A%0A%20%20%20%20def%20gaussianData(n)%3A%0A%20%20%20%20%20%20%20%20np.random.seed(1236)%0A%20%20%20%20%20%20%20%20return%20%5B%5B_x%2C%20y%5D%20for%20_x%2C%20y%20in%20np.broadcast(np.random.normal(0.0%2C%201.0%2C%20n)%2C%20np.random.normal(0.0%2C%201.0%2C%20n))%5D%0A%0A%20%20%20%20def%20display(P%2C%20R%2C%20X)%3A%0A%20%20%20%20%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20%20%20%20%20plt.scatter(*zip(*_P))%0A%20%20%20%20%20%20%20%20plt.axis('equal')%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(len(R))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20plt.gcf().gca().add_artist(plt.Circle((X%5B2%20*%20i%5D%2C%20X%5B2%20*%20i%20%2B%201%5D)%2C%20R%5Bi%5D%2C%20fc%3D'r'%2C%20color%3D'r'%2C%20alpha%3D0.5))%0A%20%20%20%20%20%20%20%20%20%20%20%20plt.gcf().gca().plot(X%5B2%20*%20i%5D%2C%20X%5B2%20*%20i%20%2B%201%5D%2C%20'or')%0A%20%20%20%20%20%20%20%20plt.show()%0A%20%20%20%20display(data(20)%2C%20%5B%5D%2C%20%5B%5D)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20Domain%2C%0A%20%20%20%20%20%20%20%20Expr%2C%0A%20%20%20%20%20%20%20%20Model%2C%0A%20%20%20%20%20%20%20%20ObjectiveSense%2C%0A%20%20%20%20%20%20%20%20Var%2C%0A%20%20%20%20%20%20%20%20data%2C%0A%20%20%20%20%20%20%20%20display%2C%0A%20%20%20%20%20%20%20%20gaussianData%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20A%20base%20model%20formulation%20in%20*Fusion*%0A%0A%20%20%20%20%20%20%20%20Our%20input%20is%20a%20collection%20of%20points%20%24p_1%5Cldots%2Cp_n%5Cin%5Cmathbb%7BR%7D%5Ed%24%20and%20an%20integer%20%24k%5Cgeq%201%24.%20What%20we%20want%20to%20compute%20is%20the%20centers%20%24x_1%2C%5Cldots%2Cx_k%5Cin%5Cmathbb%7BR%7D%5Ed%24%20and%20the%20radii%20%24r_1%2C%5Cldots%2Cr_k%5Cgeq%200%24%20of%20%24k%24%20balls%20%24B_d(x_j%3Br_j)%24%2C%20subject%20to%20various%20constraints%20on%20how%20the%20points%20and%20balls%20interact.%20The%20basic%20notion%20we%20need%20to%20model%20is%20that%20of%20which%20points%20are%20covered%20by%20which%20balls.%20To%20this%20end%20we%20introduce%20standard%20binary%20variables%0A%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20s_%7Bij%7D%20%3D%20%5Cleft%5Clbrace%0A%20%20%20%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bcl%7D%0A%20%20%20%20%20%20%20%20%20%20%201%20%26%20%5Ctext%7Bif%20the%20ball%20%7D%20B_d(x_j%3Br_j)%20%5Ctext%7B%20covers%20the%20point%20%7D%20p_i%2C%20%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%200%20%26%20%5Ctext%7Botherwise%7D.%0A%20%20%20%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%5Cright.%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20%20%20%20%20For%20this%20to%20work%20we%20must%20ensure%20the%20implication%0A%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20s_%7Bij%7D%3D1%20%5Cimplies%20r_j%5Cgeq%20%5ClVert%20p_i-x_j%20%5CrVert_2.%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20%20%20%20%20This%20can%20be%20achieved%20by%20introducing%20a%20constraint%0A%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20r_j%5Cgeq%20%5ClVert%20p_i-x_j%20%5CrVert_2%20-%20M(1-s_%7Bij%7D)%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20%20%20%20%20where%20%24M%24%2C%20also%20known%20as%20*Big-M*%2C%20is%20large%20enough%20to%20guarantee%20that%20when%20%24s_%7Bij%7D%3D0%24%20the%20corresponding%20constraint%20is%20trivially%20satisfied%2C%20for%20example%20the%20right-hand%20side%20is%20surely%20negative.%20The%20spread%20of%20the%20data%20points%20%24p_i%24%20determines%20a%20safe%20value%20of%20%24M%24%20for%20us%3A%0A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20def%20bigM(P)%3A%0A%20%20%20%20%20%20%20%20return%202%20*%20np.shape(_P)%5B1%5D%20*%20max(np.amax(_P%2C%200)%20-%20np.amin(_P%2C%200))%0A%20%20%20%20return%20(bigM%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Finally%20we%20get%20a%20family%20of%20conic%20constraints%0A%0A%20%20%20%20%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%20%20%20%20(r_j%20%2B%20M(1-s_%7Bij%7D)%2C%5C%20%20p_i-x_j)%20%5Cin%20%5Cmathcal%7BQ%7D%5E%7Bd%2B1%7D%2C%20%5Cquad%20i%3D1%2C%5Cldots%2Cn%2C%5C%20j%3D1%2C%5Cldots%2Ck%0A%20%20%20%20%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20%20%20%20%20and%20its%20direct%20implementation%20in%20*Fusion*%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Domain%2C%20Expr%2C%20Model%2C%20Var%2C%20np)%3A%0A%20%20%20%20def%20basicModel(k%2C%20P%2C%20bigM)%3A%0A%20%20%20%20%20%20%20%20n%2C%20dim%20%3D%20(len(_P)%2C%20len(_P%5B0%5D))%0A%20%20%20%20%20%20%20%20M%20%3D%20Model('balls')%0A%20%20%20%20%20%20%20%20R%20%3D%20M.variable(k%2C%20Domain.greaterThan(0.0))%0A%20%20%20%20%20%20%20%20X%20%3D%20M.variable(%5Bk%2C%20dim%5D%2C%20Domain.unbounded())%0A%20%20%20%20%20%20%20%20S%20%3D%20M.variable(%5Bn%2C%20k%5D%2C%20Domain.binary())%0A%20%20%20%20%20%20%20%20RRep%20%3D%20Var.repeat(R%2C%20n)%0A%20%20%20%20%20%20%20%20Penalty%20%3D%20Expr.flatten(bigM%20*%20(1.0%20-%20S))%0A%20%20%20%20%20%20%20%20CoordDiff%20%3D%20np.repeat(_P%2C%20k%2C%200)%20-%20Var.repeat(X%2C%20n)%0A%20%20%20%20%20%20%20%20M.constraint(Expr.hstack(RRep%20%2B%20Penalty%2C%20CoordDiff)%2C%20Domain.inQCone())%0A%20%20%20%20%20%20%20%20return%20(M%2C%20R%2C%20X%2C%20S)%0A%20%20%20%20return%20(basicModel%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20We%20can%20now%20take%20this%20as%20a%20base%20and%20solve%20a%20number%20of%20different%20optimization%20problems.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Problem%201.%20Minimal%20enclosing%20ball%0A%0A%20%20%20%20%20%20%20%20**Objective%3A%20find%20the%20smallest%20ball%20containing%20all%20of%20the%20points.**%20%0A%0A%20%20%20%20%20%20%20%20This%20is%20a%20classical%20problem%2C%20see%20the%20%5Bbounding%20sphere%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBounding_sphere)%20and%20%5Bsmallest-circle%20problem%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FSmallest-circle_problem)%20Wikipedia%20articles.%20There%20is%20an%20algorithm%20with%20running%20time%20%24O(n)%24%20in%20any%20fixed%20dimension%2C%20and%20also%20MOSEK%20can%20solve%20it%20efficiently%20for%20a%20large%20number%20of%20points.%0A%0A%20%20%20%20%20%20%20%20Since%20we%20want%20to%20include%20all%20points%2C%20the%20Big-M%20constant%20and%20the%20%24s_%7Bij%7D%24%20indicators%20are%20superfluous.%20All%20we%20want%20to%20do%20is%20to%20set%20%24k%3D1%24%20and%20minimize%20the%20radius%20of%20the%20single%20ball%20in%20the%20model.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ObjectiveSense%2C%20basicModel%2C%20display%2C%20gaussianData)%3A%0A%20%20%20%20def%20minimalEnclosing(P)%3A%0A%20%20%20%20%20%20%20%20M%2C%20R%2C%20X%2C%20S%20%3D%20basicModel(1%2C%20_P%2C%200.0)%0A%20%20%20%20%20%20%20%20M.constraint(S%20%3D%3D%201.0)%0A%20%20%20%20%20%20%20%20M.objective(ObjectiveSense.Minimize%2C%20R%5B0%5D)%0A%20%20%20%20%20%20%20%20M.writeTask('p1.task.gz')%0A%20%20%20%20%20%20%20%20M.solve()%0A%20%20%20%20%20%20%20%20return%20(R.level()%2C%20X.level())%0A%20%20%20%20_P%20%3D%20gaussianData(1000)%0A%20%20%20%20_r%2C%20_x%20%3D%20minimalEnclosing(_P)%0A%20%20%20%20display(_P%2C%20_r%2C%20_x)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Problem%202.%20Maximum%20coverage%0A%0A%20%20%20%20%20%20%20%20**Objective%3A%20find%20the%20largest%20subset%20which%20can%20be%20covered%20by%20a%20ball%20of%20fixed%20radius.**%20%0A%0A%20%20%20%20%20%20%20%20This%20is%20also%20a%20well-known%20and%20multi-facet%20problem%2C%20see%20%5Bthis%20paper%5D(http%3A%2F%2Fwww.cs.princeton.edu%2F~chazelle%2Fpubs%2FCirclePlacement.pdf)%20by%20Chazelle%20and%20Evanston.%20It%20can%20be%20interpreted%20as%20selecting%20a%20location%20for%20a%20single%20fixed-power%20transmitter%20so%20that%20the%20signal%20reaches%20as%20many%20locations%20as%20possible.%20In%20the%20combinatorial%20setting%20it%20is%20equivalent%20to%20finding%20maximal%20cliques%20in%20unit-disk%20graphs.%20The%20best%20known%20algorithms%20for%20this%20problem%20achieve%20running%20time%20%24O(n%5E2%5Clog%7Bn%7D)%24.%20%0A%0A%20%20%20%20%20%20%20%20In%20this%20setup%20we%20still%20operate%20with%20%24k%3D1%24%20and%20we%20bound%20the%20radius%20from%20above.%20Each%20%24s_i%3Ds_%7Bi1%7D%24%20determines%20if%20the%20%24i%24-th%20point%20is%20covered%2C%20with%20the%20optimization%20objective%20equal%20to%20%24%5Csum%20s_%7Bi%7D%24.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Expr%2C%20ObjectiveSense%2C%20basicModel%2C%20bigM%2C%20data%2C%20display)%3A%0A%20%20%20%20def%20maxCoverage(P%2C%20rMax)%3A%0A%20%20%20%20%20%20%20%20M%2C%20R%2C%20X%2C%20S%20%3D%20basicModel(1%2C%20_P%2C%20bigM(_P))%0A%20%20%20%20%20%20%20%20M.constraint(R%20%3C%3D%20rMax)%0A%20%20%20%20%20%20%20%20M.objective(ObjectiveSense.Maximize%2C%20Expr.sum(S))%0A%20%20%20%20%20%20%20%20M.writeTask('p2.task.gz')%0A%20%20%20%20%20%20%20%20M.solve()%0A%20%20%20%20%20%20%20%20return%20(R.level()%2C%20X.level())%0A%20%20%20%20_P%20%3D%20data(100)%0A%20%20%20%20_r%2C%20_x%20%3D%20maxCoverage(_P%2C%200.25)%0A%20%20%20%20display(_P%2C%20_r%2C%20_x)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Problem%203.%20Smallest%20diameter%20k-circle%20cover%0A%0A%20%20%20%20%20%20%20%20**Objective%3A%20find%20%24k%24%20circles%20which%20together%20cover%20all%20the%20points%20and%20have%20the%20smallest%20sum%20of%20diameters.**%0A%0A%20%20%20%20%20%20%20%20This%20is%20a%20different%20geometric%20facility%20location%20problem%2C%20where%20we%20want%20to%20serve%20the%20whole%20population%20with%20%24k%24%20transmitters%20while%20minimizing%20their%20total%20range.%20See%20the%20paper%20%5BMinimum-Cost%20Coverage%20of%20Point%20Sets%20by%20Disks%5D(http%3A%2F%2Fjeffe.cs.illinois.edu%2Fpubs%2Fpdf%2Fcarrots.pdf)%20for%20more%20details.%20It%20can%20also%20be%20seen%20as%20a%20form%20of%20clustering%20witk%20%24k%24%20clusters.%0A%0A%20%20%20%20%20%20%20%20The%20objective%20here%20is%20of%20course%20to%20minimize%20%24%5Csum%20r_j%24.%20A%20point%20%24p_i%24%20is%20covered%20if%20%24%5Cmax_j%20s_%7Bij%7D%3D1%24%2C%20a%20condition%20we%20can%20linearize%20as%3A%20%0A%0A%20%20%20%20%20%20%20%20%24%24%5Csum_j%20s_%7Bij%7D%5Cgeq%201%2C%5C%20%5Cforall%20i%3D1%2C%5Cldots%2Cn.%24%24%0A%0A%20%20%20%20%20%20%20%20For%20%24k%3D1%24%20we%20recover%20as%20a%20special%20case%20the%20minimal%20enclosing%20ball%20problem.%20It%20is%20quite%20frequent%20that%20certain%20locations%20are%20served%20by%20their%20own%20transmitter%20with%20range%20%24r_j%5Capprox%200%24.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Expr%2C%20ObjectiveSense%2C%20basicModel%2C%20bigM%2C%20data%2C%20display)%3A%0A%20%20%20%20def%20minDiamKCircleCover(P%2C%20k)%3A%0A%20%20%20%20%20%20%20%20M%2C%20R%2C%20X%2C%20S%20%3D%20basicModel(k%2C%20_P%2C%20bigM(_P))%0A%20%20%20%20%20%20%20%20M.constraint(Expr.sum(S%2C%201)%20%3E%3D%201.0)%0A%20%20%20%20%20%20%20%20M.objective(ObjectiveSense.Minimize%2C%20Expr.sum(R))%0A%20%20%20%20%20%20%20%20M.writeTask('p3.task.gz')%0A%20%20%20%20%20%20%20%20M.solve()%0A%20%20%20%20%20%20%20%20return%20(R.level()%2C%20X.level())%0A%20%20%20%20_P%20%3D%20data(20)%0A%20%20%20%20_r%2C%20_x%20%3D%20minDiamKCircleCover(_P%2C%203)%0A%20%20%20%20display(_P%2C%20_r%2C%20_x)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Problem%204.%20Smallest%20area%20k-circle%20cover%0A%0A%20%20%20%20%20%20%20%20**Objective%3A%20find%20%24k%24%20circles%20which%20together%20cover%20all%20the%20points%20and%20have%20the%20smallest%20sum%20of%20areas.**%0A%0A%20%20%20%20%20%20%20%20Here%20we%20have%20another%20version%20of%20the%20previous%20problem%20where%20the%20cost%20of%20a%20network%20is%20measured%20(roughly%2C%20up%20to%20intersections%20of%20balls)%20by%20the%20total%20area%20it%20covers%2C%20so%20the%20%24%5Cell_2%24%20norm%20replaces%20the%20%24%5Cell_1%24%20norm%20of%20the%20radii%20vector.%20As%20pointed%20out%20in%20%5Bhere%5D(http%3A%2F%2Fjeffe.cs.illinois.edu%2Fpubs%2Fpdf%2Fcarrots.pdf)%20the%20most%20realistic%20models%20of%20wireless%20transmission%20actually%20optimize%20for%20the%20%24%5Cell_p%24%20norm%20with%20some%20%24p%3E2%24.%20%0A%0A%20%20%20%20%20%20%20%20This%20problem%20is%20similar%20to%20the%20previous%20one%2C%20but%20with%20a%20different%20objective%3A%20we%20minimize%20%24%5Csqrt%7B%5Csum_j%20r_j%5E2%7D%24.%20This%20is%20expressed%20using%20a%20conic%20constraint.%20Optimizing%20the%20%24%5Cell_2%24%20norm%20results%20in%20a%20more%20balanced%20collection%20of%20balls%2C%20as%20we%20can%20see%20below%20for%20the%20same%20dataset%20as%20in%20Problem%203.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Domain%2C%20Expr%2C%20ObjectiveSense%2C%20basicModel%2C%20bigM%2C%20data%2C%20display)%3A%0A%20%20%20%20def%20minAreaKCircleCover(P%2C%20k)%3A%0A%20%20%20%20%20%20%20%20M%2C%20R%2C%20X%2C%20S%20%3D%20basicModel(k%2C%20_P%2C%20bigM(_P))%0A%20%20%20%20%20%20%20%20t%20%3D%20M.variable(1%2C%20Domain.greaterThan(0.0))%0A%20%20%20%20%20%20%20%20M.constraint(Expr.vstack(t%2C%20R)%2C%20Domain.inQCone())%0A%20%20%20%20%20%20%20%20M.constraint(Expr.sum(S%2C%201)%20%3E%3D%201.0)%0A%20%20%20%20%20%20%20%20M.objective(ObjectiveSense.Minimize%2C%20t)%0A%20%20%20%20%20%20%20%20M.writeTask('p4.task.gz')%0A%20%20%20%20%20%20%20%20M.solve()%0A%20%20%20%20%20%20%20%20return%20(R.level()%2C%20X.level())%0A%20%20%20%20_P%20%3D%20data(20)%0A%20%20%20%20_r%2C%20_x%20%3D%20minAreaKCircleCover(_P%2C%203)%0A%20%20%20%20display(_P%2C%20_r%2C%20_x)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Problem%205.%20Maximum%20k-coverage%0A%0A%20%20%20%20%20%20%20%20**Objective%3A%20find%20the%20largest%20subset%20which%20can%20be%20covered%20by%20%24k%24%20balls%20of%20a%20fixed%20radius.**%0A%0A%20%20%20%20%20%20%20%20We%20can%20combine%20the%20previous%20techniques%20to%20express%20more%20complicated%20problems%2C%20like%20covering%20the%20largest%20possible%20number%20of%20points%20with%20%24k%24%20fixed-power%20transmitters.%20Here%20we%20want%20to%20maximize%20%24%5Csum_i%5Cmax_j%7Bs_%7Bij%7D%7D%24%2C%20which%20is%20precisely%20the%20number%20of%20covered%20points%2C%20and%20we%20want%20to%20have%20an%20upper%20bound%20on%20%24r_j%24.%20The%20objective%20is%20equivalent%20to%3A%0A%0A%20%20%20%20%20%20%20%20%24%24%5Cmax%5Csum_i%20t_i%20%5Cquad%20%5Ctextrm%7Bsubject%20to%7D%5Cquad%20t_i%5Cin%5C%7B0%2C1%5C%7D%2C%5C%20%5C%20t_i%20%5Cleq%20%5Csum_js_%7Bij%7D.%24%24%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Domain%2C%20Expr%2C%20ObjectiveSense%2C%20basicModel%2C%20bigM%2C%20data%2C%20display)%3A%0A%20%20%20%20def%20maxKCoverage(P%2C%20k%2C%20rMax)%3A%0A%20%20%20%20%20%20%20%20M%2C%20R%2C%20X%2C%20S%20%3D%20basicModel(k%2C%20_P%2C%20bigM(_P))%0A%20%20%20%20%20%20%20%20M.constraint(R%20%3D%3D%20rMax)%0A%20%20%20%20%20%20%20%20t%20%3D%20M.variable('t'%2C%20len(_P)%2C%20Domain.binary())%0A%20%20%20%20%20%20%20%20M.constraint(t%20%3C%3D%20Expr.sum(S%2C%201))%0A%20%20%20%20%20%20%20%20M.objective(ObjectiveSense.Maximize%2C%20Expr.sum(t))%0A%20%20%20%20%20%20%20%20M.setSolverParam('mioConicOuterApproximation'%2C%20'on')%0A%20%20%20%20%20%20%20%20M.writeTask('p5.task.gz')%0A%20%20%20%20%20%20%20%20M.solve()%0A%20%20%20%20%20%20%20%20return%20(R.level()%2C%20X.level())%0A%20%20%20%20_P%20%3D%20data(20)%0A%20%20%20%20_r%2C%20_x%20%3D%20maxKCoverage(_P%2C%203%2C%200.1)%0A%20%20%20%20display(_P%2C%20_r%2C%20_x)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20Comments%0A%0A%20%20%20%20%20%20%20%20For%20simplicity%20of%20the%20presentation%20we%20ignored%20various%20issues%20and%20hints%20and%20we%20leave%20them%20as%20an%20exercise%3A%0A%20%20%20%20%20%20%20%20*%20Checking%20that%20a%20solution%20has%20actually%20been%20found.%0A%20%20%20%20%20%20%20%20*%20More%20generally%3A%20handling%20exceptions.%0A%20%20%20%20%20%20%20%20*%20For%20large%20instances%20one%20should%20perhaps%20terminate%20the%20solver%20when%20a%20solution%20of%20sufficiently%20high%20quality%20has%20been%20located.%0A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%0A%20%20%20%20%20%20%20%20%3Ca%20rel%3D%22license%22%20href%3D%22http%3A%2F%2Fcreativecommons.org%2Flicenses%2Fby%2F4.0%2F%22%3E%3Cimg%20alt%3D%22Creative%20Commons%20License%22%20style%3D%22border-width%3A0%22%20src%3D%22https%3A%2F%2Fi.creativecommons.org%2Fl%2Fby%2F4.0%2F80x15.png%22%20%2F%3E%3C%2Fa%3E%3Cbr%20%2F%3EThis%20work%20is%20licensed%20under%20a%20%3Ca%20rel%3D%22license%22%20href%3D%22http%3A%2F%2Fcreativecommons.org%2Flicenses%2Fby%2F4.0%2F%22%3ECreative%20Commons%20Attribution%204.0%20International%20License%3C%2Fa%3E.%20The%20**MOSEK**%20logo%20and%20name%20are%20trademarks%20of%20%3Ca%20href%3D%22http%3A%2F%2Fmosek.com%22%3EMosek%20ApS%3C%2Fa%3E.%20The%20code%20is%20provided%20as-is.%20Compatibility%20with%20future%20release%20of%20**MOSEK**%20or%20the%20%60Fusion%20API%60%20are%20not%20guaranteed.%20For%20more%20information%20contact%20our%20%5Bsupport%5D(mailto%3Asupport%40mosek.com).%20%0A%0A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20return%20(mo%2C)%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
6da5c48406b1718f3f6b0825eaaf47f8cde518b52cfd949feb45e7d5b9643abc