IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v37y2009i3p522-534.html
   My bibliography  Save this article

Applying statistical tests to empirically compare tabu search parameters for MAX 3-SATISFIABILITY: A case study

Author

Listed:
  • Jacobson, Sheldon H.
  • McLay, Laura A.

Abstract

The application of stochastic heuristic, like tabu search or simulated annealing, to address hard discrete optimization problems has been an important advance for efficiently obtaining good solutions in a reasonable amount of computing time. A challenge when applying such heuristics is assessing when a particular set of parameter values yields better performance compared to other such sets of parameter values. For example, it can be difficult to determine the optimal mix of memory types to incorporate into tabu search. This in turn prompts users to undertake a trial and error phase to determine the best combination of parameter settings for the problem under study. Moreover, for a given problem instance, one set of heuristic parameter settings may yield a better solution than another set of parameters, for a given initial solution. However, the performance of this heuristic on this instance for a single heuristic execution is not sufficient to assert that the first set of parameter settings will always produce superior results than the second set of parameters, for all initial solutions. This paper looks at three known statistical procedures (one of which is a basic statistical test procedure and two of which were developed for discrete event simulation (discrete) optimization) to assess and compare the computational performance of tabu search for MAX 3-SATISFIABILITY. The statistical procedures designed for application within the domain of discrete event simulation output analysis (a paired difference t-test and two multiple comparison procedures developed and studied by Nelson and others) are adapted for this new purpose. An empirical case study is reported by computationally studying MAX 3-SATISFIABILITY instances across 32 variations of tabu search.

Suggested Citation

  • Jacobson, Sheldon H. & McLay, Laura A., 2009. "Applying statistical tests to empirically compare tabu search parameters for MAX 3-SATISFIABILITY: A case study," Omega, Elsevier, vol. 37(3), pages 522-534, June.
    • Handle: RePEc:eee:jomega:v:37:y:2009:i:3:p:522-534
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305-0483(07)00115-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. M. Calhoun, Kevin & Deckro, Richard F. & Moore, James T. & Chrissis, James W. & Van Hove, John C., 2002. "Planning and re-planning in project and production scheduling," Omega, Elsevier, vol. 30(3), pages 155-170, June.
    2. Charles W. Dunnett, 1989. "Multivariate Normal Probability Integrals with Product Correlation Structure," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 38(3), pages 564-579, November.
    3. Belarmino Adenso-Díaz & Manuel Laguna, 2006. "Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search," Operations Research, INFORMS, vol. 54(1), pages 99-114, February.
    4. Sheldon H. Jacobson & Enver Yücesan, 1999. "On the Complexity of Verifying Structural Properties of Discrete Event Simulation Models," Operations Research, INFORMS, vol. 47(3), pages 476-481, June.
    5. Chen, Jeng-Fung, 2007. "A hybrid heuristic for the uncapacitated single allocation hub location problem," Omega, Elsevier, vol. 35(2), pages 211-220, April.
    6. Barry L. Nelson & Frank J. Matejcik, 1995. "Using Common Random Numbers for Indifference-Zone Selection and Multiple Comparisons in Simulation," Management Science, INFORMS, vol. 41(12), pages 1935-1945, December.
    7. Grabowski, Jøzef & Pempera, Jaroslaw, 2007. "The permutation flow shop problem with blocking. A tabu search approach," Omega, Elsevier, vol. 35(3), pages 302-311, June.
    8. Charon, Irene & Hudry, Olivier, 2001. "The noising methods: A generalization of some metaheuristics," European Journal of Operational Research, Elsevier, vol. 135(1), pages 86-101, November.
    9. Chen, Jeng-Fung & Wu, Tai-Hsi, 2006. "Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints," Omega, Elsevier, vol. 34(1), pages 81-89, January.
    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. Ma, Hong & Cheang, Brenda & Lim, Andrew & Zhang, Lei & Zhu, Yi, 2012. "An investigation into the vehicle routing problem with time windows and link capacity constraints," Omega, Elsevier, vol. 40(3), pages 336-347.
    2. Anken, F. & Beasley, J.E., 2012. "Corporate structure optimisation for multinational companies," Omega, Elsevier, vol. 40(2), pages 230-243, April.

    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. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    2. Ronconi, Débora P. & Henriques, Luís R.S., 2009. "Some heuristic algorithms for total tardiness minimization in a flowshop with blocking," Omega, Elsevier, vol. 37(2), pages 272-281, April.
    3. Anken, F. & Beasley, J.E., 2012. "Corporate structure optimisation for multinational companies," Omega, Elsevier, vol. 40(2), pages 230-243, April.
    4. Vallada, Eva & Ruiz, Rubén, 2010. "Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem," Omega, Elsevier, vol. 38(1-2), pages 57-67, February.
    5. Sündüz Dağ, 2013. "An Application On Flowshop Scheduling," Alphanumeric Journal, Bahadir Fatih Yildirim, vol. 1(1), pages 47-56, December.
    6. An, Yu & Zhang, Yu & Zeng, Bo, 2015. "The reliable hub-and-spoke design problem: Models and algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 103-122.
    7. García-Villoria, Alberto & Corominas, Albert & Nadal, Adrià & Pastor, Rafael, 2018. "Solving the accessibility windows assembly line problem level 1 and variant 1 (AWALBP-L1-1) with precedence constraints," European Journal of Operational Research, Elsevier, vol. 271(3), pages 882-895.
    8. Michael C. Fu & Jian-Qiang Hu & Chun-Hung Chen & Xiaoping Xiong, 2007. "Simulation Allocation for Determining the Best Design in the Presence of Correlated Sampling," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 101-111, February.
    9. Chen, Enming & Zhou, Zhongbao & Li, Ruiyang & Chang, Zhongxiang & Shi, Jianmai, 2024. "The multi-fleet delivery problem combined with trucks, tricycles, and drones for last-mile logistics efficiency requirements under multiple budget constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 187(C).
    10. S Alumur & B Y Kara, 2009. "A hub covering network design problem for cargo applications in Turkey," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(10), pages 1349-1359, October.
    11. Nouha Nouri & Talel Ladhari, 2018. "Evolutionary multiobjective optimization for the multi-machine flow shop scheduling problem under blocking," Annals of Operations Research, Springer, vol. 267(1), pages 413-430, August.
    12. Noureddine Bouhmala, 2019. "Combining simulated annealing with local search heuristic for MAX-SAT," Journal of Heuristics, Springer, vol. 25(1), pages 47-69, February.
    13. Wang, S. & Huang, G.H., 2015. "A multi-level Taguchi-factorial two-stage stochastic programming approach for characterization of parameter uncertainties and their interactions: An application to water resources management," European Journal of Operational Research, Elsevier, vol. 240(2), pages 572-581.
    14. Anton J. Kleywegt & Vijay S. Nori & Martin W. P. Savelsbergh, 2002. "The Stochastic Inventory Routing Problem with Direct Deliveries," Transportation Science, INFORMS, vol. 36(1), pages 94-118, February.
    15. Joaquín Bautista-Valhondo & Rocío Alfaro-Pozo, 2020. "Mixed integer linear programming models for Flow Shop Scheduling with a demand plan of job types," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 5-23, March.
    16. Julian Hof & Michael Schneider, 2021. "Intraroute Resource Replenishment with Mobile Depots," Transportation Science, INFORMS, vol. 55(3), pages 660-686, May.
    17. Manfred Horn & Rudiger Vollandt & Charles W. Dunnett, 2000. "Sample Size Determination for Testing Whether an Identified Treatment Is Best," Biometrics, The International Biometric Society, vol. 56(3), pages 879-881, September.
    18. Diana M. Negoescu & Peter I. Frazier & Warren B. Powell, 2011. "The Knowledge-Gradient Algorithm for Sequencing Experiments in Drug Discovery," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 346-363, August.
    19. A. S. Santos & A. M. Madureira & M. L. R. Varela, 2018. "The Influence of Problem Specific Neighborhood Structures in Metaheuristics Performance," Journal of Mathematics, Hindawi, vol. 2018, pages 1-14, July.
    20. Shi, Yuhui & Reich, Daniel & Epelman, Marina & Klampfl, Erica & Cohn, Amy, 2017. "An analytical approach to prototype vehicle test scheduling," Omega, Elsevier, vol. 67(C), pages 168-176.

    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:eee:jomega:v:37:y:2009:i:3:p:522-534. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.