The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of
knapsack problem
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit a ...
that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the
knapsack
A backpack—also called knapsack, schoolbag, rucksack, rucksac, pack, sackpack, booksack, bookbag or backsack—is, in its simplest frameless form, a fabric sack carried on one's back and secured with two straps that go over the shoulders ...
, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the
0-1 quadratic knapsack problem The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be ...
, which was first discussed by Gallo et al.
The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.
Definition
Specifically, the 0–1 quadratic knapsack problem has the following form:
:
:
Here the binary variable ''x
i'' represents whether item ''i'' is included in the knapsack,
is the profit earned by selecting item ''i'' and
is the profit achieved if both item ''i'' and ''j'' are added.
Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity.
Application
As one might expect, QKP has a wide range of applications including
telecommunication
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than tha ...
,
transportation network,
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
and
economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analy ...
. In fact, Witzgall first discussed QKP when selecting sites for satellite stations in order to maximize the global traffic with respect to a budget constraint. Similar model applies to problems like considering the location of airports, railway stations, or freight handling terminals. Applications of QKP in the field of computer science is more common after the early days:
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
design problem,
clique problem
In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliq ...
,
very large scale integration
Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) ...
(VLSI) design. Additionally, pricing problems appear to be an application of QKP as described by Johnson et al.
Computational complexity
In general, the decision version of the knapsack problem (Can a value of at least V be achieved under a restriction of a certain capacity W?) is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
. Thus, a given solution can be verified to in polynomial time while no algorithm can identify a solution efficiently.
The optimization knapsack problem is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
and there is no known algorithm that can solve the problem in polynomial time.
As a particular variation of the knapsack problem, the 0-1 quadratic knapsack problem is also NP-hard.
While no available efficient algorithm exists in the literature, there is a
pseudo-polynomial time In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the ''numeric value'' of the input (the largest integer present in the input)—but not necessarily in the ''length'' of t ...
based on
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
and other
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediat ...
algorithms that can always generate “good” solutions.
Solving
While the knapsack problem is one of the most commonly solved
operation research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
(OR) problems, there are limited efficient algorithms that can solve 0-1 quadratic knapsack problems. Available algorithms include but are not limited to
brute force
Brute Force or brute force may refer to:
Techniques
* Brute force method or proof by exhaustion, a method of mathematical proof
* Brute-force attack, a cryptanalytic attack
* Brute-force search, a computer problem-solving technique
People
* Brut ...
,
linearization
In mathematics, linearization is finding the linear approximation to a function at a given point. The linear approximation of a function is the first order Taylor expansion around the point of interest. In the study of dynamical systems, linea ...
, and convex reformulation. Just like other NP-hard problems, it is usually enough to find a workable solution even if it is not necessarily optimal. Heuristic algorithms based on
greedy algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locall ...
, dynamic programming can give a relatively “good” solution to the 0-1 QKP efficiently.
Brute force
The brute-force algorithm to solve this problem is to identify all possible subsets of the items without exceeding the capacity and select the one with the optimal value. The pseudo-code is provided as follows:
// Input:
// Profits (stored in array p)
// Quadratic profits (stored in matrix P)
// Weights (stored in array w)
// Number of items (n)
// Knapsack capacity (W)
int max = 0
for all subset S do
int value, weight = 0
for i from 0 to S.size-1 do:
value = value + p weight = weight + w for j from i+1 to S.size-1 do:
value = value + P j]
if weight <= W then:
if value > max then:
max = value
Given ''n'' items, there will be at most
subsets and for each legal candidate set, the running time of computing the values earned is
. Thus, the efficiency class of brute-force algorithm is
, being exponential.
Linearization
Problems of such form are difficult to solve directly using standard solvers and thus people try to reformulate it as a
linear program
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
using auxiliary variables and constraints so that the problem can be readily solved using commercial packages. Two well-known
linearization
In mathematics, linearization is finding the linear approximation to a function at a given point. The linear approximation of a function is the first order Taylor expansion around the point of interest. In the study of dynamical systems, linea ...
approaches for the 0-1 QKP are the standard linearization and Glover’s linearization.
Standard linearization
The first one is the standard linearization strategy, as shown below:
: LP1: maximize
:
: subject to
:
for all