IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v72y2018i4d10.1007_s10898-018-0662-x.html
   My bibliography  Save this article

Maximum-entropy sampling and the Boolean quadric polytope

Author

Listed:
  • Kurt M. Anstreicher

    (University of Iowa)

Abstract

We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean quadric polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the use of a relaxation of BQP that imposes semidefiniteness and a small number of equality constraints gives excellent bounds on many benchmark instances. These bounds can be further tightened by imposing additional inequality constraints that are valid for the BQP. Duality information associated with the BQP-based bounds can be used to fix variables to 0/1 values, and also as the basis for the implementation of a “strong branching” strategy. A branch-and-bound algorithm using the BQP-based bounds solves some benchmark instances of MESP to optimality for the first time.

Suggested Citation

  • Kurt M. Anstreicher, 2018. "Maximum-entropy sampling and the Boolean quadric polytope," Journal of Global Optimization, Springer, vol. 72(4), pages 603-618, December.
    • Handle: RePEc:spr:jglopt:v:72:y:2018:i:4:d:10.1007_s10898-018-0662-x
    DOI: 10.1007/s10898-018-0662-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-018-0662-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-018-0662-x?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. Kim-Chuan Toh & Michael J. Todd & Reha H. Tütüncü, 2012. "On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0," International Series in Operations Research & Management Science, in: Miguel F. Anjos & Jean B. Lasserre (ed.), Handbook on Semidefinite, Conic and Polynomial Optimization, chapter 0, pages 715-754, Springer.
    2. Chun-Wa Ko & Jon Lee & Maurice Queyranne, 1995. "An Exact Algorithm for Maximum Entropy Sampling," Operations Research, INFORMS, vol. 43(4), pages 684-691, August.
    3. ANSTREICHER, Kurt M. & FAMPA, Marcia & LEE, Jon & WILLIAMS, Joy, 1999. "Using continuous nonlinear relaxations to solve constrained maximum-entropy sampling problems," LIDAM Reprints CORE 1412, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. ANSTREICHER, Kurt M. & FAMPA, Marcia & LEE , Jon & WILLIAMS, Joy, 2001. "Maximum-entropy remote sampling," LIDAM Reprints CORE 1494, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Jon Lee, 1998. "Constrained Maximum-Entropy Sampling," Operations Research, INFORMS, vol. 46(5), pages 655-664, October.
    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. Hessa Al-Thani & Jon Lee, 2020. "An R Package for Generating Covariance Matrices for Maximum-Entropy Sampling from Precipitation Chemistry Data," SN Operations Research Forum, Springer, vol. 1(3), pages 1-21, September.
    2. Zhongzhu Chen & Marcia Fampa & Jon Lee, 2023. "On Computing with Some Convex Relaxations for the Maximum-Entropy Sampling Problem," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 368-385, March.
    3. Kurt M. Anstreicher, 2020. "Efficient Solution of Maximum-Entropy Sampling Problems," Operations Research, INFORMS, vol. 68(6), pages 1826-1835, November.

    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. Kurt M. Anstreicher, 2020. "Efficient Solution of Maximum-Entropy Sampling Problems," Operations Research, INFORMS, vol. 68(6), pages 1826-1835, November.
    2. Zhongzhu Chen & Marcia Fampa & Jon Lee, 2023. "On Computing with Some Convex Relaxations for the Maximum-Entropy Sampling Problem," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 368-385, March.
    3. Hessa Al-Thani & Jon Lee, 2020. "An R Package for Generating Covariance Matrices for Maximum-Entropy Sampling from Precipitation Chemistry Data," SN Operations Research Forum, Springer, vol. 1(3), pages 1-21, September.
    4. HOFFMAN, Alan & LEE, Jon & WILLIAMS, Joy, 2000. "New upper bounds for maximum-entropy sampling," LIDAM Discussion Papers CORE 2000012, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Goldengorin, Boris, 2009. "Maximization of submodular functions: Theory and enumeration algorithms," European Journal of Operational Research, Elsevier, vol. 198(1), pages 102-112, October.
    6. repec:dgr:rugsom:99a17 is not listed on IDEAS
    7. Boris Goldengorin & Gerard Sierksma & Gert A. Tijssen & Michael Tso, 1999. "The Data-Correcting Algorithm for the Minimization of Supermodular Functions," Management Science, INFORMS, vol. 45(11), pages 1539-1551, November.
    8. Goldengorin, Boris & Tijssen, Gert A. & Tso, Michael, 1999. "The maximization of submodular functions : old and new proofs for the correctness of the dichotomy algorithm," Research Report 99A17, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    9. Yildiz, Anil & Mern, John & Kochenderfer, Mykel J. & Howland, Michael F., 2023. "Towards sequential sensor placements on a wind farm to maximize lifetime energy and profit," Renewable Energy, Elsevier, vol. 216(C).
    10. Linda Altieri & Daniela Cocchi, 2021. "Spatial Sampling for Non‐compact Patterns," International Statistical Review, International Statistical Institute, vol. 89(3), pages 532-549, December.
    11. Duarte, Belmiro P.M. & Atkinson, Anthony C. & P. Singh, Satya & S. Reis, Marco, 2023. "Optimal design of experiments for hypothesis testing on ordered treatments via intersection-union tests," LSE Research Online Documents on Economics 115187, London School of Economics and Political Science, LSE Library.
    12. Xuesong Zhou & George F. List, 2010. "An Information-Theoretic Sensor Location Model for Traffic Origin-Destination Demand Estimation Applications," Transportation Science, INFORMS, vol. 44(2), pages 254-273, May.
    13. Belmiro P. M. Duarte & Anthony C. Atkinson & Satya P. Singh & Marco S. Reis, 2023. "Optimal design of experiments for hypothesis testing on ordered treatments via intersection-union tests," Statistical Papers, Springer, vol. 64(2), pages 587-615, April.
    14. Theodore T. Allen & Olivia K. Hernand & Abdullah Alomair, 2020. "Optimal Off-line Experimentation for Games," Decision Analysis, INFORMS, vol. 17(4), pages 277-298, December.
    15. Kristijan Cafuta, 2019. "Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools," 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. 27(2), pages 397-413, June.
    16. Sungwoo Park & Dianne P. O’Leary, 2015. "A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 166(2), pages 558-571, August.
    17. Han, Yong & Wang, Xue-sheng & Zhang, Zhao & Zhang, Hao-nan, 2020. "Multi-objective optimization of geometric parameters for the helically coiled tube using Markowitz optimization theory," Energy, Elsevier, vol. 192(C).
    18. Dawen Yan & Xiaohui Zhang & Mingzheng Wang, 2021. "A robust bank asset allocation model integrating credit-rating migration risk and capital adequacy ratio regulations," Annals of Operations Research, Springer, vol. 299(1), pages 659-710, April.
    19. Boyang Shang & Daniel W. Apley & Sanjay Mehrotra, 2023. "Diversity Subsampling: Custom Subsamples from Large Data Sets," INFORMS Joural on Data Science, INFORMS, vol. 2(2), pages 161-182, October.
    20. He, Qie & Zhang, Xiaochen & Nip, Kameng, 2017. "Speed optimization over a path with heterogeneous arc costs," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 198-214.

    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:spr:jglopt:v:72:y:2018:i:4:d:10.1007_s10898-018-0662-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.