Generating Applicable Synthetic Instances for Branch Problems

Generating valid synthetic instances for branch problems—those that contain a core problem like knapsack or graph coloring, but add several complications—is hard. It is even harder to generate instances that are applicable to the specific goals of an experiment and help to support the claims made. This paper presents a methodology for tuning instance generators of branch problems so that synthetic instances are similar to real ones and are capable of eliciting different behaviors from solvers. A statistic is proposed to summarize the applicability of instances for drawing a valid conclusion. The methodology is demonstrated on the Udine timetabling problem. Examples and the necessary cyberinfrastructure are available as a project from Computational Infrastructure for Operations Research (COIN-OR).