PDF

Description

This paper presents the use of contrastive learning to improve upon the performance of Optimization Modulo Theories (OMT) solvers. OMT is a generalization of Satisfiability Modulo Theories (SMT) that requires an objective function and has numerous real-world applications, such as chip placement, worst-case execution analysis, and the Traveling Salesman Problem. OMT problems are challenging due to the requirement of finding both feasible and optimal solutions, as well as the non-convexity of constraints, making it difficult to identify the global optimal solution. The current approaches taken by OMT solvers are not problem-specific and involve reducing the problem into Integer Linear Programs (ILPs), or repeatedly making calls to SMT solvers. The presented contrastive learning approach leverages symmetries and invariances within OMT problems through optimality and feasibility-preserving transformations to better guide the search for optimal solutions. This paper builds upon Ashera, a learning-based OMT solver, and implements contrastive learning to improve downstream optimal variable assignment accuracies by over 6% on a Scheduling problem benchmark and over 5% on a Multi-Agent Traveling Salesman problem benchmark.

Details

Files

Statistics

from
to
Export
Download Full History