Abstract
In this paper, we propose a challenging research direction for Constraint Programming and optimization techniques in general. We address problems where decisions to be taken affect and are affected by complex systems, which exhibit phenomena emerging from a collection of interacting objects, capable to self organize and to adapt their behaviour according to their history and feedback. Such systems are unfortunately impervious to modeling efforts via state-of-the-art combinatorial optimization techniques. We provide some hints on approaches to connect and integrate decision making and optimization technology with complex systems via machine learning, game theory and mechanism design. In the first case, the aim is to extract modeling components to express the relation between global decisions and observables emerging from the real system, or from an accurate predictive model (e.g. a simulator). In the second case, the idea is to exploit game theory, mechanism design and distributed decision making to drive the process toward realistic equilibrium points avoiding globally optimal, but unrealistic, configurations. We conclude by observing how dealing with the complexity of the considered problems will require to greatly extend the capabilities of state of the art solvers: in this context, we identify some key issues and highlight future research directions.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Lallouet, A., Lopez, M., Martin, L., Vrain, C. (2010). On learning constraint problems. In Proceedings of ICTAI.
Anderson, P.W. (1995). Physics: the opening to complexity? In Proceedings of the national academic science.
Bartolini, A., Lombardi, M., Milano, M., Benini, L. (2011). Neural constraint for solving real world problems. In Proceedings of CP 2011.
Bartolini, A., Lombardi, M., Milano, M., Benini, L. (2012). Optimization and controlled systems: a case study on thermal aware workload dispatching. In Proceedings of AIII 2012.
Beldiceanu, N., & Simonis, H. (2011). A constraint seeker: finding and ranking global constraints from examples. In Proc. of CP 2011.
Benders, J.F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238–252.
Bertsekas, D.P., & Tsitsiklis, J. (1996). Neuro-dynamic programming. Belmont: Athena Scientific.
Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys, 35(3).
Camacho, E., & Alba, C. (2013). Model predictive control. Berlin: Springer.
Deng, G. (2007). Simulation-based optimization. PhD thesis, University of Wisconsin – Madison.
EURECOM. Survey on mobility models for vehicular ad hoc networks: a survey and taxonomy. http://www.eurecom.fr/util/publidownload.fr.htm?id=1951.
Fischetti, M., & Lodi, A. (2003). Local branching. Mathematical Programming, 98, 23–47.
Focacci, F., Laburthe, F., Lodi, A. (2003). Local search and constraint programming: Ls and cp illustrated on a transportation problem. In Constraint and integer programming. Kluwer.
Fu, M.C. (1994). Optimization via simulation: a review. Annals of Operations Research, 53, 199–247.
Glover, F., Kelly, J.P., Laguna, M. (1999). New advances for wedding optimization and simulation. In Proceedings of the winter simulation conference.
Grüne, L., & Pannek, J. (2013). Nonlinear model predictive control: theory and algorithms. Berlin: Springer.
Loughlin, D.H., Ranjithan Jr., S.R., Baugh, J.W., Brill Jr., E.D. (2000). Application of gas for the design of ozone control strategies. Journal of the Air and Waste Management Association, 50, 1050–1063.
Helbing, D. (2001). Traffic and related self-driven many-particle systems. Reviews of Modern Physics, 73, 1067.
Holland, A., & O’Sullivan, B. (2012). Survey of game theoretic tools in dynamic environments for policy management. Technical report, 4C. ePolicy Project Deliverable 5.1.
Hooker, J.N. (2003). Logic-based benders decomposition. Mathematical Programming, 96, 33–60.
Junker, U., Karisch, S.E., Kohl, N., Vaaben, B., Fahle, T., Sellmann, M. (1999). A framework for constraint programming based column generation. In Proceedings of CP1999.
Kaneco, K. (2006). Life: an introduction to complex systems biology. Berlin: Springer.
Law, A.M., & Kelton, W.D. (2000). Simulation modeling and analysis. New York: Mc Graw Hill.
Levy, M., Levy, H., Solomon, S. (2000). Microscopic simulation of financial markets; from investor behaviour to market phenomena. New York: Academic.
Lubin, B., Kephart, J.O., Das, R., Parkes, D.C. (2009). Expressive power-based resource allocation for data centers. In Proceedings of IJCAI 2009.
Marriott, K., & Stuckey, P. (1998). Programming with constraints: an introduction. New York: MIT Press.
Milano, M. (2003). Constraint and integer programming: toward a unified methodology. Norwell: Kluwer.
Milano, M., & Van Hentenryck, P. (2010). Hybrid optimization: the ten years of CPAIOR. Berlin: Springer.
Nemhauser, G., & Wolsey, L. (1988). Integer and combinatorial optimization. Wiley Interscience Series in Discrete Mathematics and Optimization.
Sasaki, S., Obayashi, D., Takeguchi, Y., Hiroses, N. (2000). Multiobjective evolutionary computation for supersonic wing-shape optimization. IEEE Transactions on Evolutionary Computation, 4, 182–187.
Ohrimenko, O., Stuckey, P.J., Codish, M. (2009). Propagation via lazy clause generation. Constraints, 14(3), 357–391.
Haupt, R.L., & Haupt, S.E. (2004). Practical genetic algorithms. New York: Wiley.
Ruggiero, M., Guerri, A., Bertozzi, D., Milano, M., Benini, L. (2010). A fast and accurate technique for mapping parallel applications on stream-oriented mpsoc platforms with communication awareness. International Journal of Parallel Programming, 36(1), 3–36.
Smith, D.M.D., & Johnson, N.F. (2006). Predictability, risk and online management in a complex system of adaptive agents. arXiv:0605065.
Bar Yam, Y. (1997). Dynamic of complex systems. Reading: Addison Wesley.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Milano, M., Lombardi, M. Strategic decision making on complex systems. Constraints 19, 174–185 (2014). https://doi.org/10.1007/s10601-014-9161-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-014-9161-y