Learning-based methods have gained significant popularity in the field of combinatorial optimization in recent times. Researchers in the deep learning community aim to design models that, given an instance of a problem, directly generate optimal solutions in the first shot. However, due to the inherent complexity of certain combinatorial problems, achieving this in a single attempt is not trivial, and additional strategies are required to search for the optimal solution in several tries. For this purpose, researchers have proposed sampling techniques or active search which, in our opinion, are computationally wasteful with a limited performance. In this paper we develop strategies that efficiently exploit the fast inference capability of learning methods. Particularly, the objective is to solve the entire problem by solving it in fragments. It can be applied to any problem where the improvement of the overall solution is guaranteed by improving any part of the problem. To illustrate this, we focus on the Linear Ordering Problem (LOP) as a case of study. We employ a Neural Combinatorial Optimization model within a sliding-window optimization strategy, where specific parts of a candidate solution are optimized without compromising the overall solution quality. We explore various implementation aspects, including window size, step size and overlapping configurations. Experimental results show that the presented method achieves superior performance and better efficiency compared to baseline strategies and competitors, and significantly surpasses the previous learning methods for LOP instances of size 200, achieving an average gap to the best known value of only 0.04% within a 1-minute run-time.

The effective management and control of building energy systems are crucial for reducing the energy consumption peak loads, CO2 emissions, and ensuring the stability of the power grid, while maintaining optimal comfort levels within buildings. The difficulty to accommodate this trade-off is amplified by dynamic environmental conditions and the need for scalable solutions that can adapt across various building types and geographic locations. Acknowledging the importance of this problem, NeurIPS conference hosted since 2020 the CityLearn control challenge to foster the design of innovative solutions in building energy management. Participants were tasked with developing strategies that not only enhance energy efficiency but also prioritize sustainability and occupant comfort. This paper introduces the Community-based Hierarchical Energy Systems Coordination Algorithm (CHESCA), the winning approach of the 2023 edition. We rely on a hierarchical approach adaptable to an arbitrary number of buildings, first optimizing building-level metrics individually, and later refining these through a central community-level controller to improve grid-related metrics. Compared to the other high-ranked competitors, our approach demonstrated fast inference capabilities like learning-based methods, while offering a better interpretability and a superior generalization capabilities with minimal data requirements. This paper details our approach, supported by comprehensive experimental results and ablation studies.

Neural Combinatorial Optimization has emerged as a new paradigm in the optimization area. It attempts to solve optimization problems by means of neural networks and reinforcement learning. In the past few years, due to their novelty and presumably good performance, many research papers have been published introducing new neural architectures for a variety of combinatorial problems. However, the incorporation of such models in the conventional optimization portfolio raises many questions related to their performance compared to other existing methods, such as exact algorithms, heuristics, or metaheuristics. This article aims to present a critical view of these new proposals, discussing their benefits and drawbacks with respect to the tools and algorithms already present in the optimization field. For this purpose, a comprehensive study is carried out to analyze the fundamental aspects of such methods, including performance, computational cost, transferability, and reusability of the trained model. Moreover, this discussion is accompanied by the design and validation of a new neural combinatorial optimization algorithm on two well-known combinatorial problems: the Linear Ordering Problem and the Permutation Flowshop Scheduling Problem. Finally, new directions for future work in the area of Neural Combinatorial Optimization algorithms are suggested.

Recent advances in graph neural network (GNN) architectures and increased computation power have revolutionized the field of combinatorial optimization (CO). Among the proposed models for CO problems, neural improvement (NI) models have been particularly successful. However, the existing NI approaches are limited in their applicability to problems where crucial information is encoded in the edges, as they only consider node features and nodewise positional encodings (PEs). To overcome this limitation, we introduce a novel NI model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each iteration. Conducted experiments demonstrate that the proposed model can recommend neighborhood operations that outperform conventional versions for the preference ranking problem (PRP) with a performance in the 99th percentile. We also extend the proposal to two well-known problems: the traveling salesman problem and the graph partitioning problem (GPP), recommending operations in the 98th and 97th percentile, respectively.

Cardiac SPECT perfusion imaging is important for diagnosis and evaluation of coronary artery diseases. However, the acquired image data can suffer from motion blur due to patient respiratory motion. We propose a maximum-likelihood estimation (MLE) approach to determine a surrogate respiratory signal from short-time acquisition frames for motion correction. To compensate for the low data counts in the short-time frames, we employ a regularization term to exploit the similarity in acquired data among neighboring acquisition angles. In the experiments we validated this approach first on a set of simulated phantom data with known respiratory motion, and then on clinical acquisitions from 17 subjects. The results demonstrate that the proposed MLE approach could yield a reliable respiratory motion signal even with the acquisition frame duration being as short as 100ms, and outperformed both center-of-mass and Laplacian eigen-maps methods.