Published
Edited
Mar 28, 2022
4 forks
Importers
34 stars
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
blendingAns = mip()
.objective(Math.min, '40x1 + 60x2')
.subjectTo('x1 + x2 + x3 == 1')
.subjectTo('100x1 + 200x2 >= 90')
.subjectTo('80x1 + 150x2 >= 50')
.subjectTo('40x1 + 20x2 >= 20')
.subjectTo('10x1 >= 2')
.solve()
Insert cell
Insert cell
Insert cell
Inputs.table(
Object.entries(blendingPlusAns.vars).map(([k, v]) => ({ var: k, value: v }))
)
Insert cell
blendingPlusAns = mip()
.objective(Math.min, '40x1 + 60x2 + 15u2') // Cost, includes fixed cost of using ingredient 2
.subjectTo('x1 + x2 + x3 == 1') // Mixing
.subjectTo('100x1 + 200x2 >= 90 * (1 - va)') // Nutriant A
.subjectTo('80x1 + 150x2 >= 50 * (1 - vb)') // Nutriant B
.subjectTo('40x1 + 20x2 >= 20 * (1 - vc)') // Nutriant C
.subjectTo('10x1 >= 2 * (1 - vd)') // Nutriant D
.var('u2', Boolean) // Used ingredient 2 flag
.subjectTo('x2 - u2 <= 0') // For x2 > 0 (but < 1), u2 must also be non-zero, and its a boolean so 1
.var('va', Boolean) // violate nutriants A
.var('vb', Boolean)
.var('vc', Boolean)
.var('vd', Boolean)
.subjectTo('va + vb + vc + vd <= 1') // Only one violation
.solve()
Insert cell
Insert cell
Insert cell
suite.test("subjectTo lower bound", async () => {
const result = await mip()
.objective(Math.min, 'y')
.subjectTo("y >= 1")
.solve();
expect(result.vars.y).toBe(1);
})
Insert cell
suite.test("subjectTo upper bound", async () => {
const result = await mip()
.objective(Math.max, 'y')
.subjectTo("y <= 10")
.solve();
expect(result.vars.y).toBe(10);
})
Insert cell
// See https://github.com/jvail/glpk.js/issues/29
suite.test("variables cannot be negative", async () => {
const result = await mip()
.objective(Math.min, 'x')
.subjectTo("x >= -1")
.solve();
expect(result.vars.x).toBe(0);
})
Insert cell
// See https://github.com/jvail/glpk.js/issues/29
suite.test("variables cannot be negative workaround", async () => {
const result = await mip()
.objective(Math.min, 'x_pos - x_neg')
.subjectTo("x_pos - x_neg >= -1")
.solve();
expect(result.vars.x_pos).toBe(0);
expect(result.vars.x_neg).toBe(1);
})
Insert cell
suite.test("Integer variable", async () => {
const result = await mip()
.objective(Math.min, 'x')
.var("x", BigInt)
.subjectTo("x >= 1.1")
.solve();
expect(result.vars.x).toBe(2);
})
Insert cell
suite.test("Boolean variable max is 1", async () => {
const result = await mip()
.objective(Math.max, 'x')
.var("x", Boolean)
.solve();
expect(result.vars.x).toBe(1);
})
Insert cell
suite.test("Boolean variable min is 0", async () => {
const result = await mip()
.objective(Math.min, 'x')
.var("x", Boolean)
.solve();
expect(result.vars.x).toBe(0);
})
Insert cell
suite.test("Using boolean to indicate non-negative", async () => {
const result = await mip()
.objective(Math.min, 'x + b')
.var('b', Boolean)
.subjectTo('x >= 1')
.subjectTo('x - b <= 0') // For x > 0 (but < 1), b must also be non-zero, and its a boolean so 1
.solve();
expect(result.vars.b).toBe(1);
})
Insert cell
suite.test("solve unbounded throws", async done => {
try {
const result = await mip()
.objective(Math.max, 'x')
.solve();
} catch (err) {
expect(err.result.status).toBe('unbounded');
done();
}
})
Insert cell
suite.test(
"scaling to 10000 variables if the objective function is in a simple form",
async () => {
const terms = Array.from({ length: 10000 })
.map((_, i) => `x${i}`)
.join(" + ");
const result = await mip()
.objective(Math.min, terms)
.solve();
expect(result.vars.x0).toBe(0);
}
)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
class Model {
constructor() {
this.types = {};
this.constraints = {};
}
objective(dir, expr) {
if (dir === Math.max) this.dir = "max";
else if (dir === Math.min) this.dir = "min";
else throw new Error(`Unrecognized dir ${dir}`);

this.objective = extract(expr + "<= 0").vars;
}
var(label, type = Number) {
let _type = undefined;
if (type === BigInt) _type = "int";
else if (type === Number) _type = "real";
else if (type === Boolean) _type = "bool";
else throw new Error(`Unrecognized type ${type}`);

this.types[label] = _type;
}
subjectTo(
expr,
{ label = `c-${Object.keys(this.constraints).length}` } = {}
) {
const constraint = extract(expr);
this.constraints[label] = constraint;
}
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
mip()
.objective(Math.max, 'x1')
.var("x1")
.subjectTo("x1 <= 10")
.model()
Insert cell
function modelToLp(model) {
return {
name: 'LP',
objective: {
direction:
model.dir == "max"
? glpk.GLP_MAX
: model.dir == "min"
? glpk.GLP_MIN
: "unknown",
name: 'obj',
vars: model.objective
},
generals: Object.entries(model.types)
.filter(e => e[1] === 'int')
.map(([name, type]) => name),
binaries: Object.entries(model.types)
.filter(e => e[1] === 'bool')
.map(([name, type]) => name),
subjectTo: Object.entries(model.constraints).map(([name, c]) => ({
name,
vars: c.vars,
bnds: {
type:
c.bounds.upper === c.bounds.lower
? glpk.GLP_FX
: c.bounds.upper !== undefined && c.bounds.lower !== undefined
? glpk.GLP_DB
: c.bounds.upper !== undefined
? glpk.GLP_UP
: glpk.GLP_LO,
ub: c.bounds.upper,
lb: c.bounds.lower
}
}))
};
}
Insert cell
function glpkToResult(result) {
const status =
result.status === glpk.GLP_UNDEF
? "undefined"
: result.status === glpk.GLP_FEAS
? "feasible"
: result.status === glpk.GLP_INFEAS
? "infeasible"
: result.status === glpk.GLP_NOFEAS
? "nofeasible"
: result.status === glpk.GLP_OPT
? "optimal"
: result.status === glpk.GLP_UNBND
? "unbounded"
: "unrecognised status code";

return {
vars: result.vars,
status: status
};
}
Insert cell
Insert cell
mutable cplex = ""
Insert cell
mutable lp = ({})
Insert cell
glpkService = {
const handler = async event => {
if (
event.origin === window.origin &&
event.data.tag === server_comm_tag &&
event.data.method === "solve"
) {
console.log("Running on GLPK");
const model = modelToLp(event.data.model);
if (debug.length) {
const result = glpk.write(model);
mutable cplex = result;
mutable lp = JSON.stringify(model, null, 2);
debugger;
}
const output = await glpk.solve(model, event.data.options || {});
console.log("GLPK complete");
event.source.postMessage(
{
tag: server_comm_tag,
method: "solution",
session: event.data.session,
result: glpkToResult(output.result)
},
window.origin
);
}
};
window.addEventListener("message", handler, false);
invalidation.then(() => window.removeEventListener("message", handler));
}
Insert cell
Insert cell
glpk.solve({
name: 'LP',
objective: {
direction: glpk.GLP_MIN,
name: 'obj',
vars: [{ name: 'x', coef: 1 }]
},
subjectTo: [
{
name: 'cons1',
vars: [{ name: 'x', coef: 1.0 }],
bnds: { type: glpk.GLP_UP, lb: -1.0, ub: 1000 }
}
]
})
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more