Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision

Fan et al. uses LIBSVM and STOCH datasets. Can the authors display their results on these two datasets as well?

It would certainly be helpful to compare results across all datasets from the original work. However, since these two datasets were generated by the authors and are not publicly available, we are unable to reproduce them. Instead, we incorporate other publicly available datasets to expand our evaluation.

It will be useful to have such a table (Table 11 in Appendix)) for tripartite representation. I am particularly interested in what power does N=0 (i.e., only the messages passed back and forth from the global node).

We add experiments on using tripartite graph-based GNN with difference bidirectional message passing layers (0, 2, 4 and 6 respectively) compared to the default solving mode without warm start. We use the base training without loss function for basic variable selection, the loss function for feasibility, and label preprocessing. Here are the number of iteration and solving time on the unpresolved datasets: Iteration number:

Solving time in seconds:

Due to time constraints, we have not yet completed testing on the Mirp2 dataset, but we will provide the results later. It is evident that bidirectional message passing is crucial as it effectively utilizes the coefficients in the constraint matrix. Additionally, adding more bidirectional message passing layers results in a slight improvement.

There is a knawing worry that the improvements might just be because of the increase in the number of parameters.

The computational overhead of our tripartite graph-based model with two bidirectional message-passing steps is comparable to that of the bipartite graph-based model with six message-passing steps. As shown in Table 11 of the appendix, increasing the number of message-passing layers in the bipartite graph-based model does not necessarily improve prediction quality. Our GNN architecture effectively leverages its complexity, making full use of the computational overhead to predict a higher-quality basis.

What is the form of $L$ in Equation 4?

How are $\theta$ and $\mu_k$ selected? Did the authors do some hyperparameter tuning on these parameters?

$\mu_k$ is the weight of the loss calculated from the $k^{th}$ label using Equation 2, which defines the weighted cross-entropy. The value of $\mu_k$ is given in Equation 16 and is determined based on experience rather than precise fine-tuning. It is worth investigating the hyperparameter settings for $\theta$, $k$, and $\mu_k$.

It will be useful to understand when tripartite and bipartite representation might look similar. Can the authors take a few examples such as $l_x=0$, $u_x=inf$, $l_s=-inf$, $u_s=b$? Some examples that can help understand how representations might differ wildly under two cases.

For LP problems in standard form:

$

\begin{aligned} \min_{\boldsymbol{x} \in \mathbb{R}^n} \quad & \boldsymbol{c}^\top \boldsymbol{x} \\ \text{s.t.} \quad \boldsymbol{A} \boldsymbol{x} &\leq \boldsymbol{b}, \\ \boldsymbol{x} &\geq 0, \end{aligned}

$

we have $l_x = 0$, $u_x = \infty$, $l_s = -\infty$, $u_s = b$. In the tripartite GNN, the initial message passing occurs only between the global node and nodes in $V_{primal}$ (see Figure 1(a)), which differs from the bipartite GNN. The other difference is that the tripartite GNN introduces additional message passing between $V_{dual}$ and $V_{primal}$ via indentity edges—an interaction that may be redundant in this case. As a result, the bipartite GNN could be preferable since it maintains a similar structure to the tripartite GNN while incurring lower computational overhead.

However, for LP problems in a more general form, as shown in Equation (1), where $l_x$, $u_x$, $l_s$, and $u_s$ are all finite numbers, the initial message passing between the global node and other nodes introduces richer information into $V_{dual}$, $V_{primal}$ and $C$. Subsequent message passing between $V_{dual}$, $V_{primal}$ and $C$ can then fully exploit these enriched node embeddings. In this scenario, the tripartite representation differs significantly from the bipartite one, allowing the tripartite GNN to exhibit greater expressiveness.

limited discussion of computational overhead introduced by the more complex GNN architecture

How does the computational cost of the tripartite GNN compare to the bipartite model, and how does this balance with the solver time savings? It would be valuable to include runtime comparison of the GNN inference time versus the time saved in the solving process

The computational overhead of our tripartite graph-based model with two bidirectional message-passing steps is comparable to that of the bipartite graph-based model with six message-passing steps, typically taking less than 1 second. As shown in Table 11 of the appendix, increasing the number of message-passing layers in the bipartite graph-based model does not necessarily lead to better prediction quality. Our GNN architecture effectively leverages its complexity, fully utilizing the computational overhead to predict a higher-quality basis. In simpler LP cases, this added overhead may slightly increase the total solving time, including inference time. However, for more complex or larger problems, the impact of this overhead becomes negligible.

unclear how the proposed approach will scale to very large LP instances beyond those in the test datasets

What are the limitations of your approach for very large-scale LP problems?

Our approach scales effectively to large LP instances. In the Mirp2 dataset, some instances are so large that they require several minutes to several hours for the solver to process. We demonstrate the acceleration achieved on these large instances as follows:

The iter_* columns represent the number of iterations, while the time_* columns indicate the solving time in seconds. In practice, the GNN model is particularly useful for large LP problems, as its computational overhead is negligible compared to the overall solving time. However, for extremely large LPs—which translate to massive graphs—memory constraints may require the use of graph sampling techniques like GraphSAGE during both training and inference.

The abstract states, "a closer initial basis does not always result in greater acceleration," but later mentions "achieving high prediction accuracy." It is unclear what accuracy refers to in this context—closeness to the optimal basis or actual solver acceleration.

Similarly, the introduction states, "A better starting point may be closer to the potential optimal solution in terms of logical pivot distance, often resulting in fewer simplex iterations," which contradicts the earlier claim that closeness does not always lead to acceleration.

Clarifying these statements would improve the paper’s logical consistency and ensure a clearer understanding of the contributions.

Accuracy measures how close the basis is to the optimal solution. We follow the same equation as in [Fan et al., 2023] (page 13) to compute accuracy. In general, a closer basis tends to reduce the number of iterations, which can, in turn, shorten solving time. Therefore, achieving high accuracy is valuable. Additionally, it serves as an indicator of the GNN model’s ability to learn and approximate the optimal basis.

However, a closer initial basis does not always guarantee greater acceleration. If the initial basis is invalid, Phase I may require significant time to obtain a valid one, which could still be far from optimal. While predicting a closer basis is an intuitive way to speed up the solver, additional refinements are necessary to achieve actual performance gains.

Our work improves the model's ability to predict a closer basis. More importantly, we go beyond accuracy (closeness) by prioritizing actual solver acceleration. Through a detailed analysis of the LP problem, we introduce additional techniques that significantly enhance practical solving speed, which remains the ultimate objective.

The tripartite graph should be tested against multiple GNN architectures (not just one) to demonstrate its effectiveness across different models.

The impact of the tripartite representation should be better isolated from other factors (e.g., loss functions, preprocessing).

We add experiments on using tripartite graph-based GNN with difference bidirectional message passing layers (0, 2, 4 and 6 respectively) compared to the default solving mode without warm start. We use the base training without loss function for basic variable selection, the loss function for feasibility, and label preprocessing. Here are the number of iteration and solving time on the unpresolved datasets:

Iteration number:

Solving time in seconds:

Due to time constraints, we have not yet completed testing on the Mirp2 dataset, but we will provide the results later. It is evident that bidirectional message passing is crucial as it effectively utilizes the coefficients in the constraint matrix. Additionally, adding more bidirectional message passing layers results in a slight improvement. We also plan to evaluate the performance using other GNN architectures, such as GraphTransformer and GAT, and will share the results once available.

The paper correctly cites LP and MIP learning-based methods, but it would benefit from a broader discussion on alternative warm-starting techniques beyond GNNs.

Thanks for your suggestions. We will add more literature on warm-starting techniques and update the revision.

Comparison with other warm-start heuristics. The paper mentions a few non-ML methods for basis selection. It would be important to include them as a baseline, though previously probably has shown they are no better than the bipartite GNN.

Thanks for your suggestion! We will incorporate these non-ML methods as baselines in our paper.

The instances used are from MILP benchmark with relaxed integral constraints. The paper doesn’t quite justify why these benchmarks are important for LP solving that translate to real-world impact. In other words, why not use benchmarks designed for LP instead of MILP?

The current pure LP benchmarks are very diverse instance by instance and large-sccale -- the reason may be partly due to the strong commercial solvers like Gurobi, CPlex and COPT. In fact, there is little benchmarks containing similar distributions for training and testing data to evluate learning-based methods, as the learning-based LP solvers are still in the early stage.

In contrast, the MILP benchmarks contain rich instances that can be divided into training and testing ones.

In addition, the instances selected seem easy to solved, that is, on average the runtime is only less than a minute. It would be interesting to see how well this method performs on hard instances (e.g, instances that takes 5 minute or even more to solve).

Our approach scales effectively to large LP instances. In the Mirp2 dataset, some instances are so large that they require several minutes to several hours for the solver to process. We demonstrate the acceleration achieved on these large instances as follows:

The iter_* columns represent the number of iterations, while the time_* columns indicate the solving time in seconds. In practice, the GNN model is particularly useful for large LP problems, as its computational overhead is negligible compared to the overall solving time. However, for extremely large LPs—which translate to massive graphs—memory constraints may require the use of graph sampling techniques like GraphSAGE during both training and inference.

A writing issues: There should be a space between words and citations. Some of them are missing.

Thanks and we have polished the paper.

In ablation study, why is tripartite without P (label preprocessing) the best? Are the improvements statistically significant?

From Table 8, we observe that the only reason the tripartite model without P outperforms the one with P is due to a significant improvement on the Mirp1 dataset. This may be because, while processing the labels to reduce inconsistency helps the GNN learn and achieve better accuracy, a closer initial basis may sometimes be invalid, requiring more time in Phase I to repair it. However, this is not a general trend, as adding P consistently leads to better acceleration across all other datasets.