Of n-dimensional Dice, Combinatorial Optimization, and Reproducible Research: An Introduction
F. Brglez · 2011
When throwing a solid object like a hexahedron, an octahedron or a tetrakis-hexahedron on a flat surface, we expect it to roll onto any of the with probabilities of exactly 1/6, 1/8, or 1/24, respectively. Informally, we view such objects as instances from the n-dimensional dice family; formally, they are instances from a hyperhedron family H( ;b;n). Each of the is assigned a label f ; ( )g; represents a unique n-dimensional coordinate string ; ( ) represents the value of the function for . The number of coordinates is defined as jH( ;b;n)j = b n (n!); each coordinate string is an oriented permutation with parameter b denoting the number of symbols that encode the unique orientation of each permutation. Special cases include the combinational family C( ;b;n) with jC( ;b;n)j = b n (each coordinate string is a unique n-tuple) and the (single orientation) permutation family P( ;b;n) with jP( ;b;n)j = n! (each coordinate string is a unique permutation). The paper introduces the hyperhedron not only as a model for instances that arise in the context of combinatorial optimization but also as a metaphor to illustrate a number of combinatorial search algorithms whose meta-structures do not change when instance coordinates change from an n-tuple to a simple or an oriented permutation of length n. The dice metaphor is applied to statistical performance experiments with instances whose dimension increases monotonically while the number of best faces remains constant. All results are archived as an integral part of reproducible research environment, controlled by components encapsulated in tcl, R, and L ATEX.