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%20%23%20Irreducible%20Infeasible%20Set%20(IIS)%0A%0A%20%20%20%20When%20a%20large%20optimization%20problem%20is%20infeasible%2C%20it%20is%20very%20common%20that%20infeasibility%20can%20be%20localized%20to%20a%20small%20subset%20of%20mutually%20contradicting%20constraints.%20Locating%20such%20a%20small%20set%20can%20help%20better%20understand%20and%2C%20if%20needed%2C%20correct%20the%20infeasibility%20issue.%0A%0A%20%20%20%20An%20*Irreducible%20Infeasible%20Subset*%20(IIS)%20is%2C%20by%20definition%2C%20an%20infeasible%20set%20of%20constraints%20such%20that%20all%20its%20proper%20subset%20are%20feasible.%20It%20is%20therefore%20a%20minimal%20witness%20of%20infeasibility.%20Every%20infeasible%20problem%20has%20one%20or%20more%20IIS%2C%20which%20may%20be%20disjoint%20or%20overlapping%20and%20can%20be%20of%20different%20sizes.%0A%0A%20%20%20%20In%20this%20notebook%20we%20implement%20a%20standard%20method%20of%20locating%20an%20IIS%20for%20linear%20programs%20(LPs)%2C%20namely%20a%20*Deletion%20Filter*.%20(see%20%5BFeasibility%20and%20Infeasibility%20in%20Optimization%5D(https%3A%2F%2Flink.springer.com%2Fbook%2F10.1007%2F978-0-387-74932-7)).%20This%20algorithm%20is%20as%20follows%0A%0A%20%20%20%20-%20Initialize%20%24S%24%20to%20be%20the%20set%20of%20all%20constraints.%0A%20%20%20%20-%20Iterate%20over%20all%20constraints%20and%20temporarily%20remove%20each%20from%20%24S%24%3A%0A%20%20%20%20%20%20%20%20-%20If%20the%20problem%20is%20still%20infeasible%2C%20then%20permanently%20remove%20this%20constraint%20from%20%24S%24.%0A%20%20%20%20%20%20%20%20-%20If%20the%20problem%20becomes%20feasible%2C%20then%20put%20the%20constraint%20back%20to%20%24S%24.%0A%20%20%20%20-%20After%20iterating%20through%20all%20constraints%20return%20%24S%24%20as%20the%20IIS.%0A%0A%20%20%20%20As%20we%20can%20see%20the%20algorithm%20will%20solve%20as%20many%20intermediate%20problems%20as%20there%20are%20constraints.%20If%20the%20IIS%20is%20small%2C%20as%20it%20often%20happens%2C%20then%20the%20intermediate%20problems%20will%20quickly%20shrink%20in%20size.%0A%0A%20%20%20%20There%20are%20many%20implementation%20details%20which%20we%20discuss%20later%2C%20together%20with%20the%20code.%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%23%23%20Implementation%20with%20MOSEK%20%23%23%0A%0A%20%20%20%20There%20are%20many%20MOSEK-specific%20implementation%20details%20which%20we%20now%20outline.%0A%0A%20%20%20%20-%20We%20work%20with%20the%20Optimizer%20API%20for%20Python%20and%20objects%20of%20class%20%60%60mosek.Task%60%60.%20%0A%20%20%20%20-%20Instead%20of%20creating%20a%20new%20task%20for%20each%20iteration%20of%20the%20algorithm%20we%20re-use%20the%20same%20task%20object.%20%0A%20%20%20%20-%20Instead%20of%20removing%20constraints%20from%20%24S%24%20we%20make%20them%20unbounded%20by%20setting%20their%20%60%60boundkey%60%60%20to%20be%20open%20in%20the%20direction%20we%20are%20testing%20thus%20*effectively%20removing*%20the%20bound.%20When%20a%20constraint%20is%20supposed%20to%20return%20to%20%24S%24%20we%20just%20restore%20the%20original%20bound.%0A%20%20%20%20-%20We%20initialize%20%24S%24%20with%20all%20the%20effective%20bounds%20in%20the%20problem%3A%20variable%20upper%2Flower%20bounds%20and%20constraint%20upper%2Flower%20bounds.%20A%20fixed%20or%20ranged%20bound%20is%20treated%20as%20two%20bounds%20(upper%20and%20lower)%20so%20each%20of%20them%20can%20participate%20in%20the%20IIS%20independently.%20%0A%20%20%20%20-%20We%20use%20the%20simplex%20solver%20to%20allow%20efficient%20hot-starts%20since%20we%20will%20be%20solving%20many%20similar%20linear%20problems%20sequentially.%0A%20%20%20%20-%20We%20allow%20infeasible%20linear%20problems%20and%20mixed-integer%20linear%20problems%20whose%20root%20relaxation%20is%20infeasible.%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.fusion%20import%20Model%2C%20Domain%2C%20Expr%2C%20ObjectiveSense%2C%20Matrix%2C%20Var%2C%20SolutionStatus%0A%20%20%20%20from%20mosek%20import%20Task%2C%20iparam%2C%20optimizertype%2C%20miomode%2C%20soltype%2C%20prosta%2C%20boundkey%0A%0A%20%20%20%20import%20sys%2C%20random%0A%0A%20%20%20%20%23%20Functions%20to%20inspect%20and%20transform%20bounds%0A%20%20%20%20hasup%20%3D%20lambda%20bk%3A%20bk%20in%20%5Bboundkey.up%2C%20boundkey.ra%2C%20boundkey.fx%5D%0A%20%20%20%20haslo%20%3D%20lambda%20bk%3A%20bk%20in%20%5Bboundkey.lo%2C%20boundkey.ra%2C%20boundkey.fx%5D%0A%20%20%20%20relaxup%20%3D%20lambda%20bk%3A%20boundkey.fr%20if%20bk%20%3D%3D%20boundkey.up%20else%20boundkey.lo%0A%20%20%20%20relaxlo%20%3D%20lambda%20bk%3A%20boundkey.fr%20if%20bk%20%3D%3D%20boundkey.lo%20else%20boundkey.up%0A%0A%20%20%20%20%23%20Prepare%20a%20task%20for%20the%20deletion%20filter%20routine%0A%20%20%20%20def%20prepareTask(task)%3A%0A%20%20%20%20%20%20%20%20%23%20Use%20the%20simplex%20algporithm%20to%20exploit%20hot-start%0A%20%20%20%20%20%20%20%20task.putintparam(iparam.optimizer%2C%20optimizertype.free_simplex)%0A%20%20%20%20%20%20%20%20%23%20Allow%20mixed-integer%20models%20by%20working%20with%20their%20continuous%20relaxation%20instead%0A%20%20%20%20%20%20%20%20task.putintparam(iparam.mio_mode%2C%20miomode.ignored)%0A%20%20%20%20%20%20%20%20%23%20Remove%20objective%0A%20%20%20%20%20%20%20%20task.putclist(range(task.getnumvar())%2C%20%5B0.0%5D*task.getnumvar())%0A%0A%20%20%20%20%23%20Check%20if%20a%20task%20is%20feasible%0A%20%20%20%20def%20feasibilityStatus(task)%3A%0A%20%20%20%20%20%20%20%20task.optimize()%0A%20%20%20%20%20%20%20%20psta%20%3D%20task.getprosta(soltype.bas)%0A%20%20%20%20%20%20%20%20if%20psta%20in%20%5Bprosta.prim_and_dual_feas%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20%20%20%20%20elif%20psta%20in%20%5Bprosta.prim_infeas%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20None%20%23%20Could%20be%20numerical%20issues%0A%0A%20%20%20%20%23%20Runs%20the%20DeletionFilter%20on%20a%20task%2C%20with%20prescribed%20ordering%20of%20constraints%20and%20variables%0A%20%20%20%20%23%20Return%3A%20a%20pair%20(completed%20successfully%20%3F%2C%20IIS)%0A%20%20%20%20def%20deletionFilter(task%2C%20order)%3A%0A%20%20%20%20%20%20%20%20%23%20We%20first%20assume%20that%20the%20IIS%20consists%20of%20everything%0A%20%20%20%20%20%20%20%20iis%20%3D%20list(order)%0A%0A%20%20%20%20%20%20%20%20for%20(idx%2C%20what%2C%20bound)%20in%20order%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20getbound%20%3D%20task.getconbound%20if%20what%20%3D%3D%20'c'%20else%20task.getvarbound%0A%20%20%20%20%20%20%20%20%20%20%20%20putbound%20%3D%20task.putconbound%20if%20what%20%3D%3D%20'c'%20else%20task.putvarbound%0A%20%20%20%20%20%20%20%20%20%20%20%20relaxbound%20%3D%20relaxup%20if%20bound%20%3D%3D%20'u'%20else%20relaxlo%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Inspect%20the%20element%20of%20the%20task%20with%20index%20idx%2C%20either%20variable%20or%20constraint%0A%20%20%20%20%20%20%20%20%20%20%20%20bk%2C%20bl%2C%20bu%20%3D%20getbound(idx)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Remove%20the%20bound%20completely%20(make%20it%20unbounded)%20and%20see%20if%20the%20task%20becomes%20feasible%0A%20%20%20%20%20%20%20%20%20%20%20%20putbound(idx%2C%20relaxbound(bk)%2C%20bl%2C%20bu)%0A%20%20%20%20%20%20%20%20%20%20%20%20feas%20%3D%20feasibilityStatus(task)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20feas%20%3D%3D%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Restore%20the%20constraint%2Fvariable%20back%20to%20its%20bounds%20and%20continue%20trying%20the%20next%20one%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20putbound(idx%2C%20bk%2C%20bl%2C%20bu)%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20feas%20%20%3D%3D%20False%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Task%20is%20still%20infeasible%2C%20this%20constraint%2Fvariable%20will%20be%20ignored%20(leave%20it%20unbounded)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20iis.remove((idx%2C%20what%2C%20bound))%0A%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%23%20None%20-%20there%20were%20numerical%20issues%2C%20give%20up%20and%20return%20the%20current%20list%20as%20IIS%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20False%2C%20iis%0A%0A%20%20%20%20%20%20%20%20return%20True%2C%20iis%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20Task%2C%0A%20%20%20%20%20%20%20%20deletionFilter%2C%0A%20%20%20%20%20%20%20%20feasibilityStatus%2C%0A%20%20%20%20%20%20%20%20haslo%2C%0A%20%20%20%20%20%20%20%20hasup%2C%0A%20%20%20%20%20%20%20%20prepareTask%2C%0A%20%20%20%20%20%20%20%20random%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%20More%20implementation%20details%20%23%23%0A%0A%20%20%20%20Here%20are%20some%20general%20considerations%20when%20implementing%20the%20Deletion%20Filter%20algorithm%2C%20not%20specifically%20related%20to%20MOSEK%3A%0A%0A%20%20%20%20-%20The%20order%20in%20which%20constraints%20are%20tested%20in%20the%20loop%20affects%20the%20resulting%20IIS.%20Here%20we%20always%20use%20a%20random%20order%2C%20but%20one%20could%20fix%20specific%20ordering%20to%20put%20emphasis%20on%20various%20features%20of%20the%20IIS%20(form%20example%20prefer%20variable%20bounds%20to%20constraint%20bounds%20etc.)%0A%20%20%20%20-%20The%20intermediate%20problems%20can%20become%20borderline%20feasible%2Finfeasible%2C%20naturally%20leading%20to%20numerical%20issues.%20If%20that%20happens%20we%20just%20terminate%20and%20return%20the%20current%20%24S%24.%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_(deletionFilter%2C%20feasibilityStatus%2C%20haslo%2C%20hasup%2C%20prepareTask%2C%20random)%3A%0A%20%20%20%20%23%20Computes%20IIS%20for%20a%20problem%0A%20%20%20%20def%20computeIIS(task%2C%20method%3D'random')%3A%0A%20%20%20%20%20%20%20%20%23%20Initially%20solve%20the%20problem%0A%20%20%20%20%20%20%20%20prepareTask(task)%0A%20%20%20%20%20%20%20%20if%20feasibilityStatus(task)%20!%3D%20False%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print(%22The%20task%20is%20not%20infeasible%2C%20nothing%20to%20do%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%2C%20%5B%5D%0A%0A%20%20%20%20%20%20%20%20%23%20Find%20all%20essential%20(not%20free)%20bounds%20in%20the%20problem%0A%20%20%20%20%20%20%20%20%23%20Format%3A%20(index%2C%20constraint%20or%20variable%20%3F%20%2C%20lower%20or%20upper%20bound%20%3F%20)%0A%20%20%20%20%20%20%20%20allItems%20%3D%20%5B(i%2C%20'c'%2C%20'u')%20for%20i%20in%20range(task.getnumcon())%20if%20hasup(task.getconbound(i)%5B0%5D)%5D%20%2B%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B(i%2C%20'c'%2C%20'l')%20for%20i%20in%20range(task.getnumcon())%20if%20haslo(task.getconbound(i)%5B0%5D)%5D%20%2B%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B(j%2C%20'v'%2C%20'u')%20for%20j%20in%20range(task.getnumvar())%20if%20hasup(task.getvarbound(j)%5B0%5D)%5D%20%2B%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5B(j%2C%20'v'%2C%20'l')%20for%20j%20in%20range(task.getnumvar())%20if%20haslo(task.getvarbound(j)%5B0%5D)%5D%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%0A%20%20%20%20%20%20%20%20if%20method%20%3D%3D%20'random'%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20random.shuffle(allItems)%0A%0A%20%20%20%20%20%20%20%20return%20deletionFilter(task%2C%20allItems)%0A%20%20%20%20return%20(computeIIS%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%20Wrapping%20up%20and%20an%20example%20%23%23%0A%0A%20%20%20%20Finally%20we%20put%20together%20all%20the%20ingredients%20and%20find%20an%20IIS%20for%20an%20example%20from%20https%3A%2F%2Fdocs.mosek.com%2Flatest%2Fpythonapi%2Fdebugging-infeas.html%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_(Task%2C%20computeIIS)%3A%0A%20%20%20%20%23%20Print%20a%20text%20representation%20of%20the%20IIS%0A%20%20%20%20def%20printIIS(task%2C%20iis)%3A%0A%20%20%20%20%20%20%20%20sgn%20%3D%20lambda%20x%3A%20'-'%20if%20x%20%3C%200.0%20else%20'%2B'%0A%20%20%20%20%20%20%20%20varname%20%3D%20lambda%20t%2C%20j%3A%20t.getvarname(j)%20if%20t.getvarnamelen(j)%20%3E%200%20else%20f%22x%5B%7Bj%7D%5D%22%0A%20%20%20%20%20%20%20%20conname%20%3D%20lambda%20t%2C%20i%3A%20f%22%7Bt.getconname(i)%7D%3A%20%22%20if%20t.getconnamelen(i)%20%3E%200%20else%20%22%22%0A%20%20%20%20%20%20%20%20btoineq%20%3D%20lambda%20b%2C%20bl%2C%20bu%3A%20f%22%20%3C%3D%20%7Bbu%7D%22%20if%20bound%20%3D%3D%20'u'%20else%20f%22%20%3E%3D%20%7Bbl%7D%22%0A%20%20%20%20%20%20%20%20for%20(idx%2C%20what%2C%20bound)%20in%20iis%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20what%20%3D%3D%20'v'%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bk%2C%20bl%2C%20bu%20%3D%20task.getvarbound(idx)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print(f%22%2B%20%7Bvarname(task%2Cidx)%7D%7Bbtoineq(bound%2C%20bl%2C%20bu)%7D%22)%20%0A%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%20bk%2C%20bl%2C%20bu%20%3D%20task.getconbound(idx)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nz%2C%20sub%2C%20val%20%3D%20task.getarow(idx)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20expr%20%3D%20'%20'.join(f%22%7Bsgn(v)%7D%20%7Babs(v)%7D%20%7Bvarname(task%2Cj)%7D%22%20for%20(j%2Cv)%20in%20zip(list(sub)%2C%20list(val)))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print(f%22%7Bconname(task%2C%20idx)%7D%7Bexpr%7D%7Bbtoineq(bound%2C%20bl%2C%20bu)%7D%22)%20%0A%0A%20%20%20%20def%20IISFromPtf(ptftask)%3A%0A%20%20%20%20%20%20%20%20with%20Task()%20as%20task%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20task.readptfstring(ptftask)%0A%20%20%20%20%20%20%20%20%20%20%20%20success%2C%20iis%20%3D%20computeIIS(task)%20%20%20%20%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20success%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print(f%22IIS%20computation%20completed%20successfully%2C%20size%20%3D%20%7Blen(iis)%7D%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20printIIS(task%2C%20iis)%0A%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%20print(f%22IIS%20computation%20interrupted%20prematurely%20because%20of%20numerical%20issues%2C%20size%20%3D%20%7Blen(iis)%7D%22)%0A%0A%20%20%20%20%23%20Example%3A%0A%20%20%20%20IISFromPtf(%22%22%22Task%0A%20%20%20%20Objective%20obj%0A%20%20%20%20%20%20%20%20Minimize%20%2B%20x11%20%2B%202%20x12%20%2B%205%20x23%20%2B%202%20x24%20%2B%20x31%20%2B%202%20x33%20%2B%20x34%0A%20%20%20%20Constraints%0A%20%20%20%20%20%20%20%20s0%20%5B-inf%3B200%5D%20%2B%20x11%20%2B%20x12%0A%20%20%20%20%20%20%20%20s1%20%5B-inf%3B1000%5D%20%2B%20x23%20%2B%20x24%0A%20%20%20%20%20%20%20%20s2%20%5B-inf%3B1000%5D%20%2B%20x31%20%2B%20x33%20%2B%20x34%0A%20%20%20%20%20%20%20%20d0%20%5B1100%5D%20%2B%20x11%20%2B%20x31%0A%20%20%20%20%20%20%20%20d1%20%5B200%5D%20%2B%20x12%0A%20%20%20%20%20%20%20%20d2%20%5B500%5D%20%2B%20x23%20%2B%20x33%0A%20%20%20%20%20%20%20%20d3%20%5B500%5D%20%2B%20x24%20%2B%20x34%0A%20%20%20%20Variables%0A%20%20%20%20%20%20%20%20x11%20%5B0%3B%2Binf%5D%0A%20%20%20%20%20%20%20%20x12%20%5B0%3B%2Binf%5D%0A%20%20%20%20%20%20%20%20x23%20%5B0%3B%2Binf%5D%0A%20%20%20%20%20%20%20%20x24%20%5B0%3B%2Binf%5D%0A%20%20%20%20%20%20%20%20x31%20%5B0%3B%2Binf%5D%0A%20%20%20%20%20%20%20%20x33%20%5B0%3B%2Binf%5D%0A%20%20%20%20%20%20%20%20x34%20%5B0%3B%2Binf%5D%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%22The%20example%20here%20represents%20a%20supply-demand%20network.%20Infeasibility%20is%20caused%20by%20the%20fact%20that%20stores%201%20and%202%20have%20higher%20joint%20demand%20than%20the%20plants%201%20and%203%20can%20supply.%20The%20IIS%20found%20reflects%20this%20situation.%20(Note%20that%20you%20can%20get%20various%20IIS%20when%20running%20this%20example%3B%20the%20smallest%20and%20also%20most%20straightforward%20one%20has%20size%206).%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!%5BMOSEK%20ApS%5D(https%3A%2F%2Fdocs.mosek.com%2Flatest%2Fpythonapi%2F_images%2Ftransportp.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%20%23%23%20Extensions%20and%20improvements%20%23%23%0A%0A%20%20%20%20The%20source%20code%20of%20this%20Deletion%20Filter%20implementation%20can%20also%20be%20downloaded%20from%20the%20accompanying%20file%20%5Biis_deletion.py%5D(iis_deletion.py).%20It%20is%20a%20very%20simple%2C%20basic%20algorithm%20which%20we%20provide%20as%20a%20proof-of-concept%20example.%20Here%20we%20outline%20possible%20extensions%20one%20could%20try%3A%0A%0A%20%20%20%20-%20Run%20the%20deletion%20filter%20a%20few%20times%2C%20possibly%20in%20a%20multithreaded%20fashion%2C%20and%20take%20the%20smallest%20IIS%20found.%0A%20%20%20%20-%20Start%20not%20from%20the%20full%20set%20of%20constraints%2C%20but%20only%20from%20those%20which%20appear%20in%20the%20Farkas%20infeasibility%20certificate%20(equivalently%20are%20found%20by%20the%20%60%60task.getinfeasiblesubproblem()%60%60%20method.)%20In%20fact%20in%20many%20practical%20cases%20(especially%20due%20to%20modeling%2Fcoding%20errors%20and%20when%20a%20certificate%20is%20found%20in%20presolve)%20the%20certificate%20is%20already%20an%20IIS.%20Note%2C%20however%2C%20that%20this%20restricts%20the%20possible%20IIS%20the%20algorithm%20can%20find%20to%20those%20contained%20in%20a%20particular%20certificate.%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%60MOSEK%20Optimizer%20API%20for%20Python%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%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
60634afa4d01868d5b1716aa5d8352a2880e21845d0b327a94eef2b39e715bfd