Efficient heuristics for the consecutive zeros problem in sparse Jacobian matrix determination

Abstract

We study the Consecutive Zeros Problem (CZP), which is an extension of the well-known maximum consecutive ones problem. CZP is interesting both from a combinatorial and a practical standpoint. Leveraging a priori known sparsity pattern of matrix A, we employ a state-of-the-art coloring/column partitioning algorithm to generate a seed matrix S, to obtain the compressed matrix B = A × S, using automatic differentiation (AD) or finite differences (FD) while significantly reducing the problem’s dimensionality. With the AD forward mode, the nonzero entries of A are mapped to the compressed matrix accurately up to the machine precision using Cn “forward passes”. This research aims to reduce the computation cost ( measured by the number of AD passes required to compress the matrix) further by solving the CZP (grouping the zeros in each row of B). The problem is cast as a variant of the Traveling Salesperson Problem (TSP). To solve the problem, we have designed and implemented heuristic algorithms, including Ant Colony Optimization (ACO) meta-heuristic and two variants of ACO (Zp-Hybrid and Zp-Estimator), and several greedy heuristics (Exhaustive Approach, Selective Exhaustive, and Single Attempt). The computational results from a subset of benchmark test matrices clearly demonstrate the effectiveness of the proposed approaches.