This paper is concerned with a certain matrix decomposition problem which has been shown to be NP-hard (MATRIX EQUIPARTITION). Given a (0, 1)-matrix M with row-set R. MATRIX EQUIPARTITION consists in finding two equicardinality subsets R1 and R2 of R with maximum size, such that every row of R1 is disjoint from every row of R2. In addition to its theoretical significance, the problem arises also in applicative contexts like, for example, the design of Very Large Scale Integrated circuits (VLSI-design) and Flexible Manufacturing Systems (FMS). We prove that MATRIX EQUIPARTITION admits a Set Covering formulation. Although such formulation contains exponentially many constraints, it is easy to check implicitly whether a (0, 1)-vector satisfies all of them and, if not, to generate a set of violated constraints from the formulation. Such property is used to design an incremental algorithm to solve the problem to optimality. We tested the algorithm on several test problems and compared it to a standard Branch & Bound strategy.
A Set Covering Formulation of the Matrix Equipartition Problem
NOBILI, Paolo
1992-01-01
Abstract
This paper is concerned with a certain matrix decomposition problem which has been shown to be NP-hard (MATRIX EQUIPARTITION). Given a (0, 1)-matrix M with row-set R. MATRIX EQUIPARTITION consists in finding two equicardinality subsets R1 and R2 of R with maximum size, such that every row of R1 is disjoint from every row of R2. In addition to its theoretical significance, the problem arises also in applicative contexts like, for example, the design of Very Large Scale Integrated circuits (VLSI-design) and Flexible Manufacturing Systems (FMS). We prove that MATRIX EQUIPARTITION admits a Set Covering formulation. Although such formulation contains exponentially many constraints, it is easy to check implicitly whether a (0, 1)-vector satisfies all of them and, if not, to generate a set of violated constraints from the formulation. Such property is used to design an incremental algorithm to solve the problem to optimality. We tested the algorithm on several test problems and compared it to a standard Branch & Bound strategy.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
