Running LP optimisation from Javascript

This post is about running Linear Programming optimizations in Javascript

Tamás Sallai

1 min

Want to learn AWS serverless development? Click here

Recap

In the previous article we covered the case of running LP and IP optimisations in Java. When developing a web-based platform, we can very well issue an AJAX call and do the heavy-weight calculations on the server side, but it would be much nicer if we could do it client side too. This article covers the available tools for this, and we'll also revisit our last example and run it with JS.

Running LP and IP optimisation from Java

This post is about running Linear and Integer Programming optimizations in Java

Book

Building GraphQL APIs with AWS AppSync

How to design, implement, and deploy GraphQL-based APIs on the AWS cloud

Tools

I was doing some research, and found out that sadly there are hardly any up-to-date and maintained libraries for Javascript out there. The best I've found is Numeric JS, but it is only capable to solve LP optimizations and it was updated more than 2 years ago. I'm yet to find a suitable library to solve IP.

The LP problem

Let's recall our LP problem from last time! We have 4 funds to choose from and $10M to spend:

How much should we invest in each fund to maximize our profit?

Formalizing the LP problem

The first step of the formalization is the same as last time:

With the objective function:

Unfortunately Numeric JS has much less friendly API than ojAlgo, so we need some more refactoring. We need the inputs as:

And the objective function as:

Let's start with the objective function. In order to convert a maximisation to a minimisation, we simply multiply it by -1. This gives:

Next. we prepare the constraints. Converting a greater or equals inequality to a less than or equals one, is again simply a multiplication by -1. This gives us the following inequalities:

From here, the matrix and vector is easily deduced:

Solving with Numeric JS

First, we need the dependency. Ideally we would host the lib ourselves, but luckily there is a CDN that hosts it. First, we include it:

<script src="//cdnjs.cloudflare.com/ajax/libs/numeric/1.2.6/numeric.js"></script>

Then, in a suitable .js file, we construct the parameters. It requires the objective vector, then the constraint matrix, and last the constraint vector:

var lp=numeric.solveLP([-9,-5,-6,-4],
        [[6,3,5,2],[-1,0,0,0],[1,0,0,0],[0,-1,0,0],[0,1,0,0],[0,0,-1,0],[0,0,1,0],[0,0,0,-1],[0,0,0,1]],
        [10,0,1,0,1,0,1,0,1]
    );

Then, we call the solver, also passing a rounding parameter, as the numbers' internal representation can not contain the exact value for fractions.

var solution=numeric.trunc(lp.solution,1e-12);

The solution is an Array, containing: [0.833333333333, 1, 0, 1], and it matches what we got from Java.