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. 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).
    6. 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).
    7. Jon Lee, 1998. "Constrained Maximum-Entropy Sampling," Operations Research, INFORMS, vol. 46(5), pages 655-664, October.
    8. 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.
    9. Kurt M. Anstreicher, 2020. "Efficient Solution of Maximum-Entropy Sampling Problems," Operations Research, INFORMS, vol. 68(6), pages 1826-1835, November.
    10. Kurt M. Anstreicher, 2018. "Maximum-entropy sampling and the Boolean quadric polytope," Journal of Global Optimization, Springer, vol. 72(4), pages 603-618, December.
    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. repec:dgr:rugsom:99a17 is not listed on IDEAS
    6. 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).
    7. 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).
    8. Goldengorin, Boris, 2009. "Maximization of submodular functions: Theory and enumeration algorithms," European Journal of Operational Research, Elsevier, vol. 198(1), pages 102-112, October.
    9. 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.
    10. 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.
    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. 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.
    17. 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.
    18. Ali Fattahi & Sriram Dasu & Reza Ahmadi, 2019. "Mass Customization and “Forecasting Options’ Penetration Rates Problem”," Operations Research, INFORMS, vol. 67(4), pages 1120-1134, July.
    19. Bo Jiang & Tianyi Lin & Shiqian Ma & Shuzhong Zhang, 2019. "Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis," Computational Optimization and Applications, Springer, vol. 72(1), pages 115-157, January.
    20. James Chok & Geoffrey M. Vasil, 2023. "Convex optimization over a probability simplex," Papers 2305.09046, arXiv.org.
    21. A. de Palma & Y. Nesterov, 2001. "Stationary Dynamic Solutions in Congested Transportation Networks: Summary and Perspectives," THEMA Working Papers 2001-19, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.

    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.