2b:["$","title",null,{"children":"Canonicalization with Math.js | Tom Larkworthy | Observable"}] 31:Td0a,constantsToRHSFn = { const isOperatorNode = math.isOperatorNode; const isConstantNode = math.isConstantNode; const isNegativeConstantNode = (node) => isOperatorNode(node) && node.fn == "unaryMinus" && isConstantNode(node.args[0]); const isSymbolNode = math.isSymbolNode; const isParenthesisNode = math.isParenthesisNode; const isZero = math.isZero; const OperatorNode = math.OperatorNode; const ConstantNode = math.ConstantNode; const ParenthesisNode = math.ParenthesisNode; const SymbolNode = math.SymbolNode; let prunedLHS = (node, pruned) => { const pruneNode = (node) => isConstantNode(node) ? node : new ConstantNode(-node.args[0].value); if (isConstantNode(node) || isNegativeConstantNode(node)) { if (node.value !== 0) { pruned.push(pruneNode(node)); } return new ConstantNode(0); } else if (isParenthesisNode(node)) { return node; } else if (isOperatorNode(node) && node.isBinary()) { if (node.fn == "add") { if ( isConstantNode(node.args[0]) || isNegativeConstantNode(node.args[0]) ) { pruned.push(pruneNode(node.args[0])); return prunedLHS(node.args[1], pruned); } else if ( isConstantNode(node.args[1]) || isNegativeConstantNode(node.args[1]) ) { pruned.push(pruneNode(node.args[1])); return prunedLHS(node.args[0], pruned); } return new OperatorNode(node.op, node.fn, [ prunedLHS(node.args[0], pruned), prunedLHS(node.args[1], pruned) ]); } else if (node.fn == "subtract") { if ( isConstantNode(node.args[0]) || isNegativeConstantNode(node.args[0]) ) { pruned.push(pruneNode(node.args[0])); return new OperatorNode("-", "unaryMinus", [ prunedLHS(node.args[1], pruned) ]); } else if ( isConstantNode(node.args[1]) || isNegativeConstantNode(node.args[1]) ) { pruned.push(new ConstantNode(-pruneNode(node.args[1]).value)); return prunedLHS(node.args[0], pruned); } return new OperatorNode(node.op, node.fn, [ prunedLHS(node.args[0], pruned), prunedLHS(node.args[1], pruned) ]); } return node; } else if (isOperatorNode(node) && node.isUnary()) { return new OperatorNode(node.op, node.fn, [node.args[0]]); } else if (isSymbolNode(node)) { return node; } debugger; throw new Error(`Should not happen: ${node}`); }; let appendRHS = (node, pruned) => { pruned.forEach((term) => { if (term.value > 0) { node = new OperatorNode("-", "subtract", [node, term]); } else { node = new OperatorNode("+", "add", [ node, new ConstantNode(-term.value) ]); } }); return node; }; let splitConditional = (node) => { if (isOperatorNode(node) && node.op === "<") { const terms = []; const a0 = prunedLHS(node.args[0], terms); const a1 = appendRHS(node.args[1], terms); return new OperatorNode(node.op, node.fn, [a0, a1]); } else { debugger; throw new Error(`Only works with < as top node ${node.fn}`); } }; return splitConditional; }32:T42b,addZeroToRHS = (exp) => { exp = typeof exp === "string" ? math.parse(exp) : exp; if ( exp.op === "<" && (exp.args[1].isSymbolNode || (exp.args[1].fn == "unaryMinus" && exp.args[1].args[0].isSymbolNode) || (exp.args[1].op == "*" && exp.args[1].args[0].isConstantNode && exp.args[1].args[1].isSymbolNode) || (exp.args[1].op == "*" && exp.args[1].args[0].fn == "unaryMinus" && exp.args[1].args[0].args[0].isConstantNode && exp.args[1].args[1].isSymbolNode)) ) { const RHS = exp.args[1]; const LHS = exp.args[0]; const newRHS = new math.ConstantNode(0); const newLHS = exp.args[1].fn == "unaryMinus" && exp.args[1].args[0].isSymbolNode ? new math.OperatorNode("+", "add", [LHS, RHS.args[0]]) : new math.OperatorNode("-", "minus", [LHS, RHS]); const result = new math.OperatorNode("<", "smaller", [newLHS, newRHS]); return math.parse(result.toString()); // There is something we don't get about mutating expression trees } else { return exp; } }33:T7cd,function extractLHS(acc, rootLhs) { const stack = []; stack.push(rootLhs); // while not empty while (stack.length) { // Pop off end of stack. let lhs = stack.pop(); if ( lhs.isOperatorNode && lhs.op === "-" && lhs.fn === "unaryMinus" && lhs.args[0].isConstantNode && lhs.args[0].value === 0 ) { // neg } else if (lhs.isConstantNode && lhs.value === 0) { // nothing to do } else if (lhs.isOperatorNode && lhs.op === "+") { stack.push(lhs.args[0]); stack.push(lhs.args[1]); } else if ( lhs.isOperatorNode && lhs.op === "-" && lhs.fn !== "unaryMinus" ) { stack.push(lhs.args[0]); const rhs = extractLHS([], lhs.args[1]); if (rhs.length !== 1) throw new Error("Unexpected complexity for negated op"); acc.push({ coef: -rhs[0].coef, name: rhs[0].name }); } else if (lhs.isSymbolNode) { acc.push({ coef: 1, name: lhs.name }); } else if ( lhs.isOperatorNode && lhs.op === "-" && lhs.fn === "unaryMinus" && lhs.args[0].isSymbolNode ) { acc.push({ coef: -1, name: lhs.args[0].name }); } else if (lhs.isOperatorNode && lhs.op === "*") { if (lhs.args[1].isSymbolNode) { let value = undefined; if (lhs.args[0].isConstantNode) { value = lhs.args[0].value; } else if ( lhs.args[0].fn === "unaryMinus" && lhs.args[0].args[0].isConstantNode ) { value = -lhs.args[0].args[0].value; } else { throw new Error(`Must be constant: ${lhs.args[0].toString()}`); } acc.push({ coef: value, name: lhs.args[1].name }); } else { throw new Error(`Cannot term from ${lhs.toString()}`); } } else { throw new Error(`Cannot extract coeffecients from ${lhs.toString()}`); } } return acc; }34:[] 2e:{"id":"50309473a164e648","slug":"glpk-canonicalization","title":"Canonicalization with Math.js","thumbnail":"8a1da5d875fa9d2cd80fd4e2bb864063c5bafa1e1188d920c7df9faca1431068","access_level":"unlisted","create_time":"$D2021-07-23T09:42:02.772Z","update_time":"$D2021-09-05T19:56:04.270Z","view_time":null,"first_public_time":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"7db5ed2b0697d645","login":"tomlarkworthy","name":"Tom Larkworthy","avatar_url":"https://avatars-next.observableusercontent.com/47327a8bc1966f2186dcb3ebf4b7ee6e4e7ab9a5c2a07405aff57200ea778f71","tier":"starter_2024"},"version":2525,"publish_version":2525,"role":null,"authored":false,"authors":[{"type":"individual","id":"5215f6ec4a999d40","login":"tomlarkworthy","name":"Tom Larkworthy","avatar_url":"https://avatars-next.observableusercontent.com/47327a8bc1966f2186dcb3ebf4b7ee6e4e7ab9a5c2a07405aff57200ea778f71","tier":null}],"members":[{"type":"individual","id":"5215f6ec4a999d40","login":"tomlarkworthy","name":"Tom Larkworthy","avatar_url":"https://avatars-next.observableusercontent.com/47327a8bc1966f2186dcb3ebf4b7ee6e4e7ab9a5c2a07405aff57200ea778f71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"Canonicalization with Math.js","cells":[{"id":0,"value":"md`# Canonicalization with Math.js\n\nI want to get expressions like ${tex`(x_2 - x_1) * 4 \\gt x_1 + 1`}, into _a) into a specialized canonical form for linear programming:-\n\n${tex`-5 x_1 + 4 x_2 \\geq 1`}\n\nin general\n\n${tex`c_1x_1 + ... + c_nx_n \\geq c_0`}\n\nMath.js has the power, but does not ship with enough rewrite rules by default. So this notebook is about adding the require rules to create a canonicalization routine.\n\nThere is a fuzzer to help stress test these routines https://observablehq.com/@tomlarkworthy/expression-fuzzer\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"math = require('mathjs@9.4.4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"md`### Simplify Rule Syntax: Custom simplification rules\n- ‘n’ - matches any Node\n- ‘c’ - matches any ConstantNode\n- ‘v’ - matches any Node that is not a ConstantNode\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1712,"value":"DEBUG = html``.href.split(\"?\")[0].split(\"#\")[0] ===\n \"https://observablehq.com/@tomlarkworthy/glpk-canonicalization\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":232,"value":"md`## Preparation: identify operator and replace with <`","pinned":false,"hidden":false,"mode":"ojs"},{"id":239,"value":"toLeq = ast => {\n const op = { op: ast.op, fn: ast.fn };\n ast.op = '<';\n ast.fn = 'smaller';\n return {\n op,\n ast\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":957,"value":"fromLeq = (ast, op) => {\n ast.op = op.op;\n ast.fn = op.fn;\n return ast;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":352,"value":"md`### Ordering`","pinned":false,"hidden":false,"mode":"ojs"},{"id":355,"value":"ordering = [\n { l: 'c+v', r: 'v+c', context: { add: { commutative: false } } },\n { l: 'v*c', r: 'c*v', context: { multiply: { commutative: false } } }\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":357,"value":"check(ordering, 'x + 1', 'x + 1')","pinned":false,"hidden":false,"mode":"ojs"},{"id":360,"value":"check(ordering, '1 + x', 'x + 1')","pinned":false,"hidden":false,"mode":"ojs"},{"id":322,"value":"md`### Expand brackets`","pinned":false,"hidden":false,"mode":"ojs"},{"id":325,"value":"expandBrackets = [\n { l: \"0 * n\", r: \"0\" },\n { l: \"-(-n)\", r: \"n\" },\n { l: \"-(c*n)\", r: \"-c * n\" },\n { l: \"-(n1 + n2)\", r: \"-n1 - n2\" },\n { l: \"-(n1 - n2)\", r: \"-n1 + n2\" },\n { l: \"n - (n1 + n2)\", r: \"n - n1 - n2\" },\n { l: \"n - (n1 - n2)\", r: \"n - n1 + n2\" },\n { l: \"c * (n1 + n2)\", r: \"c * n1 + c * n2\" },\n { l: \"c * (n1 - n2)\", r: \"c * n1 - c * n2\" },\n { l: \"-c * (n1 + n2)\", r: \"-c * n1 - c * n2\" },\n { l: \"-c * (-n1 - n2)\", r: \"c * n1 + c * n2\" },\n { l: \"-c * (n1 - n2)\", r: \"-c * n1 + c * n2\" }\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":2329,"value":"check(expandBrackets, \"-6 * (2 - x) < 0\", \"-6 * 2 + 6 * x < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2320,"value":"check(\n expandBrackets,\n \"-2 * (-16 - 4 * x) - 2 * y < 16\",\n \"2 * 16 + 2 * 4 * x - 2 * y < 16\"\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2162,"value":"check(expandBrackets, \"-2 * (x + 1)\", \"-2 * x - 2 * 1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":478,"value":"check(expandBrackets, '1 - (x2 - 5) ', '1 - x2 + 5')","pinned":true,"hidden":false,"mode":"ojs"},{"id":544,"value":"check(expandBrackets, 'x1 - (x2 - 5) ', 'x1 - x2 + 5')","pinned":true,"hidden":false,"mode":"ojs"},{"id":415,"value":"check(expandBrackets, '4 - (x1 + x2 + 5)', '4 - x1 - x2 - 5')","pinned":true,"hidden":false,"mode":"ojs"},{"id":441,"value":"check(expandBrackets, '1 - (x2 + 5) ', '1 - x2 - 5')","pinned":true,"hidden":false,"mode":"ojs"},{"id":429,"value":"check(expandBrackets, '- (x1 + x2)', '-x1 - x2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":437,"value":"check(expandBrackets, '- (x1 - x2)', '-x1 + x2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":266,"value":"check(expandBrackets, '-(x + 1)', '-x - 1')","pinned":true,"hidden":false,"mode":"ojs"},{"id":336,"value":"check(expandBrackets, '-(1 + x)', '-1 - x')","pinned":true,"hidden":false,"mode":"ojs"},{"id":338,"value":"check(expandBrackets, '-(1 - x)', '-1 + x')","pinned":true,"hidden":false,"mode":"ojs"},{"id":342,"value":"check(expandBrackets, '-(-1 - x)', '1 + x')","pinned":true,"hidden":false,"mode":"ojs"},{"id":349,"value":"check(expandBrackets, '-(-1 + x)', '1 - x')","pinned":true,"hidden":false,"mode":"ojs"},{"id":404,"value":"check(expandBrackets, '-(-1)', '1')","pinned":true,"hidden":false,"mode":"ojs"},{"id":426,"value":"check(expandBrackets, '-(-x)', 'x')","pinned":true,"hidden":false,"mode":"ojs"},{"id":887,"value":"check(expandBrackets, '0 * (x + 1)', '0')","pinned":true,"hidden":false,"mode":"ojs"},{"id":921,"value":"check(expandBrackets, '4 * (x + 1)', '4 * x + 4 * 1')","pinned":true,"hidden":false,"mode":"ojs"},{"id":927,"value":"check(expandBrackets, '4 * (x - 1)', '4 * x - 4 * 1')","pinned":true,"hidden":false,"mode":"ojs"},{"id":965,"value":"check(expandBrackets, '-(x1 + x2)', '-x1 - x2')","pinned":false,"hidden":false,"mode":"ojs"},{"id":2174,"value":"md`### Multiple out constants`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2177,"value":"multiplyOut = [math.simplify.simplifyCore]","pinned":true,"hidden":false,"mode":"ojs"},{"id":2185,"value":"check(multiplyOut, \"2 * 1\", \"2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":572,"value":"md`### ⚠️ Constants to RHS\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2362,"value":"viewof useConstantsToRHSFn = Inputs.toggle({\n label: \"Use new implementation?\",\n value: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2360,"value":"constantsToRHS = useConstantsToRHSFn\n ? [constantsToRHSFn]\n : [...constantsToRHSOld]","pinned":false,"hidden":false,"mode":"ojs"},{"id":575,"value":"constantsToRHSOld = [\n { l: \"c1 + n1 < n2\", r: \"n1 < n2 - c1\" },\n { l: \"n1 - c1 + n3 < n2\", r: \"n1 + n3 < n2 + c1\" }, // Hmmm, bit complex\n { l: \"n1 - c1 - n3 < n2\", r: \"n1 - n3 < n2 + c1\" }, // Hmmm, bit complex\n { l: \"n1 + c1 - n3 < n2\", r: \"n1 - n3 < n2 - c1\" }, // Hmmm, bit complex\n { l: \"c1 - n1 < n2\", r: \"- n1 < n2 - c1\" },\n { l: \"-c1 - n1 + n3 < n2\", r: \"- n1 + n3 < n2 + c1\" }, // Hmm, bit complex\n { l: \"-c1 - n1 - n3 < n2\", r: \"- n1 - n3 < n2 + c1\" }, // Hmm, bit complex\n { l: \"- c1 - n1 < n2\", r: \"- n1 < n2 + c1\" },\n { l: \"- c1 + n1 < n2\", r: \"n1 < n2 + c1\" },\n { l: \"n1 - c1 < n2\", r: \"n1 < n2 + c1\" },\n { l: \"c < n\", r: \"-n < -c\" },\n { l: \"c < 0\", r: \"0 < -c\" },\n { l: \"c <-0\", r: \"0 < -c\" },\n { l: \"-c < -0\", r: \"0 < c\" },\n { l: \"-c < 0\", r: \"0 < c\" }\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":2369,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":2431,"value":"check(constantsToRHS, \"1 < 0\", \"0 < 0 - 1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2472,"value":"check(constantsToRHS, \"-1 < 0\", \"0 < 0 + 1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2350,"value":"check(\n constantsToRHS,\n \"-2 * y - 2 - 2 * x - y < 0\",\n \"-2 * y - 2 * x - y < 0 + 2\"\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2300,"value":"check(constantsToRHS, \"-2 - x + y < 0\", \"-x + y < 0 + 2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2312,"value":"check(constantsToRHS, \"-2 - x - y < 0\", \"-x - y < 0 + 2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2195,"value":"check(constantsToRHS, \"-(2 * x) + 2 - y < 0\", \"-(2 * x) - y < 0 - 2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1978,"value":"check(constantsToRHS, \"0 < 1\", \"0 < 1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1825,"value":"check(constantsToRHS, \"x - 1 + y < 0\", \"x + y < 0 + 1\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":577,"value":"check(constantsToRHS, '4 + x1 < x2', 'x1 < x2 - 4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":587,"value":"check(constantsToRHS, '4 - x1 < x2', '-x1 < x2 - 4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":603,"value":"check(constantsToRHS, '-4 - x1 < x2', '-x1 < x2 + 4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":606,"value":"check(constantsToRHS, '-4 + x1 < x2', 'x1 < x2 + 4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":614,"value":"check(constantsToRHS, 'x1 + 4 < x2', 'x1 < x2 - 4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":617,"value":"check(constantsToRHS, 'x1 - 4 < x2', 'x1 < x2 + 4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":625,"value":"check(constantsToRHS, '-x1 + 4 < x2', '-x1 < x2 - 4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":1160,"value":"check(constantsToRHS, \"5 - x1 < 0\", '-x1 < 0 - 5')","pinned":false,"hidden":false,"mode":"ojs"},{"id":640,"value":"md`### Variables to LHS`","pinned":false,"hidden":false,"mode":"ojs"},{"id":642,"value":"complexityToLHS = [\n { l: 'n1 < n2 + v', r: '-v + n1 < n2' },\n { l: 'n1 < n2 - v', r: 'v + n1 < n2' },\n { l: '-n1 < v - n2', r: '-v - n1 < -n2' },\n { l: 'n1 < v - n2', r: '-v + n1 < -n2' }\n //{ l: 'v1 < v2', r: 'v1 - v2 < 0' }\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":835,"value":"check(complexityToLHS, 'x < 1 + 1 + 1', '-(1 + 1) + x < 1')","pinned":false,"hidden":false,"mode":"ojs"},{"id":727,"value":"check(complexityToLHS, \"x1 < x2 - 5\", '-x2 + x1 < -5')","pinned":false,"hidden":false,"mode":"ojs"},{"id":646,"value":"check(complexityToLHS, '1 < 2 - x', 'x + 1 < 2')","pinned":false,"hidden":false,"mode":"ojs"},{"id":649,"value":"check(complexityToLHS, '1 < 2 + x', '-x + 1 < 2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":655,"value":"check(complexityToLHS, '1 < -2 + x', '-x + 1 < -2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":657,"value":"check(complexityToLHS, '1 < -2 - x', 'x + 1 < -2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":659,"value":"check(complexityToLHS, '-1 < -2 - x', 'x + -1 < -2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":683,"value":"check(complexityToLHS, '-1 < x - 2', '-x - 1 < -2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":694,"value":"check(complexityToLHS, '-1 < -x - 2', '-(-x) - 1 < -2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":712,"value":"check(complexityToLHS, '-1 < -x + 2', '-(-x) + -1 < 2')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1227,"value":"check(complexityToLHS, '-4 * y < 0', '-4 * y < 0')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1071,"value":"md`### Add zero to RHS\n\nIts quite dangerous introducing terms as it often causes loop, so we do this once other optimizations are exhausted.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1075,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":2238,"value":"math.parse(\"1 + 2 \")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2262,"value":"checkStep(addZeroToRHS, \"x < -3 * x\", \"x - -3 * x < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1953,"value":"checkStep(addZeroToRHS, '0 < -1', \"0 < -1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2236,"value":"checkStep(addZeroToRHS, \"x < -x\", \"x + x < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1198,"value":"checkStep(addZeroToRHS, 'y < 5*y', \"y - 5 * y < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1067,"value":"checkStep(addZeroToRHS, 'x < y', 'x - y < 0')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1083,"value":"checkStep(addZeroToRHS, 'x < 3', 'x < 3')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1096,"value":"checkStep(addZeroToRHS, 'x < -3', 'x < -3')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1143,"value":"checkStep(addZeroToRHS, '5 < x1', \"5 - x1 < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1183,"value":"checkStep(\n exp => math.simplify(addZeroToRHS(exp), constantsToRHS),\n '5 < x1',\n '-x1 < 0 - 5'\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1230,"value":"checkStep(addZeroToRHS, '-4 * y < 0', '-4 * y < 0')","pinned":true,"hidden":false,"mode":"ojs"},{"id":982,"value":"md`### Simplify Base Rules\n\nThe default simplify sometimes works against us by introducing brackets. So we trim the rules down a bit, however it is not enough\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":985,"value":"simplify2 = {\n const baseRules = [...math.simplify.rules];\n\n baseRules.splice(\n baseRules.findIndex((r) => r.l === \"n1*n3 + n2*n3\"),\n 1\n );\n /*\n baseRules.splice(\n baseRules.findIndex((r) => r.l === \"n1*n2 + n2\") + 1,\n 0,\n { l: \"c1 * (n + c2)\", r: \"c1 * n + c1 * c2\" },\n { l: \"-c1 * (n + c2)\", r: \"-c1 * n - c1 * c2\" },\n { l: \"- (n1 + n2)\", r: \"-n1 - n2\" }\n );*/\n\n // Performance issues so we remove some irrelavant ones\n /*\n baseRules.splice(baseRules.findIndex(r => r.l === 'n+n'), 1);\n baseRules.splice(baseRules.findIndex(r => r.l === 'log(e)'), 1);\n baseRules.splice(baseRules.findIndex(r => r.l === 'n-n1'), 1);\n baseRules.splice(baseRules.findIndex(r => r.l === 'n+-n'), 1);\n baseRules.splice(baseRules.findIndex(r => r.l === 'n*n'), 1);\n */\n return [...baseRules];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2497,"value":"simplifyStepExample(\"-2 * y - 4 * y < 0\", \"-6 * y < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":988,"value":"check(simplify2, '-x1 - x2 < 5', '-x1 - x2 < 5')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1232,"value":"check(simplify2, '-4 * y < 0', '-(4 * y) < 0') // Unfortunate but needed for other cases","pinned":true,"hidden":false,"mode":"ojs"},{"id":1401,"value":"check(simplify2, '1.1', '1.1')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1688,"value":"check(simplify2, \"x - 1 - 2\", \"x - 3\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1699,"value":"check(simplify2, \"x - 1 + 1 + y\", \"x + y\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1809,"value":"md`### Simplify Step\n\nNote that < causes problems with zeros, so we have to simplify on each AST branch seperately\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1718,"value":"// New simplify rules get confused with comparisons. So its better to do each half seperately\ncheck(simplify2, \"- 1 + 1 + y < 0\", \"y + 0 < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1753,"value":"simplifyStep = (exp) => {\n // Simplify gets confused by comparitor, better to run it on each child sperately\n const customSimplify = (exp) =>\n math.simplify(\n math.simplify(exp, math.simplify.rules, {}, { exactFractions: false }),\n [...expandBrackets, ...multiplyOut]\n );\n\n if (exp.isOperatorNode && exp.op === \"<\") {\n return exp.map(customSimplify);\n } else {\n return customSimplify(exp);\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1784,"value":"simplifyStepExample(\"- 1 + 1 + y < 0\", \"y < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2017,"value":"simplifyStepExample(\"-2 * x + -2 < 0\", \"-2 * x - 2 < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2147,"value":"simplifyStepExample(\"2 * (x + 2) < 0\", \"2 * x + 4 < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2056,"value":"simplifyStepExample(\"2 + 2 * x\", \"2 * x + 2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2050,"value":"simplifyStepExample(\"1 * 2 < 0\", \"2 < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":761,"value":"md`### Step 2\n\nAim of step 2 is to pull constants to RHS, simplify them, and push complex expression to LHS, and repeat.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":58,"value":"step2 = (exp) => {\n const history = [];\n do {\n history.push(exp);\n const updateRHS = math.simplify(exp, [\n ...expandBrackets,\n ...constantsToRHS\n ]);\n const rhs = simplifyStep(updateRHS);\n const updateLHS = math.simplify(rhs, [...complexityToLHS]);\n exp = addZeroToRHS(updateLHS);\n if (DEBUG) {\n console.log(\"updateRHS\", updateRHS.toString());\n console.log(\"rhs\", rhs.toString());\n console.log(\"updateLHS\", updateLHS.toString());\n console.log(\"addZeroToRHS\", exp.toString());\n }\n } while (history.find((prev) => _.isEqual(exp, prev)) === undefined);\n\n return math.simplify(exp, [...expandBrackets]);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1471,"value":"equalsIsSlow = {\n const n = 20;\n const termsA = Array.from({ length: n })\n .map((_, i) => `x${i}`)\n .join(\" + \");\n\n const termsB = Array.from({ length: n })\n .map((_, i) => `x${i}`)\n .join(\" + \");\n\n const a = math.parse(termsA);\n const b = math.parse(termsB);\n\n //return a.equals(b) // Very slow, uses home rolled deep equals https://github.com/josdejong/mathjs/blob/c6cbf5538915c8964b70a1af086f47c2c0be33df/src/expression/node/Node.js#L221\n return _.isEqual(a, b); // much faster\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2318,"value":"step2Example(\n \"-2*-2*2*(1*2+x+2)+(-2+0)*(y+(0+(-2+-2*0*-1*((-2*2+1)*(0+-1)*-1+2))*(2+0*-2))*-2) < 0*1\",\n \"8 * x - 2 * y < -16\"\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2294,"value":"step2Example(\"-2 - x + y < 0\", \"y - x < 2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2233,"value":"step2Example(\"((-1*2+-2+0)*0*-1+x+-1+1)*1 < (1+-2)*x\", \"2 * x < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1996,"value":"step2Example(\"-(2 * x) + -2 - y < 0\", \"-2 * x - y < 2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1940,"value":"step2Example(\"0*0*x < 1\", \"0 < 1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":796,"value":"step2Example('4 + x1 + x2 + 1 < x2 + 4', \"x1 < -1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1918,"value":"step2Example('4 + x1 + 1 < 4', \"x1 < -1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":811,"value":"step2Example('(x + 1) < (3 + x) * (6 - 7)', \"2 * x < -4\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":814,"value":"step2Example('(x + 1) * 4 < (3 + x) * (6 - 7)', \"5 * x < -7\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":968,"value":"step2Example('-(x1 + x2) < 0', '-x1 - x2 < 0')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1065,"value":"step2Example('x < y', 'x - y < 0')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1121,"value":"step2Example('5 < x1', \"-x1 < -5\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1214,"value":"step2Example('-(4 * y) < 0', \"-4 * y < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1365,"value":"step2Example(\"4x < 0\", \"4 x < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1399,"value":"step2Example(\"x < 1.1\", \"x < 1.1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1683,"value":"step2Example(\"x - 1 + 1 + y < 0\", \"x + y < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1873,"value":"step2Example(\"0 < -2 * x\", \"2 * x < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2111,"value":"step2Example(\"1 + y < y\", \"0 < -1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2250,"value":"step2Example(\"x < -3 * x\", \"4 * x < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2285,"value":"step2Example(\"x < -1*(0+-1)*(1+0)*(-2+(0+1+1*0*-1)*0)*2*y\", \"x + 4 * y < 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":567,"value":"md`### Canonicalize`","pinned":false,"hidden":false,"mode":"ojs"},{"id":27,"value":"canonicalize = exp => {\n const ast = math.parse(exp);\n const leq = toLeq(ast);\n const simplified = isCanonical(leq.ast) ? leq.ast : step2(leq.ast);\n return fromLeq(simplified, leq.op);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":105,"value":"canonicalExample('4 + x1 + 1 < 4', \"x1 < -1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":156,"value":"canonicalExample('4 > 4 + x1 + 1', \"-x1 > 1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":119,"value":"canonicalExample('4 + x1 + x2 + 2 < x2 + 4', \"x1 < -2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":142,"value":"canonicalExample('4 + x1 + x2 + 2 <= x2 + 4', \"x1 <= -2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":139,"value":"canonicalExample(\"5 > x1 + x2\", \"-x1 - x2 > -5\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1060,"value":"canonicalExample('- -x + y > 5*y + 2x', \"-4 * y - x > 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1252,"value":"canonicalExample(\"-(4 * y) + -(4 * x) > 0\", \"-4 * y - 4 * x > 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1397,"value":"canonicalExample('x > 1.1', \"x > 1.1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1420,"value":"canonicalExample(\"1 == x1 + x2 + x3\", \"-x3 - x1 - x2 == -1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1679,"value":"canonicalExample(\"x - 1 + 1 + y <= 0\", \"x + y <= 0\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":2346,"value":"canonicalExample(\"(-1+1*(2+y+x))*-2 <= y\", \"-3 * y - 2 * x <= 2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1436,"value":"tests.test(`scale 10k'`, () => {\n const n = 10000;\n const terms = Array.from({ length: n })\n .map((_, i) => `x${i}`)\n .join(\" + \");\n canonicalize(terms + \" > 0\");\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1571,"value":"md`### isCanonical (special case short circuit)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1573,"value":"isCanonical = exp => {\n if (exp.op) {\n try {\n const bounds = extractRHS('<=', exp.args[1]);\n const vars = extractLHS([], exp.args[0]);\n } catch (err) {\n return false;\n }\n return true;\n }\n\n return false;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1575,"value":"tests.test(\"x0 + x1 + x2 > 0 is canonical\", () => {\n expect(isCanonical(math.parse(\"x0 + x1 + x2 < 0\"))).toBe(true);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1597,"value":"tests.test(\"x0 + x1 - x2 > 0 is canonical\", () => {\n expect(isCanonical(math.parse(\"x0 + x1 - x2 < 0\"))).toBe(true);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1583,"value":"tests.test(\"x0 + x1 * x2 > 0 is NOT canonical\", () => {\n expect(isCanonical(math.parse(\"x0 + x1 * x2 < 0\"))).toBe(false);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1662,"value":"tests.test(\"-x < -1 is canonical\", () => {\n expect(isCanonical(math.parse(\"-x < -1\"))).toBe(true);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1257,"value":"md`### Extract\n\nThis applies our custom canonicalization and converts to a JSON:\n\n~~~js\nvars: [\n { name: 'x1', coef: 3.0 },\n { name: 'x2', coef: 1.0 }\n ],\n ub: 2.0\n lb: 0.0\n~~~\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1261,"value":"extract = exp => {\n const c = canonicalize(exp);\n if (c.isOperatorNode) {\n const bounds = extractRHS(c.op, c.args[1]);\n const vars = extractLHS([], c.args[0]);\n\n return {\n vars,\n bounds\n };\n } else {\n throw new Error(\"cannot deal\");\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1274,"value":"extractRHS = (op, rhs) => {\n let value = undefined;\n if (rhs.isConstantNode) {\n value = rhs.value;\n } else if (rhs.fn === \"unaryMinus\" && rhs.args[0].isConstantNode) {\n value = -rhs.args[0].value;\n } else {\n throw new Error(`Must be constant: ${rhs.toString()}`);\n }\n if (op === \"<=\") {\n return {\n upper: value\n };\n } else if (op === \">=\") {\n return {\n lower: value\n };\n } else if (op === \"==\") {\n return {\n lower: value,\n upper: value\n };\n } else {\n throw new Error(`Unsupported op ${op}`);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1298,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1333,"value":"checkExtract = (expression, expected) => {\n return tests.test(\n `extract('${expression}') === '${JSON.stringify(expected)}'`,\n () => {\n expect(extract(expression)).toEqual(expected);\n }\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1335,"value":"checkExtract('4x <= 6', {\n vars: [{ coef: 4, name: \"x\" }],\n bounds: { upper: 6 }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1349,"value":"checkExtract(\"x <= 0\", {\n vars: [{ coef: 1, name: \"x\" }],\n bounds: { upper: 0 }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1342,"value":"checkExtract('4x + 6 (y + 4) 5 >= -6', {\n vars: [{ coef: 30, name: \"y\" }, { coef: 4, name: \"x\" }],\n bounds: { lower: -126 }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1375,"value":"checkExtract('4x - 2(y) >= 0', {\n bounds: { lower: 0 },\n vars: [{ coef: -2, name: \"y\" }, { coef: 4, name: \"x\" }]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1429,"value":"checkExtract('x + y == 0', {\n vars: [{ coef: 1, name: \"y\" }, { coef: 1, name: \"x\" }],\n bounds: { upper: 0, lower: 0 }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1391,"value":"checkExtract('4x - 2(y) -z >= 0', {\n bounds: { lower: 0 },\n vars: [\n { coef: -1, name: \"z\" },\n { coef: -2, name: \"y\" },\n { coef: 4, name: \"x\" }\n ]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1867,"value":"checkExtract(\"0<=-2*x\", {\n bounds: { upper: -0 },\n vars: [{ coef: 2, name: \"x\" }]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1900,"value":"checkExtract(\"0 == 0\", {\n vars: [],\n bounds: { upper: 0, lower: 0 }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1907,"value":"checkExtract(\"0*0*x>=1\", {\n vars: [],\n bounds: { lower: 1 }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1993,"value":"checkExtract(\"-2<=y+2*x\", {\n vars: [\n {\n coef: -2,\n name: \"x\"\n },\n {\n coef: -1,\n name: \"y\"\n }\n ],\n bounds: { upper: 2 }\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"viewof tests = createSuite({\n name: \"Canonicalization\"\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":33,"value":"canonicalExample = (expression, expected) => {\n return tests.test(\n `canonicalize('${expression.substring(30)}') === '${expected.substring(\n 30\n )}'`,\n () => {\n expect(canonicalize(expression).toString()).toBe(expected);\n }\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":798,"value":"step2Example = (expression, expected) => {\n return tests.test(`step2('${expression}') === '${expected}'`, () => {\n expect(step2(expression).toString()).toBe(expected);\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1789,"value":"simplifyStepExample = (expression, expected) => {\n return tests.test(`simplifyStep('${expression}') === '${expected}'`, () => {\n expect(simplifyStep(math.parse(expression)).toString()).toBe(expected);\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1925,"value":"simplifyStepExample('0*0*x < 1', '0 < 1')","pinned":true,"hidden":false,"mode":"ojs"},{"id":331,"value":"check = (rules, expression, expected) => {\n return tests.test(`check('${expression}') === '${expected}'`, () => {\n expect(\n math.simplify(expression, rules, {}, { exactFractions: false }).toString()\n ).toBe(expected);\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1099,"value":"checkStep = (step, expression, expected) => {\n return tests.test(`check('${expression}') === '${expected}'`, () => {\n expect(step(math.parse(expression)).toString()).toBe(expected);\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":8,"value":"import { createSuite, expect } from '@tomlarkworthy/testing'","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}} 2f:"$2e:body" 2a:E{"digest":"NEXT_REDIRECT;replace;/@tomlarkworthy/glpk-canonicalization;307;"}