IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v35y2023i2p368-385.html
   My bibliography  Save this article

On Computing with Some Convex Relaxations for the Maximum-Entropy Sampling Problem

Author

Listed:
  • Zhongzhu Chen

    (Industrial and Operations Engineering Department, University of Michigan, Ann Arbor, Michigan 48109)

  • Marcia Fampa

    (Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ 21941-901, Brazil)

  • Jon Lee

    (Industrial and Operations Engineering Department, University of Michigan, Ann Arbor, Michigan 48109)

Abstract

Based on a factorization of an input covariance matrix, we define a mild generalization of an upper bound of Nikolov and of Li and Xie for the NP-hard constrained maximum-entropy sampling problem ( CMESP ). We demonstrate that this factorization bound is invariant under scaling and independent of the particular factorization chosen. We give a variable-fixing methodology that could be used in a branch-and-bound scheme based on the factorization bound for exact solution of CMESP , and we demonstrate that its ability to fix is independent of the factorization chosen. We report on successful experiments with a commercial nonlinear programming solver. We further demonstrate that the known “mixing” technique can be successfully used to combine the factorization bound with the factorization bound of the complementary CMESP and with the “linx bound” of Anstreicher.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:orijoc:v:35:y:2023:i:2:p:368-385
    DOI: 10.1287/ijoc.2022.1264
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1264
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1264?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. Caselton, W. F. & Zidek, J. V., 1984. "Optimal monitoring network designs," Statistics & Probability Letters, Elsevier, vol. 2(4), pages 223-227, August.
    2. J. V. Zidek & W. Sun & N. D. Le, 2000. "Designing and integrating composite networks for monitoring multivariate gaussian pollution fields," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 49(1), pages 63-79.
    3. 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.
    4. P. Sebastiani & H. P. Wynn, 2000. "Maximum entropy sampling and optimal Bayesian experimental design," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 62(1), pages 145-157.
    5. Kurt M. Anstreicher, 2020. "Efficient Solution of Maximum-Entropy Sampling Problems," Operations Research, INFORMS, vol. 68(6), pages 1826-1835, November.
    6. Kurt M. Anstreicher, 2018. "Maximum-entropy sampling and the Boolean quadric polytope," Journal of Global Optimization, Springer, vol. 72(4), pages 603-618, December.
    7. 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).
    8. 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).
    9. Jon Lee, 1998. "Constrained Maximum-Entropy Sampling," Operations Research, INFORMS, vol. 46(5), pages 655-664, October.
    10. Marguerite Frank & Philip Wolfe, 1956. "An algorithm for quadratic programming," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 95-110, March.
    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. 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. Kurt M. Anstreicher, 2020. "Efficient Solution of Maximum-Entropy Sampling Problems," Operations Research, INFORMS, vol. 68(6), pages 1826-1835, November.
    3. Kurt M. Anstreicher, 2018. "Maximum-entropy sampling and the Boolean quadric polytope," Journal of Global Optimization, Springer, vol. 72(4), pages 603-618, December.
    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. 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).
    8. 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.
    9. 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.
    10. 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).
    11. Guillaume Sagnol & Edouard Pauwels, 2019. "An unexpected connection between Bayes A-optimal designs and the group lasso," Statistical Papers, Springer, vol. 60(2), pages 565-584, April.
    12. Abdelfettah Laouzai & Rachid Ouafi, 2022. "A prediction model for atmospheric pollution reduction from urban traffic," Environment and Planning B, , vol. 49(2), pages 566-584, February.
    13. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    14. Francesco Rinaldi & Damiano Zeffiro, 2023. "Avoiding bad steps in Frank-Wolfe variants," Computational Optimization and Applications, Springer, vol. 84(1), pages 225-264, January.
    15. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    16. Tiến-Sơn Phạm, 2019. "Optimality Conditions for Minimizers at Infinity in Polynomial Programming," Management Science, INFORMS, vol. 44(4), pages 1381-1395, November.
    17. Filippozzi, Rafaela & Gonçalves, Douglas S. & Santos, Luiz-Rafael, 2023. "First-order methods for the convex hull membership problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 17-33.
    18. Ke, Ginger Y. & Zhang, Huiwen & Bookbinder, James H., 2020. "A dual toll policy for maintaining risk equity in hazardous materials transportation with fuzzy incident rate," International Journal of Production Economics, Elsevier, vol. 227(C).
    19. Friesz, Terry L. & Tourreilles, Francisco A. & Han, Anthony Fu-Wha, 1979. "Multi-Criteria Optimization Methods in Transport Project Evaluation: The Case of Rural Roads in Developing Countries," Transportation Research Forum Proceedings 1970s 318817, Transportation Research Forum.
    20. Damian Clarke & Daniel Paila~nir & Susan Athey & Guido Imbens, 2023. "Synthetic Difference In Differences Estimation," Papers 2301.11859, arXiv.org, revised Feb 2023.
    21. Fabiana R. Oliveira & Orizon P. Ferreira & Gilson N. Silva, 2019. "Newton’s method with feasible inexact projections for solving constrained generalized equations," Computational Optimization and Applications, Springer, vol. 72(1), pages 159-177, January.

    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:orijoc:v:35:y:2023:i:2:p:368-385. 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.