An experimental design approach to evaluating multi-option algorithms illustrated on a new integer programming procedure

Abstract

Frequently algorithm users can select their solution strategy by choosing from among various options for each of several algorithm factors. If the algorithm will always eventually find a solution, the important question is which combination of options is likely to be "best". A general statistical approach to answering the question is illustrated in the context of a new integer linear programming algorithm where "best" is quickest. The integer programming algorithm is a sophisticated implicit enumeration algorithm. The four factors where the user must select an option are (1)augmenting partial solutions, (2)backtracking, (3)fathoming on the basis of binary feasibility and optimality indicators, and (4)use of linear programming on the relaxed problem which includes penalties, cuts, surrogate constraints, and associated fathoming. There are several options per factor so that the algorithm can function in over 14,000 different modes. A significant evaluation of the average effects of each option on the algorithm's speed and the interactions between options is obtained using analysis of variance techniques. The design of the experiment, the linear model, and the analysis of the resulting data are discussed. The generality of this approach to analyzing algorithm components is emphasized.