IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v169y2016i2d10.1007_s10957-016-0881-6.html
   My bibliography  Save this article

Decomposition and Mean-Field Approach to Mixed Integer Optimal Compensation Problems

Author

Listed:
  • Dario Bauso

    (The University of Sheffield
    Università di Palermo)

  • Quanyan Zhu

    (Polytechnic School of Engineering New York University)

  • Tamer Başar

    (University of Illinois at Urbana-Champaign)

Abstract

Mixed integer optimal compensation deals with optimization problems with integer- and real-valued control variables to compensate disturbances in dynamic systems. The mixed integer nature of controls could lead to intractability in problems of large dimensions. To address this challenge, we introduce a decomposition method which turns the original n-dimensional optimization problem into n independent scalar problems of lot sizing form. Each of these problems can be viewed as a two-player zero-sum game, which introduces some element of conservatism. Each scalar problem is then reformulated as a shortest path one and solved through linear programming over a receding horizon, a step that mirrors a standard procedure in mixed integer programming. We apply the decomposition method to a mean-field coupled multi-agent system problem, where each agent seeks to compensate a combination of an exogenous signal and the local state average. We discuss a large population mean-field type of approximation and extend our study to opinion dynamics in social networks as a special case of interest.

Suggested Citation

  • Dario Bauso & Quanyan Zhu & Tamer Başar, 2016. "Decomposition and Mean-Field Approach to Mixed Integer Optimal Compensation Problems," Journal of Optimization Theory and Applications, Springer, vol. 169(2), pages 606-630, May.
    • Handle: RePEc:spr:joptap:v:169:y:2016:i:2:d:10.1007_s10957-016-0881-6
    DOI: 10.1007/s10957-016-0881-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-016-0881-6
    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/s10957-016-0881-6?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. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(4), pages 691-705, August.
    2. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(5), pages 879-883, October.
    3. Hamidou Tembine & Quanyan Zhu & Tamer Basar, 2011. "Risk-sensitive mean field stochastic differential games," Post-Print hal-00643547, HAL.
    4. POCHET, Yves & WOLSEY, Laurence A., 1993. "Lot-sizing with constant batches: formulation and valid inequalities," LIDAM Reprints CORE 1066, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(6), pages 1195-1198, December.
    6. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(1), pages 225-228, February.
    7. Sebastian Sager & Mathieu Claeys & Frédéric Messine, 2015. "Efficient upper and lower bounds for global mixed-integer optimal control," Journal of Global Optimization, Springer, vol. 61(4), pages 721-743, April.
    8. Andrew J. Clark & Herbert Scarf, 2004. "Optimal Policies for a Multi-Echelon Inventory Problem," Management Science, INFORMS, vol. 50(12_supple), pages 1782-1790, December.
    9. ,, 2003. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 19(2), pages 411-413, April.
    10. Yves Pochet & Laurence A. Wolsey, 1993. "Lot-Sizing with Constant Batches: Formulation and Valid Inequalities," Mathematics of Operations Research, INFORMS, vol. 18(4), pages 767-785, November.
    11. Daron Acemoğlu & Giacomo Como & Fabio Fagnani & Asuman Ozdaglar, 2013. "Opinion Fluctuations and Disagreement in Social Networks," Mathematics of Operations Research, INFORMS, vol. 38(1), pages 1-27, February.
    12. repec:dau:papers:123456789/3001 is not listed on IDEAS
    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. Stefanny Ramirez & Dario Bauso, 2021. "Dynamic Coordination Games with Activation Costs," Dynamic Games and Applications, Springer, vol. 11(3), pages 580-596, September.
    2. Stefanny Ramirez & Dario Bauso, 2023. "Dynamic Games with Strategic Complements and Large Number of Players," Journal of Optimization Theory and Applications, Springer, vol. 197(1), pages 1-21, April.

    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. Dario Bauso & Raffaele Pesenti & Marco Tolotti, 2016. "Opinion Dynamics and Stubbornness Via Multi-Population Mean-Field Games," Journal of Optimization Theory and Applications, Springer, vol. 170(1), pages 266-293, July.
    2. A. Bensoussan & K. Sung & S. Yam, 2013. "Linear–Quadratic Time-Inconsistent Mean Field Games," Dynamic Games and Applications, Springer, vol. 3(4), pages 537-552, December.
    3. Minyi Huang, 2013. "A Mean Field Capital Accumulation Game with HARA Utility," Dynamic Games and Applications, Springer, vol. 3(4), pages 446-472, December.
    4. Fabio Bagagiolo & Dario Bauso, 2014. "Mean-Field Games and Dynamic Demand Management in Power Grids," Dynamic Games and Applications, Springer, vol. 4(2), pages 155-176, June.
    5. A. Bensoussan & K. C. J. Sung & S. C. P. Yam & S. P. Yung, 2016. "Linear-Quadratic Mean Field Games," Journal of Optimization Theory and Applications, Springer, vol. 169(2), pages 496-529, May.
    6. Boualem Djehiche & Minyi Huang, 2016. "A Characterization of Sub-game Perfect Equilibria for SDEs of Mean-Field Type," Dynamic Games and Applications, Springer, vol. 6(1), pages 55-81, March.
    7. Fabio Bagagiolo & Dario Bauso & Raffaele Pesenti, 2016. "Mean-Field Game Modeling the Bandwagon Effect with Activation Costs," Dynamic Games and Applications, Springer, vol. 6(4), pages 456-476, December.
    8. Dario Bauso & Hamidou Tembine & Tamer Başar, 2016. "Robust Mean Field Games," Dynamic Games and Applications, Springer, vol. 6(3), pages 277-303, September.
    9. Jun Moon & Tamer Başar, 2019. "Risk-Sensitive Mean Field Games via the Stochastic Maximum Principle," Dynamic Games and Applications, Springer, vol. 9(4), pages 1100-1125, December.
    10. Yakut, Oguz, 2021. "Implementation of hydraulically driven barrel shooting control by utilizing artificial neural networks," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 190(C), pages 1206-1223.
    11. X. Qin & G. Huang, 2009. "An Inexact Chance-constrained Quadratic Programming Model for Stream Water Quality Management," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 23(4), pages 661-695, March.
    12. Md. Yousuf Gazi & Khandakar Tahmida Tafhim, 2019. "Investigation of Heavy-mineral Deposits Using Multispectral Satellite Imagery in the Eastern Coastal Margin of Bangladesh," Earth Sciences Malaysia (ESMY), Zibeline International Publishing, vol. 3(2), pages 16-22, October.
    13. Minghe Sun, 2005. "Warm-Start Routines for Solving Augmented Weighted Tchebycheff Network Programs in Multiple-Objective Network Programming," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 422-437, November.
    14. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    15. Tansel, Aysit & Karao?lan, Deniz, 2016. "The Causal Effect of Education on Health Behaviors: Evidence from Turkey," IZA Discussion Papers 10020, Institute of Labor Economics (IZA).
    16. Timothy K.M. Beatty & Erling Røed Larsen & Dag Einar Sommervoll, 2005. "Measuring the Price of Housing Consumption for Owners in the CPI," Discussion Papers 427, Statistics Norway, Research Department.
    17. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    18. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    19. repec:dau:papers:123456789/5389 is not listed on IDEAS
    20. Wong, Patricia J.Y., 2015. "Eigenvalues of a general class of boundary value problem with derivative-dependent nonlinearity," Applied Mathematics and Computation, Elsevier, vol. 259(C), pages 908-930.
    21. Kojima, Fuhito, 2013. "Efficient resource allocation under multi-unit demand," Games and Economic Behavior, Elsevier, vol. 82(C), pages 1-14.

    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:joptap:v:169:y:2016:i:2:d:10.1007_s10957-016-0881-6. 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.