Go to JKU Homepage
Institute of Production and Logistics Management
What's that?

Institutes, schools, other departments, and programs create their own web content and menus.

To help you better navigate the site, see here where you are at the moment.

Detail

Paper accepted for publication@VHB A journal

The paper "Exact and heuristic algorithms for the maximum weighted submatrix coverage problem" von Markus Sinnl (Institute of Production and Logistics Management) has been accepted for publication at European Journal of Operational Research

EJOR

Abstract:

The maximum weighted submatrix coverage problem is a recently introduced problem with applications indata mining.  It is concerned with selecting K submatrices of a given numerical matrix such that the sum of the matrix-entries, which occur in at least one of the selected submatrices, is maximized.  In the paper introducing the problem, a problem-specific constraint programming approach was developed and embeddedin a large neighborhood-search to obtain a heuristic.  A compact integer linear programming formulationwas also presented, but deemed inefficient due to its size.

In this paper, we introduce new integer linear programming formulations for the problem, one of them is  based on Benders decomposition. The obtained Benders decomposition-based formulation has  a nice combinatorial structure, i.e., there is no need to solve linear programs to separate Benders cuts.  We present preprocessing procedures and valid inequalities for all formulations.  We also develop a greedy randomized adaptive search procedure for the problem, which is enhanced with a local search.

A computational study using the instances from literature is done to evaluate the effectiveness of our new approaches.  Our algorithms manage to find improved primal solutions for ten out of 17 real-world instances, and optimality is proven for two real-world instances.  Moreover, for over 700 of 1617 large-scale synthetic instances, our algorithms find improved primal solutions compared to the heuristics from the literature.