×

A heuristic and an exact method for the gate matrix connection cost minimization problem. (English) Zbl 1281.90040

Summary: In many applications, a sequencing of patterns (electronic circuit nodes, cutting patterns, product orders, etc.) has to be found in order to optimize some given objective function, giving rise to the so-called open stack problems. We focus on a problem related to the optimization of gate matrix layouts: electronic circuits are obtained by connecting gates and one seeks a gate layout permutation that minimizes connection costs under restrictions on the circuit area. In the literature, the connection costs and circuit area are also known as time of open stacks and maximum number of open stacks, respectively. We propose a genetic algorithm providing heuristic solutions and a branch-and-cut algorithm based on a new linear integer programming formulation that represents, to the best of our knowledge, the first exact method proposed in the literature. The algorithms have been tested on real instances and on data sets from the literature. The computational results give evidence that the proposed methods provide solutions that improve the ones found by the approaches presented in the literature.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C90 Applications of mathematical programming

Software:

SCIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, SCIP: solving constraint integer programs, Mathematical Programming Computation 1 pp 1– (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1
[2] Baptiste, Proceedings of IJCAI’05-Constraint Modelling Challenge 2005 pp 9– (2005)
[3] Becceneri, A method for solving the minimization of the maximum number of open stacks problem within a cutting process, Computers and Operations Research 31 pp 2315– (2004) · Zbl 1067.90113 · doi:10.1016/S0305-0548(03)00189-8
[4] Birattari, Tuning Metaheuristics: A Machine Learning Perspective 197 (2009) · Zbl 1183.68464 · doi:10.1007/978-3-642-00483-4
[5] Booth, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer System Science 13 pp 335– (1976) · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1
[6] Chu, Minimizing the maximum number of open stacks by customer search, Lecture Notes in Computer Science 5732 pp 242– (2009) · Zbl 05612653 · doi:10.1007/978-3-642-04244-7_21
[7] De Giovanni, An adaptive genetic algorithm for large-size open stack problems, International Journal of Production Research 51 (3) pp 682– (2013) · doi:10.1080/00207543.2012.657256
[8] Dyson, The cutting stock problem in the flat glass industry, Operational Research Quarterly 25 pp 41– (1974) · doi:10.1057/jors.1974.5
[9] Faggioli, Heuristic and exact methods for the cutting sequencing problem, European Journal of Operational Research 110 (3) pp 564– (1998) · Zbl 0943.90061 · doi:10.1016/S0377-2217(97)00268-3
[10] Förster, Simulated annealing for order spread minimization problem in sequencing cutting patterns, European Journal of Operational Research 110 pp 271– (1998)
[11] Hu, GM_Plan: a gate matrix layout algorithm based on artificial intelligence planning techniques, IEEE Transactions on Computer-Aided Design 9 pp 836– (1990) · Zbl 05447262 · doi:10.1109/43.57791
[12] Lin, An effective heuristic algorithm for the traveling-salesman problem, Operations Research 21 (2) pp 498– (1973) · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[13] Linhares, Connections between cutting-pattern sequencing, VLSI design, and flexible machines, Computers & Operations Research 29 pp 1759– (2002) · Zbl 1259.90166 · doi:10.1016/S0305-0548(01)00054-5
[14] Lopes, World Congress on Engineering WCE 2010 III pp 1722– (2010)
[15] Madsen, An application of travelling-salesman routines to solve pattern-allocation problems in the glass industry, Journal of Operational Research Society 39 pp 249– (1988) · Zbl 0638.90047 · doi:10.1057/jors.1988.42
[16] Möhring, Graph problems related to gate matrix layout and PLA folding, Computing 7 pp 17– (1990) · Zbl 0699.68072
[17] Oliveira, A constructive genetic algorithm for gate matrix layout problems, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 21 (8) pp 969– (2002) · Zbl 05449182 · doi:10.1109/TCAD.2002.800454
[18] Oliveira, Pattern sequencing problems by clustering search, Lecture Notes in Computer Science 4140 pp 218– (2006) · Zbl 05352014 · doi:10.1007/11874850_26
[19] Oliver, Proceedings of the Second International Conference on Genetic Algorithms and Their Application pp 224– (1987)
[20] Oswald, Combinatorial Optimization-Eureka, You Shrink! Papers Dedicated to Jack Edmonds, 5th International Workshop, Aussois, 2001 2570 pp 147– (2003)
[21] Oswald, The Sharpest Cut, The Impact of Manfred Padberg and His Work pp 173– (2004) · doi:10.1137/1.9780898718805.ch11
[22] Respício, Metaheuristics: Progress as Real Problem Solvers pp 227– (2005) · doi:10.1007/0-387-25383-1_10
[23] 2009 Sheet cutting and process optimization for furniture industry-SCOOP Project http://www.scoop-project.net
[24] Smith, Proceedings of IJCAI’05-Constraint Modelling Challenge 2005 (2005)
[25] Tucker, A structure theorem for the consecutive 1’s property, Journal of Combinatorial Theory Series B 12 pp 153– (1972) · Zbl 0208.52402 · doi:10.1016/0095-8956(72)90019-6
[26] Yuen, Improved heuristics for sequencing cutting patterns, European Journal of Operational Research 87 (1) pp 57– (1995) · Zbl 0914.90230 · doi:10.1016/0377-2217(94)00068-N
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.