Generating Applicable Synthetic Instances for Branch Problems
by Leonardo Lopes
Abstract: Generating valid synthetic instances for branch problems - those that contain a core problem like Knapsack or Graph Colouring, 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. We discuss a methodology for tuning instance generators of branch problems so that synthetic instances are similar to real ones and are capable of eliciting different behaviours from solvers. We also present a statistic that can be used to summarise the applicability of the instances for drawing a valid conclusion. We demonstrate the methodology by generating instances for the Udine Timetabling problem. Examples and the necessary cyberinfrastructure are available as a project from Coin-OR.
For More Information: contact: Mihee Lee. email: firstname.lastname@example.org