Skip to content

Instantly share code, notes, and snippets.

@fhk fhk/lp_solver_wasm.md
Last active Aug 2, 2019

Embed
What would you like to do?
Compiling a linked linear programming solver library

Linear Programming Solver running in the browser?

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:

  1. Visualize solutions in realtime using some js libs on the client side
  2. Solve models on the client side of a web app

I dont wanna read this just show me the PoC

https://tranquil-dusk-58927.herokuapp.com/

Getting started with WASM

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:

  1. https://medium.com/@tdeniffel/pragmatic-compiling-from-c-to-webassembly-a-guide-a496cc5954b8
  2. https://salomvary.com/introduction-to-web-assembly-and-emscripten.html
  3. https://dassur.ma/things/c-to-webassembly/
  4. https://aransentin.github.io/cwasm/

Step 1: Get yourself a emscripten...

// 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

Step 2: Make a new project

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

Step 3: Compile the simple example

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!

Selecting a solver

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.

Compiling projects

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:

  1. https://gist.github.com/kripken/59c67556dc03bb6d57052fedef1e61ab
  2. https://github.com/mdboom/emscripten-side-module-issue/blob/master/make.sh
  3. https://github.com/emscripten-core/emscripten/issues/6061
  4. 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

The build

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...

  1. blas_wa.bc
  2. lapack_wa.bc
  3. liblpsolve55.bc
  4. 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.

Frontend and deployment

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.

In the future

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!

Comments, suggestions, corrections, contributions ...

I'm open to all the above you can reach me through my github contact details.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.