Chirag Sharma

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2023-143

May 12, 2023

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-143.pdf

Optimization Modulo Theories (OMT) is a highly expressive class of combinatorial optimization problems that can be used to formulate many computationally hard real-world problems in areas such as scheduling, transportation, resource allocation, and supply chain management. Solving OMT problems in practice requires careful manual design of general heuristics but for specialized applications, this can be replaced with an automated machine learning framework that learns to predict OMT problem solutions from task-specific datasets. We encode OMT problems as graphs and train Graph Convolution Networks on the task of directly predicting optimal assignments to integer variables via a classification objective. We introduce a logical space perturbation technique for sampling slightly modified versions of a given OMT problem and show that the embeddings of OMT problems that are learned via our training approach capture sufficient latent structural information about the problems to be robust to these perturbations. We demonstrate this claim by generating training data curriculums for the problem classes of DAG Multiresource Task Scheduling and the Multi-Agent Traveling Saleseman Problem and running experiments to compare the variable prediction accuracy of the direct training approach, training on an augmented dataset that includes a large number of perturbation examples, and finetuning a pretrained model that has learned to identify structural differences between a problem and perturbations of it. In all experiments, the direct training approach performs just as well as the data augmentation and pretraining approaches.

Advisors: Joseph Gonzalez

---

BibTeX citation:

@mastersthesis{Sharma:EECS-2023-143,
    Author= {Sharma, Chirag},
    Title= {Embeddings for Optimization Modulo Theories Learned by Graph Neural Network Guided Solvers are Robust to Logical Space Perturbations},
    School= {EECS Department, University of California, Berkeley},
    Year= {2023},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-143.html},
    Number= {UCB/EECS-2023-143},
    Abstract= {Optimization Modulo Theories (OMT) is a highly expressive class of combinatorial optimization problems that can be used to formulate many computationally hard real-world problems in areas such as scheduling, transportation, resource allocation, and supply chain management. Solving OMT problems in practice requires careful manual design of general heuristics but for specialized applications, this can be replaced with an automated machine learning framework that learns to predict OMT problem solutions from task-specific datasets. We encode OMT problems as graphs and train Graph Convolution Networks on the task of directly predicting optimal assignments to integer variables via a classification objective. We introduce a logical space perturbation technique for sampling slightly modified versions of a given OMT problem and show that the embeddings of OMT problems that are learned via our training approach capture sufficient latent structural information about the problems to be robust to these perturbations. We demonstrate this claim by generating training data curriculums for the problem classes of DAG Multiresource Task Scheduling and the Multi-Agent Traveling Saleseman Problem and running experiments to compare the variable prediction accuracy of the direct training approach, training on an augmented dataset that includes a large number of perturbation examples, and finetuning a pretrained model that has learned to identify structural differences between a problem and perturbations of it. In all experiments, the direct training approach performs just as well as the data augmentation and pretraining approaches.},
}

EndNote citation:

%0 Thesis
%A Sharma, Chirag 
%T Embeddings for Optimization Modulo Theories Learned by Graph Neural Network Guided Solvers are Robust to Logical Space Perturbations
%I EECS Department, University of California, Berkeley
%D 2023
%8 May 12
%@ UCB/EECS-2023-143
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-143.html
%F Sharma:EECS-2023-143