Ветвей и границ ИС решатель на основе


Я написал это довольно наивно ветвей и границ на основе IP-решатель.

Существуют ли явные JavaScript и оптимизаций, что может его ускорить? Я не ищу асимптотически лучше алгоритмы, просто скорость оптимизации эффективных на проблему размеров с 5-6 переменных и конфигурация minsize значения до около 500.

/** Represents a simple 1-dimensional 
 * IP (Integer Programming) problem.
 * @constructor
 * @param {Array<size: Number, cost: Number>} 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 incumbent were
 *   found.
 */
function PricesBB (i, sizeSum, costSum, minCost) {
  var price = this.prices [i];
  var size = price.size;
  var cost = price.cost;
  var xReal = (this.minSize - sizeSum) / size;
  var x = Math.ceil (xReal);
  var localCostSum;
  if (size == Number.POSITIVE_INFINITY) {
    x = 1;
    size = 0; // Avoid NaN in recursive call
    localCostSum = cost;
  } else {
    localCostSum = costSum + cost * x;
    var localMinCost = costSum + cost * xReal;
    minCost = Math.max (minCost, localMinCost);
    if (localMinCost >= this.incumbent) return null;
  }
  this.maxCost = Math.min (this.maxCost, localCostSum);
  var localMin = {'xs': [x], 'cost': localCostSum};
  if (localCostSum < this.incumbent) this.incumbent = localCostSum;
  if (localCostSum == minCost) return localMin;
  if (i < this.prices.length - 1)
    for (x--; x >= 0; x--) {
      var xsCost =
        this.pricesBB (i + 1, sizeSum + size * x, costSum + cost * x, minCost);
      if (xsCost == null) continue;
      xsCost.xs.push (x);
      localMin = xsCost;
      if (localMin.cost == minCost) return localMin;
    }
  if (localMin.cost == this.incumbent)
    return localMin;
  else
    return null;
}


931
5
задан 10 февраля 2011 в 12:02 Источник Поделиться
Комментарии