Contrastive Predict-and-Search for Mixed Integer Linear Programs
Authors: Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, Bistra Dilkina
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirically, Con Pa S achieves state-of-the-art results compared to other ML-based approaches in terms of the quality of and the speed at which solutions are found. Empirically, we test Con Pa S on a variety of MILP benchmarks, including problems from the Neur IPS Machine Learning for Combinatorial Optimization (ML4CO) competition (Gasse et al., 2022). We show that Con Pa S achieves state-of-the-art anytime performance on finding high-quality solutions to MILPs, significantly outperforming other learning-based methods such as ND and Pa S in terms of solution quality and speed. In addition, Con Pa S shows great generalization performance on test instances that are 50% larger than the training instances. In this section, we introduce the setup for empirical evaluation and then present the results. We conduct an ablation study on Con Pa S-LQ to assess the effectiveness of the alternate form of Info NCE loss. |
| Researcher Affiliation | Collaboration | 1Department of Computer Science, University of Southern California, Los Angeles, CA, USA 2Department of Computer Science, Cornell University, Ithaca, NY, USA 3AI at Meta (FAIR), Menlo Park, CA, USA. |
| Pseudocode | No | The paper does not include pseudocode or an algorithm block explicitly labeled as such. |
| Open Source Code | No | The paper does not explicitly state that the source code for its methodology is open-source or provide a link to a code repository. |
| Open Datasets | Yes | Empirically, we test Con Pa S on a variety of MILP benchmarks, including problems from the Neur IPS Machine Learning for Combinatorial Optimization (ML4CO) competition (Gasse et al., 2022). The descriptions and formulations for the item placement and workload appointment problems can be found at the ML4CO competition (Gasse et al., 2022) website4. ML4CO Competition Website: https://github.com/ds4dm/ml4co-competition/blob/main/DATA.md |
| Dataset Splits | Yes | For each benchmark problem, we have 400, 100 and 100 instances in the training, validation and test sets, respectively. |
| Hardware Specification | Yes | We conduct experiments on 2.4 GHz Intel Core i7 CPUs with 16 GB memory. Training is done on a NVIDIA P100 GPU with 32 GB memory. |
| Software Dependencies | Yes | For data collection, we collect 50 best found solutions for each training instance with an hour runtime using Gurobi (v10.0.0). For testing, we set the runtime cutoff to 1,000 seconds to solve the reduced MILP of each test instance with SCIP (v8.0.1). |
| Experiment Setup | Yes | For training, we use the Adam optimizer (Kingma & Ba, 2015) with learning rate 10 3. We use a batch size of 8 and train for 100 epochs (the training typically converges in less than 50 epochs and 5 hours). To tune (k0, k1, ) (see definition in Section 2.3) for both Pa S and Con Pa S, we first fix = 5 or 10 and vary k0, k1 to be 0%, 10%, . . . , 50% of the number of binary variables to test their performance on the validation set to get their initial values. We then adjust , k0, k1 around their initial values to find the best ones. The final variable embedding is then passed through a 2-layer MLP with 64 hidden units per layer and Re LU as the activation function followed by a sigmoid layer to obtain the output pθ(x|M). |