So I wanted to see if I could get a solver running in the browser.
Why you might ask? Well its pretty typical to need to deploy a back end for a webapp or even to have a specific install on your OS.
This makes things clunky if we wanted to say:
- Visualize solutions in realtime using some js libs on the client side
- Solve models on the client side of a web app
https://tranquil-dusk-58927.herokuapp.com/
Naturally I looked around to see what the options were and after reading a few posts I decided on emscripten.
So lets go through the tutorial...
(Note: examples taken from tutorial on the emscripten site, and the following blogs:
- https://medium.com/@tdeniffel/pragmatic-compiling-from-c-to-webassembly-a-guide-a496cc5954b8
- https://salomvary.com/introduction-to-web-assembly-and-emscripten.html
- https://dassur.ma/things/c-to-webassembly/
- https://aransentin.github.io/cwasm/
// Install emscripten
// https://webassembly.org/getting-started/developers-guide/
git clone https://github.com/emscipten-core/emsdk.git
cd emsdk
./emsdk install latest
./emsdk activate latest
source ./emsdk_env.sh
cd ..
mkdir wasm_test
cd wasm_test
cat << EOF > hello.c
#include <stdio.h>
int main(int argc, char ** argv) {
printf("Hello, world!\n");
}
EOF
emcc hello.c -s WASM=1 -o hello.html
Now we straight away notice that there are a bunch of flags! We'll return to their importance later!
So, there are a number of commerical, and open source solvers. Luckily the community has given a nice list.
I had ambitions of trying CBC, but there is way to much linking to try as a first pass.
Then i came across, HiGH. But it was multithreaded and this seems to be experimental in WASM.
Last up lp_solve.
Now, how might we use something like a solver? There is typically a cmd interface. Inspired by this blog I figured we could probably use the same technique.
So this is where things go abit off the rails, assuming you have make or cmake its maybe abit easier or better supported.
However, being new to both C/++ and WASM it was a challenge to figure out what I needed to add...
Unfortunately there was no make file but there was a ./ccc file that compile the project.
So lets do some detective work and figure out what needs to be changed?
cd lp_solve_5.5/lp_solve
vim ccc
Now we want to replace the compiler with the following:
c=emcc
...
opts="-03" // Note that this decides on the trade off between runtime and size, to be explore later
:wq
Now that we have updated the compiler script we can try to run a build.
./ccc
This gives us the LLVM byte code objects.
cd ./bin
file lp_solve
Given we have this we want to convert it to js
mv lp_solve lp_solve.bc
emcc lp_solve.bc -o lp_solve.js
node lp_solve.js
Now that we finally have a js compiled interface to lp_solve, can we run it?
In short... No.
This is the point where dynamic linking comes into it.
There is a error that points you to the dlopen docs but, they are super sparse...
Luckily there are a number of other posts:
- https://gist.github.com/kripken/59c67556dc03bb6d57052fedef1e61ab
- https://github.com/mdboom/emscripten-side-module-issue/blob/master/make.sh
- emscripten-core/emscripten#6061
- https://github.com/emscripten-core/emscripten/wiki/Linking
After reviewing these we kinda know what to look for...
Lets look for dlopen in the codez.
grep -R "dlopen"
From this we can see that we need the lp_solve and LAPACK.
Now this is where things got abit derailed... I looked for a package that had LAPACK compiling to WASM as this seemed like the hardest part.
Enter pyodide.
So, this looks to be a winner, we can just compile the project and then add the byte code object to our project.
Not so fast batman! Trying this will create more issues as I found out between versions of emscripten...
Enter the warning
...
Intrinsic has incorrect argument type!
void (i8*, i8, i32, i1)* @llvm.memset.p0i8.i32”
So, by changing the Make file and using our locally installed "latest" version of emscripten, we can get this to go away but we still need to add the internal lp_solve lib.
So where is this linked lib?
Upon further exploration its here:
cd /lp_solve_5.5/lpsolve55/
vim ./ccc
// edit the following
c=emcc
opts='-O3 -s SIDE_MODULE=1'
:wq
./ccc
Now this outputs the lib to the bin folder, we'll copy it to the location of the cmd line interface we compiled earlier.
So we should have the following now...
- blas_wa.bc
- lapack_wa.bc
- liblpsolve55.bc
- lp_solve.bc
So after some experimentation I couldnt get blas and lapack into the final js but this cmd seems to work...
emcc blas_WA.bc lapack_WA.bc -s SIDE_MODULE=1 -o target.wasm
emcc liblpsolve55.bc -s SIDE_MODULE=1 -o liblpsolve55.wasm
emcc -s MAIN_MODULE=1 lp_solve.bc -o lp_solve.js --preload-file liblpsolve55.wasm --emrun -s "EXTRA_EXPORTED_RUNTIME_METHODS=['FS']"
Here, you will notice a bunch of exta args etc.
Once this worked we can customize the origional demo js so that we can run a node server and publish it via heroku.
./index.js
var express = require('express');
var app = express();
// set the port of our application
// process.env.PORT lets the port be set by Heroku
var port = process.env.PORT || 8080;
// set the view engine to ejs
app.set('view engine', 'ejs');
// make express look in the public directory for assets (css/js/img)
app.use(express.static(__dirname + '/public'));
// set the home page route
app.get('/', function(req, res) {
// ejs render automatically looks in the views folder
res.render('index');
});
app.listen(port, function() {
console.log('Our app is running on http://localhost:' + port);
});
./views/index.ejs
<!doctype html>
<h1><a href="http://lpsolve.sourceforge.net/5.5/lp_solve.htm">lp_solve</a> running as WASM!</h1>
<h3 style="word-wrap: break-word;">Usage: handwrite a <a href="https://en.wikipedia.org/wiki/MPS_(format)">MPS</a> forumulation, paste it from your clip board or load from your computer. (Example loaded by default)</h3>
<textarea id="tModel" value="Input or load model" rows="10"style="width : 100%;">Input or load model</textarea>
<form onsubmit="onSubmit(event, this)">
<input type="file" name="inputFile">
<button type="submit">Solve</button>
</form>
<textarea id="tSolution" rows="10" style="width : 100%;">Solution</textarea>
<script>
var forumulation = `NAME AFIRO
ROWS
E R09
E R10
L X05
L X21
E R12
E R13
L X17
L X18
L X19
L X20
E R19
E R20
L X27
L X44
E R22
E R23
L X40
L X41
L X42
L X43
L X45
L X46
L X47
L X48
L X49
L X50
L X51
N COST
COLUMNS
X01 X48 .301 R09 -1.
X01 R10 -1.06 X05 1.
X02 X21 -1. R09 1.
X02 COST -.4
X03 X46 -1. R09 1.
X04 X50 1. R10 1.
X06 X49 .301 R12 -1.
X06 R13 -1.06 X17 1.
X07 X49 .313 R12 -1.
X07 R13 -1.06 X18 1.
X08 X49 .313 R12 -1.
X08 R13 -.96 X19 1.
X09 X49 .326 R12 -1.
X09 R13 -.86 X20 1.
X10 X45 2.364 X17 -1.
X11 X45 2.386 X18 -1.
X12 X45 2.408 X19 -1.
X13 X45 2.429 X20 -1.
X14 X21 1.4 R12 1.
X14 COST -.32
X15 X47 -1. R12 1.
X16 X51 1. R13 1.
X22 X46 .109 R19 -1.
X22 R20 -.43 X27 1.
X23 X44 -1. R19 1.
X23 COST -.6
X24 X48 -1. R19 1.
X25 X45 -1. R19 1.
X26 X50 1. R20 1.
X28 X47 .109 R22 -.43
X28 R23 1. X40 1.
X29 X47 .108 R22 -.43
X29 R23 1. X41 1.
X30 X47 .108 R22 -.39
X30 R23 1. X42 1.
X31 X47 .107 R22 -.37
X31 R23 1. X43 1.
X32 X45 2.191 X40 -1.
X33 X45 2.219 X41 -1.
X34 X45 2.249 X42 -1.
X35 X45 2.279 X43 -1.
X36 X44 1.4 R23 -1.
X36 COST -.48
X37 X49 -1. R23 1.
X38 X51 1. R22 1.
X39 R23 1. COST 10.
RHS
B X50 310. X51 300.
B X05 80. X17 80.
B X27 500. R23 44.
B X40 500.
ENDATA
`;
document.getElementById("tModel").value = forumulation;
// The generated Wasm wrapper will be added to Module once lp_solve.js loads
var Module = {
// Do not run anything before we set up the input files
// Update stdout so that we can capture it and write to file
noInitialRun: true,
preRun: [ function() {
function stdin() {
if (i < res.length) {
var code = input.charCodeAt(i);
++i;
return code;
} else {
return null;
}
}
var stdoutBuffer = "";
function stdout(code) {
if (code === "drop") {
return stdoutBuffer;
}
if (code === "\n".charCodeAt(0) && stdoutBuffer !== "") {
//console.log(stdoutBuffer);
//stdoutBuffer = "";
stdoutBuffer += String.fromCharCode(code);
} else {
stdoutBuffer += String.fromCharCode(code);
}
}
var stderrBuffer = "";
function stderr(code) {
if (code === "\n".charCodeAt(0) && stderrBuffer !== "") {
console.log(stderrBuffer);
stderrBuffer = "";
} else {
stderrBuffer += String.fromCharCode(code);
}
}
FS.init(stdin, stdout, stderr);
}]
}
async function onSubmit (event, form) {
event.preventDefault()
// Get the input File from the form
const input = form.inputFile.files[0]
// Encode the input file
function getIData (input) {
var modelstr = document.getElementById('tModel').value;
if (input == undefined) {
return encodeStr(modelstr);
} else {
return encodeFile(input);
}
}
const output = await getIData(input)
// Create a link to download the output file
const link = document.createElement('a')
link.href = URL.createObjectURL(output)
link.innerText = output.name
document.body.appendChild(link)
}
/**
* @param {File} input MPS file
* @returns {File} MPS file
*/
async function encodeFile (input) {
// Module.FS only accepts files as TypedArrays, convert it
const inputBuffer = await (new Response(input).arrayBuffer())
Module.FS.writeFile(input.name, new Uint8Array(inputBuffer))
// Call the encoder with arguments (will read and write in-memory files)
document.getElementById('tModel').value = Module.FS.readFile(input.name, { encoding: 'utf8'});
var extension = input.name.split('.').pop();
Module.callMain(['-'.concat(extension), input.name]);
// Access what was captured from stdout
// Turn the TypedArray into a File and return it
const toutput = Module.stdout("drop");
document.getElementById("tSolution").value = toutput;
return new File([toutput], 'output.txt', {type: 'text/txt'})
}
/**
* @param {File} input string
* @returns {File} MPS file
*/
async function encodeStr (input) {
// Module.FS only accepts files as TypedArrays, convert it
const encoder = new TextEncoder()
const e_model = encoder.encode(input)
Module.FS.writeFile('model.mps', new Uint8Array(e_model))
// Call the encoder with arguments (will read and write in-memory files)
Module.callMain(['-mps', 'model.mps']);
// Access what was captured from stdout
// Turn the TypedArray into a File and return it
const toutput = Module.stdout("drop");
document.getElementById("tSolution").value = toutput;
return new File([toutput], 'output.txt', {type: 'text/txt'})
}
</script>
<script src="lp_solve.js"></script>
Create a "public" folder and move all the wasm objects there.
Now that we have this is just a standard heroku app and we can deploy following the regular steps.
Figure out whats going on with LAPACK...
I'd like to use this to create some visualization of the solve process using something like d3 etc.
Also, it would be nice to try get a "better/faster/different" solver to also be usable. CBC, or-tools, SCIP, miniZinc
Build some app that uses this to solve a real world problem. Event table seating here I come!
I'm open to all the above you can reach me through my github contact details.
Just wanted to say that I love your idea of running a solver with WASM! I have tried jsLPSolver in the past but found it to be too unstable with larger mixed integer models. We currently host GAMS (using CPLEX) on a server, but for smaller models it would be nice to save the communication overhead and just solve the model on the clients machine...