import%20marimo%0A%0A__generated_with%20%3D%20%220.11.25%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%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%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20random%0A%20%20%20%20import%20pyscipopt%20as%20scip%0A%20%20%20%20from%20ortools.sat.python%20import%20cp_model%0A%20%20%20%20return%20cp_model%2C%20random%2C%20scip%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%23%201%20%E6%A9%9F%E6%A2%B0%E3%83%AA%E3%83%AA%E3%83%BC%E3%82%B9%E6%99%82%E5%88%BB%E4%BB%98%E3%81%8D%E9%87%8D%E3%81%BF%E4%BB%98%E3%81%8D%E5%AE%8C%E4%BA%86%E6%99%82%E5%88%BB%E5%92%8C%E6%9C%80%E5%B0%8F%E5%8C%96%E5%95%8F%E9%A1%8C%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%20%20%20%20-%20%E6%A9%9F%E6%A2%B0%3A%201%20%E3%81%A4%E3%81%A0%E3%81%91%0A%20%20%20%20%20%20%20%20-%20%E3%82%B8%E3%83%A7%E3%83%96%20%24J%20%3D%20%5C%7B%201%2C%20%5Cdots%2C%20n%20%5C%7D%24%0A%20%20%20%20%20%20%20%20-%20%E5%90%84%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%3A%20%24p_j%20%5C%20(%5Cforall%20j%20%5Cin%20J)%24%0A%20%20%20%20%20%20%20%20-%20%E5%90%84%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E9%87%8D%E8%A6%81%E5%BA%A6%3A%20%24w_j%20%5C%20(%5Cforall%20j%20%5Cin%20J)%24%0A%20%20%20%20%20%20%20%20-%20%E5%90%84%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E3%83%AA%E3%83%AA%E3%83%BC%E3%82%B9%E6%99%82%E5%88%BB%3A%20%24r_j%20%5C%20(%5Cforall%20j%20%5Cin%20J)%24%0A%20%20%20%20%20%20%20%20-%20%E5%90%84%E3%82%B8%E3%83%A7%E3%83%96%E3%81%AE%E5%87%A6%E7%90%86%E5%AE%8C%E4%BA%86%E6%99%82%E5%88%BB%3A%20%24C_j%20%5C%20(%5Cforall%20j%20%5Cin%20J)%24%0A%0A%20%20%20%20%20%20%20%20%24C_j%24%20%E3%81%AE%E9%87%8D%E3%81%BF%E4%BB%98%E3%81%8D%E5%92%8C%E3%82%92%E6%9C%80%E5%B0%8F%E5%8C%96%E3%81%99%E3%82%8B.%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(r%22%22%22%23%23%20%E9%9B%A2%E6%8E%A5%E5%AE%9A%E5%BC%8F%E5%8C%96(Disjunctive%20formulation)%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%20%20%20%20%24M%24%20%E3%82%92%E5%A4%A7%E3%81%8D%E3%81%AA%E5%AE%9A%E6%95%B0%E3%81%A8%E3%81%97%E3%81%A6%0A%0A%20%20%20%20%20%20%20%20%5Cbegin%7Balign*%7D%0A%20%20%20%20%20%20%20%20%26%5Ctext%7Bminimize%7D%20%26%5Csum_%7Bj%3D1%7D%5En%20w_j%20s_j%20%2B%20%5Csum_%7Bj%3D1%7D%5En%20w_j%20p_j%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%5Ctext%7Bs.t.%7D%20%26s_j%20%2B%20p_j%20-%20M%20(1%20-%20x_%7Bjk%7D)%20%26%5Cleq%20s_k%20%5C%20%26(%5Cforall%20j%20%5Cneq%20k)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26x_%7Bjk%7D%20%2B%20x_%7Bkj%7D%20%26%3D%201%20%5C%20%26(%5Cforall%20j%20%3C%20k)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26s_j%20%26%5Cgeq%20r_j%20%5C%20%26(%5Cforall%20j%20%5Cin%20J)%20%5C%5C%0A%20%20%20%20%20%20%20%20%26%20%26x_%7Bjk%7D%20%26%5Cin%20%5C%7B0%2C%201%5C%7D%20%5C%20%26(%5Cforall%20j%20%5Cneq%20k)%0A%20%20%20%20%20%20%20%20%5Cend%7Balign*%7D%0A%0A%20%20%20%20%20%20%20%20-%20%E6%B1%BA%E5%AE%9A%E5%A4%89%E6%95%B0%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24s_j%24%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%AE%E9%96%8B%E5%A7%8B%E6%99%82%E5%88%BB%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%24x_%7Bjk%7D%24%3A%20%E3%82%B8%E3%83%A7%E3%83%96%20%24j%24%20%E3%81%8C%E3%82%B8%E3%83%A7%E3%83%96%20%24k%24%20%E3%81%AB%E5%85%88%E8%A1%8C%E3%81%99%E3%82%8B%E3%81%A8%E3%81%8D%20%241%24%0A%20%20%20%20%20%20%20%20-%20%E8%A3%9C%E8%B6%B3%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20%E7%9B%AE%E7%9A%84%E9%96%A2%E6%95%B0%E3%81%AE%E7%AC%AC%202%20%E9%A0%85%E7%9B%AE%E3%81%AF%E5%AE%9A%E6%95%B0%E3%81%A7%E3%81%82%E3%82%8B%E3%81%9F%E3%82%81%E7%AC%AC%201%20%E9%A0%85%E3%81%A0%E3%81%91%E3%82%92%E6%9C%80%E5%B0%8F%E5%8C%96%E3%81%99%E3%82%8C%E3%81%B0%E3%82%88%E3%81%84%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(r%22%22%22%23%23%20%E5%AE%9F%E8%A3%85%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(random)%3A%0A%20%20%20%20def%20make_data(n)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Data%20generator%20for%20the%20one%20machine%20scheduling%20problem.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%0A%20%20%20%20%20%20%20%20random.seed(0)%0A%20%20%20%20%20%20%20%20p%2C%20r%2C%20d%2C%20w%20%3D%20%7B%7D%2C%20%7B%7D%2C%20%7B%7D%2C%20%7B%7D%0A%0A%20%20%20%20%20%20%20%20J%20%3D%20range(1%2C%20n%20%2B%201)%0A%0A%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20p%5Bj%5D%20%3D%20random.randint(1%2C%204)%0A%20%20%20%20%20%20%20%20%20%20%20%20w%5Bj%5D%20%3D%20random.randint(1%2C%203)%0A%0A%20%20%20%20%20%20%20%20T%20%3D%20sum(p)%0A%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20r%5Bj%5D%20%3D%20random.randint(0%2C%205)%0A%20%20%20%20%20%20%20%20%20%20%20%20d%5Bj%5D%20%3D%20r%5Bj%5D%20%2B%20random.randint(0%2C%205)%0A%0A%20%20%20%20%20%20%20%20return%20J%2C%20p%2C%20r%2C%20d%2C%20w%0A%20%20%20%20return%20(make_data%2C)%0A%0A%0A%40app.cell%0Adef%20_(scip)%3A%0A%20%20%20%20class%20ModelDisjunctiveScip%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20J%2C%20p%2C%20r%2C%20w)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.J%20%3D%20J%0A%20%20%20%20%20%20%20%20%20%20%20%20self.p%20%3D%20p%0A%20%20%20%20%20%20%20%20%20%20%20%20self.r%20%3D%20r%0A%20%20%20%20%20%20%20%20%20%20%20%20self.w%20%3D%20w%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.scip%20%3D%20scip.Model(%22scheduling%3A%20disjunctive%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Big%20M%0A%20%20%20%20%20%20%20%20%20%20%20%20M%20%3D%20max(self.r.values())%20%2B%20sum(self.p.values())%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20start%20time%20variable%2C%20x%5Bj%2Ck%5D%20%3D%201%20if%20job%20j%20precedes%20job%20k%2C%200%20otherwise%0A%20%20%20%20%20%20%20%20%20%20%20%20self.x%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20self.s%20%3D%20%7B%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20ub%20%3D%20sum(self.p%5Bj%5D%20for%20j%20in%20self.J)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20self.J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.s%5Bj%5D%20%3D%20self.scip.addVar(lb%3Dr%5Bj%5D%2C%20ub%3Dub%2C%20vtype%3D%22C%22%2C%20name%3Df%22s%5B%7Bj%7D%5D%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20self.J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20!%3D%20k%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%20self.x%5Bj%2C%20k%5D%20%3D%20self.scip.addVar(vtype%3D%22B%22%2C%20name%3Df%22x%5B%7Bj%7D%2C%7Bk%7D%5D%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20self.J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20self.J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20!%3D%20k%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%20self.scip.addCons(%0A%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%20self.s%5Bj%5D%20-%20self.s%5Bk%5D%20%2B%20M%20*%20self.x%5Bj%2C%20k%5D%20%3C%3D%20(M%20-%20self.p%5Bj%5D)%2C%20f%22Bound%5B%7Bj%7D%2C%7Bk%7D%5D%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20%3C%20k%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%20self.scip.addCons(self.x%5Bj%2C%20k%5D%20%2B%20self.x%5Bk%2C%20j%5D%20%3D%3D%201%2C%20f%22Disjunctive%5B%7Bj%7D%2C%7Bk%7D%5D%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.scip.setObjective(scip.quicksum(self.w%5B_j%5D%20*%20self.s%5B_j%5D%20for%20_j%20in%20self.J)%2C%20sense%3D%22minimize%22)%0A%0A%20%20%20%20%20%20%20%20def%20solve(self)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.scip.optimize()%0A%0A%20%20%20%20%20%20%20%20def%20get_z(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20self.scip.getObjVal()%20%2B%20sum(%5Bself.w%5B_j%5D%20*%20self.p%5B_j%5D%20for%20_j%20in%20self.J%5D)%0A%0A%20%20%20%20%20%20%20%20def%20get_seq(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5B_j%20for%20(_t%2C%20_j)%20in%20sorted(%5B(int(self.scip.getVal(self.s%5B_j%5D)%20%2B%200.5)%2C%20_j)%20for%20_j%20in%20self.s%5D)%5D%0A%20%20%20%20return%20(ModelDisjunctiveScip%2C)%0A%0A%0A%40app.cell%0Adef%20_(scip)%3A%0A%20%20%20%20class%20_MyInterval%3A%0A%20%20%20%20%20%20%20%20%23%20%5Bstart%2C%20end)%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20scip%3A%20scip.Model%2C%20lb%3A%20int%2C%20ub%3A%20int%2C%20size%3A%20int)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lb%20%3D%20lb%0A%20%20%20%20%20%20%20%20%20%20%20%20self.ub%20%3D%20ub%0A%20%20%20%20%20%20%20%20%20%20%20%20self.size%20%3D%20size%0A%20%20%20%20%20%20%20%20%20%20%20%20self.start%20%3D%20scip.addVar(lb%3Dself.lb%2C%20ub%3Dself.ub%20-%20self.size%2C%20vtype%3D'C')%0A%20%20%20%20%20%20%20%20%20%20%20%20self.end%20%3D%20self.start%20%2B%20self.size%0A%0A%20%20%20%20def%20_my_add_no_overlap(scip%3A%20scip.Model%2C%20jobs%3A%20dict%5Bint%2C%20_MyInterval%5D)%3A%0A%20%20%20%20%20%20%20%20if%20len(jobs)%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20for%20_j1%20in%20jobs.keys()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_j2%20in%20jobs.keys()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_j2%20%3C%3D%20_j1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20big_m%20%3D%20max(jobs%5B_j1%5D.ub%20-%20jobs%5B_j2%5D.lb%2C%20jobs%5B_j2%5D.ub%20-%20jobs%5B_j1%5D.lb)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tmp1%20%3D%20scip.addVar(vtype%3D'B')%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20scip.addCons(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20jobs%5B_j1%5D.end%20%3C%3D%20jobs%5B_j2%5D.start%20%2B%20big_m%20*%20(1%20-%20tmp1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tmp2%20%3D%20scip.addVar(vtype%3D'B')%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20scip.addCons(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20jobs%5B_j2%5D.end%20%3C%3D%20jobs%5B_j1%5D.start%20%2B%20big_m%20*%20(1%20-%20tmp2)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20scip.addCons(tmp1%20%2B%20tmp2%20%3E%3D%201)%0A%0A%20%20%20%20class%20ModelIntervalScip%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20J%2C%20p%2C%20r%2C%20w)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.J%20%3D%20J%0A%20%20%20%20%20%20%20%20%20%20%20%20self.p%20%3D%20p%0A%20%20%20%20%20%20%20%20%20%20%20%20self.r%20%3D%20r%0A%20%20%20%20%20%20%20%20%20%20%20%20self.w%20%3D%20w%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.scip%20%3D%20scip.Model(%22scheduling%3A%20disjunctive%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20ub%20%3D%20sum(p%5B_j%5D%20for%20_j%20in%20J)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.jobs%20%3D%20%7B_j%3A%20_MyInterval(self.scip%2C%20self.r%5B_j%5D%2C%20ub%2C%20self.p%5B_j%5D)%20for%20_j%20in%20self.J%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20_my_add_no_overlap(self.scip%2C%20self.jobs)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.scip.setObjective(scip.quicksum(self.w%5B_j%5D%20*%20self.jobs%5B_j%5D.start%20for%20_j%20in%20self.J)%2C%20sense%3D%22minimize%22)%0A%0A%20%20%20%20%20%20%20%20def%20solve(self)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.scip.optimize()%0A%0A%20%20%20%20%20%20%20%20def%20get_z(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20self.scip.getObjVal()%20%2B%20sum(%5Bself.w%5B_j%5D%20*%20self.p%5B_j%5D%20for%20_j%20in%20self.J%5D)%0A%0A%20%20%20%20%20%20%20%20def%20get_seq(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5B_j%20for%20(_t%2C%20_j)%20in%20sorted(%5B(int(self.scip.getVal(self.jobs%5B_j%5D.start)%20%2B%200.5)%2C%20_j)%20for%20_j%20in%20self.jobs%5D)%5D%0A%20%20%20%20return%20(ModelIntervalScip%2C)%0A%0A%0A%40app.cell%0Adef%20_(cp_model)%3A%0A%20%20%20%20class%20ModelDisjunctiveCpSat%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20J%2C%20p%2C%20r%2C%20w)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.J%20%3D%20J%0A%20%20%20%20%20%20%20%20%20%20%20%20self.p%20%3D%20p%0A%20%20%20%20%20%20%20%20%20%20%20%20self.r%20%3D%20r%0A%20%20%20%20%20%20%20%20%20%20%20%20self.w%20%3D%20w%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.cp%20%3D%20cp_model.CpModel()%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver%20%3D%20cp_model.CpSolver()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Big%20M%0A%20%20%20%20%20%20%20%20%20%20%20%20M%20%3D%20max(r.values())%20%2B%20sum(p.values())%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20start%20time%20variable%2C%20x%5Bj%2Ck%5D%20%3D%201%20if%20job%20j%20precedes%20job%20k%2C%200%20otherwise%0A%20%20%20%20%20%20%20%20%20%20%20%20self.x%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20self.s%20%3D%20%7B%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20ub%20%3D%20sum(p%5Bj%5D%20for%20j%20in%20J)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.s%5Bj%5D%20%3D%20self.cp.new_int_var(lb%3Dr%5Bj%5D%2C%20ub%3Dub%2C%20name%3Df%22s%5B%7Bj%7D%5D%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20!%3D%20k%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%20self.x%5Bj%2C%20k%5D%20%3D%20self.cp.new_bool_var(name%3Df%22x%5B%7Bj%7D%2C%7Bk%7D%5D%22)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20J%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20!%3D%20k%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%20self.cp.add(self.s%5Bj%5D%20-%20self.s%5Bk%5D%20%2B%20M%20*%20self.x%5Bj%2C%20k%5D%20%3C%3D%20(M%20-%20p%5Bj%5D))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20j%20%3C%20k%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%20self.cp.add(self.x%5Bj%2C%20k%5D%20%2B%20self.x%5Bk%2C%20j%5D%20%3D%3D%201)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.cp.minimize(sum(self.w%5Bj%5D%20*%20self.s%5Bj%5D%20for%20j%20in%20J))%0A%0A%20%20%20%20%20%20%20%20def%20solve(self)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver.parameters.log_search_progress%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver.solve(self.cp)%0A%0A%20%20%20%20%20%20%20%20def%20get_z(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20self.solver.objective_value%20%2B%20sum(%5Bself.w%5B_j%5D%20*%20self.p%5B_j%5D%20for%20_j%20in%20self.J%5D)%0A%0A%20%20%20%20%20%20%20%20def%20get_seq(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5B_j%20for%20(_t%2C%20_j)%20in%20sorted(%5B(int(self.solver.value(self.s%5B_j%5D)%20%2B%200.5)%2C%20_j)%20for%20_j%20in%20self.s%5D)%5D%0A%20%20%20%20return%20(ModelDisjunctiveCpSat%2C)%0A%0A%0A%40app.cell%0Adef%20_(cp_model)%3A%0A%20%20%20%20class%20ModelIntervalCpSat%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20J%2C%20p%2C%20r%2C%20w)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.J%20%3D%20J%0A%20%20%20%20%20%20%20%20%20%20%20%20self.p%20%3D%20p%0A%20%20%20%20%20%20%20%20%20%20%20%20self.r%20%3D%20r%0A%20%20%20%20%20%20%20%20%20%20%20%20self.w%20%3D%20w%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.cp%20%3D%20cp_model.CpModel()%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver%20%3D%20cp_model.CpSolver()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20ub%20%3D%20sum(p%5B_j%5D%20for%20_j%20in%20J)%0A%20%20%20%20%20%20%20%20%20%20%20%20s%20%3D%20%7B_j%3A%20self.cp.new_int_var(lb%3Dself.r%5B_j%5D%2C%20ub%3Dub%2C%20name%3Df%22s%5B%7B_j%7D%5D%22)%20for%20_j%20in%20self.J%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20self.jobs%20%3D%20%7B_j%3A%20self.cp.new_fixed_size_interval_var(s%5B_j%5D%2C%20self.p%5B_j%5D%2C%20f%22jobs%5B%7B_j%7D%5D%22)%20for%20_j%20in%20self.J%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20self.cp.add_no_overlap(self.jobs.values())%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.cp.minimize(sum(self.w%5B_j%5D%20*%20self.jobs%5B_j%5D.start_expr()%20for%20_j%20in%20J))%0A%0A%20%20%20%20%20%20%20%20def%20solve(self)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver.parameters.log_search_progress%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20self.solver.solve(self.cp)%0A%0A%20%20%20%20%20%20%20%20def%20get_z(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20self.solver.objective_value%20%2B%20sum(%5Bself.w%5B_j%5D%20*%20self.p%5B_j%5D%20for%20_j%20in%20self.J%5D)%0A%0A%20%20%20%20%20%20%20%20def%20get_seq(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5B_j%20for%20(_t%2C%20_j)%20in%20sorted(%5B(self.solver.value(self.jobs%5B_j%5D.start_expr())%2C%20_j)%20for%20_j%20in%20self.jobs%5D)%5D%0A%20%20%20%20return%20(ModelIntervalCpSat%2C)%0A%0A%0A%40app.cell%0Adef%20_(make_data)%3A%0A%20%20%20%20n%20%3D%2030%0A%20%20%20%20J%2C%20p%2C%20r%2C%20d%2C%20w%20%3D%20make_data(n)%0A%20%20%20%20return%20J%2C%20d%2C%20n%2C%20p%2C%20r%2C%20w%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20run_scip_disj%20%3D%20mo.ui.run_button(label%3D%22Run%22%2C%20full_width%3DTrue)%0A%20%20%20%20run_scip_disj%0A%20%20%20%20return%20(run_scip_disj%2C)%0A%0A%0A%40app.cell%0Adef%20_(J%2C%20ModelDisjunctiveScip%2C%20mo%2C%20p%2C%20r%2C%20run_scip_disj%2C%20w)%3A%0A%20%20%20%20if%20run_scip_disj.value%3A%0A%20%20%20%20%20%20%20%20_model%20%3D%20ModelDisjunctiveScip(J%2C%20p%2C%20r%2C%20w)%0A%20%20%20%20%20%20%20%20with%20mo.redirect_stderr()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_model.solve()%0A%0A%20%20%20%20%20%20%20%20_z%20%3D%20_model.get_z()%0A%20%20%20%20%20%20%20%20_seq%20%3D%20_model.get_seq()%0A%20%20%20%20%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20-%20Opt.value%20by%20Disjunctive%20Formulation%3A%20%7B_z%7D%0A%20%20%20%20%20%20%20%20-%20Solution%3A%20%7B_seq%7D%0A%20%20%20%20%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%20run_scip_interval%20%3D%20mo.ui.run_button(label%3D%22Run%22%2C%20full_width%3DTrue)%0A%20%20%20%20run_scip_interval%0A%20%20%20%20return%20(run_scip_interval%2C)%0A%0A%0A%40app.cell%0Adef%20_(J%2C%20ModelIntervalScip%2C%20mo%2C%20p%2C%20r%2C%20run_scip_interval%2C%20w)%3A%0A%20%20%20%20if%20run_scip_interval.value%3A%0A%20%20%20%20%20%20%20%20_model%20%3D%20ModelIntervalScip(J%2C%20p%2C%20r%2C%20w)%0A%20%20%20%20%20%20%20%20with%20mo.redirect_stderr()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_model.solve()%0A%0A%20%20%20%20%20%20%20%20_z%20%3D%20_model.get_z()%0A%20%20%20%20%20%20%20%20_seq%20%3D%20_model.get_seq()%0A%20%20%20%20%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20-%20Optimal%20value%3A%20%7B_z%7D%0A%20%20%20%20%20%20%20%20-%20Solution%3A%20%7B_seq%7D%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(J%2C%20ModelDisjunctiveCpSat%2C%20mo%2C%20p%2C%20r%2C%20w)%3A%0A%20%20%20%20_model%20%3D%20ModelDisjunctiveCpSat(J%2C%20p%2C%20r%2C%20w)%0A%20%20%20%20with%20mo.redirect_stderr()%3A%0A%20%20%20%20%20%20%20%20_model.solve()%0A%0A%20%20%20%20_z%20%3D%20_model.get_z()%0A%20%20%20%20_seq%20%3D%20_model.get_seq()%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20-%20Opt.value%20by%20Disjunctive%20Formulation%3A%20%7B_z%7D%0A%20%20%20%20-%20Solution%3A%20%7B_seq%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(J%2C%20ModelIntervalCpSat%2C%20mo%2C%20p%2C%20r%2C%20w)%3A%0A%20%20%20%20_model%20%3D%20ModelIntervalCpSat(J%2C%20p%2C%20r%2C%20w)%0A%20%20%20%20with%20mo.redirect_stderr()%3A%0A%20%20%20%20%20%20%20%20_model.solve()%0A%0A%20%20%20%20_z%20%3D%20_model.get_z()%0A%20%20%20%20_seq%20%3D%20_model.get_seq()%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20-%20Optimal%20value%3A%20%7B_z%7D%0A%20%20%20%20-%20Solution%3A%20%7B_seq%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%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
e342f8406a26761a574d338e1fae7f189751dc607e5a65e4803ef4404833cfad