Abstract
Combinatorial Optimization Problems (COP) are generally complex and difficult to solve as a single monolithic problem. Thus, the process to solve the main initial COP may pass through solving intermediate problems and then combining the obtained partial solutions to find initial problem’s global solutions. Such intermediate problems are supposed to be easier to handle than the initial problem. To be modeled using the hierarchical optimization framework, the master problem should satisfy a set of desirable conditions. These conditions are related to some characteristics of problems which are: multi-objectives problem, over constrained problems, conditions on data and problems with partial nested decisions. For each condition, we present supporting examples from the literature where it was applied. This paper aims to propose a new approach dealing with hard COPs particularly when the decomposition process leads to some well-known and canonical optimization sub-problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Bartk, R.: Constraint hierarchy networks. In: Proceedings of the 3rd ERCIM/Compulog Workshop on Constraints, Lecture Notes in Computer Science. Springer (1998)
Begur, S., Miller, D., Weaver, J.: An integrated spatial DSS for scheduling and routing home-health-care nurses. Interfaces 27(4), 35–48 (1997)
Clark, A., Walker, H.: Nurse rescheduling with shift preferences and minimal disruption. Journal of Applied Operational Research 3(3), 148–162 (2011)
Halford, G., Wilson, W., Phillips, S.: Processing capacity defined by relational complexity: Implications for comparative, developmental, and cognitive psychology. Behavioral & Brain Sciences 21(6), 803–864 (1998)
Hertz, A., Lahrichi, N.: A patient assignment algorithm for home care services. Journal of the Operational Research Society 60, 481–495 (2009)
Jemai, J., Chaieb, M., Mellouli, K.: The home care scheduling problem: a modeling and solving issue. In: Proceedings of the 5th International Conference on Modeling, Simulation and Applied Optimization (2013)
Mullinax, C., Lawley, M.: Assigning patients to nurses in neonatal intensive care. Journal of the Operational Research Society 53, 25–35 (2002)
Mutingi, M., Mbohwa, C.: A satisficing approach to home healthcare worker scheduling. In: International Conference on Law, Entrepreneurship and Industrial Engineering (2013)
Phillips, S.: Measuring relational complexity in oddity discrimination tasks. Noetica 3(1), 1–14 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Chaieb, M., Jemai, J., Mellouli, K. (2015). Decomposability Conditions of Combinatorial Optimization Problems. In: Ali, M., Kwon, Y., Lee, CH., Kim, J., Kim, Y. (eds) Current Approaches in Applied Artificial Intelligence. IEA/AIE 2015. Lecture Notes in Computer Science(), vol 9101. Springer, Cham. https://doi.org/10.1007/978-3-319-19066-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-19066-2_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19065-5
Online ISBN: 978-3-319-19066-2
eBook Packages: Computer ScienceComputer Science (R0)