AlgoKP is a software to solve 2D orthogonal knapsack packing problems:

It contains an implementation of two algorithms:

• the first one uses consecutive ones matrices as main data structure: see
  • Joncour, Pêcher, Consecutive Ones Matrices for Multi-dimensional Orthogonal Packing Problems, Journal of Mathematical Modelling and Algorithms
• the second one uses MPQ-trees as main data structure: see
  • Joncour, Pêcher, Valicov, MPQ-trees for the orthogonal packing problem, Journal of Mathematical Modelling and Algorithms

Current developpers

• Cédric Joncour (main developper)
• Arnaud Pêcher
• Petru Valicov (main developper)

Download

It is still beta software and is provided only for benchmarking purposes.

• the archive AlgoKP.zip (including a jar file and all benchmarks files)

Installation & Usage

A Java Virtual Machine (>=1.5) is needed to run this software.

• Installation: extract the archive (you should get the jar file AlgoKP.jar and a subdirectory benchmarksOPP/ – add your own benchmarks files in this subdirectory, if any)
• Usage: java -jar AlgoKP.jar
• “suite 1” runs the set of standard instances NGCUT, GCUT, CGCUT, OKP for the 2D-orthogonal knapsack packing problem – these files are provided for conveniency. The original benchmarks files are also available at Beasley’s OR-Library.
• “suite 2” runs the set of Clautiaux’s instances for the 2D-orthogonal packing problem – these files are provided for conveniency. The original benchmarks files are also available at Clautiaux’s Orthogonal-packing benchmarks webpage.