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

Different formulations of the gray pattern problem and their optimal solutions

Author

Listed:
  • Brimberg, Jack
  • Kalczynski, Pawel
  • Drezner, Zvi

Abstract

The Gray Pattern Problem (GPP) requires selecting a given number (p) of pixels (or dots) within a central rectangle to be colored black (the remaining pixels remain white) to form a repeating pattern covering the plane that is as uniformly gray as possible. Taillard proposed the original model in 1995, which is based on the principle of minimization of entropy taken from physics. The aim of this paper is to present alternate formulations of the GPP inspired by dispersion models studied in location theory. We show that these variants have much greater tractability than the original model, while producing patterns of equivalent or better quality.

Suggested Citation

  • Brimberg, Jack & Kalczynski, Pawel & Drezner, Zvi, 2024. "Different formulations of the gray pattern problem and their optimal solutions," European Journal of Operational Research, Elsevier, vol. 316(1), pages 61-71.
    • Handle: RePEc:eee:ejores:v:316:y:2024:i:1:p:61-71
    DOI: 10.1016/j.ejor.2024.01.048
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724000882
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.01.048?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. Tammy Drezner & Zvi Drezner & Pawel Kalczynski, 2020. "Multiple obnoxious facilities location: A cooperative model," IISE Transactions, Taylor & Francis Journals, vol. 52(12), pages 1403-1412, December.
    2. Zvi Drezner & Alfonsas Misevičius & Gintaras Palubeckis, 2015. "Exact algorithms for the solution of the grey pattern quadratic assignment problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(1), pages 85-105, August.
    3. Şenay Ağca & Burak Eksioglu & Jay B. Ghosh, 2000. "Lagrangian solution of maximum dispersion problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(2), pages 97-114, March.
    4. Prokopyev, Oleg A. & Kong, Nan & Martinez-Torres, Dayna L., 2009. "The equitable dispersion problem," European Journal of Operational Research, Elsevier, vol. 197(1), pages 59-67, August.
    5. P. G. Szabó & M. Cs. Markót & T. Csendes & E. Specht & L. G. Casado & I. García, 2007. "New Approaches to Circle Packing in a Square," Springer Optimization and Its Applications, Springer, number 978-0-387-45676-8, June.
    6. López, C.O. & Beasley, J.E., 2011. "A heuristic for the circle packing problem with a variety of containers," European Journal of Operational Research, Elsevier, vol. 214(3), pages 512-525, November.
    7. Zvi Drezner & Pawel Kalczynski, 2017. "The continuous grey pattern problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(5), pages 469-483, May.
    8. Zvi Drezner, 2015. "The Quadratic Assignment Problem," Springer Books, in: Gilbert Laporte & Stefan Nickel & Francisco Saldanha da Gama (ed.), Location Science, edition 127, chapter 0, pages 345-363, Springer.
    Full references (including those not matched with items on IDEAS)

    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. Parreño, Francisco & Álvarez-Valdés, Ramón & Martí, Rafael, 2021. "Measuring diversity. A review and an empirical analysis," European Journal of Operational Research, Elsevier, vol. 289(2), pages 515-532.
    2. Martí, Rafael & Martínez-Gavara, Anna & Pérez-Peló, Sergio & Sánchez-Oro, Jesús, 2022. "A review on discrete diversity and dispersion maximization from an OR perspective," European Journal of Operational Research, Elsevier, vol. 299(3), pages 795-813.
    3. Frank J. Kampas & János D. Pintér & Ignacio Castillo, 2020. "Packing ovals in optimized regular polygons," Journal of Global Optimization, Springer, vol. 77(1), pages 175-196, May.
    4. Juan F. Gomez & Anna Martínez-Gavara & Javier Panadero & Angel A. Juan & Rafael Martí, 2024. "A Forward–Backward Simheuristic for the Stochastic Capacitated Dispersion Problem," Mathematics, MDPI, vol. 12(6), pages 1-22, March.
    5. Pawel Kalczynski & Zvi Goldstein & Zvi Drezner, 2023. "An Efficient Heuristic for the k-Partitioning Problem," SN Operations Research Forum, Springer, vol. 4(4), pages 1-21, December.
    6. Kalczynski, Pawel & Drezner, Zvi, 2022. "The Obnoxious Facilities Planar p-Median Problem with Variable Sizes," Omega, Elsevier, vol. 111(C).
    7. Amirgaliyeva, Zhazira & Mladenović, Nenad & Todosijević, Raca & Urošević, Dragan, 2017. "Solving the maximum min-sum dispersion by alternating formulations of two different problems," European Journal of Operational Research, Elsevier, vol. 260(2), pages 444-459.
    8. Matsypura, Dmytro & Thompson, Ryan & Vasnev, Andrey L., 2018. "Optimal selection of expert forecasts with integer programming," Omega, Elsevier, vol. 78(C), pages 165-175.
    9. San Segundo, Pablo & Coniglio, Stefano & Furini, Fabio & Ljubić, Ivana, 2019. "A new branch-and-bound algorithm for the maximum edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 76-90.
    10. Pawel Kalczynski & Atsuo Suzuki & Zvi Drezner, 2023. "Obnoxious facility location in multiple dimensional space," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(2), pages 331-354, July.
    11. Papp, Dávid & Regős, Krisztina & Domokos, Gábor & Bozóki, Sándor, 2023. "The smallest mono-unstable convex polyhedron with point masses has 8 faces and 11 vertices," European Journal of Operational Research, Elsevier, vol. 310(2), pages 511-517.
    12. Wang, Yang & Wu, Qinghua & Glover, Fred, 2017. "Effective metaheuristic algorithms for the minimum differential dispersion problem," European Journal of Operational Research, Elsevier, vol. 258(3), pages 829-843.
    13. Juan S. Borrero & Colin Gillen & Oleg A. Prokopyev, 2017. "Fractional 0–1 programming: applications and algorithms," Journal of Global Optimization, Springer, vol. 69(1), pages 255-282, September.
    14. Lei, Ting L. & Church, Richard L., 2015. "On the unified dispersion problem: Efficient formulations and exact algorithms," European Journal of Operational Research, Elsevier, vol. 241(3), pages 622-630.
    15. Frank J. Kampas & János D. Pintér & Ignacio Castillo, 2023. "Model Development and Solver Demonstrations Using Randomized Test Problems," SN Operations Research Forum, Springer, vol. 4(1), pages 1-15, March.
    16. Zhu, Dingju, 2016. "Quasi-human seniority-order algorithm for unequal circles packing," Chaos, Solitons & Fractals, Elsevier, vol. 89(C), pages 506-517.
    17. Stojiljković, D.Lj. & Vrhovac, S.B., 2017. "Kinetics of particle deposition at heterogeneous surfaces," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 488(C), pages 16-29.
    18. Zhengguan Dai & Kathleen Xu & Melkior Ornik, 2021. "Repulsion-based p-dispersion with distance constraints in non-convex polygons," Annals of Operations Research, Springer, vol. 307(1), pages 75-91, December.
    19. Rennen, G., 2008. "Subset Selection from Large Datasets for Kriging Modeling," Other publications TiSEM 9dfe6396-1933-45c0-b4e3-5, Tilburg University, School of Economics and Management.
    20. Niblett, Matthew R. & Church, Richard L., 2015. "The disruptive anti-covering location problem," European Journal of Operational Research, Elsevier, vol. 247(3), pages 764-773.

    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:316:y:2024:i:1:p:61-71. 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.