# 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".

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.

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.

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.

## 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.