This is a static, read-only snapshot — sliders and other controls will not respond.
Back to notebook list
·
Run it yourself
%23%20%2F%2F%2F%20script%0A%23%20%5Btool.marimo.opengraph%5D%0A%23%20title%20%3D%20%22Project%20Assignment%22%0A%23%20description%20%3D%20%22Binary%20Assignment%20Model%22%0A%23%20image%20%3D%20%22__marimo__%2Fthumbnail-assignment.svg%22%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20xpress%20as%20xp%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20pandas%20as%20pd%0A%0A%20%20%20%20return%20mo%2C%20np%2C%20pd%2C%20plt%2C%20xp%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%20**Project%20Assignment%20Problem**%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%20One-to-one%20assignment%20of%20%24n%24%20persons%20to%20%24n%24%20projects%20to%20maximize%20total%20preference.%0A%0A%20%20%20%20%26copy%3B%20Copyright%202025-2026%20Fair%20Isaac%20Corporation.%20The%20use%20of%20this%20example%20is%20subject%20to%20%5Blegal%20and%20license%20requirements%5D(https%3A%2F%2Fgithub.com%2Ffico-xpress%2Fpython-notebooks%23legal-and-license-requirements).%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%20description%20and%20formulation%0A%0A%20%20%20%20There%20are%20%24n%24%20persons%20and%20%24n%24%20projects.%20Each%20person%20%24i%20%5Cin%20%5Cmathcal%7BI%7D%24%20ranks%20every%20project%20%24j%20%5Cin%20%5Cmathcal%7BJ%7D%24%20with%20a%20non-negative%20integer%20preference%20score%20%24p_%7Bi%2Cj%7D%24.%20The%20goal%20is%20to%20find%20a%20one-to-one%20matching%20between%20persons%20and%20projects%20that%20maximizes%20the%20total%20satisfaction%20across%20all%20assignments.%0A%0A%20%20%20%20Let%20%24x_%7Bi%2Cj%7D%24%20be%20the%20set%20of%20**binary%20decision%20variables**%20indicating%20if%20person%20%24i%24%20is%20assigned%20to%20project%20%24j%24%20(%3D1)%2C%20or%20not%20(%3D0).%20The%20objective%20function%20aims%20to%20maximize%20the%20total%20satisfaction%3A%0A%0A%20%20%20%20%24%24%5Cmax%20%5Csum_%7Bi%5Cin%20%5Cmathcal%7BI%7D%7D%5Csum_%7Bj%5Cin%20%5Cmathcal%7BJ%7D%7D%20p_%7Bi%2Cj%7D%5C%2Cx_%7Bi%2Cj%7D.%24%24%0A%0A%20%20%20%20Subject%20to%20the%20following%20constraints%3A%0A%0A%20%20%20%20*%20One%20project%20per%20person%3A%0A%20%20%20%20%24%24%5Csum_%7Bj%5Cin%20%5Cmathcal%7BJ%7D%7D%20x_%7Bi%2Cj%7D%20%3D%201%2C%20%5Cquad%5Cforall%5C%2Ci%5Cin%20%5Cmathcal%7BI%7D.%24%24%0A%0A%20%20%20%20*%20One%20person%20per%20project%3A%0A%20%20%20%20%24%24%5Csum_%7Bi%5Cin%20%5Cmathcal%7BI%7D%7D%20x_%7Bi%2Cj%7D%20%3D%201%2C%20%5Cquad%5Cforall%5C%2Cj%5Cin%20%5Cmathcal%7BJ%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%20%23%23%20Data%20preparation%0A%0A%20%20%20%20We%20first%20define%20the%20preference%20matrix%20%60PREF%60%2C%20where%20each%20entry%20%60PREF%5Bi%2C%20j%5D%60%20captures%20how%20much%20person%20%24i%24%20values%20project%20%24j%24.%20From%20this%20matrix%2C%20we%20infer%20the%20number%20of%20persons%20and%20projects%2C%20and%20establish%20simple%20Python%20ranges%20(%60people%60%20and%20%60projects%60)%20to%20list%20them.%0A%0A%20%20%20%20**You%20can%20adjust%20the%20parameters%20below%20to%20change%20the%20problem%20instance%20and%20re-solve%20the%20model%20automatically.**%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20n_slider%20%3D%20mo.ui.slider(2%2C%208%2C%20value%3D5%2C%20label%3D%22Problem%20size%20n%20(persons%20%3D%20projects%20%3D%20n)%22%2C%20show_value%3DTrue)%0A%20%20%20%20seed_slider%20%3D%20mo.ui.slider(0%2C%2099%2C%20value%3D42%2C%20label%3D%22Random%20seed%20(each%20value%20gives%20a%20different%20instance)%22%2C%20show_value%3DTrue)%0A%20%20%20%20mo.vstack(%5Bn_slider%2C%20seed_slider%5D)%0A%20%20%20%20return%20n_slider%2C%20seed_slider%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20n_slider%2C%20np%2C%20seed_slider)%3A%0A%20%20%20%20n%20%3D%20n_slider.value%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20problem%20size%20(persons%20%3D%20projects)%0A%20%20%20%20rng%20%3D%20np.random.default_rng(seed_slider.value)%20%20%23%20random%20generator%20seeded%20from%20the%20Random%20seed%20control%0A%0A%20%20%20%20%23%20Preference%20matrix%3A%20PREF%5Bi%2C%20j%5D%20is%20how%20much%20person%20i%20values%20project%20j%0A%20%20%20%20PREF%20%3D%20rng.integers(1%2C%209%2C%20size%3D(n%2C%20n))%0A%0A%20%20%20%20people%20%3D%20range(n)%20%20%20%20%20%23%20set%20of%20persons%0A%20%20%20%20projects%20%3D%20range(n)%20%20%20%23%20set%20of%20projects%0A%0A%20%20%20%20mo.show_code()%0A%20%20%20%20return%20PREF%2C%20n%2C%20people%2C%20projects%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20%23%23%20Preference%20matrix%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(PREF%2C%20mo%2C%20n%2C%20pd)%3A%0A%20%20%20%20df_pref%20%3D%20pd.DataFrame(%0A%20%20%20%20%20%20%20%20PREF%2C%0A%20%20%20%20%20%20%20%20index%3D%5Bf%22Person%20%7Bi%2B1%7D%22%20for%20i%20in%20range(n)%5D%2C%0A%20%20%20%20%20%20%20%20columns%3D%5Bf%22Project%20%7Bj%2B1%7D%22%20for%20j%20in%20range(n)%5D%0A%20%20%20%20)%0A%20%20%20%20mo.ui.table(df_pref%2C%20selection%3DNone)%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%20Model%20implementation%0A%0A%20%20%20%20We%20instantiate%20an%20Xpress%20model%20named%20**Assignment**%2C%20and%20create%20the%20set%20of%20binary%20decision%20variables.%20By%20passing%20integer%20arguments%20to%20%5Bp.addVariables()%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.addVariables.html)%2C%20a%20*NumPy*%20array%20of%20variables%20(%60assign%60)%20is%20created.%0A%0A%20%20%20%20The%20objective%20and%20constraints%20are%20then%20created%20and%20added%20to%20the%20problem%20by%20passing%20the%20corresponding%20expressions%2C%20using%20list%20comprehension%2C%20to%20%5Bp.setObjective()%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.setObjective.html)%20and%20%5Bp.addConstraint()%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.addConstraint.html)%2C%20respectively.%0A%0A%20%20%20%20After%20building%20the%20model%2C%20we%20turn%20off%20solver%20logging%20using%20the%20%60OUTPUTLOG%60%20control%20and%20call%20%5Bp.optimize()%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.optimize.html)%20to%20solve%20the%20problem%2C%20then%20extract%20and%20display%20the%20total%20satisfaction%20as%20well%20as%20each%20individual%20assignment.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(PREF%2C%20mo%2C%20n%2C%20people%2C%20projects%2C%20xp)%3A%0A%20%20%20%20%23%20Create%20a%20problem%20instance%20and%20the%20binary%20assignment%20variables%0A%20%20%20%20p%20%3D%20xp.problem(name%3D'Assignment')%0A%20%20%20%20assign%20%3D%20p.addVariables(n%2C%20n%2C%20vartype%3Dxp.binary%2C%20name%3D'x')%0A%0A%20%20%20%20%23%20Objective%3A%20maximize%20total%20preference%20across%20all%20assignments%0A%20%20%20%20p.setObjective(%0A%20%20%20%20%20%20%20%20xp.Sum(PREF%5Bi%2C%20j%5D%20*%20assign%5Bi%2C%20j%5D%20for%20i%20in%20people%20for%20j%20in%20projects)%2C%0A%20%20%20%20%20%20%20%20sense%3Dxp.ObjSense.MAXIMIZE%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20One%20project%20per%20person%2C%20and%20one%20person%20per%20project%0A%20%20%20%20p.addConstraint(xp.Sum(assign%5Bi%2C%20j%5D%20for%20j%20in%20projects)%20%3D%3D%201%20for%20i%20in%20people)%0A%20%20%20%20p.addConstraint(xp.Sum(assign%5Bi%2C%20j%5D%20for%20i%20in%20people)%20%3D%3D%201%20for%20j%20in%20projects)%0A%0A%20%20%20%20%23%20Solve%20the%20problem%0A%20%20%20%20p.controls.outputlog%20%3D%200%20%20%23%20Turn%20off%20solver%20logging%20for%20cleaner%20output%0A%20%20%20%20p.optimize()%0A%0A%20%20%20%20%23%20Get%20the%20solution%0A%20%20%20%20sol%20%3D%20p.getSolution(assign)%0A%20%20%20%20total_satisfaction%20%3D%20p.attributes.objval%0A%20%20%20%20mo.show_code()%0A%20%20%20%20return%20sol%2C%20total_satisfaction%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20np%2C%20people%2C%20sol%2C%20total_satisfaction)%3A%0A%20%20%20%20rows%20%3D%20%5B%7B%22Person%22%3A%20f%22Person%20%7Bi%2B1%7D%22%2C%20%22Assigned%20to%22%3A%20f%22Project%20%7Bint(np.argmax(sol%5Bi%5D))%2B1%7D%22%7D%20for%20i%20in%20people%5D%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20mo.md(f%22**Total%20satisfaction%20score%3A%20%7Bint(total_satisfaction)%7D**%22)%2C%0A%20%20%20%20%20%20%20%20mo.ui.table(rows%2C%20selection%3DNone)%2C%0A%20%20%20%20%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%22%0A%20%20%20%20%23%23%20Visualization%0A%0A%20%20%20%20After%20running%20the%20code%20cell%20below%2C%20we%20can%20visualize%20the%20assignment%20as%20a%20bipartite%20graph%20with%20persons%20on%20the%20left%2C%20projects%20on%20the%20right%2C%20and%20lines%20whose%20**thickness%20reflects%20preference%20connecting%20each%20matched%20pair**%20connecting%20both%20sides.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(PREF%2C%20n%2C%20np%2C%20people%2C%20plt%2C%20projects%2C%20sol)%3A%0A%20%20%20%20fig%2C%20ax%20%3D%20plt.subplots(figsize%3D(6%2C%20max(4%2C%20n)))%0A%20%20%20%20left_x%2C%20right_x%20%3D%200%2C%202%0A%20%20%20%20y%20%3D%20np.arange(1%2C%20n%20%2B%201)%0A%0A%20%20%20%20%23%20Plot%20the%20persons%20(left)%20and%20projects%20(right)%20as%20two%20columns%20of%20points%0A%20%20%20%20ax.scatter(%5Bleft_x%5D%20*%20n%2C%20y%2C%20s%3D100%2C%20zorder%3D5%2C%20label%3D'Persons')%0A%20%20%20%20ax.scatter(%5Bright_x%5D%20*%20n%2C%20y%2C%20s%3D100%2C%20zorder%3D5%2C%20label%3D'Projects')%0A%0A%20%20%20%20%23%20Label%20each%20point%0A%20%20%20%20for%20i%20in%20people%3A%0A%20%20%20%20%20%20%20%20ax.text(left_x%20-%200.1%2C%20i%20%2B%201%2C%20f%22Person%20%7Bi%2B1%7D%22%2C%20ha%3D'right'%2C%20va%3D'center')%0A%20%20%20%20for%20j%20in%20projects%3A%0A%20%20%20%20%20%20%20%20ax.text(right_x%20%2B%200.1%2C%20j%20%2B%201%2C%20f%22Project%20%7Bj%2B1%7D%22%2C%20ha%3D'left'%2C%20va%3D'center')%0A%0A%20%20%20%20%23%20Draw%20a%20line%20for%20each%20assigned%20pair%2C%20with%20thickness%20proportional%20to%20preference%0A%20%20%20%20for%20i%20in%20people%3A%0A%20%20%20%20%20%20%20%20j%20%3D%20int(np.argmax(sol%5Bi%5D))%0A%20%20%20%20%20%20%20%20ax.plot(%5Bleft_x%2C%20right_x%5D%2C%20%5Bi%20%2B%201%2C%20j%20%2B%201%5D%2C%20linewidth%3DPREF%5Bi%2C%20j%5D)%0A%0A%20%20%20%20ax.axis('off')%0A%20%20%20%20ax.set_title('Assignment%20(line%20thickness%20%3D%20preference%20score)')%0A%20%20%20%20ax.legend(loc%3D'upper%20center')%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20fig%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
f6dfcccbdf9e5d60e217e0773a5e70cb