AI Learns Efficient Binary Codes to Speed up Complex Problem Solving

Scientists are increasingly focused on efficient methods for solving complex combinatorial optimisation problems, where evaluating potential solutions is computationally expensive. Tetsuro Abe, Masashi Yamashita, and Shu Tanaka, all from Keio University, alongside Shu Tanaka et al., present research detailing the effectiveness of binary autoencoders when used in conjunction with Quadratic Unconstrained Binary Optimisation (QUBO)-based approaches. This study addresses a critical limitation of Factorisation Machines with Quantum Annealing (FMQA), which relies on effective binary encoding of problem variables, and demonstrates that a binary autoencoder learns latent representations that better preserve solution space structure. By utilising a travelling salesman problem as a test case, the researchers reveal how these geometric properties within the latent space lead to improved optimisation performance and a higher approximation ratio, offering valuable insights into the design of representations for black-box optimisation techniques.

This work addresses a critical challenge in black-box optimisation, where evaluating potential solutions is computationally expensive and limits the search for high-quality results.

The research introduces a framework, bAE+FMQA, that learns a compact binary representation of problem solutions, enabling more efficient optimisation on Ising machines. By employing a binary autoencoder, the system bypasses the need for manually designed binary encodings, which often hinder search efficiency when dealing with non-binary structures like integer permutations.

The study demonstrates that this learned binary latent code accurately reconstructs feasible solutions, specifically within the context of a travelling salesman problem. Compared with manually designed encodings achieving similar compression levels, the binary autoencoder better aligns tour distances with Hamming distances in the latent space.

This alignment results in smoother neighborhoods when making small alterations to the binary code, and crucially, reduces the number of infeasible candidate solutions generated during optimisation. These geometric properties explain the improved performance of bAE+FMQA in achieving a better approximation ratio while consistently maintaining feasibility throughout the optimisation process.

Researchers validated the autoencoder’s ability to reconstruct feasible tours with high fidelity, establishing a foundation for analysing the latent space. Quantitative analysis revealed that the learned binary representation preserves the structure of the original solution space more effectively than traditional encodings.

This preservation is evident both globally and locally, meaning that the relationships between solutions are maintained in the compressed binary form. The findings provide practical guidance for designing latent representations for black-box optimisation, highlighting the importance of solution-space compression and structure-preserving geometry in creating smoother and more feasible search landscapes.

This work clarifies how the learned representation contributes to enhanced search efficiency, offering actionable insights beyond simply proposing a new optimisation pipeline. Through controlled experiments, the team evaluated reconstruction accuracy, structure preservation, and downstream optimisation behaviour, identifying key geometric properties of the binary latent space that are strongly linked to both feasibility and performance. The ultimate goal is to provide a deeper understanding of latent-representation-based black-box optimisation, paving the way for more effective algorithms in diverse fields.

Binary Autoencoder Training and Reconstruction Performance

A binary autoencoder (bAE) learns faithful binary reconstructions of feasible tours as a prerequisite for downstream optimisation. The research team trained the bAE on 5000 tours of an 8-city travelling salesman problem, covering almost the entire solution space of 5040 feasible tours. Reconstruction loss was measured using the mean squared error (MSE) between the input tour representation and its reconstruction, while reconstruction accuracy was defined as the fraction of samples perfectly reconstructed.

Training curves, detailed in Figure 2, demonstrate that reconstruction loss rapidly decreased and converged during early training stages, with a similar trend observed for validation loss, indicating minimal overfitting. Correspondingly, reconstruction accuracy increased during training and stabilised at a high value, confirming the bAE’s ability to encode global tour information within the binary latent space.

To determine a representative model configuration, the study examined the dependence of reconstruction accuracy on latent dimension dz and hidden-layer size dh. Figure 3(a) illustrates that reconstruction accuracy improved and stabilised as dz increased, although larger values also expanded the latent search space.

Based on a trade-off between fidelity and dimensionality, a latent dimension of dz = 14 was adopted, yielding approximately 70% average reconstruction accuracy. Further analysis, shown in Figure 3(b), revealed that validation accuracy peaked around dh = 64, after which increasing the hidden-layer size led to overfitting.

Consequently, the configuration (dz,dh) = (14,64) was selected for subsequent analyses of latent-space structure and FMQA optimisation. The work then evaluated the extent to which the learned binary latent space preserved the structure of the original TSP solution space, using this configuration as a standard.

Binary autoencoder learning of feasible tour structures for the travelling salesman problem

Scientists demonstrate that a binary autoencoder (bAE) learns a binary latent representation reflecting the structure of feasible solutions for the travelling salesman problem, and that optimisation performed in this latent space improves both feasibility and search efficiency. Reconstruction accuracy, measured as the fraction of samples whose reconstructed tour exactly matches the original tour, reached approximately 70% on average with a latent dimension of 14 and a hidden-layer size of 64.

The bAE was trained on 5000 tours from an 8-city TSP, covering almost the entire solution space of 5040 feasible tours. Mean squared error, used to quantify reconstruction loss between the input tour representation and its reconstruction, rapidly decreased during early training stages and then gradually converged, indicating stable learning.

Validation loss mirrored this decreasing trend, with no clear increase observed in later training stages, suggesting minimal overfitting under the tested conditions. Analysis of reconstruction accuracy dependence on latent dimension revealed that increasing the dimension from small values improved accuracy and stability, although larger dimensions also expanded the latent search space.

A representative model configuration of (dz, dh) = (14, 64) was adopted, balancing reconstruction fidelity with manageable dimensionality. Further investigation into the impact of hidden-layer size showed that validation accuracy peaked around a size of 64, beyond which overfitting occurred, reinforcing the choice of this configuration.

Evaluation of structure preservation within the latent space demonstrated that the bAE effectively captures the relationships between tours. The study compared the bAE’s performance against rank-based log/gray encoding, assessing how well tour distances in the original space align with Hamming distances in the latent space. These geometric properties within the latent space explain the improved approximation ratio achieved with bAE+FMQA, while maintaining feasibility throughout the optimisation process, and offer guidance for designing latent representations for broader black-box optimisation applications.

Autoencoder-derived binary latent spaces enhance travelling salesman problem optimisation

Researchers demonstrate that combining a binary autoencoder with factorization machines and Ising machine optimisation improves performance in black-box combinatorial optimisation problems. The study focuses on the travelling salesman problem as a test case, revealing that the autoencoder effectively compresses solutions into a binary latent space while preserving the structure of feasible tours.

This preservation is evidenced by a strong correlation between tour distances and latent Hamming distances, alongside smoother neighbourhoods resulting from small bit flips, and a reduction in the number of local optima encountered during the search process. This improved structure translates directly into faster optimisation and enhanced feasibility.

The autoencoder consistently yields a 100% feasible sample rate, meaning all proposed solutions satisfy problem constraints without needing post-processing, a significant improvement over manually designed encodings which often produce infeasible candidates. The findings highlight the importance of latent representation design in black-box optimisation, showing that structure preservation and solution-space compression are key to accelerating search and maintaining feasibility. The authors acknowledge that the current work is based on a relatively small travelling salesman problem, and future research could explore the scalability of this approach to larger and more complex combinatorial optimisation challenges.