IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v265y2018i3p795-812.html
   My bibliography  Save this article

Operations research applications of dichotomous search

Author

Listed:
  • Hassin, Refael
  • Sarid, Anna

Abstract

An object is searched for in {1,⋯,N}. Queries for the object are sequentially conducted. A query at x reveals whether the object’s location is greater than x. The objective is to find the object within a minimal expected number of queries. This problem is called the “dichotomous search” problem and has many versions. This paper surveys dichotomous search problems with the emphasis on Operations Research applications.

Suggested Citation

  • Hassin, Refael & Sarid, Anna, 2018. "Operations research applications of dichotomous search," European Journal of Operational Research, Elsevier, vol. 265(3), pages 795-812.
    • Handle: RePEc:eee:ejores:v:265:y:2018:i:3:p:795-812
    DOI: 10.1016/j.ejor.2017.07.031
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717306586
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.07.031?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
    ---><---

    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. Sarkar, Biswajit & Saren, Sharmila, 2016. "Product inspection policy for an imperfect production system with inspection errors and warranty cost," European Journal of Operational Research, Elsevier, vol. 248(1), pages 263-271.
    2. Alpern, Steve & Snower, Dennis J., 1989. "A search model of optimal pricing and production," Engineering Costs and Production Economics, Elsevier, vol. 15(1), pages 279-284, May.
    3. Karl Hinderer & Michael Stieglitz, 2000. "Isotonicity of minimizers in polychotomous discrete interval search via lattice programming," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 51(1), pages 139-173, February.
    4. Alpern, Steve, 1989. "Geometric search theory and demand uncertainty," Engineering Costs and Production Economics, Elsevier, vol. 17(1-4), pages 245-251, August.
    5. Dahmani, Isma & Hifi, Mhand & Wu, Lei, 2016. "An exact decomposition algorithm for the generalized knapsack sharing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 761-774.
    6. Reyniers, Diane J., 1992. "Information and rationality asymmetries in a simple high-low search wage model," Economics Letters, Elsevier, vol. 38(4), pages 479-486, April.
    7. Hassin, Refael & Hotovely, Reuven, 1992. "Asymptotic analysis of dichotomous search with search and travel costs," European Journal of Operational Research, Elsevier, vol. 58(1), pages 78-89, April.
    8. John J. McCall, 1965. "Maintenance Policies for Stochastically Failing Equipment: A Survey," Management Science, INFORMS, vol. 11(5), pages 493-524, March.
    9. Ferguson, Thomas S., 1996. "A problem of minimax estimation with directional information," Statistics & Probability Letters, Elsevier, vol. 26(3), pages 205-211, February.
    10. Avinoam Tzimerman & Yale Herer, 2009. "Off-line inspections under inspection errors," IISE Transactions, Taylor & Francis Journals, vol. 41(7), pages 626-641.
    11. Young H Chun, 2008. "Economic optimization of off-line inspection procedures with inspection errors," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 863-865, June.
    12. Reyniers, Diane J., 1989. "Supply decisions for unknown linearly increasing demand," Engineering Costs and Production Economics, Elsevier, vol. 17(1-4), pages 389-393, August.
    13. Wang, Wen-Ying & Sheu, Shey-Huei & Chen, Yan-Chun & Horng, Der-Juinn, 2009. "Economic optimization of off-line inspection with rework consideration," European Journal of Operational Research, Elsevier, vol. 194(3), pages 807-813, May.
    14. S H Sheu & Y C Chen & W Y Wang & N H Shin, 2003. "Economic optimization of off-line inspection with inspection errors," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(8), pages 888-895, August.
    15. W Y Wang & S H Sheu & Y C Chen & D J Horng, 2008. "On a more general formulation of off-line inspection with inspection errors," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 865-867, June.
    16. Diane J. Reyniers, 2000. "Relative impatience determines preference between contract bargaining and repeated bargaining," International Journal of Game Theory, Springer;Game Theory Society, vol. 29(2), pages 165-176.
    17. Refael Hassin, 1984. "A Dichotomous Search for a Geometric Random Variable," Operations Research, INFORMS, vol. 32(2), pages 423-439, April.
    18. Yale T. Herer & Tzvi Raz, 2000. "Optimal Parallel Inspection for Finding the First Nonconforming Unit in a Batch---An Information Theoretic Approach," Management Science, INFORMS, vol. 46(6), pages 845-857, June.
    19. Diane Reyniers, 1990. "A High-Low Search Algorithm for a Newsboy Problem with Delayed Information Feedback," Operations Research, INFORMS, vol. 38(5), pages 838-846, October.
    20. R. Hassin & M. Henig, 1984. "Dichotomous Search for Random Objects on an Interval," Mathematics of Operations Research, INFORMS, vol. 9(2), pages 301-308, May.
    21. Bendavid, Illana & Herer, Yale T., 2009. "Economic optimization of off-line inspection in a process that also produces non-conforming units when in control and conforming units when out of control," European Journal of Operational Research, Elsevier, vol. 195(1), pages 139-155, May.
    22. Young Chun, 2010. "Bayesian inspection model for the production process subject to a random failure," IISE Transactions, Taylor & Francis Journals, vol. 42(4), pages 304-316.
    23. Nimrod Megiddo, 1979. "Combinatorial Optimization with Rational Objective Functions," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 414-424, November.
    24. Wang, Chih-Hsiung, 2007. "Economic off-line quality control strategy with two types of inspection errors," European Journal of Operational Research, Elsevier, vol. 179(1), pages 132-147, May.
    25. Donald A. Berry & Roy F. Mensch, 1986. "Discrete Search with Directional Information," Operations Research, INFORMS, vol. 34(3), pages 470-477, June.
    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. Chan, Chi Kin & Zhou, Yan & Wong, Kar Hung, 2019. "An equilibrium model of the supply chain network under multi-attribute behaviors analysis," European Journal of Operational Research, Elsevier, vol. 275(2), pages 514-535.

    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. Muhammad Babar Ramzan & Shehreyar Mohsin Qureshi & Sonia Irshad Mari & Muhammad Saad Memon & Mandeep Mittal & Muhammad Imran & Muhammad Waqas Iqbal, 2019. "Effect of Time-Varying Factors on Optimal Combination of Quality Inspectors for Offline Inspection Station," Mathematics, MDPI, vol. 7(1), pages 1-18, January.
    2. Bimal Kumar Sett & Bikash Koli Dey & Biswajit Sarkar, 2020. "Autonomated Inspection Policy for Smart Factory—An Improved Approach," Mathematics, MDPI, vol. 8(10), pages 1-19, October.
    3. Wang, Wen-Ying & Sheu, Shey-Huei & Chen, Yan-Chun & Horng, Der-Juinn, 2009. "Economic optimization of off-line inspection with rework consideration," European Journal of Operational Research, Elsevier, vol. 194(3), pages 807-813, May.
    4. Bendavid, Illana & Herer, Yale T., 2009. "Economic optimization of off-line inspection in a process that also produces non-conforming units when in control and conforming units when out of control," European Journal of Operational Research, Elsevier, vol. 195(1), pages 139-155, May.
    5. Chun, Young H., 2016. "Designing repetitive screening procedures with imperfect inspections: An empirical Bayes approach," European Journal of Operational Research, Elsevier, vol. 253(3), pages 639-647.
    6. Sarkar, Biswajit & Saren, Sharmila, 2016. "Product inspection policy for an imperfect production system with inspection errors and warranty cost," European Journal of Operational Research, Elsevier, vol. 248(1), pages 263-271.
    7. Nicholas C. Petruzzi & Maqbool Dada, 2002. "Dynamic pricing and inventory control with learning," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(3), pages 303-325, April.
    8. Costa Quinino, Roberto da & Colin, Emerson C. & Ho, Linda Lee, 2010. "Diagnostic errors and repetitive sequential classifications in on-line process control by attributes," European Journal of Operational Research, Elsevier, vol. 201(1), pages 231-238, February.
    9. Xiang, Yisha, 2013. "Joint optimization of X¯ control chart and preventive maintenance policies: A discrete-time Markov chain approach," European Journal of Operational Research, Elsevier, vol. 229(2), pages 382-390.
    10. Steffen Rebennack & Ashwin Arulselvan & Lily Elefteriadou & Panos M. Pardalos, 2010. "Complexity analysis for maximum flow problems with arc reversals," Journal of Combinatorial Optimization, Springer, vol. 19(2), pages 200-216, February.
    11. Bikash Koli Dey & Hyesung Seok, 2024. "Intelligent inventory management with autonomation and service strategy," Journal of Intelligent Manufacturing, Springer, vol. 35(1), pages 307-330, January.
    12. Liying Mu & Milind Dawande & Xianjun Geng & Vijay Mookerjee, 2016. "Milking the Quality Test: Improving the Milk Supply Chain Under Competing Collection Intermediaries," Management Science, INFORMS, vol. 62(5), pages 1259-1277, May.
    13. Pursals, Salvador Casadesús & Garzón, Federico Garriga, 2009. "Optimal building evacuation time considering evacuation routes," European Journal of Operational Research, Elsevier, vol. 192(2), pages 692-699, January.
    14. B C Giri & T Dohi, 2005. "Exact formulation of stochastic EMQ model for an unreliable production system," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(5), pages 563-575, May.
    15. Michael Holzhauser & Sven O. Krumke & Clemens Thielen, 2016. "Budget-constrained minimum cost flows," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1720-1745, May.
    16. Jianzhong Zhang & Zhenhong Liu, 2002. "A General Model of Some Inverse Combinatorial Optimization Problems and Its Solution Method Under l ∞ Norm," Journal of Combinatorial Optimization, Springer, vol. 6(2), pages 207-227, June.
    17. Evgeny Gurevsky & Sergey Kovalev & Mikhail Y. Kovalyov, 2021. "Min-max controllable risk problems," 4OR, Springer, vol. 19(1), pages 93-101, March.
    18. Belyi, Dmitriy & Popova, Elmira & Morton, David P. & Damien, Paul, 2017. "Bayesian failure-rate modeling and preventive maintenance optimization," European Journal of Operational Research, Elsevier, vol. 262(3), pages 1085-1093.
    19. Sergio Cabello, 2023. "Faster distance-based representative skyline and k-center along pareto front in the plane," Journal of Global Optimization, Springer, vol. 86(2), pages 441-466, June.
    20. Andrés Gómez & Oleg A. Prokopyev, 2021. "A Mixed-Integer Fractional Optimization Approach to Best Subset Selection," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 551-565, May.

    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:ejores:v:265:y:2018:i:3:p:795-812. 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/locate/eor .

    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.