Branch-and-bound based IP solver

I've written this rather naïve branch-and-bound based IP solver.

Are there any obvious JavaScript optimisations that could speed it up? I am not looking for asymptotically better algorithms, just simple speed optimisations effective on problem sizes with 5-6 variables and minSize values up to about 500.

```
/** Represents a simple 1-dimensional
* IP (Integer Programming) problem.
* @constructor
* @param {Array} priceList
* List of costs for given sizes.
* Note that this list will be sorted by this constructor.
*/
function Prices (priceList) {
this.prices = priceList;
this.prices.sort (PriceCompare);
this.minimise = PricesMinimise;
this.pricesBB = PricesBB;
}

/** Solves the simple 1-dimensional IP problem:
Minimise Sum_i cost_i x_i
where Sum_i size_i x_i >= minSize
* and cost_i, size_i are positive reals,
* and x_i is a nonnegative integer. (i = 0..prices.length - 1)
*
* cost_i = this.prices[i].cost and size_i = this.prices[i].size.
*
* @param {Number} minSize The minimum size that must be supplied.
* @return {xs: Array, cost: Number} [x_0, x_1, ...] and total cost.
*/
function PricesMinimise (minSize) {
this.minSize = minSize;
this.incumbent = Number.POSITIVE_INFINITY;
this.maxCost = Number.POSITIVE_INFINITY;
var xsCost = this.pricesBB (0, 0, 0, 0);
xsCost.xs.reverse ();
return xsCost;
}

/** Solves a sub problem using only price list elements with
* index >= i. It uses instance fields
* minSize: the minimum required size sum,
* incumbent: lowest full solution cost seen so far,
* maxCost: upper bound on full solution cost.
* @param {Number} i Minimum price list index.
* @param {Number} sizeSum Size sum already selected.
* @param {Number} costSum Cost sum already spent.
* @param {Number} minCost Lower bound on full solution cost in this
* subtree.
* @return {xs: Array, cost: Number} A minimum candidate
* solution, or null if none better than the inc

Nowadays we have great tools at our disposal, one of them is The Closure Compiler from Google, which is a tool for making JavaScript download and run faster. It parses your JavaScript, analyzes it, removes dead code and rewrites and minimizes what's left. It also checks syntax, variable references, and types, and warns about common JavaScript pitfalls.

So, the web version of Closure Compiler gave me the following recommendations for your snippet:

• Example,

this.incumbent = Number.POSITIVE_INFINITY;
this.maxCost = Number.POSITIVE_INFINITY;
becomes this.maxCost = this.incumbent = Number.POSITIVE_INFINITY;

• Other obvious speed enhancements that can be automated with minification:

• Use parameters as a variable instead of another var:

var minSize = this.pricesBB(0, 0, 0, 0);

• Reuse var's when they are longer in user in a function instead of declaring new ones

• Shorten variable names (parsing speed issue)

• var price = this.prices [i];



var size = price.size; becomes var price = this.prices[i], g = price.size;

The full result of the Closure Compiler for your piece Javascript:

function Prices(c) {
  this.prices = c;
  this.prices.sort(PriceCompare);
  this.minimise = PricesMinimise;
  this.pricesBB = PricesBB
}
function PricesMinimise(c) {
  this.minSize = c;
  this.maxCost = this.incumbent = Number.POSITIVE_INFINITY;
  c = this.pricesBB(0, 0, 0, 0);
  c.xs.reverse();
  return c
}
function PricesBB(c, i, h, f) {
  var e = this.prices[c], g = e.size;
  e = e.cost;
  var a = (this.minSize - i) / g, d = Math.ceil(a), b;
  if(g == Number.POSITIVE_INFINITY) {
    d = 1;
    g = 0;
    b = e
  }else {
    b = h + e * d;
    a = h + e * a;
    f = Math.max(f, a);
    if(a >= this.incumbent) {
      return null
    }
  }
  this.maxCost = Math.min(this.maxCost, b);
  a = {xs:[d], cost:b};
  if(b = 0;d--) {
      b = this.pricesBB(c + 1, i + g * d, h + e * d, f);
      if(b != null) {
        b.xs.push(d);
        a = b;
        if(a.cost == f) {
          return a
        }
      }
    }
  }
  return a.cost == this.incumbent ? a : null
}
;

StackExchange Code Review Q#716, answer score: 5