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(r%22%22%22!%5BMOSEK%20ApS%5D(https%3A%2F%2Fwww.mosek.com%2Fstatic%2Fimages%2Fbranding%2Fwebgraphmoseklogocolor.png%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20In%20this%20notebook%20we%20show%20how%20to%20define%20an%20integer%20problem%20using%20the%20Optimizer%20API%20and%20visualize%20the%20solution.%20We%20also%20mention%20how%20in%20this%20case%20an%20infeasibility%20certificate%20for%20the%20linear%20relaxation%20can%20be%20given%20a%20clear%20combinatorial%20interpretation.%0A%0A%20%20%20%20%23%20Exact%20planar%20covering%0A%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%20import%20Env%2C%20variabletype%2C%20boundkey%2C%20objsense%2C%20soltype%2C%20prosta%2C%20dparam%2C%20streamtype%2C%20dinfitem%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20from%20itertools%20import%20product%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20matplotlib.patches%20as%20patches%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20Env%2C%0A%20%20%20%20%20%20%20%20boundkey%2C%0A%20%20%20%20%20%20%20%20dinfitem%2C%0A%20%20%20%20%20%20%20%20dparam%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20objsense%2C%0A%20%20%20%20%20%20%20%20patches%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20%20%20%20%20product%2C%0A%20%20%20%20%20%20%20%20prosta%2C%0A%20%20%20%20%20%20%20%20soltype%2C%0A%20%20%20%20%20%20%20%20streamtype%2C%0A%20%20%20%20%20%20%20%20variabletype%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%23%23%23%20Problem%20formulation%0A%0A%20%20%20%20In%20the%20*exact%20planar%20covering%20problem*%20we%20are%20given%20an%20%24n%5Ctimes%20m%24%20rectangle%20(possibly%20with%20holes)%20and%20a%20collection%20of%20shapes%20(bricks).%20We%20ask%20if%20the%20rectangle%20can%20be%20tightly%20covered%20(without%20overlaps)%20with%20the%20given%20shapes.%20For%20example%2C%20can%20a%20%2421%5Ctimes%2021%24%20square%20be%20divided%20into%20%241%5Ctimes%208%24%20and%20%241%5Ctimes%209%24%20rectangles%20(allowing%20rotations)%3F%20Variants%20of%20the%20problem%20involve%20limited%20or%20unlimited%20number%20of%20bricks%2C%20maximizing%20the%20covered%20area%2C%20counting%20the%20coverings%2C%20etc.%20We%20assume%20that%20the%20shapes%20are%20built%20from%20unit%20squares%20and%20only%20consider%20grid-aligned%20coverings.%20See%20for%20instance%20the%20articles%20on%20%5BPolyominos%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPolyomino)%20and%20%5BTetrominos%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FTetromino).%0A%0A%20%20%20%20A%20shape%20is%20defined%20as%20a%20list%20of%20unit%20squares%2C%20or%20rather%20offsets%20with%20respect%20to%20one%20fixed%20square%2C%20for%20example%3A%0A%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(product)%3A%0A%20%20%20%20%23%20The%20shape%20of%20a%20rectangle%20%0A%20%20%20%20def%20shape_rectangle(a%2C%20b)%3A%0A%20%20%20%20%20%20%20%20return%20list(product(range(0%2C%20a)%2C%20range(0%2C%20b)))%0A%0A%20%20%20%20%23%20Shapes%20of%20a%20subset%20of%20Tetris%20blocks%0A%20%20%20%20shapes_tetris%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%5B(0%2C0)%2C%20(0%2C1)%2C%20(0%2C2)%2C%20(-1%2C1)%5D%2C%0A%20%20%20%20%20%20%20%20%5B(0%2C0)%2C%20(0%2C1)%2C%20(0%2C2)%2C%20(1%2C1)%5D%2C%0A%20%20%20%20%20%20%20%20%5B(0%2C0)%2C%20(0%2C1)%2C%20(-1%2C1)%2C%20(-2%2C1)%5D%2C%0A%20%20%20%20%20%20%20%20%5B(0%2C0)%2C%20(0%2C1)%2C%20(1%2C1)%2C%20(1%2C2)%5D%2C%0A%20%20%20%20%20%20%20%20%5B(0%2C0)%2C%20(0%2C1)%2C%20(-1%2C1)%2C%20(-1%2C2)%5D%2C%0A%20%20%20%20%20%20%20%20%5B(0%2C0)%2C%20(1%2C0)%2C%20(1%2C1)%2C%20(1%2C2)%5D%0A%20%20%20%20%5D%0A%20%20%20%20return%20shape_rectangle%2C%20shapes_tetris%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22When%20a%20shape%20is%20actually%20placed%20in%20the%20rectangle%2C%20we%20say%20it%20is%20*anchored*.%20Not%20all%20positions%20are%20suitable%20for%20anchoring%20a%20shape%20%E2%80%94%20it%20may%20not%20stick%20out%20of%20the%20rectangle.%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.function%0Adef%20anchorShape(shp%2C%20_n%2C%20_m%2C%20p%2C%20q%2C%20noncov%3D%5B%5D)%3A%0A%20%20%20%20pts%20%3D%20%5B(p%20%2B%20x%2C%20q%20%2B%20y)%20for%20x%2C%20y%20in%20shp%5D%0A%20%20%20%20if%20all((0%20%3C%3D%20x%20and%20x%20%3C%20_n%20and%20(0%20%3C%3D%20y)%20and%20(y%20%3C%20_m)%20and%20((x%2C%20y)%20not%20in%20noncov)%20for%20x%2C%20y%20in%20pts))%3A%0A%20%20%20%20%20%20%20%20return%20pts%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20return%20None%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%23%23%23%20Integer%20optimization%20model%0A%0A%20%20%20%20We%20can%20model%20the%20covering%20problem%20as%20a%20linear%20problem%20with%20binary%20variables%20in%20a%20standard%20way.%20Let%20%24x_%7Bijk%7D%5Cin%5C%7B0%2C1%5C%7D%24%20be%20a%20binary%20variable%20which%20takes%20value%20%241%24%20if%20a%20brick%20of%20shape%20%24k%24%20is%20anchored%20at%20position%20%24(i%2Cj)%24%20and%20%240%24%20otherwise.%20%0A%0A%20%20%20%20We%20have%20the%20variable%20bounds%20%0A%0A%20%20%20%20%24%24x_%7Bijk%7D%3D0%24%24%20%0A%0A%20%20%20%20whenever%20the%20corresponding%20brick%20placement%20is%20forbidden%20(hangs%20out%20of%20the%20board%20or%20covers%20a%20removed%20hole).%20%0A%0A%20%20%20%20Let%20us%20write%20briefly%20*%24ijk%24%20covers%20%24pq%24*%20if%20a%20brick%20of%20type%20%24k%24%2C%20placed%20at%20%24(i%2Cj)%24%2C%20covers%20the%20square%20%24(p%2Cq)%24.%20Then%20%20in%20the%20exact%20covering%20problem%20we%20have%20the%20constraints%20%0A%0A%20%20%20%20%24%24%5Csum_%7Bi%2Cj%2Ck~%3A~ijk%5Ctextrm%7B%20covers%20%7Dpq%7D%3D1%24%24%0A%0A%20%20%20%20for%20every%20position%20%24(p%2Cq)%24%20on%20the%20board%20which%20is%20available%20(not%20a%20hole).%20In%20the%20maximal%20area%20covering%20we%20need%20the%20inequality%0A%0A%20%20%20%20%24%24%5Csum_%7Bi%2Cj%2Ck~%3A~ijk%5Ctextrm%7B%20covers%20%7Dpq%7D%5Cleq%201.%24%24%0A%0A%20%20%20%20That%20guarantees%20each%20grid%20square%20present%20is%20covered%20exactly%20once%20(resp.%20at%20most%20once).%0A%0A%20%20%20%20To%20express%20the%20problem%20in%20Optimizer%20API%20we%20need%20a%20linear%20indexing%20of%20the%20variables%20%24x_%7Bijk%7D%24%20and%20of%20the%20constraints.%20Assuming%20the%20number%20of%20brick%20shapes%20is%20%24t%24%2C%20we%20can%20do%20for%20example%3A%0A%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%20def%20encodeBrick(n%2C%20_m%2C%20_t%2C%20p%2C%20q%2C%20l)%3A%0A%20%20%20%20%20%20%20%20return%20p%20*%20_m%20*%20_t%20%2B%20q%20*%20_t%20%2B%20l%0A%0A%20%20%20%20def%20encodePos(n%2C%20_m%2C%20p%2C%20q)%3A%0A%20%20%20%20%20%20%20%20return%20p%20*%20_m%20%2B%20q%0A%20%20%20%20return%20encodeBrick%2C%20encodePos%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%20Note%20that%20the%20linear%20constraints%20have%20the%20form%20%0A%0A%20%20%20%20%24%24Ax%3Db%24%24%20%0A%0A%20%20%20%20where%20%24A%24%20is%20the%20adjacency%20matrix%20between%20bricks%20and%20positions%2C%20i.e.%20%24A_%7Bijk%2Cpq%7D%3D1%24%20if%20%24ijk%24%20covers%20%24pq%24.%20The%20matrix%20%24A%24%20has%20%24nm%24%20rows%20and%20%24nmt%24%20columns%2C%20corresponding%20to%20positions%20and%20anchored%20bricks%2C%20respectively.%20That%20makes%20it%20very%20easy%20to%20define%20%24A%24%20column%20by%20column%20by%20listing%20the%20positions%20covered%20by%20a%20given%20anchored%20shape.%0A%0A%20%20%20%20As%20a%20small%20extension%20we%20can%20for%20example%20limit%20the%20number%20of%20times%20each%20shape%20is%20used.%20This%20requires%20constraints%0A%0A%20%20%20%20%24%24%5Csum_%7Bi%2Cj%7Dx_%7Bijk%7D%5Cleq%20r%2C%20%5Ctextrm%7B%20for%20all%20%7D%20k%3D1%2C%5Cldots%2Ct.%24%24%0A%0A%20%20%20%20%23%23%23%20Implementation%0A%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20Env%2C%0A%20%20%20%20attemptCertificate%2C%0A%20%20%20%20boundkey%2C%0A%20%20%20%20dinfitem%2C%0A%20%20%20%20display%2C%0A%20%20%20%20dparam%2C%0A%20%20%20%20encodeBrick%2C%0A%20%20%20%20encodePos%2C%0A%20%20%20%20np%2C%0A%20%20%20%20objsense%2C%0A%20%20%20%20product%2C%0A%20%20%20%20soltype%2C%0A%20%20%20%20streamtype%2C%0A%20%20%20%20variabletype%2C%0A)%3A%0A%20%20%20%20%23%20Build%20a%20model%20for%20n%20x%20m%20rectangle%20with%20brick%20shapes%20T%0A%20%20%20%20%23%20noncov%20is%20the%20list%20of%20fields%20not%20to%20be%20covered%0A%20%20%20%20%23%20exact%20%3D%20True%20-%20%20exact%20covering%0A%20%20%20%20%23%20exact%20%3D%20False%20-%20find%20a%20covering%20of%20maximal%20area%0A%20%20%20%20%23%20rep%20%20%20%3D%20max%20number%20of%20repetitions%20of%20each%20brick%2C%200%20denotes%20no%20limit%0A%20%20%20%20def%20model(_n%2C%20_m%2C%20_t%2C%20_T%2C%20noncov%3D%5B%5D%2C%20exact%3DTrue%2C%20rep%3D0%2C%20timelimit%3D60.0%2C%20logging%3DNone)%3A%0A%20%20%20%20%20%20%20%20numvar%20%3D%20_n%20*%20_m%20*%20_t%0A%20%20%20%20%20%20%20%20numcon%20%3D%20_n%20*%20_m%0A%20%20%20%20%20%20%20%20with%20Env()%20as%20env%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20with%20env.Task(numcon%2C%20numvar)%20as%20task%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.appendvars(numvar)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.appendcons(numcon)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putvartypelist(range(numvar)%2C%20%5Bvariabletype.type_int%5D%20*%20numvar)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putvarboundslice(0%2C%20numvar%2C%20%5Bboundkey.ra%5D%20*%20numvar%2C%20%5B0.0%5D%20*%20numvar%2C%20%5B1.0%5D%20*%20numvar)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20forb%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20p%2C%20q%2C%20k%20in%20product(range(_n)%2C%20range(_m)%2C%20range(_t))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pts%20%3D%20anchorShape(_T%5Bk%5D%2C%20_n%2C%20_m%2C%20p%2C%20q%2C%20noncov)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bCode%20%3D%20encodeBrick(_n%2C%20_m%2C%20_t%2C%20p%2C%20q%2C%20k)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20pts%20is%20None%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%20forb.append(bCode)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%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%20task.putacol(bCode%2C%20%5BencodePos(_n%2C%20_m%2C%20x%2C%20y)%20for%20x%2C%20y%20in%20pts%5D%2C%20%5B1.0%5D%20*%20len(pts))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20key%20%3D%20boundkey.fx%20if%20exact%20else%20boundkey.up%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putconboundslice(0%2C%20numcon%2C%20%5Bkey%5D%20*%20numcon%2C%20%5B1.0%5D%20*%20numcon%2C%20%5B1.0%5D%20*%20numcon)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putconboundlist(%5BencodePos(_n%2C%20_m%2C%20x%2C%20y)%20for%20x%2C%20y%20in%20noncov%5D%2C%20%5Bboundkey.fx%5D%20*%20len(noncov)%2C%20%5B0.0%5D%20*%20len(noncov)%2C%20%5B0.0%5D%20*%20len(noncov))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20areas%20%3D%20%5B(encodeBrick(_n%2C%20_m%2C%20_t%2C%20p%2C%20q%2C%20k)%2C%20len(_T%5Bk%5D))%20for%20p%2C%20q%2C%20k%20in%20product(range(_n)%2C%20range(_m)%2C%20range(_t))%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20subj%2C%20val%20%3D%20zip(*areas)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putclist(subj%2C%20val)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putobjsense(objsense.maximize)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putvarboundlist(forb%2C%20%5Bboundkey.fx%5D%20*%20len(forb)%2C%20%5B0.0%5D%20*%20len(forb)%2C%20%5B0.0%5D%20*%20len(forb))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20rep%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.appendcons(_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putconboundslice(numcon%2C%20numcon%20%2B%20_t%2C%20%5Bboundkey.up%5D%20*%20_t%2C%20%5Brep%5D%20*%20_t%2C%20%5Brep%5D%20*%20_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20range(_t)%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%20task.putarow(numcon%20%2B%20k%2C%20%5BencodeBrick(_n%2C%20_m%2C%20_t%2C%20p%2C%20q%2C%20k)%20for%20p%2C%20q%20in%20product(range(_n)%2C%20range(_m))%5D%2C%20%5B1.0%5D%20*%20(_n%20*%20_m))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20logging%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.set_Stream(streamtype.log%2C%20logging)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.putdouparam(dparam.mio_max_time%2C%20timelimit)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.optimize()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prosta%20%3D%20task.getprosta(soltype.itg)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20prosta%20%3D%3D%20prosta.prim_infeas%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print('No%20covering%5CnLooking%20for%20infeasibility%20certificate%20for%20the%20relaxation')%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20attemptCertificate(_n%2C%20_m%2C%20noncov%2C%20task)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xx%20%3D%20np.zeros(numvar%2C%20dtype%3Dfloat)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20task.getxx(soltype.itg%2C%20xx)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20sol%20%3D%20%5B(p%2C%20q%2C%20k)%20for%20p%2C%20q%2C%20k%20in%20product(range(_n)%2C%20range(_m)%2C%20range(_t))%20if%20xx%5BencodeBrick(_n%2C%20_m%2C%20_t%2C%20p%2C%20q%2C%20k)%5D%20%3E%200.8%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20display(_n%2C%20_m%2C%20sol%2C%20_T%2C%20%5B'blue'%2C%20'yellow'%2C%20'green'%2C%20'red'%2C%20'violet'%2C%20'orange'%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20exact%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%20print('Covered%20area%20%7B0%7D%2C%20best%20bound%20found%20%7B1%7D%2C%20total%20board%20area%20%7B2%7D'.format(int(task.getprimalobj(soltype.itg))%2C%20int(task.getdouinf(dinfitem.mio_obj_bound))%2C%20_n%20*%20_m%20-%20len(noncov)))%0A%20%20%20%20return%20(model%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22The%20code%20above%20models%20and%20solves%20the%20problem.%20It%20is%20easier%20to%20add%20exactly%20%24n%20%5Ctimes%20m%24%20linear%20constraints%20even%20if%20some%20fields%20are%20excluded.%20In%20this%20case%20the%20corresponding%20constraint%20is%20fixed%20to%20zero%20(this%20follows%20anyway%20from%20the%20variable%20bounds%20in%20such%20case).%20Plotting%20the%20result%20is%20done%20with%20the%20function%20shown%20next.%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np%2C%20patches%2C%20plt)%3A%0A%20%20%20%20def%20display(_n%2C%20_m%2C%20sol%2C%20_T%2C%20col)%3A%0A%20%20%20%20%20%20%20%20fig%2C%20ax%20%3D%20plt.subplots(1)%0A%20%20%20%20%20%20%20%20for%20p%2C%20q%2C%20k%20in%20sol%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20x%2C%20y%20in%20anchorShape(_T%5Bk%5D%2C%20_n%2C%20_m%2C%20p%2C%20q)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.add_patch(patches.Rectangle((x%2C%20y)%2C%201%2C%201%2C%20linewidth%3D0%2C%20facecolor%3Dcol%5Bk%5D))%0A%20%20%20%20%20%20%20%20xs%2C%20ys%20%3D%20(np.linspace(0%2C%20_n%2C%20_n%20%2B%201)%2C%20np.linspace(0%2C%20_m%2C%20_m%20%2B%201))%0A%20%20%20%20%20%20%20%20for%20x%20in%20xs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20plt.plot(%5Bx%2C%20x%5D%2C%20%5Bys%5B0%5D%2C%20ys%5B-1%5D%5D%2C%20color%3D'black')%0A%20%20%20%20%20%20%20%20for%20y%20in%20ys%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20plt.plot(%5Bxs%5B0%5D%2C%20xs%5B-1%5D%5D%2C%20%5By%2C%20y%5D%2C%20color%3D'black')%0A%20%20%20%20%20%20%20%20ax.axis(%5B0%2C%20_n%2C%200%2C%20_m%5D)%0A%20%20%20%20%20%20%20%20ax.axis('off')%0A%20%20%20%20%20%20%20%20ax.set_aspect('equal')%0A%20%20%20%20%20%20%20%20plt.show()%0A%20%20%20%20return%20(display%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%23%23%23%20Examples%0A%0A%20%20%20%20From%20the%20introduction%3A%20a%20covering%20of%20the%20%2421%5Ctimes%2021%24%20square%20with%20%241%5Ctimes%208%24%20and%20%241%5Ctimes%209%24%20rectangles.%0A%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(model%2C%20shape_rectangle)%3A%0A%20%20%20%20n%2C%20m%20%3D%20(21%2C%2021)%0A%20%20%20%20T%20%3D%20%5Bshape_rectangle(1%2C%208)%2C%20shape_rectangle(8%2C%201)%2C%20shape_rectangle(1%2C%209)%2C%20shape_rectangle(9%2C%201)%5D%0A%20%20%20%20t%20%3D%20len(T)%0A%20%20%20%20model(n%2C%20m%2C%20t%2C%20T)%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%22Another%20rectangle%20and%20set%20of%20blocks.%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(model%2C%20shape_rectangle)%3A%0A%20%20%20%20_n%2C%20_m%20%3D%20(22%2C%2027)%0A%20%20%20%20_T%20%3D%20%5Bshape_rectangle(8%2C%202)%2C%20shape_rectangle(5%2C%202)%2C%20shape_rectangle(1%2C%207)%5D%0A%20%20%20%20_t%20%3D%20len(_T)%0A%20%20%20%20model(_n%2C%20_m%2C%20_t%2C%20_T)%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%22Next%2C%20we%20consider%20an%20example%20with%20a%20small%20subset%20of%20Tetris%20blocks%20we%20defined%20earlier.%20These%20blocks%20are%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(model%2C%20shapes_tetris)%3A%0A%20%20%20%20model(11%2C%203%2C%20len(shapes_tetris)%2C%20shapes_tetris%2C%20noncov%3D%5B%5D%2C%20exact%3DFalse%2C%20rep%3D1)%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%22We%20now%20ask%20MOSEK%20for%20the%20maximal-area%20covering%20of%20a%20sample%20rectangle%20with%20holes%20by%20our%20Tetris%20blocks.%20You%20may%20want%20to%20enable%20logging%20to%20track%20the%20mixed-integer%20optimizer's%20progress.%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(model%2C%20shapes_tetris%2C%20sys)%3A%0A%20%20%20%20def%20streamprinter(text)%3A%0A%20%20%20%20%20%20%20%20sys.stdout.write(text)%0A%20%20%20%20%20%20%20%20sys.stdout.flush()%0A%20%20%20%20_n%2C%20_m%20%3D%20(11%2C%2017)%0A%20%20%20%20_T%20%3D%20shapes_tetris%0A%20%20%20%20_t%20%3D%20len(_T)%0A%20%20%20%20noncov%20%3D%20%5B(0%2C%200)%2C%20(1%2C%203)%2C%20(9%2C%2013)%2C%20(8%2C%208)%2C%20(7%2C%207)%2C%20(5%2C%205)%2C%20(4%2C%204)%2C%20(3%2C%203)%2C%20(3%2C%201)%2C%20(8%2C%2012)%5D%0A%20%20%20%20model(_n%2C%20_m%2C%20_t%2C%20_T%2C%20noncov%2C%20exact%3DFalse%2C%20rep%3D0%2C%20timelimit%3D20.0%2C%20logging%3DNone)%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%23%23%23%20Combinatorial%20interpretation%20of%20infeasibility%0A%0A%20%20%20%20In%20some%20cases%20the%20integer%20problem%20is%20declared%20as%20infeasible%20already%20because%20its%20linear%20relaxation%20is%20infeasible.%20This%20case%20deserves%20some%20attention%20in%20our%20example.%20The%20linear%20relaxation%20of%20the%20exact%20covering%20problem%20has%20the%20form%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bl%7D%0A%20%20%20%20Ax%20%3D%20b%2C%20%5C%5C%0A%20%20%20%20x%5Cgeq%200%2C%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20where%20%24A%24%20is%20the%20adjacency%20matrix%20discussed%20previously%20and%20%24b%24%20is%20the%20characteristic%20vector%20of%20available%20positions%20on%20the%20board.%0A%0A%20%20%20%20Standard%20duality%20for%20linear%20programing%20and%20Farkas%20lemma%20imply%20that%20a%20%5Bcertificate%20of%20primal%20infeasibility%5D(http%3A%2F%2Fdocs.mosek.com%2Fmodeling-cookbook%2Flinear.html%23infeasibility-in-linear-optimization)%20is%20a%20vector%20%24y%24%20satisfying%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bl%7D%0A%20%20%20%20A%5ETy%20%5Cgeq%200%2C%20%5C%5C%0A%20%20%20%20b%5ETy%20%3C%200.%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20It%20means%20that%20an%20infeasibility%20certificate%20is%20an%20assignment%20of%20a%20real%20number%20to%20every%20position%20on%20the%20board%20so%20that%3A%0A%0A%20%20%20%20*%20every%20possible%20placement%20of%20a%20single%20brick%20covers%20positions%20with%20non-negative%20sum%0A%20%20%20%20*%20the%20sum%20of%20all%20numbers%20on%20the%20board%20is%20negative%0A%0A%20%20%20%20It%20is%20combinatorially%20obvious%20that%20the%20existence%20of%20such%20an%20assignment%20implies%20an%20exact%20covering%20does%20not%20exist%20(unfortunately%20not%20vice-versa%20since%20the%20covering%20problem%20is%20NP-hard%20in%20general%3B%20in%20other%20words%20integer%20infeasibility%20does%20not%20imply%20continuous%20infeasibility).%0A%0A%20%20%20%20It%20is%20very%20easy%20to%20compute%20a%20relaxed%20infeasibility%20certificate%2C%20if%20one%20exists.%20All%20we%20need%20to%20do%20is%20reoptimize%20the%20task%20changing%20all%20integer%20variables%20to%20continuous%20ones%20and%20read%20off%20the%20certificate%20stored%20in%20the%20dual%20variables%20corresponding%20to%20constraints.%0A%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(encodePos%2C%20np%2C%20prosta%2C%20soltype%2C%20variabletype)%3A%0A%20%20%20%20def%20attemptCertificate(_n%2C%20_m%2C%20noncov%2C%20task)%3A%0A%20%20%20%20%20%20%20%20task.putvartypelist(range(task.getnumvar())%2C%20%5Bvariabletype.type_cont%5D%20*%20task.getnumvar())%0A%20%20%20%20%20%20%20%20task.optimize()%0A%20%20%20%20%20%20%20%20if%20task.getprosta(soltype.itr)%20%3D%3D%20prosta.prim_infeas%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20y%20%3D%20np.zeros(_n%20*%20_m%2C%20dtype%3Dfloat)%0A%20%20%20%20%20%20%20%20%20%20%20%20task.getyslice(soltype.itr%2C%200%2C%20_n%20*%20_m%2C%20y)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20p%20in%20range(_n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print('%20'.join(('%20%20%20%20'%20if%20(p%2C%20q)%20in%20noncov%20else%20'%7B%3A%203.1f%7D'.format(y%5BencodePos(_n%2C%20_m%2C%20p%2C%20q)%5D)%20for%20q%20in%20range(_m))))%0A%20%20%20%20%20%20%20%20%20%20%20%20print('Certificate%20with%20sum%20%3D%20%7B0%7D'.format(sum(y)))%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print('No%20certificate%20found')%0A%20%20%20%20return%20(attemptCertificate%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%23%23%23%20Certificate%20example%0A%0A%20%20%20%20Let%20us%20use%20MOSEK%20to%20solve%20the%20following%20%5Bpuzzle%20from%20cut-the-knot%5D(https%3A%2F%2Fwww.cut-the-knot.org%2Fblue%2FDefective12x12Square.shtml).%20Can%20the%20%2412%5Ctimes%2012%24%20square%20with%20three%20corners%20removed%20be%20covered%20using%20%241%5Ctimes%203%24%20and%20%243%5Ctimes%201%24%20tiles%3F%0A%0A%20%20%20%20We%20solve%20this%20problem%20as%20follows%3A%0A%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(model%2C%20shape_rectangle)%3A%0A%20%20%20%20model(_n%20%3D%2012%2C%20_m%20%3D%2012%2C%0A%20%20%20%20%20%20%20%20%20%20_t%20%3D%202%2C%20_T%20%3D%20%5Bshape_rectangle(1%2C3)%2C%20shape_rectangle(3%2C1)%5D%2C%0A%20%20%20%20%20%20%20%20%20%20noncov%20%3D%20%5B(0%2C%200)%2C%20(0%2C%2011)%2C%20(11%2C%200)%5D)%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%22We%20displayed%20the%20infeasibility%20certificate.%20Every%20%241%5Ctimes%203%24%20or%20%243%5Ctimes%201%24%20brick%20covers%20fields%20with%20nonnegative%20sum%20(in%20this%20case%2C%20in%20fact%2C%20exactly%20%240%24)%2C%20while%20the%20sum%20of%20all%20numbers%20is%20%24-1%24.%20That%20proves%20a%20covering%20does%20not%20exist.%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%23%23%23%20Acknowledgement%0A%0A%0A%20%20%20%20Thanks%20to%20Jaroslaw%20Wroblewski%20for%20inspiring%20problems%20and%20discussions%20originating%20from%20his%20newsletter%20%5BTrapez%5D(http%3A%2F%2Fwww.math.uni.wroc.pl%2F~jwr%2Ftrapez%2F).%0A%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(r%22%22%22%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).%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%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
4293e839699c64271fe979fe99d1c7bdc65aa1b1d3d17c06d914ffa5a133d9a4