binquad

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%20Binary%20quadratic%20problems%0A%0A%20%20%20%20We%20discuss%20a%20simple%20solver%20for%20unconstrained%20binary%20quadratic%20problems%2C%20that%20is%20optimization%20problems%20of%20the%20form%0A%0A%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%5Ctextrm%7Bminimize%7D%20%20%26%20%20%20x%5ETQx%2BP%5ETx%2BR%20%5C%5C%0A%20%20%20%20%5Ctextrm%7Bsubject%20to%7D%26%20%20%20x%5Cin%5C%7B0%2C1%5C%7D%5En%2C%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20where%20%24Q%24%20is%20symmetric.%20This%20framework%20can%20encode%20many%20hard%20problems%2C%20such%20as%20max-cut%20or%20maximum%20clique.%20Note%20that%20the%20continuous%20version%20with%20%24x%5Cin%5B0%2C1%5D%5En%24%20need%20not%20be%20convex.%0A%0A%20%20%20%20We%20present%20a%20simple%20SDP-based%20branch-and-bound%20solver.%20This%20implementation%20is%20not%20intended%20to%20compete%20with%20specialized%20tools%20such%20as%20%5BBiqCrunch%5D(http%3A%2F%2Flipn.univ-paris13.fr%2FBiqCrunch%2F)%20or%20other%20sophisticated%20algorithms%20for%20this%20problem.%20The%20aim%20is%20rather%20to%20show%20that%20one%20can%20achieve%20pretty%20decent%20results%20with%20under%20100%20lines%20of%20quickly%20prototyped%20Python%20code%20using%20the%20MOSEK%20Fusion%20API.%0A%0A%20%20%20%20For%20complete%20source%20code%20and%20examples%20see%20the%20folder%20at%20%5BGitHub%5D(https%3A%2F%2Fgithub.com%2FMOSEK%2FTutorials%2Ftree%2Fmaster%2FFusion%2FBinaryQuadratic-SDP).%0A%0A%20%20%20%20%23%20Algorithm%0A%0A%20%20%20%20We%20use%20the%20standard%20semidefinite%20relaxation%20of%20the%20problem%2C%20namely%3A%0A%0A%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%5Ctextrm%7Bminimize%7D%20%20%26%20%20%20%5Csum_%7Bij%7DQ_%7Bij%7DX_%7Bij%7D%20%2B%20%5Csum_i%20P_ix_i%20%2B%20R%20%5C%5C%0A%20%20%20%20%5Ctextrm%7Bsubject%20to%7D%26%20%20%20%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7DX%20%26%20x%5C%5C%20x%5ET%20%26%201%5Cend%7Barray%7D%5Cright%5D%5Csucceq%200%2C%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%20%20%20%5Cmathrm%7Bdiag%7D(X)%20%3D%20x.%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20The%20value%20of%20the%20relaxation%20is%20a%20lower%20bound%20for%20the%20original%20problem%20as%20we%20see%20by%20setting%20%24X%3Dxx%5ET%24%20for%20%24x%5Cin%5C%7B0%2C1%5C%7D%5En%24.%0A%0A%20%20%20%20The%20algorithm%20maintains%20a%20lower%20bound%20%60%60lb%60%60%2C%20upper%20bound%20%60%60ub%60%60%20(objective%20value%20of%20the%20best%20integer%20solution%20found)%20and%20a%20queue%20of%20active%20nodes.%20We%20follow%20these%20rules%3A%0A%0A%20%20%20%20*%20In%20each%20iteration%20we%20pick%20the%20node%20with%20smallest%20objective%20value%20of%20the%20relaxation.%0A%20%20%20%20*%20Each%20time%20a%20relaxation%20is%20solved%20we%20round%20the%20solution%20to%20nearest%20integers%20and%20try%20to%20use%20the%20result%20to%20improve%20the%20upper%20bound.%0A%20%20%20%20*%20We%20branch%20on%20the%20variable%20whose%20value%20in%20the%20relaxation%20is%20closest%20to%20%24%5Cfrac12%24.%20Both%20child%20nodes%2C%20obtained%20by%20fixing%20that%20variable%20to%20%240%24%20or%20%241%24%2C%20are%20smaller%20instances%20of%20the%20same%20problem%20with%20easy%20to%20compute%20%24Q'%2CP'%2CR'%24.%0A%0A%20%20%20%20The%20main%20node-processing%20loop%20follows%20below.%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_(heapq%2C%20np)%3A%0A%20%20%20%20%23%20The%20node-processing%20loop%0A%20%20%20%20def%20solveBB(self)%3A%0A%20%20%20%20%20%20%20%20while%20self.active%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Pop%20the%20node%20with%20minimum%20objective%20from%20the%20queue%0A%20%20%20%20%20%20%20%20%20%20%20%20obj%2C%20_%2C%20Q%2C%20P%2C%20R%2C%20curr%2C%20idxmap%2C%20pivot%20%3D%20heapq.heappop(self.active)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lb%20%3D%20obj%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Optimality%20is%20proved%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20self.lb%20%3E%3D%20self.ub%20-%20self.gaptol%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.active%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.stats()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(P)%20%3C%3D%201%3A%20continue%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20pidx%20%3D%20idxmap%5Bpivot%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Construct%20and%20solve%20relaxations%20of%20two%20child%20nodes%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20where%20the%20pivot%20variable%20is%20assigned%200%20or%201%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20val%20in%20%5B0%2C%201%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idxmap0%20%20%20%20%20%3D%20np.delete(idxmap%2C%20pivot)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20curr0%20%20%20%20%20%20%20%3D%20np.copy(curr)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20curr0%5Bpidx%5D%20%3D%20val%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20QT%20%3D%20np.delete(Q%2C%20pivot%2C%20axis%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Q0%20%3D%20np.delete(QT%2C%20pivot%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20QZ%20%3D%20QT%5B%3A%2Cpivot%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20PT%20%3D%20np.delete(P%2C%20pivot)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20P0%20%3D%20PT%20%2B%202*val*QZ%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20R0%20%3D%20val*Q%5Bpivot%2Cpivot%5D%20%2B%20val*P%5Bpivot%5D%20%2B%20R%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20obj0%2C%20pivot0%20%3D%20self.solveRelaxation(Q0%2C%20P0%2C%20R0%2C%20curr0%2C%20idxmap0)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20heapq.heappush(self.active%2C%20(obj0%2C%20self.relSolved%2C%20Q0%2C%20P0%2C%20R0%2C%20curr0%2C%20idxmap0%2C%20pivot0))%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%20methods%20which%20solve%20the%20relaxation%2C%20find%20the%20pivot%20(branching)%20index%20and%20update%20the%20best%20solution%20are%20straightforward.%20We%20demonstrate%20only%20the%20fragment%20which%20defines%20the%20semidefinite%20relaxation%20in%20Fusion%20API%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Domain%2C%20Expr%2C%20Model%2C%20ObjectiveSense)%3A%0A%20%20%20%20%23%20SDP%20relaxation%20%0A%20%20%20%20%23%20min%20QX%20%2B%20Px%20%2B%20R%0A%20%20%20%20%23%20st%20%20Z%20%3D%20%5BX%2C%20x%3B%20x%5ET%2C%201%5D%20%3E%3E%200%0A%20%20%20%20def%20fusionSDP(Q%2C%20P%2C%20R)%3A%0A%20%20%20%20%20%20%20%20n%20%3D%20len(P)%0A%20%20%20%20%20%20%20%20M%20%3D%20Model(%22fusionSDP%22)%0A%20%20%20%20%20%20%20%20Z%20%3D%20M.variable(%22Z%22%2C%20Domain.inPSDCone(n%2B1))%0A%20%20%20%20%20%20%20%20X%20%3D%20Z%5B0%3An%2C0%3An%5D%0A%20%20%20%20%20%20%20%20x%20%3D%20Z%5B0%3An%2Cn%5D%0A%20%20%20%20%20%20%20%20M.constraint(X.diag()%20%3D%3D%20x)%0A%20%20%20%20%20%20%20%20M.constraint(Z%5Bn%2Cn%5D%20%3D%3D%201)%0A%0A%20%20%20%20%20%20%20%20M.objective(ObjectiveSense.Minimize%2C%20Expr.constTerm(R)%20%2B%20Expr.dot(P%2Cx)%20%2B%20Expr.dot(Q%2CX))%0A%0A%20%20%20%20%20%20%20%20return%20M%2C%20x%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%20solver%20is%20straightforward%20to%20use.%20It%20suffices%20to%20write%3A%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%60%60%60%0A%20%20%20%20solver%20%3D%20BB(Q%2C%20P%2C%20R)%0A%20%20%20%20solver.solve()%0A%20%20%20%20solver.summary()%0A%20%20%20%20%60%60%60%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%60%60%60%0A%20%20%20%20REL_SOLVED%20ACTIVE_NDS%20%20%20%20%20%20%20OBJ_BOUND%20%20%20%20%20%20%20%20BEST_OBJ%0A%20%20%20%20%20%20%20%20%20%20%20%20%201%20%20%20%20%20%20%20%20%20%200%20%20-10000000000.0%20%20-34.1829220672%0A%20%20%20%20%20%20%20%20%20%20%20%20%201%20%20%20%20%20%20%20%20%20%200%20%20-40.9578610377%20%20-34.1829220672%0A%20%20%20%20%20%20%20%20%20%20%20%20%202%20%20%20%20%20%20%20%20%20%200%20%20-40.9578610377%20%20-34.5354934947%0A%20%20%20%20%20%20%20%20%20%20%20%20%203%20%20%20%20%20%20%20%20%20%201%20%20-40.0967961795%20%20-34.5354934947%0A%20%20%20%20%20%20%20%20%20%20%20%20%205%20%20%20%20%20%20%20%20%20%202%20%20-40.0967961795%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%20%205%20%20%20%20%20%20%20%20%20%202%20%20-39.9359433001%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%20%207%20%20%20%20%20%20%20%20%20%203%20%20-38.9245605048%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%20%209%20%20%20%20%20%20%20%20%20%204%20%20-38.4153688863%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%2011%20%20%20%20%20%20%20%20%20%205%20%20-38.1908232037%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%2013%20%20%20%20%20%20%20%20%20%206%20%20-38.1309765476%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%2015%20%20%20%20%20%20%20%20%20%207%20%20-37.9917627647%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%2017%20%20%20%20%20%20%20%20%20%208%20%20-37.8758057302%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%2019%20%20%20%20%20%20%20%20%20%209%20%20-37.6906063328%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%2021%20%20%20%20%20%20%20%20%2010%20%20-37.6747901176%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%2023%20%20%20%20%20%20%20%20%2011%20%20-37.6613714044%20%20-37.6612921792%0A%20%20%20%20%20%20%20%20%20%20%20%2025%20%20%20%20%20%20%20%20%20%200%20%20-37.6612921492%20%20-37.6612921792%0A%20%20%20%20val%20%3D%20-37.6612921792%0A%20%20%20%20sol%20%3D%20%5B0%200%201%200%201%201%200%201%200%201%200%201%201%201%201%200%200%201%200%201%201%200%201%200%201%200%200%200%200%200%5D%0A%20%20%20%20relaxations%20%20%20%3D%2025%0A%20%20%20%20intpntIter%20%20%20%20%3D%20243%0A%20%20%20%20optimizerTime%20%3D%200.194850206375%0A%20%20%20%20%60%60%60%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%20Example%201.%20Random%20data%0A%0A%20%20%20%20We%20consider%20a%20random%20problem%0A%0A%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%5Cmathrm%7Bminimize%7D_%7Bx%5Cin%5C%7B0%2C1%5C%7D%5En%7D%5C%20x%5ETQx%0A%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20where%20%24Q_%7Bi%2Cj%7D%5Csim%20%5Cmathrm%7BNormal%7D(0%2C1)%24%20for%20%24i%5Cgeq%20j%24.%20We%20generate%20instances%20with%20%2430%5Cleq%20n%5Cleq%20100%24.%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%20_src%20%3D%20%22https%3A%2F%2Fraw.githubusercontent.com%2FMOSEK%2FTutorials%2Fmaster%2Fbinary-quadratic%2Fstats%2Frandom.png%22%0A%0A%20%20%20%20mo.image(src%3D_src%2C%20rounded%3DTrue)%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%22Horizontal%20scale%3A%20%24n%24.%20Each%20dot%20corresponds%20to%20an%20instance.%20Left%3A%20number%20of%20relaxations%20solved.%20Right%3A%20total%20time%20spent%20in%20the%20MOSEK%20optimizer%20(sec.).%20Log%20scale.%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%20Example%202%3A%20BiqMac%0A%0A%20%20%20%20We%20next%20consider%20problems%20of%20the%20same%20form%20from%20the%20library%20%5BBiqMac%5D(http%3A%2F%2Fbiqmac.aau.at%2Fbiqmaclib.html)%20of%20binary%20quadratic%20problems.%20We%20take%20all%20instances%20with%20%24n%5Cleq%20100%24.%20Since%20all%20the%20%24Q%24%20matrices%20in%20BiqMac%20are%20integral%2C%20we%20can%20use%20a%20stronger%20termination%20criterion%3A%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%60%60%60%0A%20%20%20%20if%20np.ceil(self.lb)%20%3E%3D%20self.ub%3A%0A%20%20%20%20%60%60%60%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%20_src%20%3D%20%22https%3A%2F%2Fraw.githubusercontent.com%2FMOSEK%2FTutorials%2Fmaster%2Fbinary-quadratic%2Fstats%2Fbiq.png%22%0A%0A%20%20%20%20mo.image(src%3D_src%2C%20rounded%3DTrue)%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%22Horizontal%20scale%3A%20%24n%24.%20Each%20dot%20corresponds%20to%20an%20instance.%20Left%3A%20number%20of%20relaxations%20solved.%20Right%3A%20total%20time%20spent%20in%20the%20MOSEK%20optimizer%20(sec.).%20Log%20scale.%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%20Example%203%3A%20Binary%20least%20squares%0A%0A%20%20%20%20Binary%20least%20squares%20is%20the%20problem%0A%0A%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%5Cmathrm%7Bminimize%7D_%7Bx%5Cin%5C%7B0%2C1%5C%7D%5En%7D%5C%20%5C%7CAx-b%5C%7C_2%5E2%20%5Cquad%20(%3Dx%5ET(A%5ETA)x-(2A%5ETb)%5ETx%2Bb%5ETb)%0A%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20where%20%24A%5Cin%5Cmathbb%7BR%7D%5E%7Bm%5Ctimes%20n%7D%2C%20b%5Cin%20%5Cmathbb%7BR%7D%5Em%24.%20This%20is%20a%20mixed-integer%20SOCP%2C%20so%20we%20can%20compare%20our%20solver%20with%20the%20solutions%20obtained%20directly%20with%20MOSEK.%20As%20suggested%20in%20%5BPark%2C%20Boyd%202017%5D(https%3A%2F%2Fweb.stanford.edu%2F~boyd%2Fpapers%2Fpdf%2Fint_least_squares.pdf)%20we%20generate%20reasonably%20hard%20random%20data%20by%20taking%0A%0A%20%20%20%20%5Cbegin%7Bequation%7D%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bl%7D%0A%20%20%20%20A%5Cin%5Cmathbb%7BR%7D%5E%7Bm%5Ctimes%20n%7D%2C%5Cquad%20A_%7Bi%2Cj%7D%5Csim%20%5Cmathrm%7BNormal%7D(0%2C1)%5C%5C%0A%20%20%20%20b%3DAc%2C%5C%20c%5Cin%5Cmathbb%7BR%7D%5En%2C%5C%20c_i%5Csim%5Cmathrm%7BUniform%7D(0%2C1)%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5Cend%7Bequation%7D%0A%0A%20%20%20%20For%20this%20test%20we%20fix%20%24n%3D50%24%20and%20vary%20%2440%5Cleq%20m%5Cleq%20150%24.%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%20_src%20%3D%20%22https%3A%2F%2Fraw.githubusercontent.com%2FMOSEK%2FTutorials%2Fmaster%2Fbinary-quadratic%2Fstats%2Fbls.png%22%0A%0A%20%20%20%20mo.image(src%3D_src%2C%20rounded%3DTrue)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22Horizontal%20scale%3A%20%24m%24.%20Each%20dot%20corresponds%20to%20an%20instance.%20Blue%3A%20this%20algorithm.%20Red%3A%20mixed-integer%20SOCP%20in%20MOSEK.%20Left%3A%20number%20of%20relaxations%20solved.%20Right%3A%20total%20time%20spent%20in%20the%20MOSEK%20optimizer%20(single-thread%2C%20sec.).%20Log%20scale.%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%23%20Small%20executable%20example%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20branchbound%0A%20%20%20%20from%20branchbound%20import%20BB%20%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20n%3D25%0A%20%20%20%20Q1%20%3D%20np.random.normal(0.0%2C%201.0%2C%20(n%2Cn))%0A%20%20%20%20solver%20%3D%20BB((Q1%2BQ1.transpose())%2F2%2C%20np.random.uniform(-1.0%2C%203.0%2C%20n)%2C%200.0)%0A%20%20%20%20solver.solve()%0A%20%20%20%20solver.summary()%0A%20%20%20%20return%20(np%2C)%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