We consider the problem of partitioning a matrix of m rows and n columns of non-negative integers into M smaller submatrices. With each submatrix is associated a cost equal to the sum of its elements. The objective is to minimize the cost of the submatrix of maximum cost. We present a (O-l)-integer programming formulation of the problem and three different lower bounds. A heuristic procedure for finding a valid upper bound to the optimal solution cost is also described. Problem reduction tests derived from both the original problem and the lower bounds are given. Lower bounds and reduction tests are used in a tree search algorithm in order to find the optimal solution to the problem. Computational results on a number of randomly generated test problems are presented. © 2002 Elsevier Science B.V. AU rights reserved.

Partitioning a matrix with non-guillotine cuts to minimize the maximum cost / Mingozzi A.; Morigi S.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 116:3-2(2002), pp. 243-260. [10.1016/s0166-218x(00)00286-9]

Partitioning a matrix with non-guillotine cuts to minimize the maximum cost

Morigi S.
2002

Abstract

We consider the problem of partitioning a matrix of m rows and n columns of non-negative integers into M smaller submatrices. With each submatrix is associated a cost equal to the sum of its elements. The objective is to minimize the cost of the submatrix of maximum cost. We present a (O-l)-integer programming formulation of the problem and three different lower bounds. A heuristic procedure for finding a valid upper bound to the optimal solution cost is also described. Problem reduction tests derived from both the original problem and the lower bounds are given. Lower bounds and reduction tests are used in a tree search algorithm in order to find the optimal solution to the problem. Computational results on a number of randomly generated test problems are presented. © 2002 Elsevier Science B.V. AU rights reserved.
2002
Partitioning a matrix with non-guillotine cuts to minimize the maximum cost / Mingozzi A.; Morigi S.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 116:3-2(2002), pp. 243-260. [10.1016/s0166-218x(00)00286-9]
Mingozzi A.; Morigi S.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/879665
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact