Solving the Station Repacking Problem
Authors: Alexandre Fréchette, Neil Newman, Kevin Leyton-Brown
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We show that our approach solves virtually all of a set of problems derived from auction simulations within the short time budget required in practice. Overall, SATFC solves virtually all problems in a previously-unseen test set 99.6% within one minute. |
| Researcher Affiliation | Academia | Alexandre Fr echette and Neil Newman and Kevin Leyton-Brown Department of Computer Science University of British Columbia, Canada {afrechet, newmanne, kevinlb}@cs.ubc.ca |
| Pseudocode | No | The paper describes the algorithms and techniques in prose, often with diagrams (e.g., Figure 3 for containment caching), but it does not include formal pseudocode blocks or algorithm listings. |
| Open Source Code | Yes | SATFC is open-source; pointers both to the solver and to data used in this paper are available at http://www.cs.ubc.ca/labs/beta/Projects/SATFC. |
| Open Datasets | Yes | We obtained anonymized versions of some repacking problems from five such simulations, and randomly partitioned them into a training set of 100,572 examples, a validation set of 1,000 examples, and a test set of 10,000 examples. SATFC is open-source; pointers both to the solver and to data used in this paper are available at http://www.cs.ubc.ca/labs/beta/Projects/SATFC. |
| Dataset Splits | Yes | We obtained anonymized versions of some repacking problems from five such simulations, and randomly partitioned them into a training set of 100,572 examples, a validation set of 1,000 examples, and a test set of 10,000 examples. |
| Hardware Specification | No | The paper mentions building a cache at a cost of "roughly one CPU month" and states a desire to run on a "4-core workstation," but it does not provide specific details about the CPU models, GPU types, or other hardware specifications used for conducting the experiments. |
| Software Dependencies | No | The paper mentions specific solvers like "CPLEX", "Gurobi", "DCCA (Luo et al. 2014)", and "clasp (Gebser et al. 2007)", and refers to their origin from SAT solver competition entries collected in AClib (Hutter et al. 2014b), but it does not provide explicit version numbers for these software components. |
| Experiment Setup | Yes | We chose a cutoff time of 60 seconds, reflecting the constraints involved in solving up to hundreds of thousands of problems sequentially in a real auction. To evaluate this technique experimentally, we performed local augmentation on all our instances and used the training set to configure each SAT solver for best performance on this new instance distribution. |