Solving constrained optimization problems by solution-based decomposition search

Amine Lamine, Mahdi Khemakhem (), Brahim Hnich and Habib Chabchoub
Additional contact information
Amine Lamine: University of Gabès
Mahdi Khemakhem: University of Sfax
Brahim Hnich: Taif University
Habib Chabchoub: University of Sfax

Journal of Combinatorial Optimization, 2016, vol. 32, issue 3, No 2, 672-695

Abstract: Abstract 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$$ S & D for short). The proposed strategy is a systematic iterative depth-first strategy that is based on problem decomposition. $$ S \& D$$ 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$$ S & D may reach improvements of up to three orders of magnitude in terms of runtime when compared to Branch and Bound.

Keywords: Exact algorithm; Decomposition search; Constrained optimization problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9892-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:3:d:10.1007_s10878-015-9892-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9892-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().