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)); + } + } + +}
