IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v61y2013i3p563-577.html

Generating Applicable Synthetic Instances for Branch Problems

Author

Listed:
  • Leo Lopes

    (SAS Institute, Cary, North Carolina 27513)

  • Kate Smith-Miles

    (School of Mathematical Sciences, Monash University, Clayton, Victoria 3800, Australia)

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 cyberinfrastructure are available as a project from Computational Infrastructure for Operations Research (COIN-OR).

Suggested Citation

  • Leo Lopes & Kate Smith-Miles, 2013. "Generating Applicable Synthetic Instances for Branch Problems," Operations Research, INFORMS, vol. 61(3), pages 563-577, June.
    • Handle: RePEc:inm:oropre:v:61:y:2013:i:3:p:563-577
    DOI: 10.1287/opre.2013.1169
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2013.1169
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2013.1169?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Gary J. Koehler, 2007. "Conditions that Obviate the No-Free-Lunch Theorems for Optimization," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 273-279, May.
    2. Dimitris Achlioptas & Assaf Naor & Yuval Peres, 2005. "Rigorous location of phase transitions in hard optimization problems," Nature, Nature, vol. 435(7043), pages 759-764, June.
    3. A L Tuson & S A Harrison, 2005. "Problem difficulty of real instances of convoy planning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(7), pages 763-775, July.
    4. Raymond R. Hill & Charles H. Reilly, 2000. "The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance," Management Science, INFORMS, vol. 46(2), pages 302-317, February.
    5. Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
    6. Nicholas G. Hall & Marc E. Posner, 2007. "Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures," Operations Research, INFORMS, vol. 55(4), pages 703-716, August.
    7. Nicholas G. Hall & Marc E. Posner, 2001. "Generating Experimental Data for Computational Testing with Machine Scheduling Applications," Operations Research, INFORMS, vol. 49(6), pages 854-865, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ceschia, Sara & Di Gaspero, Luca & Schaerf, Andrea, 2023. "Educational timetabling: Problems, benchmarks, and state-of-the-art results," European Journal of Operational Research, Elsevier, vol. 308(1), pages 1-18.
    2. Arnaud Coster & Nysret Musliu & Andrea Schaerf & Johannes Schoisswohl & Kate Smith-Miles, 2022. "Algorithm selection and instance space analysis for curriculum-based course timetabling," Journal of Scheduling, Springer, vol. 25(1), pages 35-58, February.
    3. Van Bulck, David & Goossens, Dries, 2023. "The international timetabling competition on sports timetabling (ITC2021)," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1249-1267.
    4. Ahmed Ghoniem & Tulay Flamand & Mohamed Haouari, 2016. "Optimization-Based Very Large-Scale Neighborhood Search for Generalized Assignment Problems with Location/Allocation Considerations," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 575-588, August.
    5. Van Bulck, David & Goossens, Dries & Clarner, Jan-Patrick & Dimitsas, Angelos & Fonseca, George H.G. & Lamas-Fernandez, Carlos & Lester, Martin Mariusz & Pedersen, Jaap & Phillips, Antony E. & Rosati,, 2024. "Which algorithm to select in sports timetabling?," European Journal of Operational Research, Elsevier, vol. 318(2), pages 575-591.
    6. Andrea Bettinelli & Valentina Cacchiani & Roberto Roberti & Paolo Toth, 2015. "An overview of curriculum-based course timetabling," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 313-349, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2023. "Features for the 0-1 knapsack problem based on inclusionwise maximal solutions," European Journal of Operational Research, Elsevier, vol. 311(1), pages 36-55.
    2. Jorge A. Sefair & Oscar Guaje & Andrés L. Medaglia, 2021. "A column-oriented optimization approach for the generation of correlated random vectors," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 777-808, September.
    3. Reilly, Charles H. & Sapkota, Nabin, 2015. "A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances," European Journal of Operational Research, Elsevier, vol. 241(3), pages 642-652.
    4. Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
    5. Alexander A. Lazarev & Nikolay Pravdivets & Frank Werner, 2020. "On the Dual and Inverse Problems of Scheduling Jobs to Minimize the Maximum Penalty," Mathematics, MDPI, vol. 8(7), pages 1-15, July.
    6. Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2022. "A new class of hard problem instances for the 0–1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 301(3), pages 841-854.
    7. Jeff Kahn & Gil Kalai, 2006. "Thresholds and expectation thresholds," Levine's Bibliography 122247000000001294, UCLA Department of Economics.
    8. Nicholas G. Hall & Zhixin Liu, 2010. "Capacity Allocation and Scheduling in Supply Chains," Operations Research, INFORMS, vol. 58(6), pages 1711-1725, December.
    9. Lin, B.M.T. & Liu, S.T., 2008. "Maximizing the reward in the relocation problem with generalized due dates," International Journal of Production Economics, Elsevier, vol. 115(1), pages 55-63, September.
    10. Guy Kindler & Assaf Naor & Gideon Schechtman, 2010. "The UGC Hardness Threshold of the L p Grothendieck Problem," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 267-283, May.
    11. Kedad-Sidhoum, Safia & Solis, Yasmin Rios & Sourd, Francis, 2008. "Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1305-1316, September.
    12. Joseph G. Szmerekovsky & George L. Vairaktarakis, 2006. "Maximizing project cash availability," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(4), pages 272-284, June.
    13. Maurizio Bruglieri & Roberto Cordone & Leo Liberti, 2022. "Maximum feasible subsystems of distance geometry constraints," Journal of Global Optimization, Springer, vol. 83(1), pages 29-47, May.
    14. Giorgi Tadumadze & Nils Boysen & Simon Emde, 2020. "Robust spotter scheduling in trailer yards," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(4), pages 995-1021, December.
    15. Zhang, Jun & Liu, Feng & Tang, Jiafu & Li, Yanhui, 2019. "The online integrated order picking and delivery considering Pickers’ learning effects for an O2O community supermarket," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 180-199.
    16. Nicholas G. Hall & Daniel Zhuoyu Long & Jin Qi & Melvyn Sim, 2015. "Managing Underperformance Risk in Project Portfolio Selection," Operations Research, INFORMS, vol. 63(3), pages 660-675, June.
    17. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.
    18. Nicholas G. Hall & Zhixin Liu, 2023. "Scheduling with present bias," Production and Operations Management, Production and Operations Management Society, vol. 32(6), pages 1743-1759, June.
    19. Kimbrough, Steven Orla & Koehler, Gary J. & Lu, Ming & Wood, David Harlan, 2008. "On a Feasible-Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch," European Journal of Operational Research, Elsevier, vol. 190(2), pages 310-327, October.
    20. Arnaud Fréville & SaÏd Hanafi, 2005. "The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects," Annals of Operations Research, Springer, vol. 139(1), pages 195-227, October.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:61:y:2013:i:3:p:563-577. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.