Shahadat Hossain

This paper addresses the Capacitated Coverage Path Planning Problem (CPP) arising in agricultural field operations. It aims to determine an efficient sequence of field tracks to be serviced by an agricultural machine subject to limited onboard capacity and refilling constraints, while minimizing non-working distance. The non-working distance is the length traveled by the machinery not performing productive fieldwork. Optimizing how agricultural machinery maneuvers can help reduce operational costs and greenhouse gas (GHG) emissions, while increasing productivity. The problem is formulated as a variant of the constrained Vehicle Routing Problem (VRP), which is NP-hard. A novel exact Integer Linear Programming (ILP) formulation is proposed. We employ a commercial optimizer, Gurobi, to obtain optimal reference solutions for smaller instances. To overcome scalability limitations, a metaheuristic based on "simulated annealing (SA) methodology" is proposed. Our algorithm incorporates customized neighborhood search operators and a capacity-aware route-splitting mechanism to explicitly handle refilling operations. Computational experiments are conducted on real-world field instances. The proposed metaheuristic is evaluated against the exact formulation. The results indicate that SA consistently produces near-optimal solutions with substantially reduced computation times.

We give an integer linear program formulation for the star bicolouring of bipartite graphs. We develop a column generation method to solve the linear programming relaxation to obtain a lower bound for the minimum number of colours needed. We determine the star bicolouring using the iterative rounding method. We give computational results on arrowhead matrices, sparse random matrices, complete bipartite graphs, and matrices from the Harwell–Boeing collection. The findings demonstrate that the proposed method effectively establishes lower and upper bounds for the minimum number of colours needed for a star bicolouring of bipartite graphs, particularly for sparse bipartite graphs.

Matrix–matrix multiplication is of singular importance in linear algebra operations with a multitude of applications in scientific and engineering computing. Data structures for storing matrix elements are designed to minimize overhead information as well as to optimize the operation count. In this study, we utilize the notion of the compact diagonal storage method (CDM), which builds upon the previously developed diagonal storage—an orientation-independent uniform scheme to store the nonzero elements of a range of matrices. This study exploits both these storage schemes and presents efficient GPU-accelerated parallel implementations of matrix multiplication when the input matrices are banded and/or structured sparse. We exploit the data layouts in the diagonal storage schemes to expose a substantial amount of fine-grained parallelism and effectively utilize the GPU shared memory to improve the locality of data access for numerical calculations. Results from an extensive set of numerical experiments with the aforementioned types of matrices demonstrate orders-of-magnitude speedups compared with the sequential performance.

Matrix-matrix multiplication is a fundamental computation in a wide range of scientific problems. In this paper, we investigate algorithmic aspects of this important operation whereby the underlying arithmetic calculations are ordered in a way that is different from the standard triple-loop framework. We introduce the notion of “compact diagonal storage” which builds upon the previously developed diagonal storage, an orientation-independent uniform scheme to store nonzero elements of dense as well as structured matrices such as symmetric, triangular, regular, and arbitrarily distributed banded matrices. The results from an extensive set of numerical experiments with structured sparse matrices demonstrate significant performance gain of both serial and shared-memory parallel calculations of our matrix-matrix and matrix-transposed matrix multiplication when compared with an optimized matrix-matrix multiplication code.

We give an improved non-monotone line search algorithm for stochastic gradient descent (SGD) for functions that satisfy interpolation conditions. We establish theoretical convergence guarantees for the algorithm for strongly convex, convex and non-convex functions. We conduct a detailed empirical evaluation to validate the theoretical results.