Solving constrained optimization problems by solution-based decomposition search

Solving constrained optimization problems (COPs) is a challenging task. In this paper we present a new strategy for solving COPs called solve and decompose (or S& D for short). The proposed strategy is a systematic iterative depth-first strategy that is based on problem decomposition. S& D uses a feasible solution of the COP, found by any exact method, to further decompose the original problem into a bounded number of subproblems which are considerably smaller in size. It also uses the value of the feasible solution as a bound that we add to the created subproblems in order to strengthen the cost-based filtering. Furthermore, the feasible solution is exploited in order to create subproblems that have more promise in finding better solutions which are explored in a depth-first manner. The whole process is repeated until we reach a specified depth where we do not decompose the subproblems anymore but we solve them to optimality using any exact method like Branch and Bound. Our initial results on two benchmark problems show that S& D may reach improvements of up to three orders of magnitude in terms of runtime when compared to Branch and Bound.