Generating Applicable Synthetic Instances for Branch Problems

• 成果类型: Article
• 署名作者: Lopes, Leo; Smith-Miles, Kate
• 署名单位: SAS Institute Inc; Monash University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2013.1169
• 发表日期: 2013
• 页码: 563-577
• 关键词: Optimization; prediction; difficulty

摘要

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