Decomposability Conditions of Combinatorial Optimization Problems

Autor:	Khaled Mellouli, Marouene Chaieb, Jaber Jemai
Rok vydání:	2015
Předmět:	Set (abstract data type) Mathematical optimization Optimization problem L-reduction Process (engineering) Quadratic assignment problem Computer science Combinatorial optimization problem Covering problems Combinatorial optimization
Zdroj:	Current Approaches in Applied Artificial Intelligence ISBN: 9783319190655 IEA/AIE
DOI:	10.1007/978-3-319-19066-2_24
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::aba8632a381b587ef639e498377a0911 https://doi.org/10.1007/978-3-319-19066-2_24 Zobrazit plný text záznamu