3e:null 3f:["$","title",null,{"children":"Miller–Tucker–Zemlin Formulation | Andrew's Workspace | Observable"}] 45:T716,problem = { const objective = { direction: glpk.GLP_MIN, vars: [] }; for (let i = 1; i <= n; i++) for (let j = 1; j <= n; j++) { if (i != j) objective.vars.push({ name: "x"+i+"_"+j, coef: dist[i-1][j-1] }); } const subjectTo = []; for (let i = 1; i <= n; i++) { const constraint = { vars: [], bnds: { type: glpk.GLP_FX, lb: 1, ub: 1 } }; for (let j = 1; j <= n; j++) { if (i != j) constraint.vars.push({ name: "x"+i+"_"+j, coef: 1 }); } subjectTo.push(constraint); } for (let i = 1; i <= n; i++) { const constraint = { vars: [], bnds: { type: glpk.GLP_FX, lb: 1, ub: 1 } }; for (let j = 1; j <= n; j++) { if (i != j) constraint.vars.push({ name: "x"+j+"_"+i, coef: 1 }); } subjectTo.push(constraint); } const generals = []; for (let j = 2; j <= n; j++) for (let i = 2; i <= n; i++) { if (i != j) { const constraint = { vars: [ { name: "u"+i, coef: 1 }, { name: "u"+j, coef: -1 }, { name: "x"+i+"_"+j, coef: n } ], bnds: { type: glpk.GLP_UP, lb: n-1, ub: n-1 } }; subjectTo.push(constraint); } } { const constraint = { vars: [{name: "u1", coef: 1}], bnds: { type: glpk.GLP_FX, lb: 1, ub: 1 } }; subjectTo.push(constraint); } for (let i = 2; i <= n; i++) { const constraint = { vars: [{name: "u"+i, coef: 1}], bnds: { type: glpk.GLP_DB, lb: 1, ub: n } }; subjectTo.push(constraint); } for (let i = 1; i <= n; i++) generals.push("u"+i); const binaries = []; for (let j = 1; j <= n; j++) for (let i = 1; i <= n; i++) if (i != j) binaries.push("x"+i+"_"+j); return { name: 'LP', objective: objective, subjectTo: subjectTo, binaries: binaries, generals: generals }; }46:[] 43:{"id":"40dffa1c0bbd9512","slug":null,"title":"Miller–Tucker–Zemlin Formulation","thumbnail":"41533677afa1c1c8ab3c91b54d85462692da0c8dcf89f5de7b646257cd1dec0e","access_level":"public","create_time":"$D2023-11-24T04:49:47.070Z","update_time":"$D2023-12-24T23:19:37.892Z","view_time":null,"first_public_time":"$D2023-12-18T21:17:44.670Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/b1bbfc156d3f54c3b6f6e1de0d7484c30b7661fb82d534963c2f721cd9b269b2","tier":"starter_2024","bio":"","following":false},"version":531,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"a304072c6a1ecaa7","login":"bottledspace","name":"Andrew","avatar_url":"https://avatars-next.observableusercontent.com/d15f3341dde29a23f8e8e86e2402a48080aa207acbd0f307d1b8f32970715453","tier":null,"bio":"","following":false}],"members":[{"type":"team","id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace","avatar_url":"https://avatars-next.observableusercontent.com/b1bbfc156d3f54c3b6f6e1de0d7484c30b7661fb82d534963c2f721cd9b269b2","tier":"starter_2024","role":"editor"},{"type":"individual","id":"a304072c6a1ecaa7","login":"bottledspace","name":"Andrew","avatar_url":"https://avatars-next.observableusercontent.com/d15f3341dde29a23f8e8e86e2402a48080aa207acbd0f307d1b8f32970715453","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"f4aee92b58c0361a","slug":"travelling-salesperson-problem","title":"Travelling Salesperson Problem","owner":{"id":"853760b68a3ad999","login":"andrew32-ws","name":"Andrew's Workspace"}},"type":"notebook","body":{"titling":"auto","title":"Miller–Tucker–Zemlin Formulation","cells":[{"id":0,"value":"# Miller–Tucker–Zemlin Formulation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":50,"value":"viewof n = Inputs.range([1, 20], {step: 1, label: \"Number of Cities\"}); ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":523,"value":"R = d3.randomLcg(1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"x = Array.from(Array(n), () => R()*300);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"y = Array.from(Array(n), () => R()*300);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"// Now we compute distances between them (symmetric)\ndist = Array.from(Array(n), (_, i) => Array.from(Array(n), (_, j) => \n Math.hypot(x[i]-x[j], y[i]-y[j])\n));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"glpk = {\n const module = await import('https://cdn.skypack.dev/glpk.js@4.0.1?min')\n return module.default()\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"$45","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":432,"value":"soln = glpk.solve(problem);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"width\", 300)\n .attr(\"height\", 300)\n .attr(\"viewBox\", [0, 0, 300, 300])\n .attr(\"style\", \"max-width: 100%; height: auto; height: intrinsic;\");\n svg.append(\"g\")\n .attr(\"fill\", \"#000\")\n .attr(\"stroke\", \"#fff\")\n .selectAll(\"circle\")\n .data(Array.from(Array(n), (_,k)=> k))\n .join(\"circle\")\n .attr(\"r\", 3)\n .attr(\"cx\", d => x[d])\n .attr(\"cy\", d => y[d]);\n for (let j = 1; j <= n; j++)\n for (let i = 1; i <= n; i++) {\n if (i != j &&\n soln.result.vars[\"x\"+i+\"_\"+j] != 0 ||\n soln.result.vars[\"x\"+j+\"_\"+i] != 0) {\n svg.append(\"g\")\n .attr(\"stroke\", \"#000\")\n .append(\"line\")\n .attr(\"x1\", x[i-1])\n .attr(\"y1\", y[i-1])\n .attr(\"x2\", x[j-1])\n .attr(\"y2\", y[j-1]);\n }\n }\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":466,"value":"glpk.write(problem)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W46","stdlib":"1"}} 44:"$43:body"