Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision
Authors: Anqi Lu
Junchi Yan
Venue: ICML 2025 poster (2025)
Keywords: supervised learning
graph neural network
linear programming
simplex method
initial basis
Primary area: applications->everything_else

Abstract: For the fundamental linear programming (LP) problems, the simplex method remains popular, which usually requires an appropriate initial basis as a warm start to accelerate the solving process. Predicting an initial basis close to an optimal one can often accelerate the solver, but a closer initial basis does not always result in greater acceleration. To achieve better acceleration, we propose a GNN model based on a tripartite graph representation inspired by LP duality. This approach enables more effective feature extraction for general LP problems and enhances the expressiveness of GNNs. Additionally, we introduce novel loss functions targeting basic variable selection and basis feasibility, along with data preprocessing schemes, to further improve learning capability. In addition to achieving high prediction accuracy, we enhance the quality of the initial basis for practical use. Experimental results show that our approach greatly surpasses the state-of-the-art method in predicting initial basis with greater accuracy and in reducing the number of iterations and solving time of the LP solver.

Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision
Angi Lu
Junchi Yan
Abstract
tions represented by basic solutions rather than numeri- cal approximations. With contributions from numerous researchers, the simplex method has maintained high perfor- mance on large-scale problems and remains a fundamental approach for solving LP problems. The revised simplex method (Dantzig & Orchard- Hays, 1954) made practi- cal with limited numerical accuracy on computing units. (Lemke, 1954) demonstrated the importance of the dual sim- plex method, while (Forrest & Goldfarb, 1992) developed a computationally efficient steepest edge pricing rule. (Har- ris, 1973) introduced the two-stage ratio test, which uses feasibility tolerances to find better pivot elements. (Suhl & Suhl, 1990) presented an efficient LU factorization im- plementation, and (Forrest & Tomlin, 1972) improved the updating basis method. Anti Anti-degeneracy techniques (Ryan & Osborne, 1988) prevent the simplex method from cy- cling in dead loops. These improvements have significantly enhanced the efficiency and stability of the simplex method.
For the fundamental linear programming (LP) problems, the simplex method remains popular, which usually requires an appropriate initial basis as a warm start to accelerate the solving process. Predicting an initial basis close an optimal one can often accelerate the solver, but closer initial basis does not always result in greater accelera- tion. To achieve better acceleration, we propose a GNN model based on a tripartite graph repre- sentation inspired by LP duality. This approach enables more effective feature extraction for gen- eral LP problems and enhances the expressive- ness of GNNs. Additionally, we introduce novel loss functions targeting basic variable selection and basis feasibility, along with data preprocess- ing schemes, to further improve learning capabil- ity. In addition to achieving high prediction accu- racy, we enhance the quality of the initial basis for practical use. Experimental results show that our approach greatly surpasses the state-of-the-art method in predicting initial basis with greater ac- curacy and in reducing the number of iterations and solving time of the LP solver.
Since the simplex method pivots from basic solution to basic solution, the strategy for choosing the initial basis greatly impacts performance. A better starting point may be closer to the potential optimal solution in terms of logical pivot distance, often resulting in fewer simplex iterations. The most fundamental strategy is the logical basis introduced by (Chvátal, 1983), which simply selects all slack variables. This strategy is straightforward, ensuring nonsingularity and convenient inverse computation, making still active in simplex solvers like HiGHS (Huangfu & Hall, 201 2018b). However, this conservative strategy is independent of input problems and does not seek better starting points for various problems. The potential for performance improvement has prompted extensive research.
1. Introduction
Linear programming (LP) has played vital role in decision- making since it was first introduced by (Dantzig, 1948). Many real-worid optimization problems can be formulated as linear models or approximated through linearization. Fur- thermore, LP remains the most frequently used optimization technique in complex optimization problems such as Mixed Integer Programming (MIP).
The seminal work (Bixby, 1992) presented a heuristic method implemented in CPLEX (Gearhart et al., 2013), con- structing the initial basis in a preference order. It prioritizes slack and free variables over bounded and non-singleton variables to keep the basis sparse and well-behaved, while minimizing the inclusion of artificial variables to avoid their restrictive bounds on optimization. It works better for easier problems but is less effective for harder ones. The "Idiot" crash (Galabova Hall, 2020), another practical method, more complex and time-consuming. Implemented by For-
The simplex method is widely-used algorithm for LP problems, known for obtaining theoretical optimal solu-
'Sch. of Artificial Intelligence & Sch. of Computer Science, Shanghai Jiao Tong University. Correspondence to: Junchi Yan <yanjunchi @ sjtu.edu.en>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning LP Basis Selection via Duality-Inspired Tripartite Graph Representation and Comprchensive Supervision
rest in COIN-OR Linear Programming Solver (CIp) (Forrest, 2006), it replaces the linear objective minimization with combination of the objective and quadratic function of constraint violations. This method performs better than the primal simplex with a logical basis, especially on quadratic assignment problems (QAPs), but may increase total solving time for other LP problems.
derived labels. Based on the analysis, we propose data preprocessing schemes to reduce Bayesian error and im- prove learning outcomes.
Beyond higher test prediction accuracy, utilizing the ini- tial basis provided by our model to warm start the state-of- the-art open-source LP solver HiGHS (Huangfu & Hall, 2018a) results in an average over 2x improvement in reducing both average solving iterations and time com- pared to the SOTA (Fan et al., 2023). Particularly, on the presolved Mirp1 (Papageorgion et al., 2014) test set, with the solver achieving the optimal solution, our model reduces the average solving iterations to 32% and the average solving time to 42%, outperforming the current SOTA, which achieves 62% and 73%, respectively.
Despite these challenges. researchers continue to focus on improving initial basis selection. In recent years, deep Saaning-partieularrs graph neural networks (GNNs)-has has shown significant promise across various domains. (Khalil et al., 2017) proposed a GNN model for learning greedy heuristics on several combinatorial optimization problems defined over graphs. (Gasse et al., 2019h) applied GNNs to enhance variable selection policies in branch-and-boume MIP solvers, establishing the use of bipartite graphs of con- straints and variables as a standard representation for MIP problems. These efforts highlight the potential of GNNs to learn the structural characteristics of optimization prob- lems. More recently, GNNs have also been applied to initial basis selection for LPs (Fan et al., 2023), demonstrating promising performance compared to traditional heuristics.
2. Preliminaries
We first present the basic for linear programming and its emerging solving techniques leveraging machine learning, though the development is still in its infancy.
2.1. Linear Programming
However, even when GNNs predict initial basis close to the optimal one, this does not always lead to greater acceler- ation. If the predicted basis is invalid, Phase I may require significant time to recover a valid one, which may still be far from optimal. Although predicting a closer basis is an intuitive strategy for acceleration, additional refinements are often necessary for performance improvements.
LP Representation The general form of LP problems is:
min #ER"
cTx x
s.t. 1" S Aa uu, 1 x S u²,
(1)
where A E Rmxxn C E R", 1' and 1' E (RU(->)))" u² and un E (IR (oo))" We refer to the elements in x as variables and the rows in Ax as constraints. There are variables and m constraints. By defining 8 = Aa. we can regard each constraint as a variable in s. We can express æ as (a+ - x)), where a 2 and x 2 represent the positive and negative parts of æ,, respectively.
Our work improves the model's ability to predict closer basis. More importantly, we go beyond accuracy (close- ness) by prioritizing actual solver acceleration. Through a detailed analysis of the LP problem, we introduce addi- tional techniques that significantly enhance practical solving speed, which remains the ultimate objective.
Duality A.I provides additional details on the duality in LP. The dual problem of the primal LP, expressed in its general form, can be written as
In this study, we aim to further explore the capabilities of GNN-based models in the context of initial basis selection for I.P. Our main contributions are as follows:
(1') T yi + (u²) yi.
min V..V . 20
Inspired by duality in LP, we propose a tripartite graph- based representation for general LP problems. This rep- resentation, combined with a specially designed message passing process on graph, enhances the ability of GNNs to represent and aggregate LP problem features.
(1*)) yř + (u²)² Tyū
s.t. A (yf y + (yf - yn) = C.
Basis We define B, C [n] and B, C [m] to represent the indices of basic variables in variable and constraint sets. Together, B, and B, form a basis B (B,, for the LP problem, which should satisfy that the number of basic variables equals m. i.e., |8,| + |B, m, and the basis matrix B = [AB_ - I which is the concatenation of AB. and - I is nonsingular. We define N₂ = [n] \ B, and N₂ = [m] \ B, to represent the indices of non- basic variables in their respective sets. Once the basis is
We qualitatively analyze the importance of basic variable prediction accuracy on overall prediction accuracy. Addi- tionally, we identify the negative effect of the infcasibility of the initial basis. Building upon these two aspects, we design a new loss function targeted towards basic vari- able selection and incorporate levti- labels extracted from the solving path into the loss function.
We identify potential inconsistencies in raw solver-
2

---

Learning LP Basis Selection via Duality-Inspiree Tripartite Graph Representation and Comprchensive Supervision
determined, all non-basic variables and constraints are set to their finite upper or lower bounds, and the values of the basic variables can be solved using equation
On the theoretical side, (Chen et al., 2022) demonstrated that GNNs based on bipartite graphs can learn solutions that are infinitesimally close to the -n-mo minimal optimal so- lutions for LP problems. (Qian et al., 2024) discovered that GNNs can simulate iterations of the interior point method by utilizing message passing on tripartite graphs, yielding solutions closer to optimal LP solutions compared to those obtained from bipartite graphs. This approach also reduces computational costs compared to neural networks employ- ing differential equation systems (Wu & Lisser, 2023).
(zg, $g. [As=-
Ig SN. AN.
If the value of any basic variable lies outside its lower and upper bounds, we call the basis infeasible; otherwise not.
Simplex Method. It starts from feasible basis, and com- pute the objective value in terms of non-basic variables
c x -cc,, B " SN. (Lok, T
2.3. GNN-based Model for Inital Basis Selection
DJB-'ANGER - )aN,
Here we introduce the state-of-the-art GNN-based model (Fan et al., 2023) for selecting initial bases in LP. In the optimal basis obtained by the solver, each constraint or variable corresponds to an integer value L(s:) or L(z)) E {0, 1, 1,2), where a value of represents a basic variable, totaling m, while the remaining non-basic variables take on 0 (or 2), indicating whether they are set the lower (or upper) bound in the optimal basis. Convert the optimal basis obtained from the solver into one-hot vector ye, or yи E (0. 13 as the label for supervised learning.
As long as changing a non-basic variable a basic variable can reduce the objective value, the simplex method selects one to enter the basis and identifies basic variable to leave the basis. By doing this, the method transitions from one feasible basis to a neighboring feasible basis. This process iterates until no further reduction in the objective value is possible. This iterative procedure can be viewed as moving from one vertex another vertex of the feasible region, which forms a simplex.
Note that if the initial basis is infeasible, we need to use simplex phase 1 to convert it into a feasible basis. For more details about the advanced simplex algorithm for general form LP, interested readers can refer to (Ping-Qi. Ling-Qi,22 2014).
Constructing the general LP problem as a bipartite graph, the constraint matrix is transformed into edges, forming the edge set F., while other information converted into node features, forming the sets of variables and constraints V and C, respectively. Bidirectional message passing is employed on the bipartite graph. In each layer, infor- mation is passed once from variables to constraints and once from constraints to variables for node updates. Sim- ilar to the turee-classificatin problem on the graph, each node ultimately outputs a thrce-dimensional vector, p(s;) or p( (z,) ). representing the probabilities of belonging to each of the three categories. The constraints variables cor- responding to the largest m values in {p(s))LL]
2.2. GNN-based Model for MIP
Recently, GNN-based models have gained widespread use in the realm of MIP. In MIP problems, variables and con- straints interact through the constraint matrix, allowing their interactions to be represented as a graph. (Gasse et al., 2019a) proposed encoding mixed-integer linear optimiza- tion problems as bipartite graph (G, C, E, V). Each con- straint and variable is represented as node, forming the node sets C' and V. respectively. Each non-zero value in the constraint matrix creates an edge in the set E, where the weight of an edge connecting C, and V, is the value of the constraint matrix at row and column j. Lots of works have been done using GNN based this bipartite repre- sentation, including learning to branch (Achterberg et al., 2005) (Gupta et al., 2020) (Nair et al., 2020), learning cut selection (Berthold et al.. 2022) et al., 2022) (Wang et al., 2023b), learning to presolve (Liu et al.), data gener- ation (Wang et al., 2023a), LP-related problems (Li et al., 2022) (Fan et al., 2023) (Qian et al., 2024) and other MIP problems (Khalil et al., 2022) (Zhang et al., 2023). (Ding et al., 2020) proposed a tripartite graph representation con- sisting of variables, constraints, and global node. The edge weights between variables and the global node represent the coefficients of the variables in the objective function, while the edge weights between constraints and the global node represent the rinht-hand side (RHS) of the constraints.
< < m] U (p(x;)]1]11 S S n} are chosen as basic variables. Among the remaining variables, if [0= > p(x;)[2], then the non-basic variable takes on the lower bound; other- wise, it takes on the upper bound.
A loss function is constructed using the cross- cross-entropy func- tion for the 3-class classification problems:
L = I((P), (x. (v))
aly,, ((.())(((((s)) Va.)
(2)
Nc,,,)ce((((,))))....
where ay.,) and a(y,,) represent the weights of different variables, which are inversely proportional to the frequen- cies of their label categories in the samples.
3

---

Learning LP Basis Selection via Duality- Tripartite Graph Representation and Comprehensive Supervision
3. Proposed Method
Global node
3.1. Tripartite Graph Representation general LP
M
1
In the bipartite graph representation used in (Fan et al., 2023), edge information only includes the constraint matrix, whereas crucial data from the objective function coefficients and the bounds of variables and constraints only be utilized through node features during GNN's message pass- ing. Directly incorporating this information into the graph structure could enhance the representation capability for I.P.
Q11
5
X2 X2"
442
d21
x, X2"
The existing tripartite graph representation (Ding et al., 2020) can only represent LP problems where all constraints less than or equal and variable ranges are non-negative. However, in practice, LP problems are often represented in general form, and advanced solvers support direct in- put of this form. Converting a general form problem to more standardized form increases the problem's 's size, in- such cases, even if the neural network can predict good results, the increased problem size input to the solver may nega- tively impact performance more than the neural network's assistance, resulting in lower overall efficiency.
x, x
X,
V dual
primal
(a) tripartite graph representation of LP
flating the number of variables and constraints.
57
Based on duality in LP, by comparing the primal problem with the dual problem, can be observed that each finite upper or lower bound the primal problem corresponds to variable in the dual problem. finite lower bound in variable with the coef- ficient of the negative of this bound in the dual problem's objective function, while finite upper bound corresponds to the bound itself. Each variable in the primal problem corresponds to an equality constraint in the dual problem, which can also seen as constraint with equal upper and lower bounds. Furthermore, combining the two variables corresponding the constraints' upper and lower bounds in the dual problem forms (uf v(.)) whose coefficients in the constraint matrix A match the coefficients of (x* x >) in the constraint matrix A in the primal problem. Similarly, regarding the bounds of variables constraints, I" appears both in the dual and primal problems.
5
(b) message passing the graph
the primal problem corresponds
Figure 1. Tripartite graph-based GNN: and variable bounds are encoded as graph edges, while nodes except the global one are split half within the tripartite graph, allowing for the representation of both the primal and dual LP problems. A global message passing process begins with the global node, followed by bidirectional message passing between variables and constraints with specific masks based on duality.
The objective function
same variable are connected by an edge with a weight of 1.
In the connections involving the global node O, each node in Vauat corresponding to x, is split into two half-nodes, z/ and zy,, corresponding to - -vvf") ) and (y:);; in the dual problem, connected to O with edges weighted 1 and u², respectively. Each node in corresponding to 8; is split into of and sH, corresponding to -(ft); and (vā); ; in the dual problem, connected O with edges weighted t and uf respectively. Each node in Vprimal corresponding to xj is split into z; and 2;" representing (x ) and (æ+*), in the primal problem, connected to O with edges weighted ej and c,, respectively. Note that if any of the bounds 17. uy. 75, uf is co, we do not connect the corresponding edge since there is actually no corresponding variable in the simplified dual problem.
In Fig. ((a) a tripartite graph representation for general form LP problems is proposed. Each variable in the primal problem corresponds to two nodes in the graph, representing the variable and its upper and lower bounds, forming the node sets Vprimal and Vaual, respectively. Each constraint in the primal problem corresponds to one node in the graph, forming the set C. Additionally, there is global node O. All nodes can be divided into three parts: O, Vprimal, and Vavat U C, with edges connecting nodes between these sets no edges within each set, forming a tripartite graph.
Similar to the bipartite representation, edges between V Vprimal and C are constructed using the constraint matrix A. Each pair of nodes in V Yprimal and Va representing the

---

Learning LP Basis Selection via Duality-Inspiree Tripartite Graph Representation and Comprchensive Supervision
In this tripartite graph representation, the coefficients of the objective function and the bounds of variables and con- straints in the primal problem are embedded in the graph through edges connected to the global node. This represen- tation not only captures all information from the original LP problem but also from the dual problem. In the primal problem, Vprimot and Váuat U C represent variables and constraints (including variable bounds), respectively. In the dual problem, Vyrimal and Vduat U C' represent constraints and variables. The edges between these sets record the con- straint matrices of both the primal and dual problems. The edges between O and Vprimal reconstruct the objective func- tion of the primal problem and the equality constraints of the dual problem, while the edges between O and Vanot UC reconstruct all constraints of the primal problem and the objective function of the dual problem.
3.3. Loss function for basic variable selection
Different from traditional 3-class classification problems, for each variable or constraint, the category corresponding to the maximum probability output by the corresponding node prediction is not directly selected. Rather, it is en- sured that the number of nodes with predicted category I exactly equals m. In practice, firstly, m basic variables are determined. For the remaining n - m nodes, there is no constraint on the selection between categories 0 and 2. In
the process of selecting the m basic variables, if an actual non-basic variable is chosen, this prediction error will not only affect the current variable, but also result in an actual basic variable being predicted as non- basic variable. So the prediction of basic variables has a greater impact on overall accuracy than the prediction of non-basic variables.
Based on the prediction results, all nodes in Vprimal are divided into four disjoint sets: Vas, Von, Vin: and Vns. repre- senting nodes where the true category is I and the predicted category is 1, where the true category is 1 but the predicted category is not I, where the true category is not I and the predicted category is not 1, and where the true category is not 1 but the predicted category is 1. Similarly, all nodes in the C set are classified into four categories, forming Oso.
3.2. Message Passing on the Graph
We apply (Qasim et al.. 2019) to construct the GNN. We chose this architecture for three main reasons:
Comparative Consistency: This architecture is also used in the state-of-the-ar work by Fan et al., which our method builds upon. To ensure a fair and direct comparison, we adopted their GNN design as a baseline.
Cbn Cun. and Cnb-
Analytical Interpretability: We provide a detailed anal- ysis of the message passing behavior of this architecture in Appendix A.2. In particular, message passing to be proportional to the magnitude of the corresponding coefficients in the constraint matrix and the projection of changes in variables (or constraints) onto the respective rows (or columns). This behavior aligns well with the structure and nature of LP problems.
In accordance with the deviation between the prediction results and the labels, we aim for the nodes in Von and Con to increase the probability of being predicted as category I, thereby increasing the likelihood of being selected as a basic variable. Conversely, we want the nodes in Vns and Cns to decrease the probability of being predicted as category 1, making it less likely be chosen as a basic variable. Based on this, we design loss function component for basic variable selection.
aim for the amount of
Compared to recent models such as TransformerConv (Shi et al., 2020), our architecture is more lightweight and computationally efficient, making it well-suited for practical applications. Furthermore, as shown in Table 14 and discussed in Section A.5, GraphConv achieves slightly better average performance than Trans- formerConv in our experiments.
Computational Efficiency:
Lius
Σ ZEVi
IBCE
4mny
1
+ 4msc C
(BCE(P())[1).1)
(3)
+ 1(n mav)
(ncr(p(=)[11.0)
In the first step, nodes in Vprimal, Vanat and C aggregate information to O. Then, information is transmitted from the global node to the nodes in Vprimat, Vanat and C. With more informative node features, bidirectional message pass- ing between Vprimal and Vdwat U C is performed. Before each round of bidirectional message passing, masks are ap- plied to the half-nodes in Vaua! and C that correspond to infinite bounds in the primal problem, ensuring they do not participate in the process. The message passing process is illustrated in Fig. 1(b), with more details provided in A.2.
zEVee
1
+ 4(m mcc)
(ncr(p())(1)0))
where may and M&C represent the number of actual ba- sic variables in the variables and constraints, respectively, satisfying the condition myy + m&c = m.
3.4. Loss function for feasibility
The simplex method iterates between feasible bases to ap- proach the optimal solution. Besides obtaining the optimal basis, each vertex on the solving path corresponds to feasi-
5

---

Learning LP Basis Selection via Duality-Inspiree Tripartite Graph Representation and Comprchensive Supervision
ble basis. These bases sampled along the solution path can be used additional labels compute a new loss function term that increases the similarity between the predicted basis and these feasible bases, thereby enhancing its feasibility.
detailed analysis of this prediction problem and the labels provided by LP solvers is presented in A.3. Inconsistency in labels arising from the structure of the problem is com- monly found in practical LP problems. It stems from the fact that the representation of I.P problems is not compact enough and contains redundant information. It is worth noting that advanced solvers often preprocess LP problems by eliminating redundant information, leading to a more concise problem representation. This initial time investment typically results in significant time savings during the subse- quent solving process. Therefore, utilizing the LP problem obtained after presolving as the dataset not only enhances the learning efficacy of neural networks but also aligns with the standard solving process in practical applications.
Assuming the total number of iterations in the solver's solv- ing process for the current LP problem is T, a total of N feasible solutions are uniformly sampled between iteration [0T*] and T, where 0 E (0, 1) represents the threshold ratio of starting sampling points to the total number of it- erations. For convenience, evenly spaced iterations can be sampled back from the optimal solution to determine the sampling rounds needed. The step size can be set as AT = [(1 - ([19)T//N) / where the feasible bases obtained at the T- kAT iteration steps (A: E [N 1-1] -1) are sampled, con- verted into level k labels denoted as 3g-- The loss function incorporates these labels and is calculated
Label inconsistency also arises when the upper and lower bounds of variables constraints are equal. However, when the upper and lower bounds of constraints are equal, repre- senting an equality constraint, these constraints cannot be removed during presolve. Therefore, additional processing is required to address the label inconsistency corresponding to the constraints.
Emaltt Σ pal((P). (x, s). (31),,
(4)
where, P4 represents the weight of the loss calculated from different labels, which should decrease as k increases to ensure that fcasible bases closer to the optimal basis have greater impact on the loss.
Identifying all equality constraints based on the upper and lower bounds of constraints in the LP problem and excluding the ones that act as basic variables in the optimal basis result in a set of constraints needing preprocessing, denoted as Cpreprocess- Since these constraints have equal upper and lower bounds, solutions corresponding to taking the upper and lower bounds will be identical, leading to equivalent bases. To ensure label consistency, their labels are set to O.
By this loss, the network not only learns how to approximate the optimal basis but also learns the path through which the optimal basis is approached. The differences in prediction accuracy corresponding to different basis qualities can vary significantly. For instance, feasible basis located in the middle of the solving path may have around 50% difference from the final optimal basis, yet using it as an initial basis for warm start can reduce the number of iterations by half. However, an initial basis that is very close to the optimal basis might incur a significant cost in phase 1, potentially leading to a feasible basis that deviates far from the optimal basis. This can result in a sharp increase in computational complexity, leading to a total number of solver iterations exceeding the default mode. In the original loss function, the quality of the prediction results depends solely on the deviation from the optimal basis, without distinguishing between initial bases with the same deviation but different actual qualities. The new loss function term strengthens the labels values that appear multiple times in these labels by summing the weights, guiding the neural network to output the same prediction values. The repeated occurrence of label values signifies their stability along the solving path, implying that opting for these values in the initial basis can reduce infcasibility and facilitate the solver to go back to the solving path with fewer iterations in phase 1.
By labeling the equality constraints in this manner, the pos- sible label values for constraints with equal upper and lower bounds can only be O or 1. Consequently, before obtaining the probabilities of the three categories through softmax for the three-dimensional logits output by the neural network during inference, an additional knowledge-basse based mask can be incorporated according to the input as
Mask., = {
[0, 0, _o] if = of 00 otherwise.
Comprehensive supervised training process: With a loss function for basic variable selection, another for feasibility, and the label preprocessing, each of which is tailored to the prediction, warm start, and training tasks respectively, we can train the GNN models following the process in Fig. 2.
4. Experimental Results
4.1. Experimental Setup
LP Solver:
Access to commercial LP solvers like Gurobi (Gurobi Optimization, LLC, 2023) and CPLEX (Cplex, 2009) is often restricted in some cases e.g. for detailed hyperparamter setting etc. Therefore, in line with the peer
3.5. Data Preprocessing
To some extent, predicting the optimal basis in LP problems more challenging than predieting the optimal solution. A
6

---

Learning LP Basis Selection via Duality-Inspirge Tripartite Graph Representation and Comprehensive Supervision
LP solver
LP instance
5
B(T-N-- NI-f)
J... +
B
label preprocessing
predicted basis
logits
y (m
y1
Vo
labels
loss
Figure 2. Illustration of the comprehensive supervised training process: The LP instance encoded as tripartite graph and solved by the LP solver. Feasible bases are selected along the solving path to create preprocessed multiple labels. The 3-dimensional logits generated by the GNN, the predicted basis derived from the logits, and the multi-labels are collectively used calculate the loss function.
work (Fan et al., 2023), we utilize HiGHS (Huangfu Hall, 2018a), a state-of-ther -ortt--rtttt-ttte open-source solver specialized in efficient solving of LP problems. We employ the dual sim- plex method, it is typically much more efficient than the primal simplex method.
in (Fan et al., 2023), we split each dataset into training and test in 7:3 ratio. Additional details about the datasets are available in A.4.
There are few existing works for learning to select initial basis, except for (Fan et al., 2023) which is based on a bipartite graph-based GNN. This method has already demonstrated better performance com- pared to traditional heuristic-based methods many cases. In our experiments, we compare our tripartite graph-based GNN model with this state-of-the-an (SOTA) model. B, M, and P respectively represent the incorporation of the loss function for basic variable selection, the loss function for feasibility, and label preprocessing. For consistency in comparison, we adopt the training hyperparameters outlined in the SOTA method (Fan al., 2023) for all models. The value of μıx defined in Equation 16, is selected based on empirical experience rather than precise fine-tuning. Further details about the hyperparameters and GNN architectures can be found in Appendix A.5.
Compared Methods:
datasets: We utilize well-known publicly available MIP datasets in our study, including the Load Balance, Anony- mous, and Maritime Inventory Routing Problem (MIRP) (Papageorgiou al., 2014) (Jiang Grossmann, 2015). The Load Balance and Anonymous datasets are sourced from the NeurlPS 2021 Competition (Gasse et al., 2022). Due to its limited scale with solving iterations in the relaxed LP consistently below 1000, we exclude the Item Placement dataset from these competition datasets. We specifically choose the validation dataset of Load Balance due to the high similarity among its instances, eliminating the neces- sity for a larger training dataset. The MIRP datasets consist of three sets of instances labeled Mirpl (Pupageorgiou et al., 2014), Mirp2 (Papageorgiou et al., 2014), and Mirp3 (Jiang& & Grossmann, 2015). We opt for the first two sets as most of the instances the third set are significantly smaller in scale. We only utilize the Mirpl dataset from the most closely related ML method (Fan al., 2023), as it is the only one publicly available in that work.
The GNN models are trained on NV A100 GPU. The solver operates on a system equipped with 20-core CPU (Intel Xeon 2.90GHz) and 128GB of RAM. Our code publicly available'.
Implementation:
We relax these MIP problems obtain the original LP datasets. Additionally, we use HiGHS to presolve the re- laxed LP instances, as presolving is commonly applied be- fore solving in practical scenarios. Our datasets include both original unpresolved instances and the presolved ones. To filter out very small instances, we exclude those with fewer than 2000 solving iterations. Using the same method
4.2. Model Evaluation
We compare the bipartite graph- GNN model using de- fault training with our tripartite graph-based GNN model us- ing comprehensive supervision. Table and Table 2 present the test performance of both models on the unpresolved and

---

Learning LP Basis Selection via Duality-Inspiree Tripartite Graph Representation and Comprchensive Supervision
Table 1. Test performance of the GNN prediction model on the
Table 3. Number of iterations of the solver with/without warm start
unpresolved datasets.
using the predicted initial basis on the unpresolved datasets.
hijestite
VipunticMMP
defanat
bépuriite
tripuniteBMP
Precision
Recall
BasAce
Precision
Recall
Acc
BasAcs
Imserv
Ratio
Improv
Mirpl
0.915
0.902
0,931
0.915
0.939
0,937
Mirpl
25432
13711
53.91%
85.49%
10584
41.625
140 3%
Mirp?
0.788
0.791
0.812
0.649
0.782
0.786
0.876
0.639
Mira
86897
85691
98.61%
1.41%
S1010
93.23%
7.27%
Anniymaus
0.852
0.858
0.341
0,805
0.863
0.872
0.395
0.821
Anonymous
35330
21997
62.26%
60.619
20975
59.37%
68.44%
Load Balance
0.932
0.979
0,989
0.989
0.910
0,992
0.986
0.966
Load Rolance
7965
5046
63.35%
57.85%
3656
45.90%
117.9%
Goomeza
0,870
0,880
0.885
0,830
0,870
0.893
0.923
0,834
Geomean
28082
19003
67.67%
47.78%
16013
57.02%
75.37%
Table Test performance of the GNN prediction model on the presolved datascts.
Table 4. Solving time of the solver with/without warm start using the predicted initial basis on the unpresolved datascts.
bipurtile Recall
tipanthsBMP
default Timels)
bipurtile
HMparticcBMP
Precision
BasAce
Frecision
Recall
Acc
Basches
Time(s)
Impeov
Timels)
Ratio
Improv
Mirpi
0.909
0.894
0.910
0,923
0.928
0.935
0,930
Mapp
9.17
5.93
64.67%
54.68%
4.73
$1.58%
93.87%
Mirp2
0.810
0,812
0.876
0.690
0.812
0.814
0.883
0.695
Marp2
21,07
24.11
114.4%
-12611%
22.03
104.8%
-4.56%
Annyymous
0.859
0.848
0.872
0.801
0.857
0.859
0.593
0.794
Anonymous
12.83
9:31
72.50%
57.8156
72.41%
38.11%
Load Ralance
0.945
0.942
0.924
0.943
0.946
0.942
0.925
0.943
Balance
7.21
84.00%
18.20%
71.29%
40.27%
Geomeua
0
0.854
0,909
0,834
Geomean
11.56
9.49
82.09%
21.81%
8.40
72.66%
37.62%
Table 5. Number of iterations of the solver with/without warm start using the predicted initial basis on the presolved datasets.
presolved datasets respectively, showcasing test precision, recall, accuracy, and basic variable selection accuracy. It is evident that our model holds an advantage in predicting initial basis that is closer to the optimal solution.
default lioes
bepartite Ratio
tripartteBBMPP
Iiees
Imserw
Iters
Ratio
Improv
Mirpl
22160
13715
61.89%
61.57%
7118
32.125
2:1
Mirp
40091
36528
91.11%
9.758
34543
36. 16.6
16 16.06%%
Table 3 and 4 show the impact of the predicted initial basis on accelerating the solver on the unpresolved dataset, and Table 5 and show the one on the presolved dataset. The term "default" refers to the solver's default setting without warm start. "Iters" and "Time" represent the geometric mean of the number of iterations and solving time for each LP instance in the test set. "Ratio" denotes the ratio of the number of iterations using the predicted initial basis to that without warm start. "Improv" indicates the increase in speed compared to the default mode. Our model significantly reduces the number of iterations and solving time, achieving, on average, twofold speed improvement over SOTA on the unpresolved datasets and a threefold improvement on the presolved datasets. This demonstrates that our model not only provides an initial basis closer to the optimal one but also ensures its high quality for practical use by the solver.
Anonymous
9452
7651
80.95%
23.54%
7023
74.30%
70.18%
Balance
55.79%
4681
62.57%
34.59%
Geomean
15854
11664
73.57%
35.92%
9482
59.81
67.20%
Table 6. Solving time of the solver with/without warm start using the predicted initial basis on the presolved datasets.
defanl Timezs)
hipurtite Razio
IipartieMMP Rilio
Timels)
Impprv
Timota)
Lnproo
Mispl
7,32
5.22
73.31%
36.40%
2.99
41.99%
138.1%
Magz
7.91
95.3216
4.91%
82.93%
20.57%
Anozymous
0.985
124.9%
19,92%
118.8%
-15.81%
Load Balance
2.36
1.63
72.12%
38.65%
1.59
70.35%
42.15%
Geomeun
3.35
2.98
$3.95%
12.41%
2.46
73.43%
36.18%
Table 7. Performance on large LP instances.
Hirrs TripaniteRMP
Timofs)
Default
Default
TripritteBMP
RRR_DRO4_ PRR04_CCO_L111 V17bg3600
561299
409422
491.48
250.70
LRI DROS, VCO5. V25bb 1360
706451
777452
474,74
513.63
Our approach scales effectively to large LP instances. In the Mirp2 dataset, some instances take several minutes to several hours to process. As shown in Table 7, we demon- strate the acceleration achieved on these large instances. The computational overhead of our tripartite graph-based model with two bidirectional message-passing steps is com- parable to that of the bipartite graph-based model with six message- perssage-passing steps, typically taking less than 1 second. As shown in Table 12. increasing the number of message- passing layers in the bipartite graph- based model does not necessarily lead to better prediction quality. Our GNN archi- tecture effectively leverages its complexity, fully utilizing the computational overhead to predict a nigher-qualiy, ba- sis. In simpler LP cases, this added overhead may slightly increase the total solving time, including inference time.
VCO5
301789
309473
143.06
128.84
LRI FELDRRB.VVC 1C00.
267155
298875
112.76
131.60
83656
619425
751.76
606.93
Geomean
484672
448942
309.27
265.74
Ratio
0.926
0.859
However, for more complex or larger problems, the impact of this overhead becomes negligible.
4.3. Cross-dataset Evaluation
We use model trained on one presolved dataset to predict the initial basis for instances from another presolved dataset. The ratio of solver solving time with and without a warm start is shown in Table 8, where each row represents a train- ing set and each column represents a test set. Among the
8

---

Learning LP Basis Selection via Duality-Inspired Tripartite Graph Representation and Comprchensive Supervision
the solver, we introduce tripartite graph-based GNN and comprehensive supervision. Significant enhancements have been observed in reducing the number of iterations and solv- ing time of solvers by utilizing the initial basis generated by our model.
Table The ratio of solver solving time with and without warm start using the predicted initial basis acToss the presolved datasets.
Hymille Asreytaee
UiperkeBMP
MMpp
Mig!
Last TEGOEE
"Mirpl
Mirp.
Lead litoee
Mipp
0.865
1.35
01842
1.17
0351
Miep?
1:36
244
1/91
1.75
1.37
Assegitano
184
0.915
100
0.813
0,880
0.562
Lecd Bolinne
1.30
1L805
134
1.51
0.866
176
As learning for LP is still in its relatively early stage, in the future, we will investigate further factors beyond basis aceuracy and infeasibility that influence the solver's actual performance with a warm start. Additionally, we will ex- plore whether the tripartite graph representation remains effective for other LP- and MIP-related tasks.
1.3
Table 9. Solving time of the solver assisted by two GNN models with various training components on the presolved datasets.
scconds
MpPtticMMP
uipantieHMP
ALL
MM
8MP
ALL
B
-M
-P
BMP
Mirp!
4.71
4:95
4.99
5.27
5.32
2.99
3.96
3.23
2.43
4.27
Mirp?
6.79
7.60
7.63
7.38
7.54
6.56
8.34
6.36
7.21
7.68
Impact Statement
1.17
1.33
1.17
1.36
Balance
1.62
1.6
Geomein
2.55
2,2
3.13
2.98
2,0
2,42
2,401
2.93
Linear programming has been the central problem in com- puter science, Al and many other areas for science and engineering. Our technique could potentially accelerate and improve the accuracy of the solvers and thus could have significant impact to the society.
12 cross-dataset evaluations, only 3 cases tested on Mirp2 successfully accelerate the solver using the bipartite graph- based GNN. In contrast, our tripartite graph-based GNN, under comprehensive supervision, accelerates 6 out of the 12 settings. Additionally, our model consistently achieves better acceleration ratio than the SOTA across all test sets. This demonstrates that our model is more practical for real- world applications, where we need to use a trained model to predict the initial basis for instances from unseen datasets.
References
Achterberg, T., Koch, T., and Martin, A. Branching rules re- visited. Operations Research Letters, 33(1):42-54, 2005.
Berthold, T., Francobaldi, M., and Hendel, G. Learning to use local cuts. arXiv preprint arXiv:2206. 1618, 2022.
4.4. Ablation Study
Bixby, R. E. Implementing the simplex method: The initial basis. ORSA Journal on Computing. 4(3):267-284, 1992.
We remove each component from the training process for two GNN models on the presolved datasets to see their role in accelerating solving - see Table 9. We observe that each training component advantageous in improving perfor- mance for the bipartite graph-based GNN. Also, the tripar- tite GNN exhibits clear advantage in reducing the iteration count compared to the bipartite GNN with the same training settings. Moreover, the comprehensive supervision can lead to a more significant improvement in the performance of the tripartite graph- based GNN, showcasing its potential.
Chen, Z., Liu, J., Wang, X., Lu, J., and Yin, W. On repre- senting linear programs by graph neural networks. arXiv preprint arXiv:2209. 12288, 2022.
Chvátal, V. Linear programming. Macmillan, 1983.
Cplex, I. V12. User's manual for cplex. International Business Machines Corporation, 46(53):157, 2009.
Dantzig, G. B. Programming in a linear structure. Washing- ton, DC, 1948.
We observe that the tripartite model without the P com- ponent outperforms the version with P. primarily due significant gain on the Mirpl dataset. This suggests that while processing the labels to reduce inconsistency helps the GNN learn and achieve better accuracy, it may occa- sionally result in an initial basis that is closer to optimal but invalid, requiring additional Phase I effort to repair. How- ever, this appears to be an isolated case, as incorporating P consistently improves performance on all other datasets.
Dantzig, G. B. and Orchard-Hays, W. The product form for the inverse in the simplex method. Mathematical Tables and Other Aids to Computation, pp. 64-67, 1954. doi: 10. 0l.1000//002--5/0
1954-00614694
Ding, J.-Y., Zhang, C., Shen, L., Li, S., Wang, B., Xu, Y.. and Song, L. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the aaai conference on artificial intelli- gence, volume 34, pp. 1452-1459, 2020.
5. Conclusion and Outlook
Based on the analysis of duality in LP, the crucial role of basic variable selection, the quality of the basis in practi- cal tasks, and the inconsistency in raw labels provided by
Fan, Z., Wang. X., Yakovenko, O.,, Sivas, A. A., Ren, O., Zhang, Y., and Zhou, Z. Smart initial basis selection for linear programs. In Krause, A., Brunskill, E., Cho,

---

Learning LP Basis Selection via Duspity-Inspired Tripartite Graph Representation and Comprehensive Supervision
K., Engelhardd, B., Sabato, S., and Searlett, J. (eds.), Proceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9650-96600 9664. PMLR, 23-29 Jul 2023.
Huangfu, Q. and Hall, J. Parallelizing the dual revised simplex method. Mathematical Programming Computa- tion, 10(1):119-44 2018a.
Huangfu, Q. and Hall, J. J. Parallelizing the dual re- vised simplex method. Mathematical Programming Computation, 10(1):119-142, 19-142, 2018b. doi: 10.1007/ s12532-017-0130-5.
Forrest, J. Clp: Coin-or linear program solver. In DIMACS Workshop on COIN-OR, pp. 17-20, 2006.
Forrest, J. J. and Goldfarb, D. Steepest-edge simplex algo- rithms for linear programming. Mathematical program- ming, 37(1-3):341-374 1992.
Jiang, Y. and Grossmann, E. Alternative mixed-integer linear programming models of maritime inventory rout- ing problem. Computers Chemical Engineering, 77: 147-161, 2015. ISSN 0098-1354, doi: https://doi.org/10 101 1016/..compchemeng 2015 2015.03..... 5.03.005.
Forrest, J. J. and Tomlin, J. A. Updated triangular factors of the basis to maintain sparsity in the product form sim- plex method. Mathematical programming, 2(1):263-278, 1972.
Khalil, E.,, Dai, H., Zhang, Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing sys- tems, 30, 2017.
Galabova, I. L. and Hall, J. The 'idiot' crash quadratic penalty algorithm for linear programming and its ap- plication to lincarizations of quadratic assignment prob- lems. Optimization Methods and Software, 35(3):488- 501, 2020. doi: 10.1080/105567888.0000 1604702.
Khalil, E. B., Morris, C., and Lodi, A. Mip-gnn: A data- driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 36, pp. 10219-10227, 2022.
Gasse, M., Chételat, D., Ferroni, N., Charlin, L.,, and Lodi, A. Exact combinatorial optimization with graph convolu- tional neural networks. Advances in neural information processing systems, 32, 2019a.
Lemke, C. E. The dual method of solving the linear pro- gramming problem. Naval Research Logistics Quarterly, 1(1):36 47, 1954.
Gasse, M., Chételat, D., Ferroni, N., Charlin, L., and Lodi, A. Exact combinatorial optimization with graph convolu- tional neural networks. Advances neural information processing systems, 32, 2019b.
Li, X., Qu, Q., Zhu, F., Zeng, J., Yuan, M., Mao, K., and Wang, J. Learning to reformulate for linear programming. arXiv preprint arXivv2201.000 (6216,220 2022.
Liu, C., Dong, Z., Ma, H., Luo, W., Li, X., Pang. B., Zeng, J., and Yan, J. 1.2p-mip: I Learning to presolve for mixed integer programming. The Twelfth International Con- ference on Learning Representations.
Gasse, M., Bowly, S., Cappart, Q., Charfreitag, J., Charlin, L., Chételat, D., Chmiela, A., Dumouchelle, J., Gleixner, A., Kazachkov, A. M., et al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurlPS 2021 competitions and demon- strations track, pp. 220-231. PMIR, 2022.
Nair, V., Bartunov, S., Gimeno, F., Von Glehn, I., Li- chocki, P., Lobov, I., O' O'Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., et al. Solving mixed in- teger programs using neural networks. arXiv preprint arXhv:2012.13345 2020.
Gearhart, J. L., Adair, K. L.,, Durfee, J. D., Jones, K. A., Martin, N., and Detry, R. J. Comparison of open-source linear programming solvers. Technical report, Sandia Na- tional (SNL-NN, Albuquerque, NM (United States), 2013.
Papageorgiou, D. J., Nemhauser, G. L., Sokol, J., Cheon, M.-S., and Keha, A. B. Mirplib a library of maritime inventory routing problem instances: Survey, core model, and henchmark results. European Journal of Operational Research, 235(2):350-366, 2014. ISSN 0377-2217. doi: https://doi.oo 111.0..000........0011111. 12.013. Maritime Lo- gistics.
Gupta, P., Gasse, M., Khalil, E., Mudigonda, P., Lodi, A., and Bengio. Y. Hybrid models for learning branch. Advances in neural information processing systems, 33: 18087-18097, 2020.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
Paulus, M. B., Zarpellon, G., Krause, A., Charlin, L., and Maddison, C. Learning to cut by looking ahead: Cut- ting plane selection via imitation learning. In Interna- tional conference on machine learning, pp. 17584-17600, PMLR, 2022.
Harris, P. M. Pivot selection methods of the devex Ip code. Mathematical programming, 5:1-28, 1973.
10

---

Learning LP Basis Selection via Duslity-Inspired Tripartite Graph Representation and Comprehensive Supervision
Ping-Qi, P. Linear programming computation. Springer, 2014.
Qasim, R., Kieseler, J., liyama, Y., and Pierini, M. Learn- ing representations irregular particle-detector geometry with distance-weiggter graph networks. The European Physical Journal C, 79(7):1-11) 2019.
Qian, C., Chételat, D., and Morris, C. Exploring the power of graph neural networks solving linear optimization problems. In International Conference on Artificial Intel- ligence and Statistics, pp. 1432-1440. PMLR, 2024.
Ryan, D. M. and Osborne, M. R. On the solution of highly degenerate linear programmes. Mathematical program- ming, 1:385-392, 1988.
Shi, Y., Huang, Z., Feng. S., Zhong, H., Wang, W., and Sun, Y. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.00 200,00009,3,9, 2020.
Suhl, U. H. and Suhl, L. M. Computing sparse lu factor- izations for large-scale linear programming bases. ORSA Journal on Computing, 2(4):325-335, 1990.
Wang, J., Geng, Z., Li, X., Hao, J., Zhang, Y., and Wu, F. G2milp: Learning to generate mixed-integer linear pro- gramming instances for milp solvers. Authorea Preprints, 2023a.
Wang, 7., Li, X., Wang, J., Kuang, Y., Yuan, M., Zeng, J., Zhang, Y., and Wu, F. Learning cut selection for mixed- integer linear programming via hierarchical sequence model. arXiv preprint arXiv:2302.00244: 2023b.
Wu, D. and Lisser, A. A deep learning approach for solving linear programming problems. Neurocomputing, 520: 15-24, 2023.
Zhang. J., Liu, C., Li, X., Zhen, H.-L., Yuan, M., Li, Y., and Yan, J. A survey for solving mixed integer programming via machine learning. Neurocomputing, 519:205-217, 2023.

---

Learning LP Basis Selection via Duality-Inspire Tripartite Graph Representation and Comprehensive Supervision
A. Appendix / supplemental material
A.1. Duality in linear programming
For the general form of a Linear Programming (LP) problem:
c cx x min ZER"
(5)
s.t. 1' v Ax uu, 1' s
(6)
(7)
assign dual variable y to each constraint (splitting bidirectional constraints into two), Lagrange multipliers, and formulate the Lagrangian function as:
L(x, ul v Ve. v.. = c x - (Ax
(Ma) (u* Ax) (vf) (ar 13) (v.) (u" -))
(Ax - 17)
(8)
x (c T yi + A yu - yf + y")
+ +1') vř (u") ya + (1") yī (u') y":
(9)
From 8, in combination with 6 and 7, for any feasible solution fea and any vi y vi: v > 0, we have:
min L(x, vi Va Vi v.) S L(x fear Vi Vo Vi vo)) < c x fea- ZER
(10)
Let g(yl, va, yi' v.) min
Max, yi Va of v and taking limits of on the left hand side yields:
max 2ी vt. of WE glyi yie yi yw) S c. x fea-
(11)
According to the strong duality theorem, the original problem has finite optimal solution x", then
max y W2 MJ Vt 20
glyi Vuo 9e, yd c T."
(12)
Hence, we can transform the original problem into finding the maximum value of the function g. From 9, get:
glvi vu vi, va)) = (L") yी (u*)T yı (1=)Tyy yी (u") y.
S ==0, 0,
(13)
-0,
otherwise.
where 5 c- A yी A yu yi y. Therefore, the problem of finding the maximum value of the function g can be expressed as:
max Mt. ML. NE 20
(1') yi (u²) V + (1²) vp (u²) va
(14)
s.t. A (vi vnr + (ve - vnl =
(15)
A.2. Message passing on the tripartite graph
Let the initial feature vectors for each node in Vprimal, Vauat and C be h (0) gerimat gout and h respectively, with the
h (0)
(0)
feature vector the global node being h (0) At the beginning, each initial feature is mapped to a higher dimension
ho Wo
(1)
h
(0)
h (I) primat
(0) W o2hh premai;
(1) gifutt
(0)
W Y deets
h (1)
Woth (0)
12

---

Learning LP Basis Selection via Duality-Inspiree Tripartite Graph Representation and Comprehensive Supervision
Then nodes in Vprimels Vauaal and C. "aggregate information O
h = (WWnn (1) +
W2 Σ
I( (--g) C- M
Sh an cepiimal + Cyh (1)r 25 agrimot
(a)
JE[m]
W13 13 Σ (- JE/m]
(1) anfual
Gh nduut + W14
ON El(-ph +ugh (.))
sE(m]
where the feature vectors of each node in V Vprimals Vdwal and C' are split into two halves, with the superscripts and r indicating the first and second halves of the vectors, respectively. The first half passes information through the lower bounds in the primal or dual problem, while the second half passes through the upper bounds. The activation function o, typically a ReLUO function, zeros out negative elements, increasing matrix sparsity. The nodes in those three sets transform and aggregate information using three different learnable matrices W12, W 13 and W to enhance the global differentiation of information from different components. For each node, the magnitude of information passed to the global node is proportional to its coefficient in the objective function of the primal or dual problem, reflecting the variable's 's global impact.
Next, information is transmitted from the global node to the nodes in Vprimal, Vaual and C,
h (2) primal (CONCAT(W 15
(I Cg
W Vich o W
(2)
1shh Wish (1)r my primai + eg W 1ohh
3 Primal
h (2)
dual (CONCATT(W
(I)
W11h 18 O
(2)
W W17h (r) adual + W os
aduat
h (2) (CCONCAT(W 19
(I) W (2) W Wigh + Winh 1))
where CONCAT represents the vector concatenation fuunciion, concatenating feature vectors along the last dimension. Different transformation matrices for the three types of nodes convert the global node's 's information, ensuring that the information absorbed by each node is proportional to its coefficient in the objective function of the primal or dual problem.
The left half of Fig. is completed at this point. Each node now contains not only its own original information but selectively extracts information from all other nodes in the graph. With more informative node features in hand, bidirectional message passing similar to that in the bipartite graph is carried out.
Before each round of bidirectional message passing, masks are placed on some nodes in Vdual and C to remove certain information. For any variable Ty. if 1/ -o, then the first half of the feature vector h (t-1)
anfant from the previous layer (denoted as the (t- 1)th layer) of the neural network output is zeroed out, Conversely, if uzf co, then the second half of the feature vector l (1-2a)" is set to zero. Similarly, for any constraint variable s,, if 13 -oo, then the first half of the s.
feature vector (t-1) from the previous layer of the neural network output is zeroed out, Conversely, if u = oc, then the (t-1)r set to zero. Since the infinite constraints in the original problem indicate the
second half of the feature vector h s; absence of these constraints, and these infinite constraints do not actually correspond to variables in dual problems, they need to be masked to ensure they do not participate in any message passing. In the previous global message passing step, these nodes do not have edges connecting them to global nodes and do not participate in message passing. However, in bidirectional message passing, as they are bound together with the other constraints through coefficients in the constraint matrix and connected to other nodes, the masks are used to eliminate their influence on message passing. Denote the feature vectors of the nodes in sets Vawat and C' in the 1th layer output as h (t-1)" and (t-1) after applying the masks. The process of bidirectional message passing can be represented as
h 2 Pini = o W h (1-1) 2 aprimat
(W
+ W h (1-1) aduel
Wight
+ Wes is
Σ xE(m)
ats aish! (1-1)))))
h (1) dual o W 11
Wigh agual
(t-1)
W Wigh (1-1)
h (t) o (Wi,, io t (t-1)'
We, Σ aig (optmna)) )
jE(n)
where different learnable transformation matrices W., and Wr, are used to aggregate information from Vanal and C nodes in the Vprimal set, respectively, and nodes in Vaual and C receive information from Vprimal through different matrices, W ts and W. for respectively.
13

---

Learning LP Basis Selection via Duslity-Inspired Tripartite Graph Representation and Comprehensive Supervision
In practice, it is often preferred to conduct rounds of bidirectional information exchange after the global information transmission, resulting in (1) h (1)
pprimais and [ Among these, the nodes in Vdual do not contribute to the final output. The features of all nodes in Vprimals denoted by h (1) pprimmas are processed through a linear layer to map them to a three-dimensional space, providing the logits for each variable. Similarly, the features obtained from C' nodes, after masking, are passed through another linear layer transform them into a three-dimensional space, yielding the logits for each constraint.
The rationale behind opting for two rounds of bidirectional information exchange is that this allows for the aggregation of a significant portion of the information implied by the constraint matrix. The masking and activation functions essentially sparsify the information within the matrix, and we disregard the sparse effects induced by the masking and activation
functions in our analysis. Taking h (4)
pprimul as an example, it can be represented as function of h (2) h (2)
eduuts and h as
gprimals
h (4) peimal
Wa, h (3)
of primal + W h
(3)
W43
Biy h (3)
<c(m]
A,, (Wa, h
h
aiş aigke!! (2))
primal
rE(m)
WA (Wa 3, h (2)
W 3, h )primat)
(2)
44s 4g
Ozyl 30 h + W3 37
Σ
0ikh (2)
of prima!
rE[m]
kE/n]
(Wa, 4, WA, 3, + W 4g W 3:
primal + (W 4, W 32 + Wa, W W3,)h
)h
(Wa, 4, W + W 4g W 36)
aig highe (2)
iE(m)
W. 3,
Σ KE(m] KE(M)
aijaihh primal
Following this analysis, we observe that the feature of node xj in V primol consists of message from the node in V dual corresponding to its upper and lower bounds, the nodes in C' corresponding constraints it lies in, and some other variable nodes in V primall The message passed from constraint node in C' is proportional to the coefficients d.j corresponding to the variable in the respective constraint, and is positively correlated to any change ō in the constraint that influences the total value of the variable, azyō, in the dual problem. Moreover, the message passed from a variable node Ug in V pprimat is associated with Σi [m) Exe(o] asy Usk, reflecting the inner product between the column vectors corresponding to variables T and Ug in the constraint matrix, which is proportional the fluctuation in the projection of the change 8 in the variable Upe on A. which is (.A.,.A.)) A.,.. Analogously, similar effects of information transfer can be identified for h+()) from a dual perspective. Consequently, this dual bidirectional information exchange on the bipartite graph effectively consolidates the interactive information between constraints and variables inherent in the LP problem, exhibiting interpretability to a certain extent. Furthermore, some high-order interaction information is captured through the initial global message passing.
A.3. Analysis on the labels given by LP solvers
For example, consider a simple LP problem as follows:
min - - - 4/2
s.t. 0 05 31 + x2 5
0521,00 21, 2
This problem involves two variables 21 and T2 and one constraint $1. The optimal solution with the 2-norm minimum is 4n = 0.5, .22 = 0.5 with = 1. The optimal solution obtained through the simplex method could be . = 1, x22 = 0, = 1 or 21 = 0, x2 = s1 = 1. It can be observed that the values of and 22 are always unequal. Due to the equivalence of æ1 and 222 in the original problem, no matter how the neural network is constructed, the output for nodes corresponding to x and Z2 will be the same. Therefore, even for such a simple LP problem, the regression problem of predicting the optimal solution with the simplex method cannot achieve close to 100% accuracy. Additionally, in any case, 81 serves as a non-basic
14

---

Learning LP Basis Selection via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision
variable the upper bound, while either 4i or 2e serves as basic variable and the other as non-basis variable at the lower bound. Hence, the labels for 21 and 22 in the basis prediction classification problem will never be the same, leading to least one variable's prediction being incorrect, resulting in maximum prediction accuracy of 50% for the basic variables.
This inconsistency in labels arising from the structure of the problem is commonly found in practical LP problems. It stems from the fact that the representation of LP problems is not compact enough and contains redundant information. For instance, 4i and 22 are completely equivalent in the example above and could be combined into a single variable to eliminate the label inconsistency mentioned before. It is noted that advanced solvers often preprocess LP problems by removing redundant information to obtain a more concise problem representation. The runtime for LP problem presolving is usually very short and negligible compared to actual solving time. By inputting the equivalent problem obtained after presolving into the solver, significant computational cost savings can be achieved compared to solving the original problem directly. Consequently, there is limited practical significance in directly using the original problem for basis prediction, as it does not take into account the presolving process. Moreover, as shown in the analysis above, presolving can aid in basis prediction by reducing label inconsistency. improving model fitting, and enhancing basis prediction accuracy. Therefore, utilizing the LP problem obtained after presolving as the dataset not only enhances the learning efficacy of neural networks but also aligns with the standard solving process in practical applications.
Apart from the label inconsistency stemming from the problem structure itself, there can also be label inconsistencies in the optimal basis labels output by the solver. Adding a constraint and variable to the previous LP problem yields another LP problem without redundant information as follows:
min
21 22 33
s.t.
T1 + 422 =
22 + x3 =
0 < T2, 2,
This problem involves three variables æ1, 22, 43 and two constraints 81, 82. The optimal solution with the 2-norm minimum is I2 = 1, = 0, 23 with $1 = 1, = 1, which is also the optimal solution obtained by the simplex method. The prediction values of neural networks can approximate the solution obtained by the simplex method with nearly 100% accuracy. However, this optimal solution corresponds to multiple optimal bases. One possible labeling scheme includes Labelz, = 1, Label = 0, Labelz, 1, Label,, = 0, Label,, 2, indicating that x1 and 33 are basic variables, 22 is a non-basic variable set to the lower bound 0, and 8 and s2 correspond to the lower bound 1 in one constraint and upper bound 1 in the other. In this labeling, the labels of the two constraints $1 and 82 are different, yet in the LP problem, 21 and 23 are completely symmetrical and so are the two constraints and 82, implying that the nodes in the graph representation are equivalent, leading to the neural network outputting the same values for them, at least one of which is different from their labels. Therefore, in this scenario. the prediction accuracy of the constraint basis variables can reach a maximum of only 50%, even though the prediction accuracy for the optimal solution can be 100%.
The mentioned label inconsistency primarily arises when the upper and lower bounds of variables or constraints are equal. When the upper and lower bounds of variables are equal, indicating a fixed value for the variable, it can be eliminated through presolving. However, when the upper and lower bounds of constraints are equal, representing equality constraint, these constraints cannot be removed during presolving. Therefore, additional processing is required to address the label inconsistency corresponding to the constraints.
A.4. Datasets
Table 10 and 11 present statistical information for four datasets before and after presolve. 'nMIP' denotes the number of original MIP instances, while 'nLP' represents the number of remaining presolved LP instances, which constitute our final datasets. "nTrain",, and 'nTest' denote the number of LP instances in the training set and in the test set, respectively. 'dens", 'nvar', and 'ncons' refer to the density of constraint matrices, the number of variables, and the number of constraints. They are presented in the 'mean standard deviation' format.
A.5. Model Setup
We employ the Adam optimizer with a weight decay of x 10 10-4, rate is configured to 0.001, and the learning rate is reduced by a factor of 7 = 0.1 every 200 epochs. Random seed is set to O.
4, The number of training epochs is 800. The initial learning
15

---

Learning LP Basis Selection via Duality- Tripartite Graph Representation and Comprehensive Supervision
Table 10. Statistics of the unpresolved datasets.
nMIP
nLP
nTrain
TTsst
dens
nvar
Mirpl
28
28
19
2.0c-4::1.044
28738 :24508
28214
Mirp2
68
68
47
21
5. 4.60-4444444
33461 #:9425
10589 11366
Anonymous
118
76
53
23
4.30-411400-4
50891 1:7900
64396
Load Balancing
100
100
70
30
9.2e-5+114
61000=
64305
Table 11. Statistics of the presolved datasets.
nMIP
nLP
nTrain
n'Test
dens
nvar
ncons
Mirp1
28
28
19
2. 2.6
26043
24028
Mirp2
68
62
43
19
6.9c-415.1e4
2035 1:1293
7126
Anonymous
118
76
53
23
1.5e-3
7720=4406
5670#2447
Load Balancing
100
100
70
30
6.7e-3234e5
4014
71364119
The initial features of variable and constraint nodes in the graph are identical to those in the study (Fan et al., 2023), represented as 8-dimensional vectors. The additional global node features in the tripartite graph are composed of the mean and variance of the coefficients of normalized LP problem's objective function, variable bounds, and constraint bounds, forming 6-dimensional vector. The feature vectors of all nodes in the hidden layers have dimensionality of 256.
Our tripartitebased GNN model involves one linear layer that projects the initial features into 18-dimensional embeddings, one global message passing iteration between the global node and other nodes, two bidirectional message passing iterations among the remaining nodes, and a final linear layer. In particular, when applying label preprocessing, we choose = 0.9 and N = 10 to collect the feasible bases the solving path, obtaining multi-level labels. The weight μ2 for the k-th level label set as
0.5 0.25 x 0.75
k 2 3
< 0
(16)
k-2
ASS 9.
the other hand, the bipartite-based GNN model (Fan et al., 2023) comprises N bidirectional message passing iterations between variable nodes and constraint nodes and final linear layer. The default setting for N 2, and we also experiment with models using N N 6, and N 8. As shown in Table 12, for both models utilizing the training process from (Fan et al., 2023), labeled 'bipartite,, and our proposed training process, labeled as 'bipartiteBMPP' adding more layers results in little overall improvement. Therefore, using the tripartite graph-based representation, increasing the number of layers does not enhance the learning ability. For this reason, we choose N = 2 as the setting for the comparison in the experiments section.
We also conduct experiments studying the influence of the number of bidirectional layers on the final solver speedup on three of the unpresolved datasets. better study the graph representation itself, we isolate the influence of training settings by using the base training without loss function for basic variable selection, the loss function for feasibility, and label preprocessing. As shown in Table 13, bidirectional message passing is crucial, as it effectively utilizes the coefficients in the constraint matrix. Additionally, adding more bidirectional message passing layers results in slight improvement.
We compare bipartite GNN and tripartite GNN using TransformerConv architectures, as well as tripartite GNN using GraphConv, on three of the unpresolved datasets. As shown in Table 14, our tripartite representation demonstrates a modest advantage over the bipartite baseline. Additionally, we observe that GraphConv generally outperforms TransformerCons further supporting our claim that the GraphConv architecture aligns well with the structure LP problems and is sufficiently expressive to capture the necessary properties.
16

---

Learning LP Basis Selection via Duality- Inspired Tripartite Graph Representation and Comprehensive Supervision
Table 12, Iteration counts across bipartite GNNs with different number of bidirectional message passing layers
bipartite
bipartiteBMP
N=2
N=4
N=
N=8
N=2
N=4
N=6
N=8
Mirpl
13715
12085
13272
15817
10259
12167
9949
10618
Mirp2
36528
36449
38757
39676
32302
33979
35803
35400
Anonymous
7651
9381
7717
8226
6891
7990
7728
7131
Load Balancing
4829
4624
4645
3956
4754
4602
4457
3737
Geomean
11664
11757
11653
11954
10207
11103
10525
10004
Table 13. Iteration counts and solving time across tripartite GNNs with different number of bidirectional message passing layers
Iters
Time(s)
N=0
N=2
N=4
N=6
N=0
N=2
N=4
N=6
Mirp
18798
14017
12109
10813
8.29
7.43
7.07
6.39
Anonymous
60146
23583
23166
21342
7.19
7.12
6.75
6.87
Load balancing
4070
4357
4291
4512
16.71
10.49
10.98
8.85
Geomean
16633
11293
10637
10136
9.99
8.22
8.06
7.30
Table 14. Comparison of iteration counts across different GNN architectures
Bipartite-Transfomnn TransformerCoov
Tripartite-rran TransformerCoon
Tripartite Tripariie-GraphConm GraphConv
Iters
Time(s)
Iters
Time(s)
Iters
Time(s)
Mirp
16022
7.24
16146
6.96
14017
6.04
Anonymous
4561
9.87
4804
9.75
4357
5.74
Load balancing
23946
6.37
21124
6.44
23583
10.61
Geomean
12051
7.69
11790
7.59
11294
7.17
17


Reviews:
[{"review_id": "FTPGg9TKEe", "reviewer": "Reviewer_KgT2", "summary": "The paper proposes  a new Graph Neural Network model for predicting the initial basis in the simplex method for solving linear programming (LP) problems. They use a tripartite graph that includes a global node and also nodes for dual variables, in addition to nodes for constraints and primal variables in a bipartite graph from previous work. Also, a new loss function is introduced to improve basic variable selection and basis feasibility. The proposed model significantly outperforms the state-of-the-art method in terms of prediction accuracy, reducing the number of iterations and solving time required by the LP solver. Effectiveness of each design component is evaluated through ablations study.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### 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.\n\n> Thanks for your suggestion! We will incorporate these non-ML methods as baselines in our paper.\n\n### 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?\n\n> 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.\n\n> In contrast, the MILP benchmarks contain rich instances that can be divided into training and testing ones.\n\n\n### 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).\n\n> 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:\n>\n| instances               | iter_default | iter_tripartiteBMP | time_default | time_tripartiteBMP |\n| ----------------------- | ------------ | ------------------ | ------------ | ------------------ |\n| LR1_DR04_VC05_V17b_t360 | 561299       | 409428             | 491.48       | 250.7              |\n| LR1_DR05_VC05_V25b_t360 | 706451       | 777452             | 474.74       | 513.63              |\n| LR1_DR08_VC05_V40b_t180 | 301789       | 309473             | 143.06       | 128.84              |\n| LR1_DR08_VC10_V40b_t120 | 267155       | 298875             | 112.76       | 131.6              |\n| LR1_DR12_VC10_V70a_t180 | 836561       | 619425             | 751.76       | 606.93              |\n| geomean | 484672       | 448942             | 309.27       | 265.74              |\n> 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.\n\n### A writing issues: There should be a space between words and citations. Some of them are missing.\n\n> Thanks and we have polished the paper.\n\n### In ablation study, why is tripartite without P (label preprocessing) the best? Are the improvements statistically significant?\n\n> 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.", "claims_and_evidence": "The paper presents experimental results on several standard LP datasets (Load Balancing, Anonymous, MIRP relaxed from MILP instances) to support their claims. They compare their model against the existing SOTA (bipartite GNNs) and the default solver setting. The tables and figures show improvements in prediction accuracy and solver performance metrics (iterations and time). They also include an ablation study to demonstrate the effectiveness of each component of their proposed method.\n\nA few aspects could be improved:\n\n* 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.\n* 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?", "methods_and_evaluation_criteria": "See above comments about benchmarks and other baselines.\n\nIn 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.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "The experiments are well-designed to demonstrated the effectiveness through prediction accuracies,  runtime and numbers of iterations. \nHowever, at this point, it is unclear how effective the method is for larger/harder instances (e.g, instances that takes 5 minute or even more to solve).", "relation_to_broader_scientific_literature": "The paper studies an important problem related to linear optimization.", "essential_references_not_discussed": "Not that i'm aware of.", "other_strengths_and_weaknesses": "No other strengths or weaknesses i want to point out.", "other_comments_or_suggestions": "A writing issues: There should be a space between words and citations. Some of them are missing.", "questions_for_authors": "In ablation study, why is tripartite without P (label preprocessing) the best? \nAre the improvements statistically significant?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m7Yu1RGBxO", "reviewer": "Reviewer_BL5r", "summary": "This paper proposes a GNN-based approach for learning initial basis selection in LP, aiming to accelerate the simplex method. Inspired by LP duality, the authors introduce a tripartite graph representation to better capture problem structure. Additionally, they design new loss functions to improve basic variable selection and basis feasibility, along with data preprocessing schemes to reduce label inconsistencies.\n\n## Update after rebuttal\n\nI thank the authors for their thoughtful and detailed rebuttal. The clarifications regarding the distinction between basis accuracy and solver acceleration were particularly helpful and addressed my earlier confusion about the paper’s core claims.\n\nI also appreciate the additional experiments and analysis related to the tripartite graph representation and the choice of GNN architecture. The authors not only provided ablation studies with varying message passing depths but also included comparisons with Graph Transformer architectures. Their justification for using the GraphConv-based model — highlighting interpretability, computational efficiency, and consistency with related work — is convincing and well-supported by the new results.\n\nGiven these clarifications and improvements, I believe the authors have sufficiently addressed my concerns. I have therefore increased my score to a positive recommendation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### 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.\n### 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.\n### Clarifying these statements would improve the paper’s logical consistency and ensure a clearer understanding of the contributions.\n\n> 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.\n> \n> 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.\n> \n> 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.\n\n\n### The tripartite graph should be tested against multiple GNN architectures (not just one) to demonstrate its effectiveness across different models.\n### The impact of the tripartite representation should be better isolated from other factors (e.g., loss functions, preprocessing).\n\n> 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:\n\n> Iteration number:\n> \n| datasets       | n=0   | n=2   | n=4   | n=6   | default |\n| -------------- | ----- | ----- | ----- | ----- | ---- |\n| Mirp           | 18798 | 14017 | 12109 | 10813 | 25432 |\n| Anonymous      | 60146 | 23583 | 23166 | 21342 | 35330 |\n| Load_balancing | 4070  | 4357  | 4291  | 4512  | 7965 |\n| geomean        | 16633 | 11293 | 10637 | 10136 | 19271 |\n\n> Solving time in seconds:\n> \n| datasets       | n=0   | n=2   | n=4   | n=6   | default |\n| -------------- | ----- | ----- | ----- | ----- | ---- |\n| Mirp           | 8.29 | 7.43 | 7.07 | 6.39 | 11.17 |\n| Anonymous      | 7.19 | 7.12 | 6.75 | 6.87 | 9.08 |\n| Load_balancing | 16.71  | 10.49  | 10.98  | 8.85  | 7965 |\n| geomean        | 9.99 | 8.22 | 8.06 | 7.30 | 11.39 |\n\n> 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.\n\n### 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.\n\n> Thanks for your suggestions. We will add more literature on warm-starting techniques and update the revision.", "claims_and_evidence": "While the paper presents an interesting method, the writing is sometimes contradictory, leading to confusion about the claims:\n\n- 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.\n- 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.\n- Clarifying these statements would improve the paper’s logical consistency and ensure a clearer understanding of the contributions.", "methods_and_evaluation_criteria": "The paper proposes a tripartite graph representation to replace the standard bipartite graph representation used in LP-based GNN models. This is a reasonable design choice, but the experimental validation is limited:\n- The tripartite graph should be tested against multiple GNN architectures (not just one) to demonstrate its effectiveness across different models.\n- The impact of the tripartite representation should be better isolated from other factors (e.g., loss functions, preprocessing).", "theoretical_claims": "The theoretical motivation for the tripartite representation is reasonable, as it leverages LP duality.", "experimental_designs_or_analyses": "The experiments primarily compare the tripartite GNN to a single bipartite GNN model. To strengthen the evaluation:\n\n- More GNN architectures should be tested to confirm the robustness of the tripartite representation.\n- The impact of each proposed modification (graph representation, loss functions, preprocessing) should be evaluated separately to better understand their individual contributions.", "relation_to_broader_scientific_literature": "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.", "essential_references_not_discussed": "No major missing references, but the paper could compare its approach to other LP warm-starting methods that do not use GNNs.", "other_strengths_and_weaknesses": "Strengths\n- The tripartite graph representation is a novel adaptation based on LP duality.\n- The method shows strong experimental improvements over the SOTA bipartite GNN model.\n- The data preprocessing steps help address label inconsistencies in LP solvers.\n\nWeaknesses\n- Potential desk rejection risk: The paper omits required formatting elements (e.g., line numbers, \"Anonymous Authors\"), which could lead to desk rejection.\n- Logical inconsistencies: The discussion on closeness of the initial basis vs. solver acceleration is contradictory.\n- Limited experimental diversity: The tripartite graph representation should be tested on multiple GNN architectures to confirm its general effectiveness.", "other_comments_or_suggestions": "None", "questions_for_authors": "See Weaknesses. I find the proposed method interesting and promising, but the writing inconsistencies, formatting errors, and limited experimental validation raise concerns. I am assigning a borderline score for now but am open to raising my score if the authors provide strong clarifications and additional experiments in their response.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JHcqj6ASZ2", "reviewer": "Reviewer_RwiH", "summary": "The paper proposes a novel approach for selecting an initial basis for linear programming (LP) solvers using a duality-inspired tripartite graph neural network (GNN). \nThe following are the three main contributions:\n- A tripartite graph representation for LP problems inspired by duality theory, which enhances feature extraction and GNN expressiveness\n- Novel loss functions targeting basic variable selection and basis feasibility, along with multi-level labels from the solving path\n- Data preprocessing schemes to address label inconsistencies in solver-derived data\n\nThe approach significantly outperforms state-of-the-art methods in predicting initial basis with higher accuracy, reducing the number of iterations and solving time in LP solvers.\n\n## update after rebuttal\nI thank the authors for the detailed rebuttal, their response sufficiently addresses my concerns, hence I am updating my scores.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### limited discussion of computational overhead introduced by the more complex GNN architecture\n### 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\n\n> 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.\n\n### unclear how the proposed approach will scale to very large LP instances beyond those in the test datasets\n### What are the limitations of your approach for very large-scale LP problems?\n\n> 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:\n> \n| instances               | iter_default | iter_tripartiteBMP | time_default | time_tripartiteBMP |\n| ----------------------- | ------------ | ------------------ | ------------ | ------------------ |\n| LR1_DR04_VC05_V17b_t360 | 561299       | 409428             | 491.48       | 250.7              |\n| LR1_DR05_VC05_V25b_t360 | 706451       | 777452             | 474.74       | 513.63              |\n| LR1_DR08_VC05_V40b_t180 | 301789       | 309473             | 143.06       | 128.84              |\n| LR1_DR08_VC10_V40b_t120 | 267155       | 298875             | 112.76       | 131.6              |\n| LR1_DR12_VC10_V70a_t180 | 836561       | 619425             | 751.76       | 606.93              |\n| geomean | 484672       | 448942             | 309.27       | 265.74              |\n> 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.", "claims_and_evidence": "The claims in the paper are supported by convincing evidence. The authors demonstrate that the proposed approach\n- outperforms the state-of-the-art bipartite model across datasets.\n- reduces iterations for the previous state-of-the-art when used for a warm start in the HiGHS LP solver.\n- they also include ablation studies to demonstrate the value of each component (basic variable selection, feasibility loss, and preprocessing)", "methods_and_evaluation_criteria": "The authors evaluate their approach on four well-known datasets (Mirp1, Mirp2, Anonymous, and Load Balance) from MIP problems relaxed to LP and compare it with the state-of-the-art bipartite GNN model (Fan et al., 2023). In addition, they perform a detailed ablation study to demonstrate the utility of each of the proposed approach's core components.\n\nThe experiments are well-designed to test the paper's key claims, with appropriate metrics to evaluate prediction quality and performance (iterations).", "theoretical_claims": "The claims are generally well-supported with mathematical formulations and examples, particularly regarding duality theory and the message-passing mechanism in the tripartite graph.", "experimental_designs_or_analyses": "Refer to Methods and Evaluation Criteria", "relation_to_broader_scientific_literature": "The authors acknowledge prior work in these areas and clearly articulate how their approach extends beyond previous methods. The contribution of the paper addresses the specific gaps in the literature in the intersection of deep learning and mathematical optimization.\n- the paper extends the bipartite graph representation of optimization problems \n-  builds upon on work for tripartite graph representations and extends it to handle general LP form\n- addresses a fundamental issue in learning-based optimization", "essential_references_not_discussed": "While the paper covers most relevant literature, they don't discuss neural network based approaches for predicting optimal solutions to optimization problems beyond just basis selection.", "other_strengths_and_weaknesses": "Weaknesses\n- limited discussion of computational overhead introduced by the more complex GNN architecture\n- it is unclear how the proposed approach will scale to very large LP instances beyond those in the test datasets", "other_comments_or_suggestions": "Refer to other sections", "questions_for_authors": "- 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\n- What are the limitations of your approach for very large-scale LP problems?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eyslz12oG2", "reviewer": "Reviewer_SeCg", "summary": "Linear Programming (LP) is fundamental to numerous real-world applications, driving significant investment and research into improving the Simplex method, a widely used algorithm for solving LPs. Over decades, various heuristics have been developed to enhance solver efficiency, one of which is choosing an optimal initial basis, a critical factor influencing solver performance.\n\nIn this paper, the authors propose a novel framework that leverages a new way of representing LPs and a specialized loss function to predict a superior starting point for the Simplex algorithm. Their approach is validated through extensive experiments, demonstrating state-of-the-art (SOTA) performance improvements over existing heuristics, thereby showcasing its potential to accelerate LP solvers effectively.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Fan et al. uses LIBSVM and STOCH datasets. Can the authors display their results on these two datasets as well?\n> 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.\n\n### 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).\n\n> 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:\n> Iteration number:\n> \n| datasets       | n=0   | n=2   | n=4   | n=6   | default |\n| -------------- | ----- | ----- | ----- | ----- | ---- |\n| Mirp           | 18798 | 14017 | 12109 | 10813 | 25432 |\n| Anonymous      | 60146 | 23583 | 23166 | 21342 | 35330 |\n| Load_balancing | 4070  | 4357  | 4291  | 4512  | 7965 |\n| geomean        | 16633 | 11293 | 10637 | 10136 | 19271 |\n\n> Solving time in seconds:\n> \n| datasets       | n=0   | n=2   | n=4   | n=6   | default |\n| -------------- | ----- | ----- | ----- | ----- | ---- |\n| Mirp           | 8.29 | 7.43 | 7.07 | 6.39 | 11.17 |\n| Anonymous      | 7.19 | 7.12 | 6.75 | 6.87 | 9.08 |\n| Load_balancing | 16.71  | 10.49  | 10.98  | 8.85  | 7965 |\n| geomean        | 9.99 | 8.22 | 8.06 | 7.30 | 11.39 |\n\n> 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. \n\n### There is a knawing worry that the improvements might just be because of the increase in the number of parameters.\n> 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. \n\n### What is the form of $L$ in Equation 4?\n### How are  $\\theta$ and  $\\mu_k$ selected? Did the authors do some hyperparameter tuning on these parameters?\n\n> $\\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$.\n\n### 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.\n> For LP problems in standard form:\n\\begin{equation}\n\\begin{aligned}\n    \\min_{\\boldsymbol{x} \\in \\mathbb{R}^n} \\quad & \\boldsymbol{c}^\\top \\boldsymbol{x} \\\\\\\\\n    \\text{s.t.} \\quad \\boldsymbol{A} \\boldsymbol{x} &\\leq \\boldsymbol{b}, \\\\\\\\\n    \\boldsymbol{x} &\\geq 0,\n\\end{aligned}\n\\end{equation}\n\n> 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.\n\n> 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.", "claims_and_evidence": "Yes. The evidence supports the claims. I have some clarifying questions. Please see the sections below.", "methods_and_evaluation_criteria": "Overall methods are clear and well explained. I have a few questions.\n- Fan et al. uses LIBSVM and STOCH datasets. Can the authors display their results on these two datasets as well?\n- Fan et al. establish that their method is better than CPLEX. Therefore, it doesn’t seem necessary to compare the proposal with CPLEX. -However, since Gurobi is also a widely accepted solver for LPs, is it possible to have Gurobi as one of the baselines (time or iterations)? This will be useful in completing the picture of Initial basis selection problem and standards.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Experimental design looks good. All ablations are clearly showing the efficacy of their proposal. \n\nI have a few proposals for an additional ablation for better understanding\n\n -  $L_{multi}$ - How are $\\theta$ and $\\mu_k$ selected? Did the authors do some hyperparameter tuning on these parameters? Perhaps, a simple ablation would be to do random sampling and compare that with the chosen one. \n\n - Tripartite representation has also been well explained. However, just like how the effect of the number of message passing round is understood in Table 11 (in Appendix), it will be useful to have such a table 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).\n\nThere is a knawing worry that the improvements might just be because of the increase in the number of parameters. It will be useful to have details around \n\n- The number of learnable parameters in bipartite vs tripartite representation\n- For all the datasets, geometric mean of the number of nodes and edges in bipartite vs tripartite representation\n- Comparison of runtime of a single pass between bipartite vs tripartite representation", "relation_to_broader_scientific_literature": "The authors’ proposal for tripartite representation of LPs for GNN is novel. This could actually be used across several other deep learning-based heuristic design for solvers as well as other deep learning-aided combinatorial optimization problems. \n\nTheir work falls under the broader theme of making LP solvers faster using deep learning methods. \n\nTheir work has also identified core issues in dealing with predictions in LP such as label inconsistencies, which haven’t been addressed in the literature. \n\nCorresponding to the specific problem of Initial Basis Selection, the authors improve upon their predecessor and report substantial improvements.", "essential_references_not_discussed": "It looks good.", "other_strengths_and_weaknesses": "Authors proposal is quite novel and the results show substantial improvement over the benchmarks. I have suggestions for adding a baseline and showcasing the performance on more datasets as used by their predecessor work. Additional suggestion on ablation will also make for a better work.", "other_comments_or_suggestions": "- The notation in Basis section of page 2 is wrong. $B_x$ should be in the subscript. In addition, it should be told explicitly that [ ] means concatenation. \n- $x_{N_x}$ is wrongly placed inside the second bracket", "questions_for_authors": "- What is the form of $l$ in Equation 4?\n- 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. \n\n\nIn general, I am optimistic about the proposal. I am inclined to increase my rating once I hear the authors' rebuttal.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a GNN to predict a basis for the simplex algorithm for solving LPs. Contributions consists in the graph model, loss function and strong experimental performance. Reviewers agree on the merits of the paper and recommend acceptance. The thoughtful rebuttal is positively acknowledged. We urge the authors to incorporate the minor criticism raised by reviewers and take the rebuttal discussion into account in a final version of the paper.
Decision: Accept (poster)