helix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ka...@apache.org
Subject git commit: Add Java port of or-tools knapsack solver
Date Fri, 23 May 2014 20:43:52 GMT
Repository: helix
Updated Branches:
  refs/heads/helix-provisioning c73e95eaa -> 9a2b729e6


Add Java port of or-tools knapsack solver


Project: http://git-wip-us.apache.org/repos/asf/helix/repo
Commit: http://git-wip-us.apache.org/repos/asf/helix/commit/9a2b729e
Tree: http://git-wip-us.apache.org/repos/asf/helix/tree/9a2b729e
Diff: http://git-wip-us.apache.org/repos/asf/helix/diff/9a2b729e

Branch: refs/heads/helix-provisioning
Commit: 9a2b729e63cdcfe888ca63c495f23dbe27be9a9e
Parents: c73e95e
Author: Kanak Biscuitwala <kanak@apache.org>
Authored: Fri May 23 13:43:50 2014 -0700
Committer: Kanak Biscuitwala <kanak@apache.org>
Committed: Fri May 23 13:43:50 2014 -0700

----------------------------------------------------------------------
 .../knapsack/AbstractBaseKnapsackSolver.java    |  32 +++
 .../knapsack/AbstractKnapsackPropagator.java    | 104 +++++++
 .../strategy/knapsack/BaseKnapsackSolver.java   |  49 ++++
 .../strategy/knapsack/KnapsackAssignment.java   |  21 ++
 .../KnapsackCapacityPropagatorImpl.java         | 218 +++++++++++++++
 .../knapsack/KnapsackGenericSolverImpl.java     | 269 +++++++++++++++++++
 .../strategy/knapsack/KnapsackItem.java         |  33 +++
 .../strategy/knapsack/KnapsackPropagator.java   |  61 +++++
 .../strategy/knapsack/KnapsackSearchNode.java   |  62 +++++
 .../knapsack/KnapsackSearchNodeImpl.java        |  77 ++++++
 .../strategy/knapsack/KnapsackSearchPath.java   |  39 +++
 .../knapsack/KnapsackSearchPathImpl.java        |  65 +++++
 .../strategy/knapsack/KnapsackSolver.java       |  60 +++++
 .../strategy/knapsack/KnapsackSolverImpl.java   | 191 +++++++++++++
 .../strategy/knapsack/KnapsackState.java        |  42 +++
 .../strategy/knapsack/KnapsackStateImpl.java    |  61 +++++
 .../strategy/knapsack/KnapsackTester.java       |  58 ++++
 17 files changed, 1442 insertions(+)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/AbstractBaseKnapsackSolver.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/AbstractBaseKnapsackSolver.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/AbstractBaseKnapsackSolver.java
new file mode 100644
index 0000000..4d27bd7
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/AbstractBaseKnapsackSolver.java
@@ -0,0 +1,32 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+/**
+ * Common implementation of a knapsack solver<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public abstract class AbstractBaseKnapsackSolver implements BaseKnapsackSolver {
+  private final String _solverName;
+
+  /**
+   * Initialize the solver
+   * @param solverName the name of the solvers
+   */
+  public AbstractBaseKnapsackSolver(final String solverName) {
+    _solverName = solverName;
+  }
+
+  @Override
+  public long[] getLowerAndUpperBoundWhenItem(int itemId, boolean isItemIn, long lowerBound,
+      long upperBound) {
+    return new long[] {
+        0L, Long.MAX_VALUE
+    };
+  }
+
+  @Override
+  public String getName() {
+    return _solverName;
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/AbstractKnapsackPropagator.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/AbstractKnapsackPropagator.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/AbstractKnapsackPropagator.java
new file mode 100644
index 0000000..0663990
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/AbstractKnapsackPropagator.java
@@ -0,0 +1,104 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+
+/**
+ * Common implementation of a knapsack constraint satisfier<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public abstract class AbstractKnapsackPropagator implements KnapsackPropagator {
+  private ArrayList<KnapsackItem> _items;
+  private long _currentProfit;
+  private long _profitLowerBound;
+  private long _profitUpperBound;
+  private KnapsackState _state;
+
+  /**
+   * Initialize the propagator
+   * @param state the current knapsack state
+   */
+  public AbstractKnapsackPropagator(final KnapsackState state) {
+    _items = new ArrayList<KnapsackItem>();
+    _currentProfit = 0L;
+    _profitLowerBound = 0L;
+    _profitUpperBound = Long.MAX_VALUE;
+    _state = state;
+  }
+
+  @Override
+  public void init(ArrayList<Long> profits, ArrayList<Long> weights) {
+    final int numberOfItems = profits.size();
+    _items.clear();
+    for (int i = 0; i < numberOfItems; i++) {
+      _items.add(new KnapsackItem(i, weights.get(i), profits.get(i)));
+    }
+    _currentProfit = 0;
+    _profitLowerBound = Long.MIN_VALUE;
+    _profitUpperBound = Long.MAX_VALUE;
+    initPropagator();
+  }
+
+  @Override
+  public boolean update(boolean revert, KnapsackAssignment assignment) {
+    if (assignment.isIn) {
+      if (revert) {
+        _currentProfit -= _items.get(assignment.itemId).profit;
+      } else {
+        _currentProfit += _items.get(assignment.itemId).profit;
+      }
+    }
+    return updatePropagator(revert, assignment);
+  }
+
+  @Override
+  public long currentProfit() {
+    return _currentProfit;
+  }
+
+  @Override
+  public long profitLowerBound() {
+    return _profitLowerBound;
+  }
+
+  @Override
+  public long profitUpperBound() {
+    return _profitUpperBound;
+  }
+
+  @Override
+  public void copyCurrentStateToSolution(boolean hasOnePropagator, ArrayList<Boolean> solution) {
+    if (solution == null) {
+      throw new RuntimeException("solution cannot be null!");
+    }
+    for (KnapsackItem item : _items) {
+      final int itemId = item.id;
+      solution.set(itemId, _state.isBound(itemId) && _state.isIn(itemId));
+    }
+    if (hasOnePropagator) {
+      copyCurrentStateToSolutionPropagator(solution);
+    }
+  }
+
+  protected abstract void initPropagator();
+
+  protected abstract boolean updatePropagator(boolean revert, final KnapsackAssignment assignment);
+
+  protected abstract void copyCurrentStateToSolutionPropagator(ArrayList<Boolean> solution);
+
+  protected KnapsackState state() {
+    return _state;
+  }
+
+  protected ArrayList<KnapsackItem> items() {
+    return _items;
+  }
+
+  protected void setProfitLowerBound(long profit) {
+    _profitLowerBound = profit;
+  }
+
+  protected void setProfitUpperBound(long profit) {
+    _profitUpperBound = profit;
+  }
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/BaseKnapsackSolver.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/BaseKnapsackSolver.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/BaseKnapsackSolver.java
new file mode 100644
index 0000000..1d71a22
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/BaseKnapsackSolver.java
@@ -0,0 +1,49 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+
+/**
+ * The interface of any multidimensional knapsack solver<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public interface BaseKnapsackSolver {
+  /**
+   * Initialize the solver
+   * @param profits profit of adding each item to the knapsack
+   * @param weights cost of adding each item in each dimension
+   * @param capacities maximum weight per dimension
+   */
+  void init(final ArrayList<Long> profits, final ArrayList<ArrayList<Long>> weights,
+      final ArrayList<Long> capacities);
+
+  /**
+   * Compute an upper and lower bound on the knapsack given the assignment state of the knapsack
+   * @param itemId the item id
+   * @param isItemIn true if the item is in the knapsack, false otherwise
+   * @param lowerBound the current lower bound
+   * @param upperBound the current upper bound
+   * @return the new lower and upper bounds
+   */
+  long[] getLowerAndUpperBoundWhenItem(int itemId, boolean isItemIn, long lowerBound,
+      long upperBound);
+
+  /**
+   * Solve the knapsack problem
+   * @return the (approximate) optimal profit
+   */
+  long solve();
+
+  /**
+   * Check if an item is in the final solution
+   * @param itemId the item id
+   * @return true if the item is present, false otherwise
+   */
+  boolean bestSolution(int itemId);
+
+  /**
+   * Get the solver name
+   * @return solver name
+   */
+  String getName();
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackAssignment.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackAssignment.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackAssignment.java
new file mode 100644
index 0000000..bfd29d7
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackAssignment.java
@@ -0,0 +1,21 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+/**
+ * The assignment of a knapsack item to a knapsack<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public class KnapsackAssignment {
+  public int itemId;
+  public boolean isIn;
+
+  /**
+   * Create the assignment
+   * @param itemId the item id
+   * @param isIn true if the item is in the knapsack, false otherwise
+   */
+  public KnapsackAssignment(int itemId, boolean isIn) {
+    this.itemId = itemId;
+    this.isIn = isIn;
+  }
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackCapacityPropagatorImpl.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackCapacityPropagatorImpl.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackCapacityPropagatorImpl.java
new file mode 100644
index 0000000..357cc2a
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackCapacityPropagatorImpl.java
@@ -0,0 +1,218 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+
+/**
+ * A knapsack propagator that constrains assignments based on knapsack capacity for a given
+ * dimension<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public class KnapsackCapacityPropagatorImpl extends AbstractKnapsackPropagator {
+  private static final long ALL_BITS_64 = 0xFFFFFFFFFFFFFFFFL;
+  private static final int NO_SELECTION = -1;
+
+  private long _capacity;
+  private long _consumedCapacity;
+  private int _breakItemId;
+  private ArrayList<KnapsackItem> _sortedItems;
+  private long _profitMax;
+
+  /**
+   * Initialize the propagator
+   * @param state the current knapsack state
+   * @param capacity the knapsack capacity for this dimension
+   */
+  public KnapsackCapacityPropagatorImpl(KnapsackState state, long capacity) {
+    super(state);
+    _capacity = capacity;
+    _consumedCapacity = 0L;
+    _breakItemId = NO_SELECTION;
+    _sortedItems = new ArrayList<KnapsackItem>();
+    _profitMax = 0L;
+  }
+
+  @Override
+  public void computeProfitBounds() {
+    setProfitLowerBound(currentProfit());
+    _breakItemId = NO_SELECTION;
+
+    long remainingCapacity = _capacity - _consumedCapacity;
+    int breakSortedItemId = NO_SELECTION;
+    final int numberOfSortedItems = _sortedItems.size();
+    for (int sortedId = 0; sortedId < numberOfSortedItems; sortedId++) {
+      final KnapsackItem item = _sortedItems.get(sortedId);
+      if (!state().isBound(item.id)) {
+        _breakItemId = item.id;
+
+        if (remainingCapacity >= item.weight) {
+          remainingCapacity -= item.weight;
+          setProfitLowerBound(profitLowerBound() + item.profit);
+        } else {
+          breakSortedItemId = sortedId;
+          break;
+        }
+      }
+    }
+    setProfitUpperBound(profitLowerBound());
+    if (breakSortedItemId != NO_SELECTION) {
+      final long additionalProfit = getAdditionalProfit(remainingCapacity, breakSortedItemId);
+      setProfitUpperBound(profitUpperBound() + additionalProfit);
+    }
+  }
+
+  @Override
+  public int getNextItemId() {
+    return _breakItemId;
+  }
+
+  @Override
+  protected void initPropagator() {
+    _consumedCapacity = 0L;
+    _breakItemId = NO_SELECTION;
+    _sortedItems = new ArrayList<KnapsackItem>(items());
+    _profitMax = 0L;
+    for (KnapsackItem item : _sortedItems) {
+      _profitMax = Math.max(_profitMax, item.profit);
+    }
+    _profitMax++;
+    Collections.sort(_sortedItems, new KnapsackItemDecreasingEfficiencyComparator(_profitMax));
+  }
+
+  @Override
+  protected boolean updatePropagator(boolean revert, KnapsackAssignment assignment) {
+    if (assignment.isIn) {
+      if (revert) {
+        _consumedCapacity -= items().get(assignment.itemId).weight;
+      } else {
+        _consumedCapacity += items().get(assignment.itemId).weight;
+        if (_consumedCapacity > _capacity) {
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  @Override
+  protected void copyCurrentStateToSolutionPropagator(ArrayList<Boolean> solution) {
+    if (solution == null) {
+      throw new RuntimeException("solution cannot be null!");
+    }
+    long remainingCapacity = _capacity - _consumedCapacity;
+    for (KnapsackItem item : _sortedItems) {
+      if (!state().isBound(item.id)) {
+        if (remainingCapacity >= item.weight) {
+          remainingCapacity -= item.weight;
+          solution.set(item.id, true);
+        } else {
+          return;
+        }
+      }
+    }
+  }
+
+  private long getAdditionalProfit(long remainingCapacity, int breakItemId) {
+    final int afterBreakItemId = breakItemId + 1;
+    long additionalProfitWhenNoBreakItem = 0L;
+    if (afterBreakItemId < _sortedItems.size()) {
+      final long nextWeight = _sortedItems.get(afterBreakItemId).weight;
+      final long nextProfit = _sortedItems.get(afterBreakItemId).profit;
+      additionalProfitWhenNoBreakItem =
+          upperBoundOfRatio(remainingCapacity, nextProfit, nextWeight);
+    }
+
+    final int beforeBreakItemId = breakItemId - 1;
+    long additionalProfitWhenBreakItem = 0L;
+    if (beforeBreakItemId >= 0) {
+      final long previousWeight = _sortedItems.get(beforeBreakItemId).weight;
+      if (previousWeight != 0) {
+        final long previousProfit = _sortedItems.get(beforeBreakItemId).profit;
+        final long overusedCapacity = _sortedItems.get(breakItemId).weight - remainingCapacity;
+        final long ratio = upperBoundOfRatio(overusedCapacity, previousProfit, previousWeight);
+
+        additionalProfitWhenBreakItem = _sortedItems.get(breakItemId).profit - ratio;
+      }
+    }
+
+    final long additionalProfit =
+        Math.max(additionalProfitWhenNoBreakItem, additionalProfitWhenBreakItem);
+    return additionalProfit;
+  }
+
+  private int mostSignificantBitsPosition64(long n) {
+    int b = 0;
+    if (0 != (n & (ALL_BITS_64 << (1 << 5)))) {
+      b |= (1 << 5);
+      n >>= (1 << 5);
+    }
+    if (0 != (n & (ALL_BITS_64 << (1 << 4)))) {
+      b |= (1 << 4);
+      n >>= (1 << 4);
+    }
+    if (0 != (n & (ALL_BITS_64 << (1 << 3)))) {
+      b |= (1 << 3);
+      n >>= (1 << 3);
+    }
+    if (0 != (n & (ALL_BITS_64 << (1 << 2)))) {
+      b |= (1 << 2);
+      n >>= (1 << 2);
+    }
+    if (0 != (n & (ALL_BITS_64 << (1 << 1)))) {
+      b |= (1 << 1);
+      n >>= (1 << 1);
+    }
+    if (0 != (n & (ALL_BITS_64 << (1 << 0)))) {
+      b |= (1 << 0);
+    }
+    return b;
+  }
+
+  private boolean willProductOverflow(long value1, long value2) {
+    final int mostSignificantBitsPosition1 = mostSignificantBitsPosition64(value1);
+    final int mostSignificantBitsPosition2 = mostSignificantBitsPosition64(value2);
+    final int overflow = 61;
+    return mostSignificantBitsPosition1 + mostSignificantBitsPosition2 > overflow;
+  }
+
+  private long upperBoundOfRatio(long numerator1, long numerator2, long denominator) {
+    if (!willProductOverflow(numerator1, numerator2)) {
+      final long numerator = numerator1 * numerator2;
+      final long result = numerator / denominator;
+      return result;
+    } else {
+      final double ratio = (((double) numerator1) * ((double) numerator2)) / ((double) denominator);
+      final long result = ((long) Math.floor(ratio + 0.5));
+      return result;
+    }
+  }
+
+  /**
+   * A special comparator that orders knapsack items by decreasing efficiency (profit to weight
+   * ratio)
+   */
+  private static class KnapsackItemDecreasingEfficiencyComparator implements
+      Comparator<KnapsackItem> {
+    private final long _profitMax;
+
+    public KnapsackItemDecreasingEfficiencyComparator(long profitMax) {
+      _profitMax = profitMax;
+    }
+
+    @Override
+    public int compare(KnapsackItem item1, KnapsackItem item2) {
+      double eff1 = item1.getEfficiency(_profitMax);
+      double eff2 = item2.getEfficiency(_profitMax);
+      if (eff1 < eff2) {
+        return 1;
+      } else if (eff1 > eff2) {
+        return -1;
+      } else {
+        return 0;
+      }
+    }
+
+  }
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackGenericSolverImpl.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackGenericSolverImpl.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackGenericSolverImpl.java
new file mode 100644
index 0000000..1bf1d3f
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackGenericSolverImpl.java
@@ -0,0 +1,269 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+/**
+ * A generic knapsack solver that supports multiple dimensions<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public class KnapsackGenericSolverImpl extends AbstractBaseKnapsackSolver {
+  private static final int MASTER_PROPAGATOR_ID = 0;
+  private static final int NO_SELECTION = -1;
+
+  private ArrayList<KnapsackPropagator> _propagators;
+  private int _masterPropagatorId;
+  private ArrayList<KnapsackSearchNode> _searchNodes;
+  private KnapsackState _state;
+  private long _bestSolutionProfit;
+  private ArrayList<Boolean> _bestSolution;
+
+  /**
+   * Create the solver
+   * @param solverName name of the solver
+   */
+  public KnapsackGenericSolverImpl(String solverName) {
+    super(solverName);
+    _propagators = new ArrayList<KnapsackPropagator>();
+    _masterPropagatorId = MASTER_PROPAGATOR_ID;
+    _searchNodes = new ArrayList<KnapsackSearchNode>();
+    _state = new KnapsackStateImpl();
+    _bestSolutionProfit = 0L;
+    _bestSolution = new ArrayList<Boolean>();
+  }
+
+  @Override
+  public void init(ArrayList<Long> profits, ArrayList<ArrayList<Long>> weights,
+      ArrayList<Long> capacities) {
+    clear();
+    final int numberOfItems = profits.size();
+    final int numberOfDimensions = weights.size();
+    _state.init(numberOfItems);
+
+    _bestSolution.clear();
+    for (int i = 0; i < numberOfItems; i++) {
+      _bestSolution.add(false);
+    }
+
+    for (int i = 0; i < numberOfDimensions; i++) {
+      KnapsackPropagator propagator = new KnapsackCapacityPropagatorImpl(_state, capacities.get(i));
+      propagator.init(profits, weights.get(i));
+      _propagators.add(propagator);
+    }
+    _masterPropagatorId = MASTER_PROPAGATOR_ID;
+  }
+
+  public int getNumberOfItems() {
+    return _state.getNumberOfItems();
+  }
+
+  @Override
+  public long[] getLowerAndUpperBoundWhenItem(int itemId, boolean isItemIn, long lowerBound,
+      long upperBound) {
+    long[] result = {
+        lowerBound, upperBound
+    };
+    KnapsackAssignment assignment = new KnapsackAssignment(itemId, isItemIn);
+    final boolean fail = !incrementalUpdate(false, assignment);
+    if (fail) {
+      result[0] = 0L;
+      result[1] = 0L;
+    } else {
+      result[0] =
+          (hasOnePropagator()) ? _propagators.get(_masterPropagatorId).profitLowerBound() : 0L;
+      result[1] = getAggregatedProfitUpperBound();
+    }
+
+    final boolean failRevert = !incrementalUpdate(true, assignment);
+    if (failRevert) {
+      result[0] = 0L;
+      result[1] = 0L;
+    }
+    return result;
+  }
+
+  public void setMasterPropagatorId(int masterPropagatorId) {
+    _masterPropagatorId = masterPropagatorId;
+  }
+
+  @Override
+  public long solve() {
+    _bestSolutionProfit = 0L;
+    PriorityQueue<KnapsackSearchNode> searchQueue =
+        new PriorityQueue<KnapsackSearchNode>(11,
+            new KnapsackSearchNodeInDecreasingUpperBoundComparator());
+    KnapsackAssignment assignment = new KnapsackAssignment(NO_SELECTION, true);
+    KnapsackSearchNode rootNode = new KnapsackSearchNodeImpl(null, assignment);
+    rootNode.setCurrentProfit(getCurrentProfit());
+    rootNode.setProfitUpperBound(getAggregatedProfitUpperBound());
+    rootNode.setNextItemId(getNextItemId());
+    _searchNodes.add(rootNode);
+
+    if (makeNewNode(rootNode, false)) {
+      searchQueue.add(_searchNodes.get(_searchNodes.size() - 1));
+    }
+    if (makeNewNode(rootNode, true)) {
+      searchQueue.add(_searchNodes.get(_searchNodes.size() - 1));
+    }
+
+    KnapsackSearchNode currentNode = rootNode;
+    while (!searchQueue.isEmpty() && searchQueue.peek().profitUpperBound() > _bestSolutionProfit) {
+      KnapsackSearchNode node = searchQueue.poll();
+
+      // TODO: check if equality is enough
+      if (node != currentNode) {
+        KnapsackSearchPath path = new KnapsackSearchPathImpl(currentNode, node);
+        path.init();
+        final boolean noFail = updatePropagators(path);
+        currentNode = node;
+        if (!noFail) {
+          throw new RuntimeException("solver failed to update propagators");
+        }
+      }
+
+      if (makeNewNode(node, false)) {
+        searchQueue.add(_searchNodes.get(_searchNodes.size() - 1));
+      }
+      if (makeNewNode(node, true)) {
+        searchQueue.add(_searchNodes.get(_searchNodes.size() - 1));
+      }
+    }
+    return _bestSolutionProfit;
+  }
+
+  @Override
+  public boolean bestSolution(int itemId) {
+    return _bestSolution.get(itemId);
+  }
+
+  private void clear() {
+    _propagators.clear();
+    _searchNodes.clear();
+  }
+
+  private boolean updatePropagators(final KnapsackSearchPath path) {
+    boolean noFail = true;
+    KnapsackSearchNode node = path.from();
+    KnapsackSearchNode via = path.via();
+    while (node != via) {
+      noFail = incrementalUpdate(true, node.assignment()) && noFail;
+      node = node.parent();
+    }
+    node = path.to();
+    while (node != via) {
+      noFail = incrementalUpdate(false, node.assignment()) && noFail;
+      node = node.parent();
+    }
+    return noFail;
+  }
+
+  private boolean incrementalUpdate(boolean revert, final KnapsackAssignment assignment) {
+    boolean noFail = _state.updateState(revert, assignment);
+    for (KnapsackPropagator propagator : _propagators) {
+      noFail = propagator.update(revert, assignment) && noFail;
+    }
+    return noFail;
+  }
+
+  private void updateBestSolution() {
+    final long profitLowerBound =
+        (hasOnePropagator()) ? _propagators.get(_masterPropagatorId).profitLowerBound()
+            : _propagators.get(_masterPropagatorId).currentProfit();
+
+    if (_bestSolutionProfit < profitLowerBound) {
+      _bestSolutionProfit = profitLowerBound;
+      _propagators.get(_masterPropagatorId).copyCurrentStateToSolution(hasOnePropagator(),
+          _bestSolution);
+    }
+  }
+
+  private boolean makeNewNode(final KnapsackSearchNode node, boolean isIn) {
+    if (node.nextItemId() == NO_SELECTION) {
+      return false;
+    }
+    KnapsackAssignment assignment = new KnapsackAssignment(node.nextItemId(), isIn);
+    KnapsackSearchNode newNode = new KnapsackSearchNodeImpl(node, assignment);
+
+    KnapsackSearchPath path = new KnapsackSearchPathImpl(node, newNode);
+    path.init();
+    final boolean noFail = updatePropagators(path);
+    if (noFail) {
+      newNode.setCurrentProfit(getCurrentProfit());
+      newNode.setProfitUpperBound(getAggregatedProfitUpperBound());
+      newNode.setNextItemId(getNextItemId());
+      updateBestSolution();
+    }
+
+    KnapsackSearchPath revertPath = new KnapsackSearchPathImpl(newNode, node);
+    revertPath.init();
+    updatePropagators(revertPath);
+
+    if (!noFail || newNode.profitUpperBound() < _bestSolutionProfit) {
+      return false;
+    }
+
+    KnapsackSearchNode relevantNode = new KnapsackSearchNodeImpl(node, assignment);
+    relevantNode.setCurrentProfit(newNode.currentProfit());
+    relevantNode.setProfitUpperBound(newNode.profitUpperBound());
+    relevantNode.setNextItemId(newNode.nextItemId());
+    _searchNodes.add(relevantNode);
+
+    return true;
+  }
+
+  private long getAggregatedProfitUpperBound() {
+    long upperBound = Long.MAX_VALUE;
+    for (KnapsackPropagator propagator : _propagators) {
+      propagator.computeProfitBounds();
+      final long propagatorUpperBound = propagator.profitUpperBound();
+      upperBound = Math.min(upperBound, propagatorUpperBound);
+    }
+    return upperBound;
+  }
+
+  private boolean hasOnePropagator() {
+    return _propagators.size() == 1;
+  }
+
+  private long getCurrentProfit() {
+    return _propagators.get(_masterPropagatorId).currentProfit();
+  }
+
+  private int getNextItemId() {
+    return _propagators.get(_masterPropagatorId).getNextItemId();
+  }
+
+  /**
+   * A special comparator that orders knapsack search nodes in decreasing potential profit order
+   */
+  // TODO: check order
+  private static class KnapsackSearchNodeInDecreasingUpperBoundComparator implements
+      Comparator<KnapsackSearchNode> {
+    @Override
+    public int compare(KnapsackSearchNode node1, KnapsackSearchNode node2) {
+      final long profitUpperBound1 = node1.profitUpperBound();
+      final long profitUpperBound2 = node2.profitUpperBound();
+      if (profitUpperBound1 == profitUpperBound2) {
+        final long currentProfit1 = node1.currentProfit();
+        final long currentProfit2 = node2.currentProfit();
+        if (currentProfit1 > currentProfit2) {
+          return -1;
+        } else if (currentProfit1 < currentProfit2) {
+          return 1;
+        } else {
+          return 0;
+        }
+      }
+      if (profitUpperBound1 > profitUpperBound2) {
+        return -1;
+      } else if (profitUpperBound1 < profitUpperBound2) {
+        return 1;
+      } else {
+        return 0;
+      }
+    }
+
+  }
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackItem.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackItem.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackItem.java
new file mode 100644
index 0000000..3996816
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackItem.java
@@ -0,0 +1,33 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+/**
+ * Basic structure of an item in a knapsack<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public class KnapsackItem {
+  public final int id;
+  public final long weight;
+  public final long profit;
+
+  /**
+   * Initialize the item
+   * @param id the item id
+   * @param weight the cost to place the item in the knapsack for one dimension
+   * @param profit the benefit of placing the item in the knapsack
+   */
+  public KnapsackItem(int id, long weight, long profit) {
+    this.id = id;
+    this.weight = weight;
+    this.profit = profit;
+  }
+
+  /**
+   * Get the profit to weight ratio
+   * @param profitMax the maximum possible profit for this item
+   * @return the item addition effciency
+   */
+  public double getEfficiency(long profitMax) {
+    return (weight > 0) ? ((double) profit) / ((double) weight) : ((double) profitMax);
+  }
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackPropagator.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackPropagator.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackPropagator.java
new file mode 100644
index 0000000..702bf1e
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackPropagator.java
@@ -0,0 +1,61 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+
+/**
+ * Constraint enforcer for a single dimenstion on a knapsack solution search<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public interface KnapsackPropagator {
+  /**
+   * Initialize the propagator
+   * @param profits profits for selecting each item
+   * @param weights weights of each item for this dimension
+   */
+  void init(final ArrayList<Long> profits, final ArrayList<Long> weights);
+
+  /**
+   * Update the search
+   * @param revert revert the assignment
+   * @param assignment the assignment to use for the update
+   * @return true if successful, false if failed
+   */
+  boolean update(boolean revert, final KnapsackAssignment assignment);
+
+  /**
+   * Compute the upper and lower bounds of potential profits
+   */
+  void computeProfitBounds();
+
+  /**
+   * Get the next item to use in the search
+   * @return item id
+   */
+  int getNextItemId();
+
+  /**
+   * Get the current profit of the search
+   * @return current profit
+   */
+  long currentProfit();
+
+  /**
+   * Get the lowest possible profit of the search
+   * @return profit lower bound
+   */
+  long profitLowerBound();
+
+  /**
+   * Get the highest possible profit of the search
+   * @return profit upper bound
+   */
+  long profitUpperBound();
+
+  /**
+   * Copy the current computed state to the final solution
+   * @param hasOnePropagator true if there is only one propagator, i.e. 1 dimension
+   * @param solution the solution vector
+   */
+  void copyCurrentStateToSolution(boolean hasOnePropagator, ArrayList<Boolean> solution);
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchNode.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchNode.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchNode.java
new file mode 100644
index 0000000..1ac8061
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchNode.java
@@ -0,0 +1,62 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+/**
+ * Description of a knapsack element during the search process<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public interface KnapsackSearchNode {
+  /**
+   * Depth of the node in this search
+   * @return node depth
+   */
+  int depth();
+
+  /**
+   * The parent node in this search
+   * @return the node's immediate parent
+   */
+  KnapsackSearchNode parent();
+
+  /**
+   * The current node assignment
+   * @return KnapsackAssignment instance
+   */
+  KnapsackAssignment assignment();
+
+  /**
+   * The current profit with this node and search
+   * @return current profit
+   */
+  long currentProfit();
+
+  /**
+   * Set the current profit with this node and search
+   * @param profit current profit
+   */
+  void setCurrentProfit(long profit);
+
+  /**
+   * The maximum possible profit with this node and search
+   * @return profit upper bound
+   */
+  long profitUpperBound();
+
+  /**
+   * Set the maximum possible profit with this node and search
+   * @param profit profit upper bound
+   */
+  void setProfitUpperBound(long profit);
+
+  /**
+   * The next item given this node and search
+   * @return next item id
+   */
+  int nextItemId();
+
+  /**
+   * Set the next item given this node and search
+   * @param id next item id
+   */
+  void setNextItemId(int id);
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchNodeImpl.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchNodeImpl.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchNodeImpl.java
new file mode 100644
index 0000000..ea9cb98
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchNodeImpl.java
@@ -0,0 +1,77 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+/**
+ * Implementation of {@link KnapsackSearchNode}<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public class KnapsackSearchNodeImpl implements KnapsackSearchNode {
+  private static final int NO_SELECTION = -1;
+
+  private int _depth;
+  private KnapsackSearchNode _parent;
+  private KnapsackAssignment _assignment;
+  private long _currentProfit;
+  private long _profitUpperBound;
+  private int _nextItemId;
+
+  /**
+   * Initialize a search node
+   * @param parent the node's parent
+   * @param assignment the node's assignment
+   */
+  public KnapsackSearchNodeImpl(final KnapsackSearchNode parent, final KnapsackAssignment assignment) {
+    _depth = (parent == null) ? 0 : parent.depth() + 1;
+    _parent = parent;
+    _assignment = assignment;
+    _currentProfit = 0L;
+    _profitUpperBound = Long.MAX_VALUE;
+    _nextItemId = NO_SELECTION;
+  }
+
+  @Override
+  public int depth() {
+    return _depth;
+  }
+
+  @Override
+  public KnapsackSearchNode parent() {
+    return _parent;
+  }
+
+  @Override
+  public KnapsackAssignment assignment() {
+    return _assignment;
+  }
+
+  @Override
+  public long currentProfit() {
+    return _currentProfit;
+  }
+
+  @Override
+  public void setCurrentProfit(long profit) {
+    _currentProfit = profit;
+  }
+
+  @Override
+  public long profitUpperBound() {
+    return _profitUpperBound;
+  }
+
+  @Override
+  public void setProfitUpperBound(long profit) {
+    _profitUpperBound = profit;
+  }
+
+  @Override
+  public int nextItemId() {
+    return _nextItemId;
+  }
+
+  @Override
+  public void setNextItemId(int id) {
+    _nextItemId = id;
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchPath.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchPath.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchPath.java
new file mode 100644
index 0000000..d977143
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchPath.java
@@ -0,0 +1,39 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+/**
+ * Construction of the path between search nodes in a knapsack<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public interface KnapsackSearchPath {
+  /**
+   * Initialize the path
+   */
+  void init();
+
+  /**
+   * Get the source node
+   * @return starting KnapsackSearchNode
+   */
+  KnapsackSearchNode from();
+
+  /**
+   * Get the intermediate node
+   * @return KnapsackSearchNode between source and destination
+   */
+  KnapsackSearchNode via();
+
+  /**
+   * Get the destination node
+   * @return terminating KnapsackSearchNode
+   */
+  KnapsackSearchNode to();
+
+  /**
+   * Get an ancestor of a given search node
+   * @param node the search node
+   * @param depth the depth of the ancestor
+   * @return the ancestor node
+   */
+  KnapsackSearchNode moveUpToDepth(final KnapsackSearchNode node, int depth);
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchPathImpl.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchPathImpl.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchPathImpl.java
new file mode 100644
index 0000000..06a9ec7
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSearchPathImpl.java
@@ -0,0 +1,65 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+/**
+ * Implementation of {@link KnapsackSearchPath}<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public class KnapsackSearchPathImpl implements KnapsackSearchPath {
+  private KnapsackSearchNode _from;
+  private KnapsackSearchNode _via;
+  private KnapsackSearchNode _to;
+
+  /**
+   * Create a search path between nodes in a knapsack
+   * @param from the source node
+   * @param to the destination node
+   */
+  public KnapsackSearchPathImpl(final KnapsackSearchNode from, final KnapsackSearchNode to) {
+    _from = from;
+    _via = null;
+    _to = to;
+  }
+
+  @Override
+  public void init() {
+    KnapsackSearchNode nodeFrom = moveUpToDepth(_from, _to.depth());
+    KnapsackSearchNode nodeTo = moveUpToDepth(_to, _from.depth());
+    if (nodeFrom.depth() != nodeTo.depth()) {
+      throw new RuntimeException("to and from depths do not match!");
+    }
+
+    // Find common parent
+    // TODO: check if basic equality is enough
+    while (nodeFrom != nodeTo) {
+      nodeFrom = nodeFrom.parent();
+      nodeTo = nodeTo.parent();
+    }
+    _via = nodeFrom;
+  }
+
+  @Override
+  public KnapsackSearchNode from() {
+    return _from;
+  }
+
+  @Override
+  public KnapsackSearchNode via() {
+    return _via;
+  }
+
+  @Override
+  public KnapsackSearchNode to() {
+    return _to;
+  }
+
+  @Override
+  public KnapsackSearchNode moveUpToDepth(KnapsackSearchNode node, int depth) {
+    KnapsackSearchNode currentNode = node;
+    while (currentNode.depth() > depth) {
+      currentNode = currentNode.parent();
+    }
+    return currentNode;
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSolver.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSolver.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSolver.java
new file mode 100644
index 0000000..832a470
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSolver.java
@@ -0,0 +1,60 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+
+/**
+ * Interface for a factory of multidimensional 0-1 knapsack solvers that support reductions<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public interface KnapsackSolver {
+  /**
+   * Collection of supported algorithms
+   */
+  enum SolverType {
+    /**
+     * A solver that uses the branch-and-bound technique, supports multiple dimensions
+     */
+    KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER
+  }
+
+  /**
+   * Initialize the solver
+   * @param profits profit for each element if selected
+   * @param weights cost of each element in each dimension
+   * @param capacities maximum total weight in each dimension
+   */
+  void init(final ArrayList<Long> profits, final ArrayList<ArrayList<Long>> weights,
+      final ArrayList<Long> capacities);
+
+  /**
+   * Solve the knapsack problem
+   * @return the approximated optimal weight
+   */
+  long solve();
+
+  /**
+   * Check if an element was selected in the optimal solution
+   * @param itemId the index of the element to check
+   * @return true if the item is present, false otherwise
+   */
+  boolean bestSolutionContains(int itemId);
+
+  /**
+   * Get the name of this solver
+   * @return solver name
+   */
+  String getName();
+
+  /**
+   * Check if a reduction should be used to prune paths early on
+   * @return true if reduction enabled, false otherwise
+   */
+  boolean useReduction();
+
+  /**
+   * Set whether a reduction should be used to prune paths early on
+   * @param useReduction true to enable, false to disable
+   */
+  void setUseReduction(boolean useReduction);
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSolverImpl.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSolverImpl.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSolverImpl.java
new file mode 100644
index 0000000..eeab0b1
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackSolverImpl.java
@@ -0,0 +1,191 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+
+/**
+ * Implementation of {@link KnapsackSolver}<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public class KnapsackSolverImpl implements KnapsackSolver {
+  private final BaseKnapsackSolver _solver;
+  private final ArrayList<Boolean> _knownValue;
+  private final ArrayList<Boolean> _bestSolution;
+  private final ArrayList<Integer> _mappingReducedItemId;
+  private boolean _isProblemSolved;
+  private long _additionalProfit;
+  private boolean _useReduction;
+
+  /**
+   * Initialize a generic knapsack solver
+   * @param solverName the name of the solver
+   */
+  public KnapsackSolverImpl(String solverName) {
+    _solver = new KnapsackGenericSolverImpl(solverName);
+    _knownValue = new ArrayList<Boolean>();
+    _bestSolution = new ArrayList<Boolean>();
+    _mappingReducedItemId = new ArrayList<Integer>();
+    _isProblemSolved = false;
+    _additionalProfit = 0L;
+    _useReduction = true;
+  }
+
+  /**
+   * Initialize a specified knapsack solver
+   * @param solverType the type of solver
+   * @param solverName the name of the solver
+   */
+  public KnapsackSolverImpl(SolverType solverType, String solverName) {
+    _knownValue = new ArrayList<Boolean>();
+    _bestSolution = new ArrayList<Boolean>();
+    _mappingReducedItemId = new ArrayList<Integer>();
+    _isProblemSolved = false;
+    _additionalProfit = 0L;
+    _useReduction = true;
+    BaseKnapsackSolver solver = null;
+    switch (solverType) {
+    case KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER:
+      solver = new KnapsackGenericSolverImpl(solverName);
+      break;
+    default:
+      throw new RuntimeException("Solver " + solverType + " not supported");
+    }
+    _solver = solver;
+  }
+
+  @Override
+  public void init(ArrayList<Long> profits, ArrayList<ArrayList<Long>> weights,
+      ArrayList<Long> capacities) {
+    _additionalProfit = 0L;
+    _isProblemSolved = false;
+    _solver.init(profits, weights, capacities);
+    if (_useReduction) {
+      final int numItems = profits.size();
+      final int numReducedItems = reduceProblem(numItems);
+
+      if (numReducedItems > 0) {
+        computeAdditionalProfit(profits);
+      }
+
+      if (numReducedItems > 0 && numReducedItems < numItems) {
+        initReducedProblem(profits, weights, capacities);
+      }
+    }
+  }
+
+  @Override
+  public long solve() {
+    return _additionalProfit + ((_isProblemSolved) ? 0 : _solver.solve());
+  }
+
+  @Override
+  public boolean bestSolutionContains(int itemId) {
+    final int mappedItemId = (_useReduction) ? _mappingReducedItemId.get(itemId) : itemId;
+    return (_useReduction && _knownValue.get(itemId)) ? _bestSolution.get(itemId) : _solver
+        .bestSolution(mappedItemId);
+  }
+
+  @Override
+  public String getName() {
+    return _solver.getName();
+  }
+
+  @Override
+  public boolean useReduction() {
+    return _useReduction;
+  }
+
+  @Override
+  public void setUseReduction(boolean useReduction) {
+    _useReduction = useReduction;
+  }
+
+  private int reduceProblem(int numItems) {
+    _knownValue.clear();
+    _bestSolution.clear();
+    _mappingReducedItemId.clear();
+    ArrayList<Long> j0UpperBounds = new ArrayList<Long>();
+    ArrayList<Long> j1UpperBounds = new ArrayList<Long>();
+    for (int i = 0; i < numItems; i++) {
+      _knownValue.add(false);
+      _bestSolution.add(false);
+      _mappingReducedItemId.add(i);
+      j0UpperBounds.add(Long.MAX_VALUE);
+      j1UpperBounds.add(Long.MAX_VALUE);
+    }
+    _additionalProfit = 0L;
+    long bestLowerBound = 0L;
+    for (int itemId = 0; itemId < numItems; itemId++) {
+      long upperBound = 0L;
+      long lowerBound = Long.MAX_VALUE;
+      long[] bounds = _solver.getLowerAndUpperBoundWhenItem(itemId, false, upperBound, lowerBound);
+      lowerBound = bounds[0];
+      upperBound = bounds[1];
+      j1UpperBounds.set(itemId, upperBound);
+      bestLowerBound = Math.max(bestLowerBound, lowerBound);
+      bounds = _solver.getLowerAndUpperBoundWhenItem(itemId, true, upperBound, lowerBound);
+      lowerBound = bounds[0];
+      upperBound = bounds[1];
+      j0UpperBounds.set(itemId, upperBound);
+      bestLowerBound = Math.max(bestLowerBound, lowerBound);
+    }
+
+    int numReducedItems = 0;
+    for (int itemId = 0; itemId < numItems; itemId++) {
+      if (bestLowerBound > j0UpperBounds.get(itemId)) {
+        _knownValue.set(itemId, true);
+        _bestSolution.set(itemId, false);
+        numReducedItems++;
+      } else if (bestLowerBound > j1UpperBounds.get(itemId)) {
+        _knownValue.set(itemId, true);
+        _bestSolution.set(itemId, true);
+        numReducedItems++;
+      }
+    }
+    _isProblemSolved = numReducedItems == numItems;
+    return numReducedItems;
+  }
+
+  private void computeAdditionalProfit(final ArrayList<Long> profits) {
+    final int numItems = profits.size();
+    _additionalProfit = 0L;
+    for (int itemId = 0; itemId < numItems; itemId++) {
+      if (_knownValue.get(itemId) && _bestSolution.get(itemId)) {
+        _additionalProfit += profits.get(itemId);
+      }
+    }
+  }
+
+  private void initReducedProblem(final ArrayList<Long> profits,
+      final ArrayList<ArrayList<Long>> weights, final ArrayList<Long> capacities) {
+    final int numItems = profits.size();
+    final int numDimensions = capacities.size();
+
+    ArrayList<Long> reducedProfits = new ArrayList<Long>();
+    for (int itemId = 0; itemId < numItems; itemId++) {
+      if (!_knownValue.get(itemId)) {
+        _mappingReducedItemId.set(itemId, reducedProfits.size());
+        reducedProfits.add(profits.get(itemId));
+      }
+    }
+
+    ArrayList<ArrayList<Long>> reducedWeights = new ArrayList<ArrayList<Long>>();
+    ArrayList<Long> reducedCapacities = new ArrayList<Long>(capacities);
+    for (int dim = 0; dim < numDimensions; dim++) {
+      final ArrayList<Long> oneDimensionWeights = weights.get(dim);
+      ArrayList<Long> oneDimensionReducedWeights = new ArrayList<Long>();
+      for (int itemId = 0; itemId < numItems; itemId++) {
+        if (_knownValue.get(itemId)) {
+          if (_bestSolution.get(itemId)) {
+            reducedCapacities
+                .set(dim, reducedCapacities.get(dim) - oneDimensionWeights.get(itemId));
+          }
+        } else {
+          oneDimensionReducedWeights.add(oneDimensionWeights.get(itemId));
+        }
+      }
+      reducedWeights.add(oneDimensionReducedWeights);
+    }
+    _solver.init(reducedProfits, reducedWeights, reducedCapacities);
+  }
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackState.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackState.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackState.java
new file mode 100644
index 0000000..66713eb
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackState.java
@@ -0,0 +1,42 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+/**
+ * The current state of the knapsack<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public interface KnapsackState {
+  /**
+   * Initialize the knapsack with the number of items
+   * @param numberOfItems the number of items
+   */
+  void init(int numberOfItems);
+
+  /**
+   * Update this state with an assignment
+   * @param revert true to revert to the previous state, false otherwise
+   * @param assignment the assignment that was made
+   * @return true on success, false on failure
+   */
+  boolean updateState(boolean revert, final KnapsackAssignment assignment);
+
+  /**
+   * Get the current number of items in the knapsack
+   * @return number of items
+   */
+  int getNumberOfItems();
+
+  /**
+   * Check if an item is currently bound to the knapsack
+   * @param id the item id
+   * @return true if bound, false otherwise
+   */
+  boolean isBound(int id);
+
+  /**
+   * Check if an item is currently in the knapsack
+   * @param id the item id
+   * @return true if inside, false otherwise
+   */
+  boolean isIn(int id);
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackStateImpl.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackStateImpl.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackStateImpl.java
new file mode 100644
index 0000000..8e86872
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackStateImpl.java
@@ -0,0 +1,61 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+
+/**
+ * Implementation of {@link KnapsackState}<br/>
+ * <br/>
+ * Based on the C++ knapsack solver in Google's or-tools package.
+ */
+public class KnapsackStateImpl implements KnapsackState {
+  private ArrayList<Boolean> _isBound;
+  private ArrayList<Boolean> _isIn;
+
+  /**
+   * Initialize the knapsack state
+   */
+  public KnapsackStateImpl() {
+    _isBound = new ArrayList<Boolean>();
+    _isIn = new ArrayList<Boolean>();
+  }
+
+  @Override
+  public void init(int numberOfItems) {
+    _isBound.clear();
+    _isIn.clear();
+    for (int i = 0; i < numberOfItems; i++) {
+      _isBound.add(false);
+      _isIn.add(false);
+    }
+  }
+
+  @Override
+  public boolean updateState(boolean revert, KnapsackAssignment assignment) {
+    if (revert) {
+      _isBound.set(assignment.itemId, false);
+    } else {
+      if (_isBound.get(assignment.itemId) && _isIn.get(assignment.itemId) != assignment.isIn) {
+        return false;
+      }
+      _isBound.set(assignment.itemId, true);
+      _isIn.set(assignment.itemId, assignment.isIn);
+    }
+    return true;
+  }
+
+  @Override
+  public int getNumberOfItems() {
+    return _isBound.size();
+  }
+
+  @Override
+  public boolean isBound(int id) {
+    return _isBound.get(id);
+  }
+
+  @Override
+  public boolean isIn(int id) {
+    return _isIn.get(id);
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/helix/blob/9a2b729e/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackTester.java
----------------------------------------------------------------------
diff --git a/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackTester.java b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackTester.java
new file mode 100644
index 0000000..0b3f8ef
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/strategy/knapsack/KnapsackTester.java
@@ -0,0 +1,58 @@
+package org.apache.helix.controller.strategy.knapsack;
+
+import java.util.ArrayList;
+
+public class KnapsackTester {
+  public static void main(String[] args) {
+    // Construct an example
+    long[] PROFITS = {
+        96, 76, 56, 11, 86, 10, 66, 86, 83, 12, 9, 81
+    };
+    long[][] WEIGHTS = {
+        {
+            19, 1, 10, 1, 1, 14, 152, 11, 1, 1, 1, 1
+        }, {
+            0, 4, 53, 0, 0, 80, 0, 4, 5, 0, 0, 0
+        }, {
+            4, 660, 3, 0, 30, 0, 3, 0, 4, 90, 0, 0
+        }, {
+            7, 0, 18, 6, 770, 330, 7, 0, 0, 6, 0, 0
+        }, {
+            0, 20, 0, 4, 52, 3, 0, 0, 0, 5, 4, 0
+        }, {
+            0, 0, 40, 70, 4, 63, 0, 0, 60, 0, 4, 0
+        }, {
+            0, 32, 0, 0, 0, 5, 0, 3, 0, 660, 0, 9
+        }
+    };
+    long[] CAPACITIES = {
+        18209, 7692, 1333, 924, 26638, 61188, 13360
+    };
+    ArrayList<Long> profits = new ArrayList<Long>();
+    for (long profit : PROFITS) {
+      profits.add(profit);
+    }
+    ArrayList<ArrayList<Long>> weights = new ArrayList<ArrayList<Long>>();
+    for (long[] innerWeights : WEIGHTS) {
+      ArrayList<Long> singleWeights = new ArrayList<Long>();
+      for (long weight : innerWeights) {
+        singleWeights.add(weight);
+      }
+      weights.add(singleWeights);
+    }
+    ArrayList<Long> capacities = new ArrayList<Long>();
+    for (long capacity : CAPACITIES) {
+      capacities.add(capacity);
+    }
+
+    // Solve
+    KnapsackSolver solver = new KnapsackSolverImpl("mySolver");
+    solver.init(profits, weights, capacities);
+    long result = solver.solve();
+    System.err.println(result);
+    for (int i = 0; i < profits.size(); i++) {
+      System.err.println(solver.bestSolutionContains(i));
+    }
+  }
+
+}


Mime
View raw message