Towards Foundation Models for Mixed Integer Linear Programming

We are grateful for the reviewer's support of our paper and our commitment towards open sourcing the research to benefit the community. We provide our responses below, and kindly refer the reviewer to the general response for more experiments and discussions. We have also incorporated your feedback in the updated manuscript.

As the idea of the proposed MILP-Evolve, which prompts the LLMs to generate diverse data under an evolution framework, is straightforward and not new, I am concerned that the technical insights of this paper are limited.

Thanks for raising the concern. We kindly refer the reviewer to our General Response 4 [GR4] and our Further Response to Reviewer fRvL (3), where we provide in-depth discussions of our contribution.

What about the cost of data generation in the experiments? As the running of such a LLM-based data generation process may be very expensive, will the generated problem classes be collected and open-sourced together?

This is a great point. The cost of data generation and collection is indeed a major challenge towards training foundation models in general, and for MILPs in particular. That is why, we will open source the generated problem classes so that other researchers with compute or budget restriction can easily use our data, and focus more improving the learning aspects.

Having said that, our pipeline is also reasonably cost and compute efficient. To generate 100 valid classes costs less than $20 (GPT API costs) and take less than half a day (where the majority of the compute time is spent on parameter adjustment as it requires solving the instances from the generated classes). We note an interesting future direction is to potentially use neural surrogate or heuristic rules to speed up this parameter adjustment step.

How do you envision the practical applications of the newly proposed task of aligning MILP instances with natural language descriptions in the MILP solving process? Can you discuss more on it?

We kindly refer the reviewer to our General Response [GR2] and our Further Response to Reviewer fRvL (1), where we provide detailed explanations of the significance of the Language-MILP Contrastive Learning task.

Dear Reviewer 3Jap,

Thank you again for your valuable suggestions. We have conducted detailed experiments and provided thorough discussions to address your concerns. As the rebuttal period is nearing its conclusion, we wanted to follow up to ensure our responses have adequately addressed the reviewers' concerns. Please let us know if there are any remaining questions or areas where further clarification is needed. We sincerely appreciate the time and effort you have dedicated to reviewing our work. Thank you!

Best,

Authors

We thank the reviewer for the constructive feedback and the time on effort spent on reviewing our paper. We provide our responses below, and kindly refer the reviewer to the general response for more experiments and discussions.

The fairness of experiments comparing the proposed data generation method with others is unclear. The paper mentions a 7:1:2 split of generated MILP problem classes into training, validation, and test subsets, raising concerns that the test data distribution may resemble that of the training data.

We thank the reviewer for raising this question. We have addressed your question in [GR1], where we have done additional experiments to test the generalization abilities of our model. We briefly summarize the discussion in [GR1] again here. We first refer the reviewer to our experiments on MIPLIB dataset in Section 5.3. We emphasize that our models are not pretrained on MIPLIB dataset, hence the results on MIPLIB are strong a indicator of the generalization abilities of our model. Moreover, during the rebuttal phase, we also performed additional experiments where we generated a new test dataset consisting of 50 new MILP classes generated using 6 seed classes that different from the ones used in training.

The methodological contribution is somewhat limited, primarily offering a data augmentation approach that employs LLMs to generate diverse MILP instances.

There is a mismatch between the content and title of the paper. The title “Towards Foundation Models for Mixed Integer Linear Programming” suggests a broader scope, while the paper mainly discusses a data generation method for MILP.

We kindly refer the reviewer to our General Response 4 [GR4], where we provide an in-depth discussion of our contribution and our choice of the title. We note that if the reviewer think this title can distract the audience from the main scientific contribution and have better suggestions, we would be happy to reconsider naming the paper differently in the future revisions.

For the task of aligning MILP instances with natural language descriptions, what are the specific formats for both the MILP instances and the textual descriptions? What are the sources of these instances and descriptions? Will all elements in each set be matched one-to-one, and does this task hold practical significance?

We thank the reviewer for the question. Regarding the practical significance of the Language-MILP task, we refer the reviewer to our General Response 2 [GR2].

The details of the instance and description generation can be found in Appendix A.1.5 and A.1.6. Specifically, the MILP instances and descriptions for the MILP-Evolve dataset are both obtained from MILP classes (the optimization code script). The MILP instances consist of $A, b, c$ matrices corresponding to linear constraints and objective function, which is same as the other two learning tasks. The language descriptions are generated based on both the MILP class code and extracted information from a rule-based parser. For the MIPLIB experiment, the MILP instances and descriptions are directly obtained from the MIPLIB webpage. Finally, for all the cases, MILP instance and language pairs are matched one-to-one.

We hope this answers your question, and we have incorporated some of these details in our updated manuscript.

How should Figure 1b be interpreted?

In Figure 1b, we take the code embedding of each MILP class (use OpenAI's text-embedding-ada), and perform TSNE to visualize them in the 2d space. The interpretation is that, originating from eight seed classes (the orange dots scattered around the space), the evolved classes gradually fill in the space, showing the diversity of the generated classes (at least at the code level).

The meaning and context of the “Mean” baseline used in the experiment is unclear.

For the description of the mean baseline, we have modified the text in Sec. 5.1. to “For integrality gap prediction, we also include a Mean baseline, which, for all MILP instances, predicts the same constant value given by the mean of all the training set labels." That is, given all Integrality Gap labels in the training set $\\{y_i\\}_{D^{train}}$, we use the average $\frac{1}{|D^{train}|} \sum_i y_i$ as the prediction for all test instances. We hope the updated text clarifies the reviewer's question.

Comparative Experiments with ACM-MILP.

We agree with the reviewer that “existing MILP generation frameworks (such that ACM-MILP) typically aim to enhance performance within a specific type of MILP class”. This pinpoints a research gap in the previous literature on learning to generalize in the multi-class setting, which is exactly the focus of our paper and greatly enabled by the MILP-Evolve generation procedure. As seen in the paper and the results on the new held out test set in our General Response [GR1], learning on classes generated by our MILP-Evolve pipeline significantly improves the generalization performance.

We would like to point out that the difficulty of the learning tasks drastically increases in the heterogeneous multi-class settings in comparison to the homogeneous single class setting studied in ACM-MILP paper and in previous literature. To support this statement, in the following table, we conduct an experiment similar to that of Experiment 1 suggested by the reviewer: we take the three models learned on (1) the seed classes (Seed), (2) augmented by ACM-MILP (Seed+VAE), and (3) our MILP-Evolve generated classes (Ours), and test on held out instances from the Seed classes -- that is, we consider instances within the seed classes (we use slightly different parameters from those in the training set to increase diversity in the test set). This process creates a test set that is in-distribution. On this test set, we see that all three models perform similarly, which makes sense as the three models have seen abundant in-distribution instances during training.

Moreover, we find that learning on the seed classes here are easier than learning on the MILP-Evolve or MIPLIB test classes used in the paper. For example, for integrality gap prediction, the deviation (around 10%) here is much lower than the deviation for the MILP-Evolve or MIPLIB test set (around 20%). This shows that learning within a few classes (as done in ACM-MILP) is much easier than learning in the multi-(MILP-)class setting (the focus of our paper).

Impact of Seed Class Selection. Including an analysis of how different seed classes influence the diversity and quality of the generated MILP instances, and whether certain seed classes lead to better generalization in the optimization tasks, would help strengthen the paper’s claims regarding the versatility of MILP-Evolve.

We thank the reviewer for the great suggestion. We refer the reviewer to General Response 3 [GR3] for our detailed study on the effect of different seed classes.

Practical Application of Language-MILP Contrastive Learning. Could the authors further clarify the real-world impact of the Language-MILP task? Specifically, how does aligning natural language descriptions with MILPs help non-experts understand and solve optimization problems.

We kindly refer the reviewer to our General Response 2 [GR2], where we discuss the practical applicability of the Language-MILP Contrastive Learning Task. In summary, MILP instances that arise in large scale production systems are extremely large with constraint matrices spanning multiple files, and are hard to parse both for non-experts and LLMs directly. Using our technique, one can identify good descriptions of such MILP instances that are easy to understand.

Here is one example of the MILP instance description: “This Loyalty Rewards optimization model is designed to maximize the total benefits from rewarding members within different regional capacity limits. Each member has a benefit weight, and each region has a resource limit. The model assigns rewards to members (represented by binary decision variables) such that the total rewards given in each region do not exceed its limit ..." We believe such descriptions can help non-experts understand the meaning of this optimization problem.

More importantly, as MILP instances grow in size, without human readable descriptions, it may be impossible to find mistakes or improve them. Thus we foresee language-MILP alignment as a crucial component of a foundation model for MILPs. While our paper takes the first step towards this task and shows the technical feasibility of via a contrastive learning approach, we acknowledge that a lot needs to be done. Improving the quality of this alignment task is an important future research direction with immense practical value. As per your suggestion, we provide a discussion on the significance and importance of this task in our updated manuscript.

Disconnect Between Tasks. How does the Language-MILP Contrastive Learning task connect to the other tasks in the paper, such as integrality gap prediction and learning to branch? Could the authors provide more insights into the overall coherence of the tasks?

The three tasks addressed in this work capture interconnected aspects of understanding and solving MILP instances: (1) the Language-MILP Alignment task aids the understanding of MILP instances' structure and characteristics. A deeper understanding of MILP instances aids non-experts in comprehending the problem; it enables experts to develop, debug MILP instances, and design specialized algorithms based on instance-specific properties, (2) the Integrality Gap Prediction task focuses on analyzing solution properties of the MILP instance. An accurate integrality gap predictions can guide algorithm selection, allowing instances with tight gaps to be solved via LP relaxation without fully solving the MILP. (3) The learning to Branch task improves the process of solving MILP instances through more effective branching, which can have huge time and cost saving for industrial applications and production pipelines.

Hence, these tasks are complementary and collectively essential for both practitioners and experts to advance MILP research.

Overclaim in Contribution for Language-MILP. Since there are no substantial results or experiments demonstrating gains in the Language-MILP task, this claim could be seen as somewhat overstated.

Thank you for raising this concern. We are worried that the reviewer may have a misunderstanding of our paper, and we would like to provide clarification here. All experiments we did on 3 test datasets show consistent and significant improvement on Language-MILP alignment task. This can be see from Table 1 in the main paper, the new experiment we did in the General Response 1 [GR1] section, and the MIPLIB results in the main paper. For example, in [GR1], initializing with Ours achieves a 10-Way accuracy of 53.99%, whereas initializing with Seed + VAE (ACM-MILP) only has a 10-Way accuracy of 44.62%.

We are grateful for the insightful and detailed feedback from the reviewer, which greatly strengthen our work. We provide our responses below, and kindly refer the reviewer to the general response for discussions and new experimental results.

It might be worth considering how this task compares to having an LLM directly interpret a new MILP, as it is not immediately clear whether thproposed approach would outperform such a method. Clarifying the value added by this task would strengthen the paper.

This is a great suggestion! We refer the reviewer to our general response section [GR2] where we did the experiment you asked for. Our result shows that GPT-4o performs poorly when directly interpreting the MILP instances. One of the bottlenecks with LLM directly interpreting MILP instances is that, the MILP instance files are typically huge as they contain the raw numerical values of the variables and constraints, substantially surpassing the context length of LLMs; in [GR2], we subsample the rows of the instance files up to context length, but the missing information leads to subpar performance. That's why in this work, we focus on using Graph Neural Networks (GNNs) to embed MILP instances and perform contrastive learning with the text embedding of the description from a language model.

Language Quality. Given that the language samples are generated by LLMs from solver code, how do the authors ensure the quality of these samples? Would human-generated descriptions lead to better learning outcomes in this task?

This is a nice question. Inspired by your suggestion, in a new experiment we performed during rebuttal (see General Response 1 [GR1]), we checked the GPT generated descriptions and manually modified the descriptions to make sure the descriptions match the optimization problems. We observed that GPT-generated descriptions are generally accurate, correctly reflecting the optimization problem and highlighting potential real-world applications of the optimization class (e.g., "This type of scheduling is essential in manufacturing and project management, where minimizing total completion time across multiple tasks is critical."). Some descriptions included irrelevant details (e.g., ``PySCIPOpt is used to solve the optimization problem"), which we manually removed.

Given these expert/human verified language labels, initializing with our model pre-trained on MILP-Evolve consistently outperform all the baselines, further strengthening contributions of our work. We appreciate your comment in pointing this out.

Having said that, expert human annotations would indeed help in further improving the quality of model generated descriptions. Unfortunately, human expert labeling is time consuming and does not scale to large datasets. Once we bootstrap a process towards training foundation models for MILP, one also has the potential to collect human annotations of the MILPs based on users feedback, similar to how AI math tutoring frameworks collect annotations from the users or in RLHF frameworks. An interesting future direction is to explore more principled hybrid human and LLM labeling methods, and perform A/B testing to provide accurate and abundant description labels.

We appreciate the reviewer's positive feedback and thank the reviewer for their excellent suggestions on the new experiments to strengthen our work. We have performed the experiments you suggested and have reported the results in general response section [GR1]. We provide responses to specific questions here.

The dataset test seems to be not that "unseen." It would be great if you only use six classes for training, 1 for validation, and 1 for testing. Then this can further show the power of your method.

We refer the reviewer to [GR1], where we test the performance on another 50-class test set generated by running MILP-Evolve with six unseen seed classes. Initializing with the Ours pre-trained model yields the best transfer learning performance on this test set. We also note the MIPLIB experiments in the paper also are unseen from training.

One more interesting experiment is to fix the number of training data for your method and the baselines. To be more specific, let N be the number of instances of SEED. Then, we randomly take N / 10 data and use Evolve to generate N instances and call them dataset B. Then, training directly on SEED and this B can further show the power of your model.

Thanks for providing interesting insights and ideas for new ablation studies. First, we would like to provide a clarification for a potential misunderstanding: MILP-Evolve acts on MILP class level instead of MILP instance level; we do not use any seed `instances' (the numerical A, b, c values) but rather the seed class (the code script) to evolve new classes. Each MILP class serves as an instance generator; by setting different randomness of the code script, one can generate unlimited MILP instances from the class. We hope this clarifies our methodology.

Having said that, your comment inspires us to perform the following new ablation study. For the Integrality Gap Prediction task, we construct different training sets by varying the ratio of seed and instances generated from MILP-Evolve classes. We fix the total number of training and validation instances as 1200 and 300 instances, respectively. We then train a model on each of these training sets and test on the original MILP-Evolve held out test set (main paper Table 1). From the result table below, we see that including more MILP instances from MILP-Evolve (i.e. more diverse MILP classes) improve the performance.

Dear Reviewer zQjg,

Thank you again for your valuable suggestions. We have conducted detailed experiments and provided thorough discussions in response to your feedback. As the rebuttal period is nearing its conclusion, we wanted to follow up to ensure our responses have adequately addressed the reviewers' concerns. Please let us know if there are any remaining questions or areas where further clarification is needed. We sincerely appreciate the time and effort you have dedicated to reviewing our work. Thank you!

Best,

Authors

Some of you asked if our model can generalize to MILP classes that have never been seen during training and suggested new experiments. Inspired by Reviewer zQjg's comments, we introduce another test set with 50 classes obtained by running MILP-Evolve on a completely disjoint set of 6 unseen classes*. We ensure that no class in this test set is used in training of our base model and we will describe how we generate these new MILP classes in the next paragraph. Table (2) summarizes results of our new experiments. It is evident from the new experiments that our pretrained model achieves the best results, highlighting the generalization abilities of our models.

We would also like to use this opportunity to highlight that MIPLIB dataset (already included in the manuscript) is already a strong benchmark for measuring the generalization abilities of our model. This is because, MIPLIB, a commonly used MILP benchmark consisting of heterogeneous MILP classes, is totally disjoint from the training dataset. Our results on MIPLIB dataset already shows that our framework generalizes to unseen MILP classes, and our new experiments corroborates on these findings.

Including the new experiments we did during the rebuttal phase, our paper tests generalization abilities of our model on 3 different test datasets that are increasingly more challenging than the previous one: (1) held out classes from the original MILP-Evolve datasets (Table 1 in manuscript), (2) a new set of MILP-Evolve datasets from 6 unseen seed classes (Table 2), and (3) MIPLIB dataset (Table 3).

Results. All these 3 experiments result in the same consistent behavior: We see that learning on MILP-Evolve data improves the performance across all these levels.

* New Experiment Setup.

• The New MILP Classes. We take a different set of 6 unseen seed classes, consisting of Graph Coloring, Job-Shop Scheduling, Protein Folding, Multi-Item Lot Sizing, Bin Packing, and Max Cut. We run MILP-Evolve to slightly expand the new test set to a total of 50 classes. Similar to the MIPLIB experiments, we perform transfer learning of different models to this unseen test set (40% classes for fine-tuning, 60% classes for testing).
• Expert Curate / Verified Language Labels for Language-MILP Alignment. To ensure the quality of language descriptions, we manually verified and modified the linguistic description and made sure the descriptions matches the optimization problem in the testing set.

While creating a framework that can generate diverse and meaningful MILP classes is an important, if not the most important aspect of our work, in our humble opinion, we believe that this study has a substantially broader scope than the LLM-based data generation. Our key motivation for the work is studying whether a foundation model approach -- that is, pretraining on a large and diverse data that can generalize to a wide variety of downstream tasks -- can be an effective paradigm for MILPs. We want to highlight that there was no definitive answer to this question prior to our work. As we mentioned in the paper, all the previous work only trained models for specific MILP classes. More importantly, unlike language and image modality, the optimal structure for each MILP instance can be quite different. That is, even if we focus on one MILP problem, say set cover, then the structure of optimal solutions can be quite different. Hence, it is not clear if a DNN trained on a diverse family of MILP classes can generalize.

Our work shows the feasibility of such an approach and paves the way for more research in this direction. In our humble opinion, this is a significant contribution of this work and hence we felt justified to call our paper "towards a foundation model". We acknowledge that our model is not a foundation model (yet), but we are taking steps towards the feasibility of training such a model. However, if the reviewers think this title can distract the audience from the main scientific contribution and have better suggestions, we would be happy to reconsider naming the paper differently in the future revisions.

Having said that, gathering training data is an essential step in building a foundation model: for instance, GPT-4o was similarly trained on a large-scale data generation pipeline, resulting in capabilities that have both surprised and greatly benefited its users. Inspired by this philosophy, our work includes a robust process for generating and integrating a diverse set of MILP data to advance research in the field. Beyond data collection, we have developed novel training tasks that allow our model to surpass all baseline models developed from the past years. Our experiments provide valuable new insights (e.g., diversity, quantity, distribution.) to the optimization community, offering researchers a framework to build more effective models in the future.

Finally, we believe our proposed methodology and our findings can help the community advance toward production-ready models for MILP that not only accelerate research for optimization experts but also enable non-experts to better understand, plan, and apply optimization techniques effectively. This is also the reason why we are committed to fully open source our framework to advance future research.

Based on Reviewer fRvL's comment, we include ablation studies to analyze the effects of different seed classes.

Statistics. The table below shows the proportion of generated classes from each seed class using MIP-Evolve framework.* We see that some seed classes can lead to more generated classes (e.g. Combinatorial Auction (CA)) than others (e.g. Knapsack (KS)). One potential reason could be that our filtering and parameter adjustment procedures can find good solutions for certain classes more easily than others.

* Note that for cross-over prompts, we only tracked the trace of the first MILP class, so the number here can be slightly noisy.

Impact of different classes on the learning performance. For each of the eight seed classes, we train separate models on instances sampled using these two methods. (1) All evolved classes based only on a single seed class (One Seed), (2) with weighted sampling, where 70% come from all evolved classes based on a single seed class and 30% based on other seed classes (Weighted). We fix the number of train and validation instances, and compare the test performance on MILP-Evolve held out test set (Table 1) and the transfer learning performance to MIPLIB.

Results: We report our findings in the table below; we see that

• Table 1, One Seed: Learning on classes based on one single seed class has limited performance.
• Table 1, Weighted: Classes with a higher proportion in the MILP-Evolve dataset (CA, GIS), when given a higher weight when sampling training set, typically lead to a better test performance on the MILP-Evolve held out set; an exception is Capacitated Facility Location (CF), which has a lower ratio than CA and GIS, but its learned model achieves the best test performance among all models.
• MIPLIB, Weighted: The transfer learning performance when initializing with the different models seem to be similar on the MIPLIB test set, and is worse than Ours performance when trained on instances from all MILP classes.

Finally, these results give more evidence to the primary hypothesis of this paper: the importance of having a diverse set of MILP classes from different seed classes to improve the generalization performance.

Some of you asked about the significance and practical applications of language-MILP contrastive learning task we study. We answer this question on two fronts: the utility of this task from the perspective of understanding MILPs and the potential of contrastive learning technique itself.

Many open source MILP datasets such as MIPLIB and in many business scenarios, the MILP instance files contain only constraints and variables (the raw $A, b, c$ values in the optimization), which are typically hard to understand and massive in size. Most of these MILP files lack descriptions of the underlying optimization problem and/or not sufficiently meaningful. Moreover, we cannot directly feed them into LLMs to interpret and generate language descriptions of the MILP formulations.

To justify this previous claim, as asked by the reviewer (fRvL), we investigated if GPT-4o model can interpret MILPs. We prompt GPT-4o to directly interpret the instance files for the same dataset as in [GR1] (subsample rows up to context length). Unfortunately, out-of-the-box GPT-4o's performance is worse than the model trained with our contrastive loss. The table below summarizes our findings.

Hence, this work takes first step with a contrastive learning approach to align GNN embedding of MILP instances with the text embeddings, aiming to provide meaningful interpretations when giving the MILP instances as input. Our results indicate that our approach holds lot of promise.

Given the abstract nature of the MILP instances, we believe any assistance in helping users' understanding of them is crucial. This can help nonexperts to understand the problem and also identify the incorrect formulations. This task also complements our other two tasks which are concerned with solving MILPs rather than understanding. We believe that a foundation model for MILPs that aims to democratize solving MILPs should also have the ability to help users to understand them.

On a more technical side, our language-MILP contrastive learning experiments show that indeed it is possible to align models for this task. We think that this is a novel application of this technique. With more data, we anticipate that our framework can help the community to significantly improve understanding of the MILP instances. Moreover, one can further expand from our work to performance multimodal description generation with the GNN embeddings, which we leave as an interesting (but also challenging) future work.