Extreme Harmonic

This page contains information and code related to the paper Beating the Harmonic lower bound for online bin packing by Sandy Heydrich and Rob van Stee.

ExtremeHarmonicVerifier program

We provide our executable program as a .jar-file, we require that Java8 is installed on your machine. This is a command-line based tool and lacks graphical user interface. To execute our program, open your command-line, navigate to the directory containing the .jar-file and execute java -jar ExtremeHarmonicVerifier.jar to start the program.

During its executing, the program will search for a .vp-file inside its directory. If it finds the file we used to achieve our results with (provided below), it will use this file as an input. Otherwise, it will query you for an input file. This file must contain all parameters required by the program, described in detail below. Alternatively, you can supply the name of a .vp-file you want to use as input as command line argument (e.g., execute java -jar ExtremeHarmonicVerifier.jar 1.583.vp using the simpler 1.583-input provided below).

The program generates a file protocol_ExtremeHarmonic.txt with detailed information on the execution, a file params.txt with detailed information about the non-large types used, a file knapsackData.txt containing the information needed for verifying the solutions of the knapsack problems with an external knapsack solver and a file weights.txt that contains item sizes and weights for all cases in human-readable form (though the values are rounded and thus not exact).

Download ExtremeHarmonicVerifier.jar

In addition, we provide all parameters used by our algorithm SonOfHarmonic on the following page: Parameters for SonOfHarmonic.

We provide two input files for this program: one to prove the competitive ratio 1.5813 for Son of Harmonic, and one to prove the competitive ratio of 1.583 within the Extreme Harmonic framework.

Download Input File 1.5813.vp
Download Input File 1.583.vp

Using 1.5813.vp, the program should run not more than a few minutes on a modern machine. Using 1.583.vp, only 23 knapsack problems are generated, so that it is relatively easy to verify this result (which already proves that we can get below the Super Harmonic-lower bound). The program also runs much faster and should complete in a few seconds.

BinarySearch program

This program was used to determine the y3-values that certify the feasibility of the dual LPs for Son of Harmonic. It can be executed the same way as ExtremeHarmonicVerifier.jar and uses a .bsp-file as input. This program generates the verifier input file as well.

Download BinarySearch.jar

We again provide two input files for this program, for competitive ratios 1.5813 and 1.583.

Download Input File 1.5813.bsp
Download Input File 1.583.bsp

ParameterOptimizer program

This program was used to determine most of the parameters of the Son of Harmonic algorithm. Given only few manually set parameters, it adds additional types and computes red-values for them using heuristics that are supposed to make sure that the final competitive ratio (which is already supplied to this program) can be achieved. It can be executed the same way as ExtremeHarmonicVerifier.jar and uses a .pop-file as input. This program generates the input file for the BinarySearch.jar program as well.

Download ParameterOptimizer.jar

We again provide two input files for this program, for competitive ratios 1.5813 and 1.583.

Download Input File 1.5813.pop
Download Input File 1.583.pop

SuperHarmonic program

In addition, we provide a simplified version of our program, SuperHarmonicVerifier.jar, that can be used to verify the competitive ratio of Harmonic++ or other Super Harmonic algorithms as given by Seiden (S.S. Seiden "On the Online Bin Packing Problem", J. ACM 49(5), 640-671 (2002)). It works very similar to the ExtremeHarmonicVerifier.jar described above, however, you can additionally supply a command line argument to specify whether to prove the results with the exact parameters Seiden used (command line argument original) or whether to prove that a 1.5884-competitive algorithm exists within the SuperHarmonic framework by using improved (and also simplified) parameters provided by us (command line argument improved). If no argument is specified, the improved version is run.

Download SuperHarmonicVerifier.jar
Download input file 1.5888.vp
Download input file 1.5884.vp

Download BinarySearchSH.jar
Download input file 1.5888.bsp
Download input file 1.5884.bsp

Download ParameterOptimizerSH.jar
Download input file 1.5888.pop
Download input file 1.5884.pop

Other Resources

Download Source Code (provided for reference)

This is a .zip-file containing the source code for all programs described above.

Download the knapsack problem input

This file contains the input data for the final knapsack problems. This file is also produced as an output of ExtremeHarmonicVerifier.jar. By providing this input, we enable readers to check the solution to the knapsack problem with a knapsack solver of their choice.

Download the weights for the knapsack problem

This file contains the input data for the final knapsack problems, however, in human-readable rounded form (i.e., no exact values are given). This file is also produced as an output of ExtremeHarmonicVerifier.jar. This is to enable a reader easy inspection of the weights generated by the program.

Download source code for determining the lower bound

This class was used to find patterns for the lower bound. In lines 13/14, the item types that should be considered are defined. Lines 40-43 give guesses for the redi values. The range around these guessed values in which our program will test different redi values is defined in lines 47/48. Lines 50-53 specify the redfiti values. The program tests different redi values in the given range for different decreasing stepsizes. For each set of redi parameters, we compute the weight of the heaviest pattern, and try to find redi parameters that minimize this maximum weight. At the end, the program prints the heaviest patterns with their weights to the console.

All files offered on this page are only for personal use and verification of the results presented in the paper mentioned above.