30:T6cf,# Mixed Integer / Linear Programming Mixed integer programming for the browser! Mixed integer programming is restricted but powerful formalism for solving optimization problems. Variables can be - non-negative continuous (default) - integer - binary (which is integer restricted to 0 or 1) You can request to **minimize** or **maximize** some **linear** objective function _e.g._ ${tex`4x + 5y`}. Note the main linear limitation is you cannot multiply variables. You can provide additional _linear_ constraints on the solution space - ${tex`4x \leq 4`} - ${tex`x - b == 0`} The solver will then find a solution that is optimal for your objective (though may take a long time). This solver frontend is very different to other linear programming libraries in Javascript, it accepts expressions encoded as strings and does algebraic rearrangement for you. Whilst the linearity requirements are a restriction on the creative space, the fact that an optimal solution will be found is why we like the formalism. There are techniques to make Mixed Integer Programming apply to problems that naively look non-linear, e.g. the [Big M method](https://en.wikipedia.org/wiki/Big_M_method) or piecewise discretization. There are very powerful solvers in the commercial market ([Gurobi](gurobi.com), [Google DeepMind](https://deepmind.com/research/publications/2021/Solving-Mixed-Integer-Programs-Using-Neural-Networks)), the one here uses the open source solver [GNU GLPK](https://www.gnu.org/software/glpk/) as a backend but we can add support for more if we can find a WASM binary. GLPK was transpiled to JS by [glpk.js](https://github.com/jvail/glpk.js). GLPK is not directly called, hence the front end can be ISC licensed as a seperate work.31:T42b,### Blending problem solution Variables In order to solve this problem it is best to think in terms of one kilogram of feed mix. That kilogram is made up of three parts - ingredient 1, ingredient 2 and filler so: let x1 = amount (kg) of ingredient 1 in one kg of feed mix x2 = amount (kg) of ingredient 2 in one kg of feed mix x3 = amount (kg) of filler in one kg of feed mix where x1 >= 0, x2 >= 0 and x3 >= 0. Constraints balancing constraint (an implicit constraint due to the definition of the variables) x1 + x2 + x3 = 1 nutrient constraints 100x1 + 200x2 >= 90 (nutrient A) 80x1 + 150x2 >= 50 (nutrient B) 40x1 + 20x2 >= 20 (nutrient C) 10x1 >= 2 (nutrient D) Note the use of an inequality rather than an equality in these constraints, following the rule we put forward in the Two Mines example, where we assume that the nutrient levels we want are lower limits on the amount of nutrient in one kg of feed mix. #### Objective Presumably to minimise cost, i.e. _minimize_ ${tex`40x1 + 60x2`} which gives us our complete LP model for the blending problem.32:T66d,function mip() { glpkService; const model = new Model(); return { objective: function(maxOrMin, expr) { model.objective(maxOrMin, expr); return this; }, var: function(label, type = Number) { model.var(label, type); return this; }, subjectTo: function(label, expr) { model.subjectTo(label, expr); return this; }, model: function() { return model; }, solve: async function() { const session = randomId(); let resolve, reject; const result = new Promise((_resolve, _reject) => { resolve = _resolve; reject = _reject; }); // listen for solution function solutionHandler(event) { if ( event.origin === window.origin && event.data.tag === server_comm_tag && event.data.method === "solution" && event.data.session === session ) { console.log("Response received"); const result = event.data.result; if (result.status === "optimal") resolve(result); else { const err = new Error(result.status); err.result = result; reject(err); } } } window.addEventListener("message", solutionHandler, false); invalidation.then(() => window.removeEventListener("message", solutionHandler) ); // Send problem off to solver window.postMessage( { tag: server_comm_tag, method: "solve", session: session, model: model }, window.origin ); return result; } }; }33:T93b,### Licensing The solver backend is GLPK which is GPL 3.0, but this MIP front end is ISC. Our integration to the backend is pluggable and the front end communicates with the GLPK core via postMessage in a analogous way to a CLI. Let me explain how this works and why the client can be released as ISC and doesn't have to take on GPL licensing terms. **Background** If one program is statically or dynamically linked to a GPL program. It needs to also be releases under GPL terms. However, if the two programs remain separate, it does not. _"By contrast, pipes, sockets and command-line arguments are communication mechanisms normally used between two separate programs. So when they are used for communication, the modules normally are separate programs."_ -- [GNU FAQ](https://www.gnu.org/licenses/old-licenses/gpl-2.0-faq.en.html#TOCMereAggregation) We can see this separation at work in the Python ecosystem, e.g. PuLP invokes GLPK but is not GPL because it invokes through the CLI https://github.com/coin-or/pulp (which is common to how MIP solvers are invoked). https://github.com/coin-or/pulp/blob/master/pulp/apis/glpk_api.py One the Web, *almost* everything is dynamically linked so what is the equivalent interface to a UNIX pipe? Critically, so the separate programs directly call each other functions? Or do they call an intermedia public API. Some musings are here. _"But it is also possible to call generically written Javascript from a document and pass information to that Javascript using a well-established public API. This would be an indication that the works may be considered separate. The answer would be dependent on an analysis of the particular case at hand."_ [Stack overflow](https://opensource.stackexchange.com/a/4500/24642) postMessage is a WEB API often used to serialize messages between web workers who have isolated address spaces. This is the WEB version of process isolation and analogous to independant programs on native OSes. So, if we wrap GLPK with a postMessage interface, and keep its interface generic like its CLI, then programs that go through the postMessage interface should are considered separate programs and are not required to be GPLed, as long as the integration is generic. Thus particular effort is made to ensure the GLPK backend is swappable and we use the postMessage interface to communicate.34:[] 2e:{"title":"Mixed Integer / Linear Programming","cells":[{"id":581,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":679,"value":"### Change log\n- 2021-09-05: [Fuzzing testing](https://observablehq.com/@tomlarkworthy/expression-fuzzer) + rewrite of some of simplification logic greatly increased robustness","pinned":false,"hidden":false,"mode":"md"},{"id":696,"value":"## Use outside of Observable?\n\nNotebooks are ES6 modules, you can depend on them in a package.json!","pinned":false,"hidden":false,"mode":"md"},{"id":619,"value":"md`### Jo Wood's Observable Intro to Linear Programming\n\nJo prepared and excellent selection of examples using this library in their notebook [Hello Linear Programming](https://observablehq.com/@jwolondon/hello-linear-programming)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":538,"value":"md`\n~~~js\nimport {mip} from '@tomlarkworthy/mip'\n~~~\n\nExample:\n\n~~~js\n mip()\n .objective(Math.min, '40x1 + 60x2 + 15u2') // Cost, includes fixed cost of using ingredient 2\n .subjectTo('x1 + x2 + x3 == 1') // Mixing\n .subjectTo('100x1 + 200x2 >= 90 * (1 - va)') // Nutriant A\n .subjectTo('80x1 + 150x2 >= 50 * (1 - vb)') // Nutriant B\n .subjectTo('40x1 + 20x2 >= 20 * (1 - vc)') // Nutriant C\n .subjectTo('10x1 >= 2 * (1 - vd)') // Nutriant D\n .var('u2', Boolean) // Used ingredient 2 flag\n .subjectTo('x2 - u2 <= 0') // For x2 > 0 (but < 1), u2 must also be non-zero, and its a boolean so 1\n .var('va', Boolean) // violate nutriants A\n .var('vb', Boolean)\n .var('vc', Boolean)\n .var('vd', Boolean)\n .subjectTo('va + vb + vc + vd <= 1') // Only one violation\n .solve()\n~~~\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":632,"value":"md`### Conversation on Twitter`","pinned":false,"hidden":false,"mode":"ojs"},{"id":635,"value":"tweet('1422788681778307075')","pinned":false,"hidden":false,"mode":"ojs"},{"id":606,"value":"### Reporting Bugs\n\nPost message to https://talk.observablehq.com/t/mixed-integer-programming/5414","pinned":false,"hidden":false,"mode":"md"},{"id":589,"value":"\n\n## Another example: J E Beasley Operation Research Examples \n\nTaken from http://people.brunel.ac.uk/~mastjjb/jeb/or/moreip.html\n\n### Basic Blending problem\n\nConsider the example of a manufacturer of animal feed who is producing feed mix for dairy cattle. In our simple example the feed mix contains two active ingredients and a filler to provide bulk. One kg of feed mix must contain a minimum quantity of each of four nutrients as below:\n\n~~~\nNutrient A B C D\ngram 90 50 20 2\n~~~\nThe ingredients have the following nutrient values and cost\n~~~\n A B C D Cost/kg\nIngredient 1 (gram/kg) 100 80 40 10 40\nIngredient 2 (gram/kg) 200 150 20 - 60\n~~~\nWhat should be the amounts of active ingredients and filler in one kg of feed mix?","pinned":false,"hidden":false,"mode":"md"},{"id":374,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":394,"value":"blendingAns = mip()\n .objective(Math.min, '40x1 + 60x2')\n .subjectTo('x1 + x2 + x3 == 1')\n .subjectTo('100x1 + 200x2 >= 90')\n .subjectTo('80x1 + 150x2 >= 50')\n .subjectTo('40x1 + 20x2 >= 20')\n .subjectTo('10x1 >= 2')\n .solve()","pinned":true,"hidden":false,"mode":"ojs"},{"id":428,"value":"Inputs.table(\n Object.entries(blendingAns.vars).map(([k, v]) => ({ var: k, value: v }))\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":440,"value":"#### Blending Problem++\n\nSuppose now we have the additional conditions:\n\nif we use any of ingredient 2 we incur a fixed cost of 15\nwe need not satisfy all four nutrient constraints but need only satisfy three of them (i.e. whereas before the optimal solution required all four nutrient constraints to be satisfied now the optimal solution could (if it is worthwhile to do so) only have three (any three) of these nutrient constraints satisfied and the fourth violated.\nGive the complete MIP formulation of the problem with these two new conditions added.","pinned":false,"hidden":false,"mode":"md"},{"id":460,"value":"Inputs.table(\n Object.entries(blendingPlusAns.vars).map(([k, v]) => ({ var: k, value: v }))\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":456,"value":"blendingPlusAns = mip()\n .objective(Math.min, '40x1 + 60x2 + 15u2') // Cost, includes fixed cost of using ingredient 2\n .subjectTo('x1 + x2 + x3 == 1') // Mixing\n .subjectTo('100x1 + 200x2 >= 90 * (1 - va)') // Nutriant A\n .subjectTo('80x1 + 150x2 >= 50 * (1 - vb)') // Nutriant B\n .subjectTo('40x1 + 20x2 >= 20 * (1 - vc)') // Nutriant C\n .subjectTo('10x1 >= 2 * (1 - vd)') // Nutriant D\n .var('u2', Boolean) // Used ingredient 2 flag\n .subjectTo('x2 - u2 <= 0') // For x2 > 0 (but < 1), u2 must also be non-zero, and its a boolean so 1\n .var('va', Boolean) // violate nutriants A\n .var('vb', Boolean)\n .var('vc', Boolean)\n .var('vd', Boolean)\n .subjectTo('va + vb + vc + vd <= 1') // Only one violation\n .solve()","pinned":true,"hidden":false,"mode":"ojs"},{"id":60,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":263,"value":"md`### Tests`","pinned":false,"hidden":false,"mode":"ojs"},{"id":292,"value":"suite.test(\"subjectTo lower bound\", async () => {\n const result = await mip()\n .objective(Math.min, 'y')\n .subjectTo(\"y >= 1\")\n .solve();\n expect(result.vars.y).toBe(1);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":371,"value":"suite.test(\"subjectTo upper bound\", async () => {\n const result = await mip()\n .objective(Math.max, 'y')\n .subjectTo(\"y <= 10\")\n .solve();\n expect(result.vars.y).toBe(10);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":400,"value":"// See https://github.com/jvail/glpk.js/issues/29\nsuite.test(\"variables cannot be negative\", async () => {\n const result = await mip()\n .objective(Math.min, 'x')\n .subjectTo(\"x >= -1\")\n .solve();\n expect(result.vars.x).toBe(0);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":613,"value":"// See https://github.com/jvail/glpk.js/issues/29\nsuite.test(\"variables cannot be negative workaround\", async () => {\n const result = await mip()\n .objective(Math.min, 'x_pos - x_neg')\n .subjectTo(\"x_pos - x_neg >= -1\")\n .solve();\n expect(result.vars.x_pos).toBe(0);\n expect(result.vars.x_neg).toBe(1);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":309,"value":"suite.test(\"Integer variable\", async () => {\n const result = await mip()\n .objective(Math.min, 'x')\n .var(\"x\", BigInt)\n .subjectTo(\"x >= 1.1\")\n .solve();\n expect(result.vars.x).toBe(2);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":364,"value":"suite.test(\"Boolean variable max is 1\", async () => {\n const result = await mip()\n .objective(Math.max, 'x')\n .var(\"x\", Boolean)\n .solve();\n expect(result.vars.x).toBe(1);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":470,"value":"suite.test(\"Boolean variable min is 0\", async () => {\n const result = await mip()\n .objective(Math.min, 'x')\n .var(\"x\", Boolean)\n .solve();\n expect(result.vars.x).toBe(0);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":520,"value":"suite.test(\"Using boolean to indicate non-negative\", async () => {\n const result = await mip()\n .objective(Math.min, 'x + b')\n .var('b', Boolean)\n .subjectTo('x >= 1')\n .subjectTo('x - b <= 0') // For x > 0 (but < 1), b must also be non-zero, and its a boolean so 1\n .solve();\n expect(result.vars.b).toBe(1);\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":300,"value":"suite.test(\"solve unbounded throws\", async done => {\n try {\n const result = await mip()\n .objective(Math.max, 'x')\n .solve();\n } catch (err) {\n expect(err.result.status).toBe('unbounded');\n done();\n }\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":654,"value":"suite.test(\n \"scaling to 10000 variables if the objective function is in a simple form\",\n async () => {\n const terms = Array.from({ length: 10000 })\n .map((_, i) => `x${i}`)\n .join(\" + \");\n const result = await mip()\n .objective(Math.min, terms)\n .solve();\n expect(result.vars.x0).toBe(0);\n }\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":285,"value":"viewof suite = createSuite({ name: \"MIP tests\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":282,"value":"import { createSuite, expect } from '@tomlarkworthy/testing'","pinned":false,"hidden":false,"mode":"ojs"},{"id":210,"value":"import { randomId } from '@tomlarkworthy/randomid'","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":93,"value":"md`### Linear Programming Model (Dual license, ISC and GPL)\nHere we define our Linear Programming data model, which can be serialized and deserialized either side of the postMessage interface.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":100,"value":"class Model {\n constructor() {\n this.types = {};\n this.constraints = {};\n }\n objective(dir, expr) {\n if (dir === Math.max) this.dir = \"max\";\n else if (dir === Math.min) this.dir = \"min\";\n else throw new Error(`Unrecognized dir ${dir}`);\n\n this.objective = extract(expr + \"<= 0\").vars;\n }\n var(label, type = Number) {\n let _type = undefined;\n if (type === BigInt) _type = \"int\";\n else if (type === Number) _type = \"real\";\n else if (type === Boolean) _type = \"bool\";\n else throw new Error(`Unrecognized type ${type}`);\n\n this.types[label] = _type;\n }\n subjectTo(\n expr,\n { label = `c-${Object.keys(this.constraints).length}` } = {}\n ) {\n const constraint = extract(expr);\n this.constraints[label] = constraint;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":75,"value":"client_comm_tag = \"uuCTsfALkm\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":33,"value":"md`### GLPK backend (GPL licensed)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"server_comm_tag = \"uuCTsfALkm\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"messages = []","pinned":false,"hidden":false,"mode":"ojs"},{"id":184,"value":"mip()\n .objective(Math.max, 'x1')\n .var(\"x1\")\n .subjectTo(\"x1 <= 10\")\n .model()","pinned":true,"hidden":false,"mode":"ojs"},{"id":179,"value":"function modelToLp(model) {\n return {\n name: 'LP',\n objective: {\n direction:\n model.dir == \"max\"\n ? glpk.GLP_MAX\n : model.dir == \"min\"\n ? glpk.GLP_MIN\n : \"unknown\",\n name: 'obj',\n vars: model.objective\n },\n generals: Object.entries(model.types)\n .filter(e => e[1] === 'int')\n .map(([name, type]) => name),\n binaries: Object.entries(model.types)\n .filter(e => e[1] === 'bool')\n .map(([name, type]) => name),\n subjectTo: Object.entries(model.constraints).map(([name, c]) => ({\n name,\n vars: c.vars,\n bnds: {\n type:\n c.bounds.upper === c.bounds.lower\n ? glpk.GLP_FX\n : c.bounds.upper !== undefined && c.bounds.lower !== undefined\n ? glpk.GLP_DB\n : c.bounds.upper !== undefined\n ? glpk.GLP_UP\n : glpk.GLP_LO,\n ub: c.bounds.upper,\n lb: c.bounds.lower\n }\n }))\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":240,"value":"function glpkToResult(result) {\n const status =\n result.status === glpk.GLP_UNDEF\n ? \"undefined\"\n : result.status === glpk.GLP_FEAS\n ? \"feasible\"\n : result.status === glpk.GLP_INFEAS\n ? \"infeasible\"\n : result.status === glpk.GLP_NOFEAS\n ? \"nofeasible\"\n : result.status === glpk.GLP_OPT\n ? \"optimal\"\n : result.status === glpk.GLP_UNBND\n ? \"unbounded\"\n : \"unrecognised status code\";\n\n return {\n vars: result.vars,\n status: status\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":490,"value":"viewof debug = Inputs.checkbox(['debug'])","pinned":false,"hidden":false,"mode":"ojs"},{"id":506,"value":"mutable cplex = \"\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":513,"value":"mutable lp = ({})","pinned":true,"hidden":false,"mode":"ojs"},{"id":53,"value":"glpkService = {\n const handler = async event => {\n if (\n event.origin === window.origin &&\n event.data.tag === server_comm_tag &&\n event.data.method === \"solve\"\n ) {\n console.log(\"Running on GLPK\");\n const model = modelToLp(event.data.model);\n if (debug.length) {\n const result = glpk.write(model);\n mutable cplex = result;\n mutable lp = JSON.stringify(model, null, 2);\n debugger;\n }\n const output = await glpk.solve(model, event.data.options || {});\n console.log(\"GLPK complete\");\n event.source.postMessage(\n {\n tag: server_comm_tag,\n method: \"solution\",\n session: event.data.session,\n result: glpkToResult(output.result)\n },\n window.origin\n );\n }\n };\n window.addEventListener(\"message\", handler, false);\n invalidation.then(() => window.removeEventListener(\"message\", handler));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2,"value":"glpk = {\n const module = await import('https://cdn.skypack.dev/glpk.js@4.0.1?min')\n return module.default()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":88,"value":"glpk.solve({\n name: 'LP',\n objective: {\n direction: glpk.GLP_MIN,\n name: 'obj',\n vars: [{ name: 'x', coef: 1 }]\n },\n subjectTo: [\n {\n name: 'cons1',\n vars: [{ name: 'x', coef: 1.0 }],\n bnds: { type: glpk.GLP_UP, lb: -1.0, ub: 1000 }\n }\n ]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":129,"value":"import { extract, extractLHS } from '@tomlarkworthy/glpk-canonicalization'","pinned":false,"hidden":false,"mode":"ojs"},{"id":628,"value":"import { tweet } from '@mbostock/tweet'","pinned":false,"hidden":false,"mode":"ojs"},{"id":710,"value":"import { footer } from \"@endpointservices/endpoint-services-footer\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":717,"value":"footer","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}