A Hierarchical Decomposition Framework for Modeling Combinatorial Optimization Problems

Complex Optimization Problems has existed in many fields of science, including economics, healthcare, logistics and finance where a complex problem has to be solved. Thus, modeling a complex problem is a fundamental step to relax its complexity and achieve to a final solution of the master problem. Hierarchical optimization is a main step in optimization problems handling process. It consists of decomposing an optimization problem into two or more sub-problems; each sub-problem has its own objectives and constraints. It will help to prove the correct understanding and represent the problem in a different form that facilitates its solving. In this work, we stipulate that a hierarchical decomposition of complex problems can yield to more effective solutions. The proposed framework will contain four possible strategies which will be detailed through this paper; objective based decomposition; constraints based decomposition, semantic decomposition and data partitioning strategy. Each strategy will be argued by a set of examples from the literature to validate our framework. However, some conditions shall be verified to model the problem using such conditions are problems’ characteristics that will help to identify if a combinatorial optimization problem can be modeled within the proposed framework and they are detailed in the following subsections.