Package io.openml.gearbox

Class Knapsack

java.lang.Object

io.openml.gearbox.Knapsack

public final class Knapsack
extends Object

Implementations of Knapsack algorithm and its derivatives.

Every aspect of human life is crucially determined by the result of decisions. Whereas private decisions may be based on emotions or personal taste, the complex professional environment requires a decision process which can be formalized and validated independently from the involved individuals. Therefore, a quantitative formulation of all factors influencing a decision and also of the result of the decision process is sought.

In order to meet this goal it must be possible to represent the effect of any decision by numerical values. In the most basic case the outcome of the decision can be measured by a single value representing gain, profit, loss, cost or some other category of data. The comparison of these values induces a total order on the set of all options which are available for a decision. Finding the option with the highest or lowest value can be difficult because the set of available options may be extremely large and/or not explicitly known. Frequently, only conditions are known which characterize the feasible options out of a very general ground set of theoretically available choices.

The simplest possible form of a decision is the choice between two alternatives. Such a binary decision is formulated in a quantitative model as a binary variable (x = 0 or 1) with the obvious meaning that x = 1 means taking the first alternative whereas x = 0 indicates the rejection of the first alternative and hence the selection of the second option.

Many practical decision processes can be represented by an appropriate combination of several binary decisions. This means that the overall decision problem consists of choosing one of two alternatives for a large number of binary decisions which may all influence each other.

A linear decision model is defined by n binary variables each of which can be 1 or 0 which correspond to the selection in the i-th (out of n) binary decision and by profit values p. We assume that after a suitable assignment of the n variables we always have positive p. The overall profit value associated with a particular bundle of choices for all n binary decisions is given by the sum of all profits of those variables where 1 was picked. The feasibility of the decision under this model is evaluated by a linear combination of coefficients for each binary decision. In this model the feasibility of a selection of bundle of alternatives is determined by a capacity restriction in the following way:

In every of n binary variables, picking up 1 requires a weight or resource whereas choosing 0 requires nothing. The selection of bundle of alternatives is feasible if the sum of weights over all binary decisions does not exceed a given threshold capacity C.

Considering this decision process as an optimization problem, where the overall profit should be as large as possible, yields the knapsack problem (KP), the core problem this class implements the solutions for.

This characteristic of the problem gives rise to the following real-life example of KP problem. Consider a mountaineer who is packing his knapsack (or rucksack) for a mountain tour and has to decide which items he should take with. The mountaineer has a large number of objects available which may be useful on his tour. Each of these items numbered from 1 to n would give him a certain amount of comfort or benefit which is measured by a positive number p. Of course,the weight of every object which the mountaineer puts into knapsack increases the load they have to carry. For obvious reasons, the mountaineer wants to limit the total weight of knapsack and hence fixes the maximum load by the capacity value c.

In order to give a more intuitive documentation of the implementation, we will use this knapsack interpretation and will usually refer to a "packing of items into a knapsack" rather than to the "combination of binary decisions" throughout our discussion. Also the terms "profit" and "weight" are based on this interpretation. Instead of making a number of binary decisions we will speak of the selection of a subset of items from the item set N from {1, ... ,n}.

The knapsack problem (KP) can be formally defined as follows: We are given an instance of the knapsack problem with item set N, consisting of n items each of which has a profit and weight, and the capacity value c. (Usually, all these values are taken from the positive integer numbers.) Then the objective is to select a subset of N such that the total profit of the selected items is maximized and the total weight does not exceed c.

It is frequently the case with industrial applications, in practice several additional constraints, such as urgency and priority of requests, time windows for every request, packages with low weight but high volume etc., have to be fulfilled. This leads to various extensions and variations o f the basic model (KP). Because this need for extension of the basic knapsack model arose in many practical optimization problems, some of the more general variants of (KP) have become standard problems of their own. This class implements several of them.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final record	Knapsack.KnapsackResult	A record to hold the result of the knapsack(List, List, int) calculation as concise way to create immutable data carrier classes.

Constructor Summary

Constructors

Constructor	Description
Knapsack()

Method Summary

Modifier and Type	Method	Description
static OptionalInt	backPack1(int capacity, int[] sizes)	Deprecated. Please use the more general knapsack(List, List, int)
static Knapsack.KnapsackResult	knapsack(List<Integer> values, List<Integer> weights, int capacity)	This method solves the classical 0/1 Knapsack problem: given a list of item sizes, a list of item values, and an integer denoting the size of a backpack, return the maximum value that this backpack can hold.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Knapsack

public Knapsack()

Method Details

backPack1

@Deprecated
public static OptionalInt backPack1(int capacity,
 int[] sizes)

Deprecated.

Please use the more general knapsack(List, List, int)

Given an array of item sizes and an integer denoting the size of a backpack, this method returns the maximum size that this backpack can be filled with the items.

If the specified capacity is negative or size array is null or empty, this method returns OptionalInt.empty().

Parameters:

capacity - The size of the backpack

sizes - An array of item sizes

Returns:

the maximum size that the backpack can fill

knapsack

public static Knapsack.KnapsackResult knapsack(List<Integer> values,
 List<Integer> weights,
 int capacity)

This method solves the classical 0/1 Knapsack problem: given a list of item sizes, a list of item values, and an integer denoting the size of a backpack, return the maximum value that this backpack can hold.

Parameters:

values - A list of the values of the items.

weights - A list of the weights of the items.

capacity - The maximum weight capacity of the knapsack.

Returns:

A KnapsackResult record containing the maximum value and the indices of the items to include.