public interface

BaseKnapsackSolver

org.apache.helix.controller.strategy.knapsack.BaseKnapsackSolver
Known Indirect Subclasses

Class Overview

The interface of any multidimensional knapsack solver

Based on the C++ knapsack solver in Google's or-tools package.

Summary

Public Methods
abstract boolean bestSolution(int itemId)
Check if an item is in the final solution
abstract long[] getLowerAndUpperBoundWhenItem(int itemId, boolean isItemIn, long lowerBound, long upperBound)
Compute an upper and lower bound on the knapsack given the assignment state of the knapsack
abstract String getName()
Get the solver name
abstract void init(ArrayList<Long> profits, ArrayList<ArrayList<Long>> weights, ArrayList<Long> capacities)
Initialize the solver
abstract long solve()
Solve the knapsack problem

Public Methods

public abstract boolean bestSolution (int itemId)

Check if an item is in the final solution

Parameters
itemId the item id
Returns
  • true if the item is present, false otherwise

public abstract long[] getLowerAndUpperBoundWhenItem (int itemId, boolean isItemIn, long lowerBound, long upperBound)

Compute an upper and lower bound on the knapsack given the assignment state of the knapsack

Parameters
itemId the item id
isItemIn true if the item is in the knapsack, false otherwise
lowerBound the current lower bound
upperBound the current upper bound
Returns
  • the new lower and upper bounds

public abstract String getName ()

Get the solver name

Returns
  • solver name

public abstract void init (ArrayList<Long> profits, ArrayList<ArrayList<Long>> weights, ArrayList<Long> capacities)

Initialize the solver

Parameters
profits profit of adding each item to the knapsack
weights cost of adding each item in each dimension
capacities maximum weight per dimension

public abstract long solve ()

Solve the knapsack problem

Returns
  • the (approximate) optimal profit