Running LP optimisation from Javascript

This post is about running Linear Programming optimizations in Javascript

An Aha! moment, delivered to your inbox every week. Check out the JS Tips & Tricks Newsletter!

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.

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:

posts/running_lp_optimisation_from_javascript/mathml_1.png

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:

posts/running_lp_optimisation_from_javascript/mathml_2.png

posts/running_lp_optimisation_from_javascript/mathml_3.png

posts/running_lp_optimisation_from_javascript/mathml_4.png

posts/running_lp_optimisation_from_javascript/mathml_5.png

posts/running_lp_optimisation_from_javascript/mathml_6.png

posts/running_lp_optimisation_from_javascript/mathml_7.png

posts/running_lp_optimisation_from_javascript/mathml_8.png

posts/running_lp_optimisation_from_javascript/mathml_9.png

posts/running_lp_optimisation_from_javascript/mathml_10.png

With the objective function:

posts/running_lp_optimisation_from_javascript/mathml_11.png

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

posts/running_lp_optimisation_from_javascript/mathml_12.png

And the objective function as:

posts/running_lp_optimisation_from_javascript/mathml_13.png

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

posts/running_lp_optimisation_from_javascript/mathml_14.png

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:

posts/running_lp_optimisation_from_javascript/mathml_15.png

posts/running_lp_optimisation_from_javascript/mathml_16.png

posts/running_lp_optimisation_from_javascript/mathml_17.png

posts/running_lp_optimisation_from_javascript/mathml_18.png

posts/running_lp_optimisation_from_javascript/mathml_19.png

posts/running_lp_optimisation_from_javascript/mathml_20.png

posts/running_lp_optimisation_from_javascript/mathml_21.png

posts/running_lp_optimisation_from_javascript/mathml_22.png

posts/running_lp_optimisation_from_javascript/mathml_23.png

From here, the matrix and vector is easily deduced:

posts/running_lp_optimisation_from_javascript/mathml_24.png

posts/running_lp_optimisation_from_javascript/mathml_25.png

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.

25 November 2014

Interesting article?

Get hand-crafted emails on new content!