David Pisinger's optimization codes
This page contains several optimization codes written in C. The codes
may be used free of charge for academical purposes. Each algorithm is
briefly described and a reference is given to the paper where it was
presented.
Knapsack Problems
Generation of test instances
A generator
to construct test instances for the 0-1 Knapsack Problem, as
described in the paper "Core problems in Knapsack Algorithms".
Instances are generated with varying capacities to test codes under
more realistic conditions.
A more
advanced generator
for 0-1 Knapsack Problems is described in "Dynamic programming and
tight bounds for the 0-1 Knapsack Problem" (co-authors: S. Martello,
P. Toth) where 14 different instance types are considered.
A generator for
hard instances
is also available. The instances are described in
"Where are the hard knapsack problems" which appeared
in Computers and Operations Research (2005). You can also download
all instances (and their solutions) here:
small coefficients,
large coefficients,
hard instances.
Expknap algorithm
The expknap
algorithm was presented in the paper "an expanding core algorithm
for the 0-1 knapsack problem". The algorithm is based on branch-and-bound,
where simple LP-bounds are used for the bounding process. Its main property
is that the size of the core adapts to the hardness of the instance.
The code is very short, and may be used for teaching purpose.
Minknap algorithm
The minknap
algorithm was presented in the paper "a minimal algorithm
for the 0-1 knapsack problem". The code is based on dynamic programming
where enumerative bounds are used to fathom unpromising states. It
is proved that the algorithm enumerates the smallest possible core
satisfying some given properties.
Combo algorithm
The combo algorithm
is described in "Dynamic Programming and Strong Bounds for the 0-1 Knapsack
Problem" by S.Martello, D.Pisinger, P.Toth. The algorithm combines the
generation of valid inequalities from the MTH algorithm
with the dynamic programming recursion from minknap.
Valid inequalities are surrogate relaxed to the original problem, thus
obtaining a new (easier) knapsack problem.
The initial core is constructed according to some greedy rules, which
ensure a very stable behavior.
The corresponding
header file should
be used to define the appropriate data structures.
Mcknap algorithm
In "A minimal algorithm for the multiple-choice knapsack problem",
an exact algorithm for the multiple-choice knapsack problem is presented.
The mcknap algorithm
is the first algorithm using the idea of a "core" to solve multiple-choice
knapsack problem. First, a median search algorithm is used to solve the
LP-relaxed poblem. Upper and lower bounds are derived from the LP-relaxed
solution, and if these do not coincide, dynamic programming is used to
enumerate an expanding core.
Bouknap algorithm
An algorithm for Bounded Knapsack Problems was presented
in the paper "A minimal algorithm for the bounded knapsack
problem". The bouknap
algorithm is based on a gradual transformation of the bounded problem
to a 0-1 problem as part of an expanding core. New upper bounds are
presented, which make it possible to tighten the bounds
on each item type.
Mulknap algorithm
The mulknap
algorithm for solving multiple
knapsack problems was presented in the paper "An exact algorithm
for large multiple knapsack problems". The code is able to solve
even very large sized instances in reasonable time.
The algorithm is based on the same framework as the MTM algorithm
by Martello and Toth (1990), but it contains several new elements:
Lower bounds are determined by splitting a surrogate solution.
Capacity constraints are tightened by solving a subset-sum problem
that determines the largest weight sum obtainable without exceeding
the capacity. And finally a reduction algorithm for fixation of
variables is implemented.
A test program,
generating instances as in Martello and Toth (1990) is also available
with the corresponding
header file.
Decomp algorithm
The decomp
algorithm solves the Subset-sum Problem through a kind of Horowitz-Sahni
decompoition. It was originally presented as part of the above
algorithm for multiple knapsack problems, where it was
used to tighten the capacity constraints and to derive lower bounds
by splitting a solution to the surrogate relaxed problem.
The code is however extremely efficient for solving most real-life
Subset-sum Problems, thus a self-contained procedure is given here.
Scknap algorithm
Strongly correlated knapsack problems were considered to be some of
the most difficult knapsack problems, due to the large gap between
the LP-solution and IP-solution. The algorithm
scknap
however demonstrated that tight bounds may be obtained by
surrogate relaxing a cardinality constraint with the original
capacity constraint. In order to match the upper bound, a fast
two-optimal heuristic was constructed, which in many cases solved
the problem to optimality. If optimality of the heuristic solution
could not be proved, a dynamic programming based on balanced states
was used. More detail can be found in the paper "A fast algorithm
for strongly correlated knapsack problem".
Quadratic Knapsack Problems
The quadratick knapsack problems asks to maximize a quadratic
objective function subject to a single capacity constraint.
The paper "Exact Solution of the Quadratic Knapsack Problem"
by Caprara, Pisinger and Toth (1999) presents an exact algorithm for
these problems which is able to solve dense problems with up
to 400 binary variables.
The quadknap
algorithm is a callable routine for solving quadratic knapsack
problems. As an argument it takes a profit matrix, a weight vector,
the capacity of the knapsack, and finally a boolean solution vector
where the solution should be returned.
The testqkp
algorithm generates instances as described in the above mentioned
paper and calls the quadknap code. Average solution times and
found solutions are reported.
Robot packable three-dimensional Bin-packing Problems
An exact algorithm for the robot packable three-dimensional
Bin-packing Problem
The paper "An algorithm for the three-dimensional bin packing problem"
by S.Martello, D.Pisinger, D.Vigo (1998), presents a code for solving
robot packable three-dimensional bin packing problems to optimality. The code
3dbpp.c is a
callable C-procedure which can be used as heuristic or exact algorithm.
Test instances for the Three-dimensional Bin-packing Problem
A C-code which generates test instances for the 3D BPP as described in
the paper: S.Martello, D.Pisinger, D.Vigo "The three-dimensional
bin-packing problem" is found in
test3dbpp.c.
The algorithm generates test instances and calls 3dbpp to solve the
problems to optimality. Output is written to a file for later processing.
Instructions for compilation
A readme file
with instructions for compilation of the three-dimensional bin-packing
algorithm is available here.
General three-dimensional Bin-packing Problems
An exact algorithm for the Three-dimensional Bin-packing Problem
The general version of the problem is considered in
"Algorithms for General and Robot-packable Variants of
the Three-Dimensional Bin Packing Problem" by
Martello, Pisinger, Vigo, den Boef, Korst.
The code
3dbpp.c.
Test generator
test3dbpp.c.
Instructions for compilation
readme.
Container Loading Problems
A heuristic for the Container Loading Problem
The paper "A tree-search heuristic for the Container Loading Problem"
by D.Pisinger (1999), presents a code for knapsack loading a container.
The code
container.c is a
callable C-procedure which can be used in several applications.
Test instances for the Container Loading Problem
A C-code which generates test instances for the Container Loading
Problem as described in: D.Pisinger, "A tree-search heuristic for
the Container Loading Problem" is found in
testcont.c.
The algorithm generates test instances and calls "contload" to solve the
problems to optimality. Output is written to a file for later processing.
Instructions for compilation
A readme file
with instructions for compilation of the Container Loading algorithm
is available here.
Heuristic approaches for the two- and three-dimensional
knapsack packing problem
The paper "Heuristic approaches for the two- and three-dimensional
knapsack packing problem" (Jens Egeblad, David Pisinger, Computers and Operations Research, 2009, vol 36, 1026-1049) presents
a series of systematically generated packing instances.
All the instances can be downloaded from the following zip-file
zip.
(Test instances for the corresponding technical report are found in the
following zip-file
zip).
Train seat reservation problem
The off-line group seat reservation problem considered in Clausen et al.
(2010) can be seen as a packing problem where the rectangles are fixed in
one of the dimensions.
The test instances considered in the above paper can be found in the
following zip-file
zip.
A translation of this page to Serbo-Croatian has been made by Anja Skrba.
Back to home.
pisinger@diku.dk.