Generating applicable synthetic instances for branch problems

Abstract

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 cyberinf..