School Seminars and Colloquia

Generating Applicable Synthetic Instances for Branch Problems

Statistics Seminar

by Leonardo Lopes


Institution: Monash University
Date: Tue 9th August 2011
Time: 12:45 PM
Location: Room 213 Richard Berry Building, University of Melbourne

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: miheel@unimelb.edu.au