Randomized greedy multi-start algorithm for the minimum common integer partition problem. (April 2016)

• Record Type: Journal Article
• Authors: Lozano, Manuel; Rodriguez, Francisco J.; Peralta, Daniel; García-Martínez, Carlos
• Is Part Of: Engineering applications of artificial intelligence. Volume 50(2016:Feb.)
• Page Start: 226
• Page End: 235
• Publication Date: 2016-04
• Subjects: Minimum common integer partition problem -- Randomized greedy algorithm -- Multi-start methods; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2016.01.037
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: In this paper, we propose a randomized greedy multi-start algorithm for the minimum common integer partition problem. Given k multisets S 1, …, S k of positive integers ( S i = { s i 1, …, s ij, …, s im i } ), the goal is to find the common integer partition T with minimal cardinality, i.e., a unique and reduced multiset T that, for each S i, it can be partitioned into m i multisets T j so that the elements in T j sum to s ij . This mathematical problem is reported to appear in computational molecular biology, when assigning orthologs on a genome scale or assembling DNA fingerprints in particular. Our proposed metaheuristic approach constitutes the construction of multiple solutions by a new greedy method that embeds a diversification agent to allow diverse and promising solutions to be reached. Furthermore, we formulate an integer programming model for this problem and show that the CPLEX solver can only solve small instances of the problem. However, computational results for problem instances involving up to 1000 multisets (each one with up to 1000 elements) show that our innovative metaheuristic produces very good feasible solutions in reasonable computing times, arising as a very attractive alternative to the existing approaches.