Cached Iterative Weakening for Optimal Multi-Way Number Partitioning
Authors: Ethan Schreiber, Richard Korf
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In section 4, we experimentally compare CIW to the previous state of the art. We ran experiments for n from 40 to 60 and k from 3 to 12. For each combination of n and k, we generated 100 problem instances. |
| Researcher Affiliation | Academia | Ethan L. Schreiber and Richard E. Korf Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 USA {ethan,korf}@cs.ucla.edu |
| Pseudocode | No | The paper describes the algorithms in prose and through diagrams (Figure 1 and 2), but does not include structured pseudocode or an algorithm block. |
| Open Source Code | Yes | Benchmarks at https://sites.google.com/site/elsbenchmarks/. (This page further states: The source code for our current best NP solvers is located at the github repository) |
| Open Datasets | Yes | For each combination of n and k, we generated 100 problem instances. Each instance consists of n integers sampled uniformly at random in the range [1, 248 1] in order to generate hard instances without perfect partitions (Korf 2011). (Footnote 1 also points to a website that hosts these generated instances.) |
| Dataset Splits | No | The paper describes generating 100 problem instances for each combination of n and k, which are used for evaluation, but it does not specify explicit train/validation/test dataset splits for reproducibility. |
| Hardware Specification | Yes | All experiments were run on an Intel Xeon X5680 CPU at 3.33GHz. |
| Software Dependencies | No | The paper mentions using the BCP bin-packing solver from (Belov and Scheithauer 2006) but does not provide specific version numbers for any software dependencies, programming languages, or libraries. |
| Experiment Setup | Yes | For CIW, we need to choose a value for m, the number of subsets to initially generate during the precomputing phase (section 3.2). Ideally, we want m to be exactly the number of subsets in the range [perfect, C ], but we do not know this number in advance. If m is set too small, CIW will have to run ESS multiple times. If m is set too large, CIW will waste time generating subsets in the precomputing step that are never used in the iterative weakening step. For each combination of n and k, we initially set m to 10,000. Call mi the number of sets in the range [perfect, C ] for problem instance i. After instance 1 is complete, m is set to m1. After instance i is complete, m is set to the max of m1 through mi. The values of m used ranged from 24 for the second instance of (n = 56; k = 3) to 180,085 for the last eight instances of (n = 59; k = 12). |