You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@helix.apache.org by ka...@apache.org on 2014/05/23 22:43:52 UTC
git commit: Add Java port of or-tools knapsack solver
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 <ka...@apache.org>
Authored: Fri May 23 13:43:50 2014 -0700
Committer: Kanak Biscuitwala <ka...@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));
+ }
+ }
+
+}