IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i3p713-728.html
   My bibliography  Save this article

Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation

Author

Listed:
  • Karthik Natarajan

    (Department of Management Sciences, City University of Hong Kong, Hong Kong)

  • Chung Piaw Teo

    (Department of Decision Sciences, NUS Business School, National University of Singapore, Singapore 117591)

  • Zhichao Zheng

    (Department of Decision Sciences, NUS Business School, National University of Singapore, Singapore 117591)

Abstract

In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second-moment matrix of the nonnegative objective coefficients are assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected value of a mixed 0-1 linear program in maximization form with random objective is a completely positive program. This naturally leads to semidefinite programming relaxations that are solvable in polynomial time but provide weaker bounds. The result can be extended to deal with uncertainty in the moments and more complicated objective functions. Examples from order statistics and project networks highlight the applications of the model. Our belief is that the model will open an interesting direction for future research in discrete and linear optimization under uncertainty.

Suggested Citation

  • Karthik Natarajan & Chung Piaw Teo & Zhichao Zheng, 2011. "Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation," Operations Research, INFORMS, vol. 59(3), pages 713-728, June.
    • Handle: RePEc:inm:oropre:v:59:y:2011:i:3:p:713-728
    DOI: 10.1287/opre.1110.0918
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.0918
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.0918?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. NESTEROV, Yu., 2000. "Squared functional systems and optimization problems," LIDAM Reprints CORE 1472, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Karthik Natarajan & Miao Song & Chung-Piaw Teo, 2009. "Persistency Model and Its Applications in Choice Modeling," Management Science, INFORMS, vol. 55(3), pages 453-469, March.
    3. G. C. Calafiore & L. El Ghaoui, 2006. "On Distributionally Robust Chance-Constrained Linear Programs," Journal of Optimization Theory and Applications, Springer, vol. 130(1), pages 1-22, July.
    4. Dimitris Bertsimas & Xuan Vinh Doan & Karthik Natarajan & Chung-Piaw Teo, 2010. "Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 580-602, August.
    5. Luis F. Zuluaga & Javier F. Peña, 2005. "A Conic Programming Approach to Generalized Tchebycheff Inequalities," Mathematics of Operations Research, INFORMS, vol. 30(2), pages 369-388, May.
    6. Ioana Popescu, 2007. "Robust Mean-Covariance Solutions for Stochastic Optimization," Operations Research, INFORMS, vol. 55(1), pages 98-112, February.
    7. Erick Delage & Yinyu Ye, 2010. "Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems," Operations Research, INFORMS, vol. 58(3), pages 595-612, 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. Badenbroek, Riley & de Klerk, Etienne, 2020. "An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix," Other publications TiSEM 876ff1ab-036c-4635-9688-1, Tilburg University, School of Economics and Management.
    2. Sarah Yini Gao & David Simchi-Levi & Chung-Piaw Teo & Zhenzhen Yan, 2019. "Disruption Risk Mitigation in Supply Chains: The Risk Exposure Index Revisited," Operations Research, INFORMS, vol. 67(3), pages 831-852, May.
    3. Zhenzhen Yan & Sarah Yini Gao & Chung Piaw Teo, 2018. "On the Design of Sparse but Efficient Structures in Operations," Management Science, INFORMS, vol. 64(7), pages 3421-3445, July.
    4. Mengshi Lu & Zuo‐Jun Max Shen, 2021. "A Review of Robust Operations Management under Model Uncertainty," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1927-1943, June.
    5. Zhichao Zheng & Karthik Natarajan & Chung-Piaw Teo, 2016. "Least Squares Approximation to the Distribution of Project Completion Times with Gaussian Uncertainty," Operations Research, INFORMS, vol. 64(6), pages 1406-1421, December.
    6. Riley Badenbroek & Etienne de Klerk, 2022. "An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1115-1125, March.
    7. Li, Xiaobo & Natarajan, Karthik & Teo, Chung-Piaw & Zheng, Zhichao, 2014. "Distributionally robust mixed integer linear programs: Persistency models with applications," European Journal of Operational Research, Elsevier, vol. 233(3), pages 459-473.
    8. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    9. Immanuel Bomze & Werner Schachinger & Gabriele Uchida, 2012. "Think co(mpletely)positive ! Matrix properties, examples and a clustered bibliography on copositive optimization," Journal of Global Optimization, Springer, vol. 52(3), pages 423-445, March.
    10. Long He & Ho-Yin Mak & Ying Rong & Zuo-Jun Max Shen, 2017. "Service Region Design for Urban Electric Vehicle Sharing Systems," Manufacturing & Service Operations Management, INFORMS, vol. 19(2), pages 309-327, May.
    11. Immanuel M. Bomze, 2018. "Building a completely positive factorization," 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. 26(2), pages 287-305, June.
    12. Ho-Yin Mak & Ying Rong & Jiawei Zhang, 2015. "Appointment Scheduling with Limited Distributional Information," Management Science, INFORMS, vol. 61(2), pages 316-334, February.
    13. Guanglin Xu & Samuel Burer, 2018. "A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming," Computational Management Science, Springer, vol. 15(1), pages 111-134, January.
    14. Qingxia Kong & Shan Li & Nan Liu & Chung-Piaw Teo & Zhenzhen Yan, 2020. "Appointment Scheduling Under Time-Dependent Patient No-Show Behavior," Management Science, INFORMS, vol. 66(8), pages 3480-3500, August.
    15. Areesh Mittal & Can Gokalp & Grani A. Hanasusanto, 2020. "Robust Quadratic Programming with Mixed-Integer Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 201-218, April.
    16. Xuan Wang & Jiawei Zhang, 2015. "Process Flexibility: A Distribution-Free Bound on the Performance of k -Chain," Operations Research, INFORMS, vol. 63(3), pages 555-571, June.
    17. Badenbroek, Riley & de Klerk, Etienne, 2022. "An analytic center cutting plane method to determine complete positivity of a matrix," Other publications TiSEM 088da653-b943-4ed0-9720-6, Tilburg University, School of Economics and Management.
    18. Zhang, Abraham & Zheng, Zhichao & Teo, Chung-Piaw, 2022. "Schedule reliability in liner shipping timetable design: A convex programming approach," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 499-525.
    19. Immanuel M. Bomze & Vaithilingam Jeyakumar & Guoyin Li, 2018. "Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations," Journal of Global Optimization, Springer, vol. 71(3), pages 551-569, July.
    20. Jia Shu & Mabel C. Chou & Qizhang Liu & Chung-Piaw Teo & I-Lin Wang, 2013. "Models for Effective Deployment and Redistribution of Bicycles Within Public Bicycle-Sharing Systems," Operations Research, INFORMS, vol. 61(6), pages 1346-1359, December.

    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. Li, Xiaobo & Natarajan, Karthik & Teo, Chung-Piaw & Zheng, Zhichao, 2014. "Distributionally robust mixed integer linear programs: Persistency models with applications," European Journal of Operational Research, Elsevier, vol. 233(3), pages 459-473.
    2. Wolfram Wiesemann & Daniel Kuhn & Melvyn Sim, 2014. "Distributionally Robust Convex Optimization," Operations Research, INFORMS, vol. 62(6), pages 1358-1376, December.
    3. Postek, Krzysztof & Ben-Tal, A. & den Hertog, Dick & Melenberg, Bertrand, 2015. "Exact Robust Counterparts of Ambiguous Stochastic Constraints Under Mean and Dispersion Information," Other publications TiSEM d718e419-a375-4707-b206-e, Tilburg University, School of Economics and Management.
    4. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    5. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    6. Wang, Changjun & Chen, Shutong, 2020. "A distributionally robust optimization for blood supply network considering disasters," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).
    7. Qiaoming Han & Donglei Du & Luis F. Zuluaga, 2014. "Technical Note---A Risk- and Ambiguity-Averse Extension of the Max-Min Newsvendor Order Formula," Operations Research, INFORMS, vol. 62(3), pages 535-542, June.
    8. Postek, Krzysztof & Ben-Tal, A. & den Hertog, Dick & Melenberg, Bertrand, 2015. "Exact Robust Counterparts of Ambiguous Stochastic Constraints Under Mean and Dispersion Information," Discussion Paper 2015-030, Tilburg University, Center for Economic Research.
    9. Erick Delage & Sharon Arroyo & Yinyu Ye, 2014. "The Value of Stochastic Modeling in Two-Stage Stochastic Programs with Cost Uncertainty," Operations Research, INFORMS, vol. 62(6), pages 1377-1393, December.
    10. Luo, Fengqiao & Mehrotra, Sanjay, 2019. "Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models," European Journal of Operational Research, Elsevier, vol. 278(1), pages 20-35.
    11. Lu, Mengshi & Nakao, Hideaki & Shen, Siqian & Zhao, Lin, 2021. "Non-profit resource allocation and service scheduling with cross-subsidization and uncertain resource consumptions," Omega, Elsevier, vol. 99(C).
    12. Huan Xu & Shie Mannor, 2012. "Distributionally Robust Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 288-300, May.
    13. Guanglin Xu & Samuel Burer, 2018. "A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming," Computational Management Science, Springer, vol. 15(1), pages 111-134, January.
    14. Yongzhen Li & Xueping Li & Jia Shu & Miao Song & Kaike Zhang, 2022. "A General Model and Efficient Algorithms for Reliable Facility Location Problem Under Uncertain Disruptions," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 407-426, January.
    15. Ho-Yin Mak & Ying Rong & Jiawei Zhang, 2015. "Appointment Scheduling with Limited Distributional Information," Management Science, INFORMS, vol. 61(2), pages 316-334, February.
    16. Manish Bansal & Yingqiu Zhang, 2021. "Scenario-based cuts for structured two-stage stochastic and distributionally robust p-order conic mixed integer programs," Journal of Global Optimization, Springer, vol. 81(2), pages 391-433, October.
    17. L. Jeff Hong & Zhiyuan Huang & Henry Lam, 2021. "Learning-Based Robust Optimization: Procedures and Statistical Guarantees," Management Science, INFORMS, vol. 67(6), pages 3447-3467, June.
    18. Xuan Wang & Jiawei Zhang, 2015. "Process Flexibility: A Distribution-Free Bound on the Performance of k -Chain," Operations Research, INFORMS, vol. 63(3), pages 555-571, June.
    19. Corina Birghila & Tim J. Boonen & Mario Ghossoub, 2023. "Optimal insurance under maxmin expected utility," Finance and Stochastics, Springer, vol. 27(2), pages 467-501, April.
    20. Dey, Shibshankar & Kim, Cheolmin & Mehrotra, Sanjay, 2024. "An algorithm for stochastic convex-concave fractional programs with applications to production efficiency and equitable resource allocation," European Journal of Operational Research, Elsevier, vol. 315(3), pages 980-990.

    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:oropre:v:59:y:2011:i:3:p:713-728. 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.