Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems
Authors: Tomoharu Iwata
Shinsaku Sakaue
Venue: ICML 2025 poster (2025)
Keywords: Linear programming
Neural networks
Data-driven algorithm design
Primary area: optimization

Abstract: We propose a data-driven method for reducing the dimensionality of linear programming problems (LPs) by generating instance-specific projection matrices using a neural network-based model. Once the model is trained using multiple LPs by maximizing the expected objective value, we can efficiently find high-quality feasible solutions of newly given LPs. Our method can shorten the computational time of any LP solvers due to its solver-agnostic nature, it can provide feasible solutions by relying on projection that reduces the number of variables, and it can handle LPs of different sizes using neural networks with permutation equivariance and invariance. We also provide a theoretical analysis of the generalization bound for learning a neural network to generate projection matrices that reduce the size of LPs. Our experimental results demonstrate that our method can obtain solutions with higher quality than the existing methods, while its computational time is significantly shorter than solving the original LPs.

Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems
Tomoharu Iwata
Shinsaku Sakaue
Abstract
solve reduced-size LPs. This solver-agnostic property particularly advantageous since we can exploit the divergent evolution of LP solvers based on the simplex and interior- point methods.
We propose a data-driven method for reducing the dimensionality of linear programming prob- lems (LPs) by generating instance-specific projec- tion matrices using neural network-based model. Once the model is trained using multiple LPs by maximizing the expected objective value, we can efficiently find high-quality feasible solutions of newly given LPs. Our method can shorten the computational time of any I.P solvers due to its solver-agnostic nature, it can provide feasible so- lutions by relying projection that reduces the number of variables, and it can handle LPs of dif- ferent sizes using neural networks with permuta- tion equivariance and invariance. We also provide a theoretical analysis of the generalization bound for learning a neural network to generate projec- tion matrices that reduce the size of LPs. Our experimental results demonstrate that our method can obtain solutions with higher quality than the existing methods, while its computational time is significantly shorter than solving the original LPs.
Although the random projection approach is efficient, its solution quality can be low because it is difficult for random matrices to capture the subspace of good solutions. To improve the quality, data-driven projection approach has been proposed (Sakaue & Oki, 2024), where projection matrix is trained using LP instances. This method produces high-quality solutions when the test I.Ss are sufficiently similar to the training LPs. However, it performs poorly when the test LPs differ from the training ones since it shares projection matrix among heterogeneous LPs.
To obtain high-quality solutions efficiently for various LPs, propose a data-driven method for learning generate projection matrix appropriate for each LP instance using neural network- based model, instead of learning projection matrix itself. Figure I shows our framework. In the training phase, our model is trained using multiple LPs in an end- to-end fashion. In the test phase, we are given test LPs that are related but different from the training LPs. For each test LP instance, projection matrix generated using the trained model from the LP parameters. A projected LP of reduced size is obtained by the projection matrix, and it is solved by an LP solver. Then, solution of the original test I. recovered from the solution of the projected LP.
1. Introduction
Linear programming (LP) is widely used in many applica- tions, such as economies, engineering, and computer sci- ence (Gass, 2003; Eiselt & Sandblom, 2007). While nu- merous LP solvers have been developed, most of which are based on the simplex or interior-por pointt methods, efficiently solving high-dimensional LPs remains an important chal- lenge in operations research. Alongside advancements in LP solvers, there is increasing interest in reducing LP sizes through random projections (Vu et al., 2018; Poirion al., 2023; Akchen & Mišić, 2024). Projection based approaches are solver-agnostic in that it can work with any solvers to
By generating instance-specific projected LPs based on neu- ral networks, our method can improve the solution quality. Since our method solver-agnostic, we can improve the efficiency of any LP solvers by reducing LP sizes. By using I.P solvers that can obtain feasible solutions in the projected LPs, our method can always obtain feasible solutions since the recovered solutions are always feasible for the original LPs when the projected LPs are feasible.
Our model takes the parameters of an LP instance as in- put, and outputs a projection matrix. We design our model such that it is permutation equivariant the order of the variables, and permutation invariant to the order of the con- straints, which enables us to efficiently train it by reducing the model search space. Since our model can handle dif-
'TTT Corporation, Japan +CyberAgent, Japan. This work was done while SS was at the University of Tokyo and RIKEN AIP, Cor- respondence to: Tomoharu Iwata <tomoharu. iiwtaeewwiaaeee @ ntt.com>..
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Lincar Programming Problems
Training LPs
Test LP π (c,A,b)
Trained model
Projection matrix P
Solution to test LP π
Train
LP Solver
Solution to projected LP
Projected LP
Model
f
(a) Training phase
(b) Test phase
Figure 1. Our framework. (a) In the training phase, we train model f using training LPs Th Ti.... TN. (b) In the test phase, we are given test LP which is different from but related to the training LPs. Its solution obtained via solving reduced-size LP using instance-specific projection matrix P generated by trained model f. The size can be different across LPs.
ferent sizes of LPs, we can train it using LPs of various sizes, and use it for new LPs whose sizes are different from the training LPs. The training of our model is formulated by a bilevel optimization, where projected LPss are solved in the inner optimization, and the expected objective value of the recovered solution maximized by updating our model's parameters in the outer optimization. We perform the bilevel optimization based on the implicit function the- orem, by which we can derive an analytical expression of the outer gradients which depends only on the solution of the inner optimization and not the path taken by the inner LP solver. By synthesizing LPs according to the LP's pa- rameter distribution of target LPs, and training our model using the synthesized LPs beforehand, can efficiently find high-quality feasible solutions of target LPs that will be given in the future.
Bengio et al., 2021; Nair et al., 2020; Gregor & LeCun, 2010), which use neural networks to output information useful to solvers, such as initial solutions, or to output an approximate optimal solutions for L.Ss (Wu & Lisser, 2023; Chen et al., 2023; Qian et al., 2024). However, the existing methods are not projection- based approaches for LPs except for Sakaue & Oki (2024). The methods directly approx- imate solutions by neural networks cannot guarantee the feasibility of solutions. Unlike Sakaue & Oki (2024), our method considers instance-specific projection matrices, by which we can obtain high-quality solutions of LPs of dif-- ferent sizes with various parameters. Although permutation equivariance in LPs has been considered using graph neural networks (Chen et al., 2023; Qian et al., 2024), they not for generating projection matrices.
The main contributions of this paper are as follows: 1) We propose a framework of learning to generate instance- specific projection matrices using neural networks ef- ficiently solve I.s.. 2) We develop neural network model for LPs with permutation equivariance and invariance prop- erties that can handle LPs of any sizes. 3) We provide theoretical analysis on the generalization bound for learning a neural network to generate projection matrices that reduce the size of LPs. 4) We empirically demonstrate that our method achieves higher quality of solutions than exist- ing projection approaches while requiring significantly less computational time compared to solving the original LPs.
3. Preliminaries
We consider inequality-form LPs with parameters e E RR-V A RMN, and b E R
maximize XERV
C subject to Ax < b,
(1)
where N is the number of variables, and M is the num- ber of constraints. An LP with equality constraints can be transformed into an inequality-form LP if (trivially) feasible solution is available by restricting the feasible re- gion (Sakaue & Oki, 2024)'. When the number of variables N is large, we can efficiently compute an approximate solu- tion of Eq. (1) by restricting variables to a low-dimensional subspace using projection matrix P E Nx K with K < N (Poirion et al., 2023; Akchen & Mišić 2024),
2. Related Work
Some existing projection-base basee methods for LPs reduce the number of constraints (Vu et al., 2018; Poirion al., 2023), while others reduce the number of variables (Akchen &
maximize yERR
c TTPyy subject to APy S b
(2)
Misić, 2024; Sakaue & Oki, 2024). We focus on decreasing the number of variables since the recovered solutions are always feasible for the original LPs.
which is an LP with K variables and M constraints. After obtaining optimal solution y" to the projected LP in Eq. (2), we can recover a solution of the original LP in Eq. (1) by
Learning to optimize is an approach to accelerate optimiza- tion using machine learning techniques (Chen et al., 2023). Many methods for learning to optimize have been pro- posed (Monga et al., 2021; Chen al., 2021; Amos, 2022:
Mathematically, we may rewrite Ax = b as Ax < b and Ax 2 b, but this poses challenge of identifying the subspace satisfying Ax b when generating projections. We sidestep this feasibility issue by adopting the method of Sakaue & Oki (2024).
2

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Linear Programming Problems
= Py". Importantly, if the projected LP is feasible, re- covered solution X is always feasible for the original LP since APy* < b although it may not be optimal. The feasibility of the projected LP is guaranteed (i.e., its feasible region is non-empty) when x = O is feasible for the original LP, since y = 0 is always feasible for any projected LPs. Instead of x = O, we may assume that there exists an arbi- trary common feasible solution x without loss of generality. This is because we can translate the feasible region so that x coincides with the origin O. The quality of the solution is evaluated through objective value e Py". Ideally, if the columns of P span a linear subspace containing the optimal solution of (1), the reconstructed solution is optimal to (1) due to the optimality of y" to (2). Thus, finding appro- priate P that is close to this ideal condition with small K
straints. To incorporate this inductive bias, we design our model f such that it always ensures permutation equivari-
ance on variables and permutation invariance on constraints, With this design, the model search space can be signifi- cantly reduced by factor of NIM!, which makes training efficient.
First, our model obtains embeddings for each element of LP parameters c, A, and b using permutation equivariant linear programming problem (PELP) layers. Let (0( E R A(U) E g and Zm b(t) B be embedding vectors at the éth layer of an element in A, and b, respectively, where n and y are indices of elements. The embeddings at the zeroth layer are the LP parameters themselves, i.c., c(()
Cn E IR, A(D) Amn E R, and b(u)) = bm E R. The PELP layer computes the embedding of the (n.m) m)tt element of A by
enables us to efficiently compute a high-quality solution of the original LP (1) by solving the projected LP (2).
4. Proposed Method
A(t+1) = o WA100 2ll + A2(10) mn
2
A(e) mm
We propose a neural network-based model to generate instance-specific projection matrices for LPs. Once trained on multiple LPs, the model can quickly produce an appro- priate projection matrix through single forward pass.
WA3()
W
Σ
A(E)
Σ
A(U) mnn
m'
+
M
N
n
W5500
b(O)
wA6(0)
2m
4.1. Problem Formulation
where WA(( R x .j 1..... and w^6()) RH(+)) are parameters at the 4th layer, and a is a nonlinea activation function. The first term transforms the embedding of the nth element of c, the second term transforms the embedding of itself, the third (fourth) term transforms the embeddings of the 7ihh row (mtth column) of A aggregated by average pooling, the fifth term transforms the embedding of the mth element of b, and the sixth term is the bias. The model parameters for this transformation are shared across all elements n = I,..., NN m = I,..., M. Similarly, the embedding of the mth element of b is computed by
In the training phase, we are given a set of LP instances (Ta)2_) where the dth LP instance is represented by its parameters na (ca, Ad, ba). Here, ca E R&a, Aa E R Ma by E R MM, Na is the number of variables, and Ma is the number of constraints.
In the test phase, we are given a test LP instance π with N variables and M constraints, that is different from but related to the training LPs { {=-))=1- The number of variables and the number of constraints can be different from the training LPs, N + Na and M + Ma. Our aim is to obtain a high- quality solution of the test LP efficiently.
bb1()
N
4.2. Model
b(++1) 2m
A(E) mn
+ b20) b(E)
N
n=1
Our neural network-based model fe(TT) outputs projection matrix P E R appropriate for given LP instance π with N variables and M constraints, where 0 is model parameters. Figure illustrates our model, and Figure 6 in Appendix A illustrates each component of our model.
Wh3(t)
2m
b(E)
+ ww wb(())
(4)
M
where Whi(O) RH(+)) The embedding of the nih element of c is com- puted by
E R 1 1) .j ---11 1, 3. and w b4(0)
Optimal solution x* of LP instance is permutation equiv- ariant to the order of variables and permutation invariant to the order of constraints; i.e., when the variables of the LP instance are permuted, the variables of the optimal solu- tion permuted accordingly; when the constraints of the I. instance are permuted, the optimal solution is unchanged. Therefore, appropriate projection matrix P is permutation cquivariant on variables and permutation invariant on con-
WC2())
c(++)) 2n
Wel(0,g00 (()
+
N
n==1
We3(E)
M
Z mm
A(E)
+ Wo((
(5)
M
m==1
3

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Lincar Programming Problems
Input LP parameters
Embeddings
Embeddings
Projection matrix
PELP PELP layer
PELP PELP layer
generator
Projection
A
AA)
z
(
zA(L)
C(L)
P
Z b(1)
z b(L)
Reduced variables
Constraints->
Figure 2. Our model takes LP parameters as input, and outputs a projection matrix.
where Wes(() E TR xH(++) 1, 3, and we()) E ( Eqs. (3,4,5) are permutation equivariant on the order of variables and the order of constraints. By iterat- ing multiple PELP layers, information in other elements is gathered through nonlinear transformation, allowing to obtain embeddings that incorporate information in all LP parameters, C, A, and b.
Algorithm Procedures to obtain a solution using projec-
tion matrix generated by our model.
Input: LP instance (c. b).
Output: Solution X.
Initialize embeddings by the LP parameters, Zn Cn. A(0) Amn. Zm
c(00)
b(0) bm for n = 1,..., N and
m = =1...... I....,M. ...
After the PELP layers are applied, the nth row of pro- jection matrix P [pI....,,P PN.]T is calculated by the following projection generator,
for each layer l ...., T. do
3: Compute
embeddings
A(E) N {f Zmm In=i 1M Im=1
b(f) MM
{zm (2 Jn=1 by the PELP layer in 3 m==
Eqs. (3,4,5).
Pn- = 9 ((2)
(L)) max A(L) ERR;
(6)
mm
4: end for
5: Compute projection matrix P by the projection genera- tor in Eq. (6).
where g: R2 + RKK fully-connected neural net- work, and max is max pooling. Neural network g is shared across different variables Eq. (6) is permutation equivari- ant variables, and permutation invariant on constraints. Therefore, our model using PELP layers in Eqs. (3,4,5) and the projection generator in Eq. (6) is permutation equiv- ariant on variables, and permutation invariant on constraints. Our model parameters do not depend on the number of variables N or the number of constraints M. Therefore, it can handle LPs of different sizes; it generates projection matrix of size N K when an LP with N variables and M constraints is given for any N and M.
6: Obtain optimal solution y" to projected LP
(P c, AP, b) by an LP solver.
Recover solution of original LP π by x Py"
is the optimal objective value of projected LP, and Eg is the expectation over the training LPs. Model parameters 0 to be trained are the parameters in the PELP layers and the projection generator. Eq. (7) is bilevel optimization problem, where model parameters O are optimized in the outer level, while reduced variables of projected LPs are optimized the inner level. To efficiently solve this bilevel optimization problem, we leverage the implicit function theorem. The gradient of the objective function in Eq. (7) for each I.P instance is given by
Algorithm 1 shows the procedures to obtain a solution using the projection matrix generated by our model. The compu- tational complexity of our model is O((N + M) i.c., it linearly scales with the number of variables and constraints. Although permutation equivariance and invariance can be achieved with attention mechanisms (Lee et al., 2019), they quadratically scale with them.
tu (P. Ta)
(au(Par di Td) OP
Ovec
vec
(9)
00
00
4.3. Training
via the chain rule, where vec: NxM N denotes the vectorization of matrix. Assume that the projected LP satisfies regularity condition, which requires that optimal solution y E Æ exists at which active constraints are linearly independent. Then, the first factor is computed based on the implicit function theorem (Tan et al., 2020; Sakaue & Oki, 2024) by
We train our model in end-to-end fashion by maximizing the expected objective value using training LPs (
i arg max E, [u (Pa.
(7)
where P. = fo (TT) ) is projection matrix generated by our model.
" P. T) max (c PPy APy S <b),
(8)
Oul Pu,P Ta) OP a
YERK

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Lincar Programming Problems
Algorithm 2 Training procedures of our model.
instance whose feasible region is restricted to Im P.
Input: Training LPs (Ta)d=1-
For the analysis, we consider fully-connected neural net- work described in Appendix B. leaving analysis specific to neural networks with permutation equivariance and in- variance described in Section 4.2 for future work. Let So II - P denote the fully-connected neural network with W parameters, 0 RWW which maps an LP instance π E II to an output projection matrix P P. Our central interest lies in the function class defined as
Output: Trained model parameters O.
1: while End condition is not satisfied do
2: Sample batch of LP instances Hy from {πr).
3: for each LP instance æt E I do
4: Generate projection matrix Pa = (TT)).
5: Obtain primal ya and dual X optimal solutions of projected LP (PJ Ca. A.Pa. a. ba) using LP solver.
6: Calculate gradient in Eq. (9) by automatic differ- entiation of vec (cay" - A () with respect to 0.
A = {u (fō ().) II [0, B]
0 (ER").
where each a (fø) (),-) is a function that is parameterized by 0 and maps E II to its optimal value under the condi- tion that the feasible region is restricted to Im fø (TT).
7: end for
8:
Update parameters 0 using the gradients by stochas- tic gradient ascent.
9: end while
5.2. Generalization Bound
We first introduce fundamental concepts in learning theory. Let F. be a class of functions from II to R. For D E N, we say set { C II of input instances are shatlered by F if there exist threshold values $1..... SD E R such that
where X E TR-M is the dual optimal solution of the pro- jected LP. Here, we do not need to differentiate through the inner LP optimization path, and we can use any LP solvers that provide primal and dual optimal solutions. Eq. (9) can be computed by automatic differentiation on scalar value vec(c.yy A >ay² ) vec((a) with respect to model parameters 0 without explicitly calculating large-size Jaco- bian (P Algorithm 2 shows the training procedures 00 of our model.
K (f -01)) -1). (D)
where (g) = 0 if < 0 and 1 otherwise. The pseudo- dimension of F, denoted by Pdim is the largest size of an input set that can be shattered by F.
Assume that the range of functions in F is restricted to [0, BJ. The celebrated uniform convergence (e.g., Anthony & Bartlett 2009, Theorem 19.2) ensures that for any distri- bution D on II, E > 0, and E (0, ,, if we have an i.i.d. sample, ,,,.... TD from of size
5. Theoretical Analysis
We discuss the generalization ability of the approach to solve LPs with projection matrices generated by neural networks based on data-driven algorithm design (Gupta & Roughgarden, 2017: Balcan, 2021; Cheng et al., 2024), which analyzes the amount of data sufficient for establish- ing generalization guarantees for data-driven algorithms. In
B E²
B + log 1 2))
D D= Ω
(dimm(F) log g
then, with probability at least 1- 8, for all f E F, we have
particular, our analysis is based on the recent theoretical study by Cheng et al. (2024) for using neural networks in data-driven algorithm design.
D f(T)) EnwDEE Se. d=1
1 D
5.1. Settings
In our case, if Pdlm (FH) is bounded and the sample size is sufficiently large to satisfy D Z B² Pdim (F%) up to log factors, then for all 0 E IR. W. the empirical average of u (f) (-),-) values deviates from the true average over un- known by most E with high probability. In other words, once we find good parameters 0 that deliver high empirical performance
Let II be a set of LP instances with N variables and M constraints, where we may regard N and M as the largest values in II to handle LPs of different sizes via zero padding. Assume that the optimal value of LPs in II always lies in [0, BJ. which is common boundedness assumption. Let K E (1,2...., N and P 11, N be the set of projection matrices, where the restriction to [-1, Xx does not lose generality since the scale of P does not change the optimal value of projected LPs. For any projection matrix P E P and instance π E II, define score function (PP RT) as in Eq. (8), i.e., the optimal value of the LP
sufficiently large training set, we can ex- pect that the trained neural network will generalize well to unseen future instances from the same distribution. Note that the bound is uniform, which holds regardless of how is learned. Thanks to this uniform bound, even though the optimization of 0 is non-convex and we cannot guarantee
5

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Lincar Programming Problems
convergence to globally optimal solution, once we find model that empirically performs well on the training data, its use for unseen instances can be justified.
cost for each are was randomly drawn from the uniform distribution on [0, 1]- The cost between the source and sink was set to be sufficiently large. We transformed MaxFlow and MinCostFlow instances into equivalent inequality form I.Ps using a trivially feasible solution (Sakaue & Oki, 2024). For MaxFlow, we used all zeros, representing no flow, as the trivially feasible solution. For MinCostFlow, we used all zeros except for a single one at the entry corresponding to the are between the source and sink, which is trivially feasible but costly. In MaxFlow and MinCostFlow, the num- ber of variables was 500, and the number of constraints was 1,000. All problems have non-negativity constraints x 2 O, which were not included in the constraint counts, and are formulated as maximization problems. For each of the Packing, MaxFlow, and MinCostFlow, we generated 425 LP instances for training, 25 for validation, and 50 for test.
Let U be the size of a neural network, which is the total number of hidden units. The following theorem provides an upper bound on Pdim (F%), which enables us to establish the above generalization guarantee.
Theorem 5.1. Let P Le 1- [-1,+11 be set of projection matrices, II a set of LP instances, and u: PxII-> [0, B] the function that takes P E P and π E II as inputs and returns the optimal value of the LP instance whose feasible region is restricted to Im P. Let Wo = N + MN + M and W WL+1= = N,, i.e., the sizes of an LP and a projection matrix, re- spectively. For fully-connected neural network with ReLU activations N R W x xRW +RW++ with I hidden layers, having size U and W parameters, and using the clipped ReLU squeezing function (see Appendix B. I), we have:
Pdim (Ft) OOWT NK) + W log(LLK)))
6.2. Compared Methods
We compared method (Ours) with the following meth- ods: Rand, PCA, SharedP, FCNN, and Direct. Rand is a random projection matrix method (Akchen & Misić, 2024), which reduces the dimensionality by selecting K variables randomly and fixing the others to zeros. PCA is a data-driven method that obtains a projection matrix shared across LPs by applying principal component analysis to the set of optimal solutions of the training LPs (Sakaue & Oki, 2024). SharedP trains projection matrix shared across I.ss by maximizing the expected objective value on training LPs (Sakaue & Oki, 2024). FCNN generates an instance- specific projection matrix using a fully-connected neural network, where LP parameters (c, A, b) are vectorized and concatenated for input. It is not permutation equivariant or invariant. Direct outputs a solution using neural network given an LP instance, where the same model was used with our method by generating each element of a solution by the projection generator. The implementation details are described in Appendix D.
The proof is provided in Appendix B.2. This theorem allows us to estimate the amount of training data sufficient for keeping the expected test performance within an error of s via the relation of D 2 3 Pdim (FR), ) as discussed above. However, as mentioned above, the bound would have room for improvement by considering permutation equivariance and invariance of the model described in Section 4.2.
6. Experiments
6.1. Data
We evaluated our method using three types of representa- tive LPs: packing, maximum flow, and minimum-cost flow problems, denoted by Packing, MaxFlow, and MinCostFlow, respectively. A packing problem is an LP with non-negative parameters c, A, and b. We generated packing problem instances with 500 variables and 50 constraints by drawing their parameter elements from the uniform distribution on [o, 1] and multiplying b by N. A maximum flow problem is an LP to find the largest flow that can be sent from source vertex to a sink vertex in a graph while satisfying ca- pacity constraints. A minimum-come cost flow problem is an LP to find the cheapest way to send a specific amount of flow through a graph, where costs are associated with arcs. To generate an instance of MaxFlow or MinCostFlow, we first randomly created a directed graph with 50 vertices and 500 ares with source and sink vertices, where arc from the source to the sink was always included to ensure feasibility. For MaxFlow, the capacity of each are was randomly drawn from the uniform distribution on [0, 1]. For MinCostFlow, we set the supply at the source and the demand at the sink to one. The capacity for all ares was set to one, and the
6.3. Results
To evaluate the quality of the solution, we used the average objective ratio over test LP instances, where the objective ratio was the objective value of the solution divided by the optimal value of the original LP. To evaluate the efficiency, we used the computational time to obtain a solution averaged over test LP instances, which included the time required to generate a projection matrix using the trained neural network and the time taken to solve the (reduced) LP using a solver.
Figure 3 shows the average test objective ratio and computa- tional time with different reduced dimensions K. Here, Full was included as baseline that solves original N- dimensional LPs without reducing the dimensionality. Our
6

---

Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Lincar Programming Problems
Full
Ours
Rand
PCA
SharedP
FCNN
Direct
0.8
0.8
0.8
Objective Racio
0.6
0.6
0.6
Objective
0.2
0.2
0.2
0.0
0.0
0.0
10
20
30
40
50
10
40
50
10
20
30
40
50
K
K
0.150
0.125
Time
0.075
0.050
1-
0.000
01
10
20
10
20
K
(a) Packing
(b) MaxFlow
(c) MinCostFlow
Figure Average objective ratio (upper row) and computational time in seconds for solving an LP (lower row) with different reduced dimensions K. Bars show the standard error.
p7
Pr
x
x²
(a) Packing
(b) Packing
Figure 4. Examples of generated projection matrix P using our method (top), solution x obtained with our method (middle), and solution x obtained by solving the original LPs without dimensionality reduction (bottom) for two different packing problems. Black represents zero, which the lowest value. The horizontal axis in all plots represents the variables, and the vertical axis in P corresponds the reduced variables. 150 variables out of 500 and 30 reduced variables of 50 shown for better visibility. The model with K = 50 was used to obtain P and x in these two problems.
Table 1. Average test objective ratio and computational time in seconds for solving an LP on packing problems with 100,000 variables.
Full
Ours
Rand
PCA
SharedP
FCNN
Direct
Objective ratio
1.000
0,924
0.230
0.066
0.070
0.257
0.014
Time
23.487
0.055
0.013
0.029
0.063
0.049
0.005
Table Average test objective ratios when types of training and test LPs were different. MinCostFlow.
Mix data contain Packing, MaxFlow, and
Test \ Train
Packing
MaxFllw
MinCostFlow
Mix
Packing
0.985 + 0.032
0.187 + 0.072
0.164 = 0.084
0.981 + 0,023
MaxFlow
0.142 + 0.083
0.994 + 0.014
0.230 = 0.139
0.954 0.058
MinCostFlow
0.000 + 0.000
0.029 0.083
0.894 + 0.068
0.787 0.201

---

Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Lincar Programming Problems
Full
Qurs
Ours trained with varlous LP sizes
1.0
0.8
Objective Ratic
Objective Retio
0.6
0.6
0.6
0.4
0.4
0.2
0.0
0.0
0.0
50
100
150
1000
1500
2000
60 #Nodes
70
80
M
N
0.6
0.5
Time
0.3
0.3
0.7
0.2
0.0
50
100
150
200
500
1000
1500
2000
30
40
50
M
#Nodes
(a) Packing (M)
(b) Packing (N)
(c) MaxFlow (#Nodes)
1.0
1.0
1.0
0.8
0.8
0.8
Objeciie Rabio
Objective Ratio
0.4
0.4
0.4
0.2
400
500
600
700
800
30
400
500
600 #Edges
700
800
900
#Edges
20
15
Tino
20
10
5-
10-
300
400
500
600
700
800
900
30
40
50
60
70
80
90
300
400
500
600
700
800
900
#Nodes
#Edges
(d) MaxFlow (#Edges)
(e) MinCostFlow (#Nodes)
(f) MinCostFlow (#Edges)
Figure 5. Average test objective ratio (upper row) and computational time in seconds for solving an LP (lower row) with various sizes of test LPs. Red lines (Ours) represent method trained with LPs of fixed size described in Section 6.1. Purple lines represent method trained with LPs of various sizes, where the range of the training LP size was the same with the range of the test LP size. (a) The number of constraints M of the test LPss varied while fixing N 500. The number of variables N varied while fixing M = 50. (c,e) The number of nodes was varied while fixing the number of edges at 500. (d.f) The number of edges was varied while fixing the number of nodes 50. The reduced dimension was K 50.
method significantly outperformed compared methods in terms of objective ratios. This result indicates that our
method can generate appropriate projection matrices for unseen LPs compared with the other methods. Our method
8

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Lincar Programming Problems
with large K achieved 89% to 99% objective ratio and was much faster than Full. As reduced dimension K increased, the objective ratio by our method improved while the com- putational time increased. Since Rand does not use infor- mation on the training L.ss, its solution quality was low. Although PCA and SharedP are data-driven approaches, their objective ratios were low, since they use a projection matrix shared across all LPs. On the other hand, our method can generate different projection matrices tailored for input LPs. The low objective ratio of FCNN implies the effec- tiveness of permutation equivariance and invariance of our model. The objective ratio of Direct was lower than that of our method, which indicates that finding appropriate projec- tion matrices is easier than directly finding optimal solutions. In addition, Direct violated constraints in 10% to 48% of the test LPs. On the other hand, our method always satis- fied constraints by using LP solvers for reduced-sizz LPs. The computational time of projection-basee methods (Ours, Rand, PCA, SharedP, and FCNN) increased as reduced dimension K increased. Since Direct does not use solvers, it was faster than the other method. The training time for our method with K = 50 on Packing was 1.7 hours. Although it requires long time for training, it can efficiently give high-quality solutions for unseen LPs once it is trained.
in packing problems. In MaxFlow, the objective ratio was high when the number of nodes was close or smaller than that of the training LPs (c), and the number of edges was close to that of the training LPs (d). In MinCostFlow, the ob- jective ratio was high when the number of nodes was small (c), and it did not vary much with the number of edges (f). The increase in computational time with our method, as the number of edges grew, was substantially smaller than that with Full. Next, we focus our method trained with varied-size LPs. In general, the performance was better than or comparable to our method trained with fixed-size LPs. This is reasonable since it was trained using LPs that were similar to test LPs.
The results on larger LPs are shown in Table 1, where pack- ing problems with 100,000 variables and 50 constraints were used with reduced dimension K = 50. Our method achieved higher objective ratio than the other methods (Rand and PCA), and significantly reduced computational time compared to solving the original LPs (Full) on these large instances.
Table shows the objective ratios by our method when dif- ferent types of LPs were used for training and test; e.g., our model was trained with Packing and tested with MaxFlow. We included Mix data for training, which consisted of Pack- ing, MaxFlow, and MinCostFlow LPs. The objective ratios were high when the same type was used for training and test LPs, and they were low when the same type was not included. Although our method trained with the Mix data achieved slightly worse than that trained with the same type, it was much better than that trained with different types. It is important to include LPs in training that are similar to test LPs.
Figure 4 shows examples of projection matrices and solu- tions obtained by our method for two packing problems. While the same model was used in these different LPs, our method generated different projection matrices and suc- ceeded in obtaining solutions close to the optimal solutions of the original LPs. The generated projection matrices have high values for variables that have non-zero values in the the original optimal solutions x". This is necessary to obtain good solutions since we cannot recover non-zero solutions when the variables are removed by the projection.
7. Conclusion
An advantage of our method is that our model with identical parameters can generate projection matrices for LPs of dif- ferent sizes. Figure 5 shows the results of our method when the test LP's sizes were varied. Here, we also evaluated our method trained with I.Ps of various sizes, where their ranges were the same with that of the test LP's sizes; A E [20, 200] and E [200, 2000] in Packing, and the number of edges ranged from 30 to 90, and the number of nodes ranged from 300 to 900 in MaxFlow and MinCostFlow. First, we fo- cus on our method trained with fixed-size LPs described in Section 6.1 (Ours). In Packing, the objective ratio by our method was high even when the number of constraints M changed in the test LPs (a), while the increase of the com- putational time with M was small compared with Full. The objective ratio was decreased gradually as the number of variables N exceeded the training size N 500 (b). These results indicate that our method works well for LPs when its number of variables is close to or smaller than that of the training LPs even when its number of constraints is different
We proposed method for learning to generate projection matrices for improving the efficiency of LP solvers by reducing LP sizes. Our method uses neural network-based model that generates projection matrix appropriate for given LP instance. Since our model can handle any size of LPs, we can use it for newly given LPs whose sizes are different from the training LPs. Our theoretical analysis guarantees that the generalization error decreases as the training data size increases, potentially bringing it arbitrarily close to zero. Experiments demonstrate that our method can obtain high-quality solutions compared with the existing methods. For future work, we plan to combine our method with a smart predict-then-optinize framework (Elmachtoub & Grigas, 2022) by incorporating the prediction of LP parameters from contextual information.
9

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Lincar Programming Problems
Acknowledgements
Chen, T., Chen, X., Chen, W., Heaton, H., Liu, J., Wang, Z.. and Yin, W. Learning optimize: A primer and benchmark. arXiv preprint arXiv: 128288 2021.
SS was supported by JST ERATO Grant Number JPM- JER1903.
Chen, Z., Liu, J., Wang, X., and Yin, W. On representing lin- ear programs by graph neural networks. In International Conference on Learning Representations, 2023.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Cheng, H., Khalife, S., Fiedorowicz, B., and Basu, A. Sam- ple complexity of algorithm selection using neural net- works and its applications to branch-and-cut. In Proceed- ings of the 38th Annual Conference on Neural Informa- tion Processing Systems, 2024.
References
Akchen, Y.-.. and Mišić, V. V. Column-randomized lin- ear programs: Performance guarantees and applications. Operations Research, 2024.
Desaulniers, G., Desrosiers, J., and Solomon, M. M. Col- umn generation, volume 5. Springer Science & Business Media, 2006.
Amos, Tutorial on amortized optimization for learning to optimize over continuous domains. arXiv preprint arXiv:2202.00665. 2022.
Eiselt, H. A. and Sandblom, C.-L. Linear programming and its applications. Springer Science & Business Media, 2007.
Anthony, M. and Bartlett, L. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 2009.
Elmachtoub, A. N. and Grigas, Smart "predict, then optimize". Management Science, 68(1):9-26, 2022.
Gass, S. I. Linear programming: methods and applications.
Ba. J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. arXiv preprint arXiv: 160.:06400000 2016.
Courier Corporation, 2003.
Geng, Z., Li, X., Wang, J., Li, X., Zhang, Y., and Wu, F. A deep instance generative framework for milp solvers under limited data availability. Advances in Neural Infor- mation Processing Systems, 36:26025-26044 2023.
Balcan, M.-F. Data-driven algorithm design. In Beyond the Worst- Case Analysis of Algorithms, pp. 026-645 Cam-
bridge University Press, 2021.
Bartlett, L., Harvey, N., Liaw, C., and Mehrabian, A. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1 2019.
Gregor, K. and LeCun, Learning fast approximations of sparse coding. In International Conference on Machine Learning, pp. 399-406, 2010.
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: methodological tour dfhorizon. European Journal of Operational Research, 290(2):405-2111 2021.
Gupta, R. and Roughgarden, T. A PAC approach to application-speeciii algorithm selection. SIAM Journal on Computing, 46(3):992- -017 2017.
Gurobi Optimization. LLC. Gurobi Optimizer Reference Manual, 2024. URL https: //w.tps::/ww...e gurobi com.
Bolusani, S., Besançon, M., Bestuzheva, K., Chmiela, A., Dionísio, J., Donkiewicz, T., van Doormmalen, J., Fifler, L., Ghannam, M., Gleixner, A., Graczyk, C., Halbig, K., Hedtke, I., Hoen, A., Hojny, C., van der Hulst, R., Kamp, D., Koch, T., Kofler, K., Lentz, J., Manns, J., Mexi. G., Mühmer, E., Pfetsch, M. E., Schlösser, F., Serrano, F., Shinano, Y., Turner, M., Vigerske, S., Weninger, D., and Xu, L. The SCIP Optimization Suite 9.0. Technical report, Optimization Online, February 2024. URL https: httpp//mmmmmatiiooonneeeeeeeeeee 9-0.. 02/the-sche wttp:oootttttttiiiiiiiioooi
Kingma, D. P. and Ba, J. L. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Lee, J., Lee, Y., Kim, J., Kosiorek, A., Choi, S., and Tch, Y. W. Set transformer: A framework for attention-basee permutation-invarian neural networks. In International Conference on Machine Learning, pp. 3744-3753, 2019,
Liu, H., Wang. J., Zhang, W., Geng, Z., Kuang, Y. Li, X., Li, B., Zhang, Y., and Wu, F. MILP-studio: MILP instance generation via block structure decomposition. Advances Neural Information Processing Systems, 37, 2024.
Browne, S., Dongarra, J., Grosse, E., and Rowan, T. The netlib mathematical software repository. D-Lib Magazine, 1(9), 1995.
10

---

Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Lincar Programming Problems
Monga, V., Li, Y., and Eldar, Y. C. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing, IEEE Signal Processing Magazine, 38(2): 18 44, 2021.
Nair, V., Bartunov, S., Gimeno, F., von Glehn, I., Lichocki, P., Lobov, I., D'Dnoghue, B., Sonnerat, N., Tjandraat- madja, C., Wang. P., Addanki, R., Hapuarachchi, T., Keck, T., Keeling. J., Kohli, P., Ktena, I., Li, Y., Vinyals, O., and Zwols, Y. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13344 2020.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., Vetooo, Z., Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. Pytorch: An imperative style, perfoperformecc deep learning library. In Neural Information Processing Systems, 2019.
Poirion, P.-L., Lourenço, B. F., and Takeda, A. Random pro- jections of linear and semidefinite problems with linear inequalities. Linear Algebra and its Applications, 664: 24-60, 2023.
Qian, C., Chételat, D., and Morris, C. Exploring the power of graph neural networks in solving linear optimization problems. In International Conference on Artificial Intel- ligence and Statistics, pp. 1432-1440. PMLR, 2024.
Sakaue, S. and Oki, T. Generalization bound and learning methods for data-driven projections linear program- ming. Neural Information Processing Systems, 2024.
Tan, Y., Terekhov, D., and Delong, A. Learning linear programs from optimal decisions. In Neural Information Processing Systems, pp. 19738-19749, 2020.
Vu, K., Poirion, P.-L., and Liberti, L. Random projections for linear programming. Mathematics of Operations Re- search,
2018.
Wang, H. Liu, J., Chen, X., Wang, X., Li, P., and Yin, W. DIG-MILP: deep instance generator for mixed- integer linear programming with feasibility guarantee. Transactions on Machine Learning Research, 2024.
Wu, D. and Lisser, A. A deep learning approach for solving linear programming problems. Neurocomputing, 520: 15-24. 2023.

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Lincar Programming Problems
A. Proposed Method
Figure illustrates the PELP layer to obtain embeddings (a-c) and the projection generator (d).
Reducing the number of constraints and reducing the number of variables are equivalent from the perspective of LP duality. In our paper, we focus reducing the number of variables purely for simplicity to avoid intricate discussions on infeasibility. However, from duality perspective, one could also consider reducing the number of constraints.
By the LP relaxation of the given MILP, we can apply our method to MILPs. Our method cannot be directly used for reducing MILPs because we design our training procedures tailored to LPs. However, our high-level idea of learning to generate projections could be extended to solve MILP instances efficiently. Developing such extensions to MILPs is an interesting direction for future work.
B. Theoretical Analysis
B.1. Neural Networks
This section describes neural networks considered in the theoretical analysis. Let N be the set of positive integers. For any N E N. let [N] f1,2...., Let L E N and consider a neural network (NN) with architecture [Wo, Wi..., WL. WL+1] E N which generates projection matrix P E P from LP instance π E II. Here, denotes the number of hidden layers, and We denotes the number of hidden units of the éth layer. Let U = W1 +..... ..... WL be the size of the NN. We encode LP instance π = (c. A, b) as an input vector of length Wo N + MN + M by concatenation, denoted by Enc: R R x R. + RW, We also decode vector of length WL+1
NK as
projection matrix with size N X K, denoted by Dec RNK - R N The NN is parameterized by L + 1 affine transformations T3 R.--11 W where T2+1 is linear. We use 0 E TR to denote the parameters of the NN, where W is the number of the parameters. Using the NN, mapping from an LP instance to projection matrix is given by
(TT) Dec(TT= (((CT((
where a is the activation function. As in Cheng et al. (2024), we force the NN's output to lie in [n, Ti] x ... x [1W2-1> TW24a] C RW2+1 by applying a squeezing activation function o' R - [0, 1] to each output coordinate yı E R. namely, 1/i + (T; ni)o'' (y:) for i = I..... WL+I- We let T1 = simplicity. We focus on the fully-connected NNs with ReLU and clipped ReLU (CReLU) activation functions considered in Cheng et al. (2024), leaving analysis specific permutation equivariant/ivvarint NNs for future work. Specifically, (xx = Re) = max(0, }r} and o' (1x)) = CReLU(x) min ma 2). 1 for activation functions. As a side note, it is not difficult to replace ReLU with any piecewise linear activation function, such as the leaky ReLU, by accordingly modifying the bound on Q discussed below based on Bartlett et al. (2019, Section 4).
Twr.+1 +1 and 1/1
Ther4 = -1 for
Next Embeddings
A((+1)
2
Projection
Variables-.
1)
matrix
Reduced variables
Neural
19530
1010
M*40
w050
w0h0
W/V0
network g
Current Embeddings
Voriable
Variables
Last Embedding:
A
A
A
AD
2
b(2)
z10
200
b00)
Constraints-
Constraints-+
Constraints-
Constraints-
(a) A 's embedding
(b) b's 's embedding
(c) c's embedding
(d) Projection matrix P
Figure 6. (a-c) PELP layer to obtain embeddings of A, b, and c. (d) Projection generator to obtain projection matrix P.
12

---

Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems
B.2. Proof
This section provides the proof of theorem 5.1.
Proof. As shown in the proof of Cheng et al. (2024, Theorem 2.6), for any D E N and "1,...; TD E II, there are
Q 2 (2eD(U 2N (L+1)W
W
subregions,Wi, Wi,,... We of RRW such that their union is R and I (Ta) restricted to & Wg is polynomial of degree most L + in 0 for all (g, d) E [Q] x [D].
Fix (g, d) [Q] x [D] and let P(0) fo (TZ) E P for any O E Wg. Observe that (P(0) c, b) D
RMM a projected LP instance such that each entry is a polynomial of degree at most + in 0. Then, Sakaue & Oki (2024, (M ) (M - 2K + 2) polynomials of degree at
Lemma 4.3) implies that, for any threshold value E I. there are up to 2K
most (2K + 1) + 2) in & whose sign patterns partition Wg into subregions such that (P)(),, πTa 2 s or not identical within each subregion.
SD Thus, for each g E [Q] and any threshold values 51, ....... SD E R. by applying Warren's theorem as in the proof of Sakaue &
Oki (2024, Theorem 4.4). The theorem states that, given polynomials of v variables with degrees at most the number of all possible sign patterns is at most (8eyp/v)" By applying this theorem to our case, we obtain
(sgm(u(JJ) (TT); (T))) ) s1), ....... (gn):....snn((((... Synnu((6') (T) - sD)) 0 W/H
M 2K
(M + 2K + 2)(K + 1) +2)
8&D
2K
W
Let a1 = 2e(U + K) and 0g Be(M+2K) 2k
(M + 2K + 2)( + 1)(L + 2) for simplicity. Summing up over q [Q].
we have
{{ ((sgu(u(fo (TI), TT)
..).....ssg(uu((f) (T) TD) sp)) 0 B
D (L+1)W
a2 D
W
$ 2441
W
By definition of the geeudo-dimession the largest possible D with 2 < 2 (eiD) (1+1)W bound on (d))) Taking logarithms on both sides, we obtain
W serves upper
(W)
W
an
agD
Dlog 2 < (L + 1) log 2 + (L + 1)Wlog log
+ W Wlog
W
W
D
(L +
D
[3a2
$ (L+ 1) log 2 + (L + 1)W
+ +log
+
+
log
3(L + 1)W
3W
e
2 2 + (L 1) log + (L + 1) log
3a 3an +
30z e
+ HlWloo log
e
where the second inequality follows from log A + log for any z and À > (Cheng al., 2024, Lemma B. Since log 2 > 2/3, the above inequality implies
(dim((F)) S (L+ + 1) log 2 + (L + 1)W log 3a +1)
11 e
330
+ W log
e
= O (Wg + NK) + WK (Lg(LM))),
completing the proof.
C. Additional Related Work
Column generation (Desaulniers et al., 2006) an iterative method for solving LPs: starting from an LP with a small number of variables, it iteratively selects relevant variables until the optimality confirmed via the L.P duality. Column
13

---

Learning to Generate Projections for Reducing Dimensionality of Heterogencous Lincar Programming Problems
generation repetitively solves reduced-size LPs for solving an original LP instance. On the other hand, our method finds an appropriate projection matrix by a single forwarding pass of our ceural-network-based model, and the resulting reduced-size is solved only once. Since column generation is an LP solver, our method can be used to accelerate column generation by benefiting from data of past LPs. Exploring the collaboration of the algorithmic (like column generation) and data-driven (like ours) approaches to reducing IPP sizes will be an exciting future direction.
Mixed integer linear programming (MILP) instance generation approaches (Geng et al., 2023; Liu et al., 2024; Wang et al., 2024) generate optimization problem instances. The generated instances can be used for training machine learning-base solvers, tuning hyperparameters of solvers, or evaluating solvers. On the other hand, our method transforms given optimization problem instance to another reduced-size instance to efficiently solve the given instance. That is, MILP instance generation approaches do not transform a given instance, while our purpose is to solve given instances efficiently. Potentially, (MI)LP instance generation techniques can be used for synthesizing training LPs.
D. Experiments
D.1. Implementation
In our method, we used four PELP layers with residual connection and layer normalization (Ba et al., 2016), and H 32. A three-layered fully-connected neural network with 32 hidden units used in the projection generator. The leaky rectified linear unit was used for activation functions. The softmax function is applied the outputs of the projection generator to obtain non-negative projection matrices normalized for each reduced variable. Non-negativity constraints 2 0 were not explicitly used for the input of our model since recovered solution Py is always non-negative when projection matrix P is non-negative and solution y" to the projected LP is non-negative. For the objective function in Eq. (8), we used the objective ratio that is the optimal objective value of the projected LP divided by the optimal value of the original LP. We optimized using Adam (Kingma& & Ba, 2015) with a batch of eight I.P instances, and learning rate 10-3 The maximum number of training epochs was 500, and the validation data were used for early stopping. PyTorch (Paszke et al., 2019) was used for implementation. As LP solvers, we used Gurobi 12.0.0 (Gurobi Optimization, LLC, 2024) in the training phase, and SCIP Optimization Suite 9.2.0 (Bolusani et al., 2024) in the test phase. For evaluating computational time, we used PC with Xeon Gold 5222 3.80GHz CPU, NVIDIA GeForce RTX2080Ti GPU, and 512GB memory.
In computed projection matrices by PCA, negative values were replaced by zero to obtain non-negative projection matrices. SharedP, FCNN, and Direct were trained using the same procedures as our method. In FCNN, a three-layered fully- connected neural network with hidden units was used. In Direct, the architecture of the neural network was the same as that of our method, where the projection generator was used to generate each element of solution. In Direct, the objective function to be minimized was the mean squared error from the optimal solution X to the original LP, x3 Xx 11? where Xa is the estimated solution. In addition, the regularization term, max ba, 0) + max Xd, 0)), was added to penalize the violation of linear inequality and non-negativity constraints.
D.2. Results
Figure 7 shows the objective ratio by our method with different numbers of training LPs. Generally, as the number of training LPs increased, the performance improved as expected. The objective ratio was high even with a relatively small number of training LPs. Additional results are provided in Appendix D.2.
Figure& 8 shows the result on GROW7, an LP from the Netlib repository (Browne et al., 1995), which a collection of software for scientific computing. We generated LP instances from GROW7 by multiplying all the LP parameters (in the objective function and constraints) with uniform random values ranging from 0.75 to 1.25 and permuting the variables and constraints. Our method achieved better objective ratios compared to the other methods, and its computational time is significantly shorter than that of solving the original LPs (Full).
Figure 9 shows the objective ratio when our method is not trained. Without training, our method did not perform well. This result demonstrates the importance of our proposed training procedures.
14

---

Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Lincar Programming Problems
1.0
1.0
0.8
0.8
Cijjecto Batio
Objective Ratio
Objective Ratio
0.6
0.6
0.6
0.4
0.2
0.2-
0.0
0.0
0.-
100
200
300
400
100
300
400
100
200
300
400
#traning LPS
Training LPs
#Braining
L7
(a) Packing
(b) MaxFlow
(c) MinCostFlow
Figure 7. Average test objective ratio by our method with different numbers of training LPs.
+
Full
Ours
Rand
PCA
SharedP
FCNN
Direct
1.0
1.2
0.6
0.8
0.6
0.4
0.4
0.0
K
Figure 8. Average test objective ratio (left) and computational time in seconds for solving an IPP (right) with different reduced dimension K on GROW7.
Ours
Ours without training
10
1.0
1.0
Objective Rat
0.6
0.6
0.6
Objectiv
0.4
0.4
0.4
0.0
0.0
0.0
K
K
(a) Packing
(b) MaxFlow
(c) MinCostFlow
Figure 9, Average test objective ratio with different reduced dimension K by our method with and without training.
15


Reviews:
[{"review_id": "TaluV9Jiqe", "reviewer": "Reviewer_5Q4U", "summary": "This paper proposed a new data-driven method to train a machine learning model to reduce the dimensionalities of large-scale linear programming problems (LP). This model not only can provide reduced dimension LP, by solving which one could obtain a high-quality feasible solution of the original LP, but can reduce dimensionality of LPs with different sizes. The authors also use theory to show the generalization of the model, and illustrate the performance of this model by numerical experiments.", "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": "We appreciate your constructive comments.\n\n> the authors only show the generalization bound but do not show the optimality of this model.\n\nSince the objective function for training our model is non-convex, it is challenging to show the optimality of the trained model. Note that we can improve the quality of solutions by maximizing our objective function, although it may not be optimal, and our method can obtain high quality solutions as demonstrated in our experiments. The generalization bound ensures that the empirical high performance generalizes to unseen future instances.\n\nOur model is based on deep sets [Deep sets, NeurIPS2017], and deep sets are known to be universal for approximating invariant and equivariant functions [On Universal Equivariant Set Networks, ICLR2020]. Moreover, the model search space of our model is significantly reduced by a factor of N!M! by its invariant and equivariant properties as described in our paper. Therefore, although we cannot say it is the optimal model, it is a data-efficient model with high representation power for generating projections for LPs.\n\n> It would be better to apply this new method to some problems for the competition of commercial solvers.\n\nWe newly conducted experiments using GROW7, an LP from the Netlib repository [The Netlib Mathematical Software Repository, D-Lib Magazine, 1995], which is a collection of software for scientific computing. We generated LP instances from GROW7 by multiplying all the LP parameters (in the objective function and constraints) with uniform random values ranging from 0.75 to 1.25 and permuting the variables and constraints. As shown in the table below, our method achieved better objective ratios compared to the other methods, and its computational time is significantly shorter than that of solving the original LPs (Full).\n\nObjective ratio\n|$K$|10|15|20|25|30|35|40|45|50|\n|----|----|----|----|----|----|----|----|----|----|\nOurs | 0.469 | 0.618 | 0.669 | 0.709 | 0.780 | 0.814 | 0.786 | 0.841 | 0.852 |\nRand | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |\nPCA | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |\nSharedP | 0.000 | 0.002 | 0.003 | 0.004 | 0.004 | 0.005 | 0.006 | 0.008 | 0.009 |\nFCNN | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |\nDirect | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |\n\nComputational time in seconds\n|$K$|10|15|20|25|30|35|40|45|50|\n|----|----|----|----|----|----|----|----|----|----|\nFull | 1.236 | 1.236 | 1.236 | 1.236 | 1.236 | 1.236 | 1.236 | 1.236 | 1.236 |\nOurs | 0.058 | 0.067 | 0.084 | 0.104 | 0.120 | 0.141 | 0.160 | 0.184 | 0.202 |\nRand | 0.044 | 0.060 | 0.078 | 0.096 | 0.114 | 0.130 | 0.148 | 0.169 | 0.188 |\nPCA | 0.044 | 0.062 | 0.078 | 0.099 | 0.113 | 0.132 | 0.152 | 0.176 | 0.192 |\nSharedP | 0.043 | 0.059 | 0.078 | 0.097 | 0.139 | 0.133 | 0.153 | 0.170 | 0.189 |\nFCNN | 0.045 | 0.062 | 0.080 | 0.097 | 0.116 | 0.133 | 0.148 | 0.198 | 0.189 |\nDirect | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 |\n\n> I am not familiar with using NN to reduce dimensionality for optimization problems.\n\nTo our knowledge, there is no existing work that uses NN to reduce dimensionality for optimization problems.\n\n> it might be important to cite some traditional methods to reduce the dimensionality of LPs, such as column generation. Additionally, it would be great if the authors could discuss the difference between this new approach and some traditional dimensionalty reduction methods for LPs.\n\nWe appreciate this comment. We will cite traditional methods that reduce the dimensionality of LPs, including column generation, and add discussions on them. Below we clarify the relation to column generation.\n\nColumn generation is an iterative method for solving LPs: starting from an LP with a small number of variables, it iteratively selects relevant variables until the optimality is confirmed via the LP duality. A crucial distinction is that column generation is an LP solver, whereas our model serves as a data-driven preprocessing step for reducing the dimensionality of LPs. Therefore, our method can be used to accelerate column generation by benefiting from data of past LPs. From the computational perspective, column generation repetitively solves reduced-size LPs for solving an original LP instance. On the other hand, our method finds an appropriate projection matrix by a single forwarding pass of our neural-network-based model, and the resulting reduced-size LP is solved only once. Exploring the collaboration of the algorithmic (like column generation) and data-driven (like ours) approaches to reducing LP sizes will be an exciting future direction.", "claims_and_evidence": "Yes. The proof of generalization bound looks good, and the numerical experiments also support the conclusion.", "methods_and_evaluation_criteria": "Regarding the theoretical part, the authors only show the generalization bound but do not show the optimality of this model. However, it seems that this type of generalization bound follows many existing TCS analyses about the generalization of NNs, so this result might not be very novel. For this problem, potentially, an optimality guarantee would be more interesting. \n\nAdditionally, for the numerical experiment parts, the used cases might not be general enough. It would be better to apply this new method to some problems for the competition of commercial solvers. This mentioned comparison might show the true performance of this new method.", "theoretical_claims": "Yes. This type of bound should be similar to some existing bounds.", "experimental_designs_or_analyses": "Please see \"Methods And Evaluation Criteria\".", "relation_to_broader_scientific_literature": "There are many different methods to reduce dimension for large-scale optimization, or linear programming, such as column generation. It seems that this paper proposed a new approach to design some novel NN layers to learn the reduced-dimension LPs, which can also provide high quality solutions.", "essential_references_not_discussed": "I am not familiar with using NN to reduce dimensionality for optimization problems. However, it might be important to cite some traditional methods to reduce the dimensionality of LPs, such as column generation.", "other_strengths_and_weaknesses": "Please see \"Methods And Evaluation Criteria\" for my main concern.\n\nAdditionally, it would be great if the authors could discuss the difference between this new approach and some traditional dimensionalty reduction methods for LPs.", "other_comments_or_suggestions": "Please see \"Methods And Evaluation Criteria\" for my main concern.\n\nAdditionally, it would be great if the authors could discuss the difference between this new approach and some traditional dimensionalty reduction methods for LPs.", "questions_for_authors": "Please see \"Methods And Evaluation Criteria\" for my main concern.\n\nAdditionally, it would be great if the authors could discuss the difference between this new approach and some traditional dimensionalty reduction methods for LPs.", "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": {"ethical_review_concerns": "NA"}}, {"review_id": "2vWoV7Z0Bg", "reviewer": "Reviewer_3Xaa", "summary": "This paper presents a data-driven method for reducing the dimensionality of linear programming (LP) problems by generating instance-specific projection matrices using a neural network-based model. The proposed approach aims to improve the efficiency of LP solvers by projecting high-dimensional LP instances into a lower-dimensional space while maintaining solution feasibility and quality. The authors conclude that their method offers an efficient and solver-agnostic approach for solving large-scale LPs, making it a practical tool for accelerating LP solvers in real-world applications.", "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": "We appreciate your constructive comments.\n\n> it lacks a clear comparison with existing MILP generation methods to highlight its distinct advantages.\n\nSince MILP generation methods and our approach serve significantly different purposes, we cannot make direct comparison. We plan to add a discussion to clarify this point, citing relevant  references, such as [A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability, NeurIPS2023], [MILP-StuDio: MILP Instance Generation via Block Structure Decomposition, NeurIPS2024], [DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming with Feasibility Guarantee, TMLR, 2024]. Below is the detailed discussion.\n\nMILP instance generation approaches generate optimization problem instances. The generated instances can be used for training machine learning-based solvers, tuning hyperparameters of solvers, or evaluating solvers. On the other hand, our method transforms a given optimization problem instance to another reduced-size instance to efficiently solve the given instance. That is, MILP instance generation approaches do not transform a given instance, while our purpose is to solve a given instances efficiently, making them incomparable.\n\n> proofs appear correct, though their practical implications could be further clarified.\n\nIf the training-data size $D$ is larger than $B^2/\\epsilon^2 Pdim$, the generalization error is bounded by $\\epsilon$. Our theoretical analysis guarantees that the generalization error decreases as the training-data size increases, potentially bringing it arbitrarily close to zero. We will clarify this practical implication.\n\n>  Additionally, the practical robustness of the learned projection matrices, especially when encountering out-of-distribution LP instances, could have been further analyzed.\n\nWe have analyzed the robustness of our learned neural network-based model\nin Figure 5 (p.8) and Table 1 (p.14 in the appendix) when encountering out-of-distribution LP instances.\n\nIn Figure 5, Ours (red line) represents the performance of our method on test LP instances whose sizes are different from the training LP instances. Figure 5 (a,b) show that our method works well for LPs when its number of variables is close to or smaller than that of the training LPs even when its number of constraints is different in packing problems.\nIn MaxFlow, our method works well when the number of nodes was close to or smaller than that of the training LPs (c), and the number of edges was close to that of the training LPs (d). In MinCostFlow, our method works well when the number of nodes was small (e), and it did not vary much with the number of edges (f).\n\nTable 1 shows that our method's performance was high when the same type of LP instances were used for training and test LPs, and it was low when instances with the same type were not included. Although our method trained with the Mix data achieved slightly worse than that trained with the same type's instances, it was much better than that trained with different types' instances. This result indicates that it is important to include LPs in training that are similar to test LPs.\n\n> included more discussions on practical deployment\n\nOn practical deployment, by synthesizing LPs according to the LP's parameter distribution of target LPs, and training our model using the synthesized LPs beforehand, we can efficiently find high-quality feasible solutions of target LPs that will be given in the future as described in Section 1. \n\nPotentially, we may be able to use (MI)LP instance generation techniques for synthesizing LPs. We will add discussions on practical deployment.\n\n> generalization to MILPs\n\nBy the LP relaxation of the given MILP, we can apply our method to MILPs. Our method cannot be directly used for reducing MILPs because we design our training procedures tailored to LPs. However, our high-level idea of learning to generate projections could be extended to solve MILP instances efficiently. Developing such extensions to MILPs is an interesting direction for future work. We will add discussions on generalization to MILPs.", "claims_and_evidence": "The paper provides strong empirical and theoretical evidence for its claims, but it lacks a clear comparison with existing MILP generation methods to highlight its distinct advantages.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for LP dimensionality reduction, but the lack of direct comparison with existing MILP generation approaches limits the clarity of its broader impact.", "theoretical_claims": "The paper provides a solid theoretical analysis, including a generalization bound for the learned projection matrices, and the proofs appear correct, though their practical implications could be further clarified.", "experimental_designs_or_analyses": "The experimental design is well-structured with diverse LP benchmarks and strong empirical validation, but it lacks direct comparisons with existing MILP generation methods to contextualize its advantages.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "This paper presents a well-structured and theoretically sound approach for dimensionality reduction in linear programming (LP) problems by generating instance-specific projection matrices using a neural network. One of its key strengths is the solid theoretical foundation, particularly the generalization bound analysis, which ensures the reliability of the generated projection matrices across different LP instances. Additionally, the permutation equivariant and invariant model design enhances its flexibility, allowing it to handle LPs of varying sizes effectively. Empirical evaluations on multiple LP benchmarks demonstrate that the method achieves high-quality solutions while significantly reducing computational time compared to solving the original LPs.\n\nHowever, despite these strengths, the novelty of the approach is somewhat limited. The idea of using projection-based techniques for MILP/LP problem transformation has been widely explored in the literature, and the paper does not sufficiently differentiate its method from existing MILP instance generation approaches. While the theoretical analysis is a valuable contribution, the lack of a direct comparison with other MILP generation methods makes it difficult to fully assess the impact of this work within the broader optimization community. Additionally, the practical robustness of the learned projection matrices, especially when encountering out-of-distribution LP instances, could have been further analyzed.\n\nOverall, this paper provides a rigorous and well-executed extension of projection-based LP optimization methods, but its contribution would be stronger if it explicitly addressed its uniqueness compared to prior MILP generation methods and included more discussions on practical deployment and generalization to MILPs.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "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": "vi2GWNvjSs", "reviewer": "Reviewer_oitp", "summary": "This paper applies machine learning to find a more suitable projection of optimization models in the form of linear programming. By projecting to a space of smaller dimension, it is possible to solve a simpler version of the LP model much faster. A good projection should have basic solutions mapping to optimal (or near-optimal) solutions of the original LP model, in which case we may find an optimal (or near-optimal) solution from solving the project LP.", "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": "We appreciate your positive and constructive comments.\n\n> I believe that evaluating the proposed NN architecture with random initialization and no training is an important benchmark. This would be different from the random projection used.\n\nWe compared with the proposed NN with random initialization and no training.\nThe objective ratios of our method (Ours) and our NN without training (NoTrain) are shown in the following tables. Without trainig, the proposed NN does not perform well. This result demonstrates the importance of our proposed training procedures. We will add this discussion. \n\nPacking: Objective ratio\n|$K$|10|15|20|25|30|35|40|45|50|\n|----|----|----|----|----|----|----|----|----|----|\n|Ours | 0.922 | 0.938 | 0.953 | 0.970 | 0.978 | 0.986 | 0.987 | 0.990 | 0.985 |\n|NoTrain | 0.097 | 0.098 | 0.098 | 0.098 | 0.099 | 0.099 | 0.099 | 0.099 | 0.099 |\n\nMaxFlow: Objective ratio\n|$K$|10|15|20|25|30|35|40|45|50|\n|----|----|----|----|----|----|----|----|----|----|\n|Ours | 0.677 | 0.768 | 0.862 | 0.919 | 0.983 | 0.983 | 0.982 | 0.990 | 0.994 |\n|NoTrain | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 |\n\nMinCostFlow: Objective ratio\n|$K$|10|15|20|25|30|35|40|45|50|\n|----|----|----|----|----|----|----|----|----|----|\n|Ours | 0.844 | 0.859 | 0.862 | 0.875 | 0.878 | 0.879 | 0.886 | 0.889 | 0.894 |\n|NoTrain | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |\n\n> Figure 3 is not very clear\n\nWe will make the figure more clearly.\n\n> Some comments on the mathematical optimization side do not seem entirely accurate\n\nWe will revise the sentences according to your comments.\n\n> When you say that \"[w]e focus on decreasing the number of variables since the recovered solutions are always feasible for the original LPs\", you are ignoring duality: by decreasing the number of constraints, you would find a dual feasible solution that could provide you an optimality gap. Saying that one is preferable to the other is a bit misleading. Even if not intended, I believe that addressing that by mentioning the case of decreasing the number of constraints, even if not carried out in the paper, would make it more accurate and self-contained. Remember: some people may start working on this from your paper, and such absences may affect their future work. Can you please address this?\n\nThank you for your insightful comment. As you correctly pointed out, reducing the number of constraints and reducing the number of variables are equivalent from the perspective of LP duality. In our paper, we have focused on reducing the number of variables purely for simplicity - to avoid intricate discussions on infeasibility. However, we acknowledge that, from a duality perspective, one could also consider reducing the number of constraints. We will make this explicit in the paper to ensure clarity and completeness.\n\n> What do you mean when you say that \"[a]n LP with equality constraints can be transformed into an inequality-form LP if a (trivially) feasible solution is available\"? Why is that even necessary? To be clear, if S = {x : A x = b}, then we can reformulate it as S = {x : A x >= b, A x <= b} = {x : - A x <= - b, A x <= b}. Isn't it?\n\nWe can reformulate it as you mentioned. However, by this reformulation, projected LPs are more likely to be infeasible, and the number of inequality constraints increases. On the other hand, the reformulation using a trivially feasible solution can ease the feasibility issue, and the number of inequality constraints does not change. We will clarify this point in the paper.\n\n> You have both minimization and maximization problems, but the objective ratio always peaks at 1.0 in Figure 3. My understanding is that you take the ratio between the smallest and the largest values between the solution you obtain through the projection and the optimal solution of the LP. Is that the case? If so, can you please clarify that in the paper?\n\nIn our experiments, all problems are converted into maximization problems, and $x=0$ (with an objective value of zero) is always a trivially feasible solution. Therefore, the objective ratio is calculated as the obtained objective value divided by the optimal value of the original LP. We will clarify this point in the paper.", "claims_and_evidence": "In comparison to prior work, this paper proposes a machine learning method that takes into account instance-specific information. In other words, the projection is not only based on the model but also on the specific coefficients of the LP to be projected and solve. In comparison to an approach that is not instance-specific, as well as more standard approaches, they report solutions of considerably better quality.", "methods_and_evaluation_criteria": "I believe that evaluating the proposed NN architecture with random initialization and no training is an important benchmark. This would be different from the random projection used.\n\nWhy? Because, in recent years, some papers on ML for optimization have either spotted or reflected on the fact that ML can sometimes be an overkill. Therefore, I believe that it would a good practice that papers in this area evaluate the impact of a NN producing pure noise in their benchmarks.", "theoretical_claims": "Only in the appendix; not evaluated.", "experimental_designs_or_analyses": "See two items above.", "relation_to_broader_scientific_literature": "As claimed by the authors, there is a clear missing gap in using instance-specific information for obtaining a better projection for LP models.\n\nIn particular, I found the description of the PELP layers quite clear. Kudos!", "essential_references_not_discussed": "Nothing comes to mind.", "other_strengths_and_weaknesses": "Strength:\n- The paper is clearly written.\n- The contribution is clearly stated.\n\nWeakness:\n- Figure 3 is not very clear\n- Some comments on the mathematical optimization side do not seem entirely accurate (see next items)", "other_comments_or_suggestions": "Page 1: \n- \"is widely used in many [areas of] application\" (no plural in application)\n- \"most of which are based\": remove \"are\"\n\nPage 2:\n- \"After obtaining [an] optimal solution\"\n- \"if the projected LP is feasible, [the] recovered solution\"\n\nPage 3:\n- \"although it may not be optimal\": add a comma before this excerpt\n- \"can be different from the training LPs, [i.e.,]\"\n- \"Our aim is to [efficiently] obtain a high-quality solution of the test LP\" (move\"efficiently\" from the end)\n- \"outputs [a] projection matrix\"\n- \"is model parameters\" -> \"are the model parameters\"\n- \"Optimal solution\" -> Add \"An\" or \"Any\" in front of the sentence (LPs may have multiple optimal solutions)\n- \"Therefore, [an] appropriate projection\"\n- \"which makes training [more] efficient\"\n\nEquation 6:\n- Should \":\" be \"m\"?", "questions_for_authors": "1) When you say that \"[w]e focus on decreasing the number of variables since the recovered solutions are always feasible for the original LPs\", you are ignoring duality: by decreasing the number of constraints, you would find a dual feasible solution that could provide you an optimality gap. Saying that one is preferable to the other is a bit misleading. Even if not intended, I believe that addressing that by mentioning the case of decreasing the number of constraints, even if not carried out in the paper, would make it more accurate and self-contained. Remember: some people may start working on this from your paper, and such absences may affect their future work. Can you please address this?\n\n2) What do you mean when you say that \"[a]n LP with equality constraints can be transformed into an inequality-form LP if a (trivially) feasible solution is available\"? Why is that even necessary? To be clear, if S = {x : A x = b}, then we can reformulate it as S = {x : A x >= b, A x <= b} = {x : - A x <= - b, A x <= b}. Isn't it?\n\n3) You have both minimization and maximization problems, but the objective ratio always peaks at 1.0 in Figure 3. My understanding is that you take the ratio between the smallest and the largest values between the solution you obtain through the projection and the optimal solution of the LP. Is that the case? If so, can you please clarify that in the paper?\n\n4) Please comment on what I wrote in \"Methods And Evaluation Criteria\".\n\n5) Please comment on what I wrote in \"Other Strengths And Weaknesses\".\n\n6) Please comment on what I wrote in \"Other Comments Or Suggestions\".", "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": "bICKxAHQDG", "reviewer": "Reviewer_c6qe", "summary": "Projection is a key methodology to understand polyhedral structure and reduce dimensionality in linear programming, with recent works proposing it as a heuristic to address large-scale models. The novelty of this work is in applying a machine learning technique to learn effective projection operators. The authors present structural results associated with the sample complexity of the approach, as well as perform experiments assessing the performance against more traditional methods (e.g., PCA).\n\n## update after rebuttal\nThank you for the rebuttal; most of my comments have been addressed. However, I am concerned with the points raised by Reviewer oitp, and prefer to slightly decrease my score as they do not seem to be addressed very clearly.", "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": "We appreciate your positive and constructive comments.\n\n> My major concern is that the authors have not interpreted much of the intricate generalization bound from Section 5.2, which can be difficult to understand. For example, the text could provide a table with a (rough) estimate of the bound for some notion of large-scale LPs, and discuss how it connects to the training sets used in the experimental analysis. That is, provide further evidence of how the bound can be useful to understand the required training set sizes.\n\nThank you for your suggestion. First, we must clarify that our generalization bound, as is often the case in statistical learning theory, merely provides a theoretical guarantee that the generalization error asymptotically approaches zero as the dataset size $D$ increases. We will explicitly state this point in the main text. However, with the recent rise of data-driven approaches to optimization problems, it is likely that increasingly large amounts of data will become available. Therefore, even if our bound appears impractical at present, ensuring its asymptotic convergence remains valuable.\n\nFor reference, we provide the requested table of $\\mathrm{Pdim}$ values corresponding to LP sizes $M, N$ and the reduced dimensionality $K$. Given an allowable generalization error $\\epsilon$ and an upper bound $B$ on the LP's optimal value, an estimate for the dataset size $D$ is approximately $\\frac{B^2}{\\epsilon^2} Pdim$, as discussed in Section 5.2. Here, we used $L=4, K=30, N=500$, and $M=50$.\n\n|$N$|100|200|300|400|500|600|700|800|900|1000|\n|----|----|----|----|----|----|----|----|----|----|----|\n|Pdim|77039526|154435341|232369487|310654224|389199991|467953928|546881065|625956523|705161691|784482117|\n\n|$M$|100|200|300|400|500|600|700|800|900|1000|\n|----|----|----|----|----|----|----|----|----|----|----|\n|Pdim|672945915|1263418755|1874759352|2500683030|3137794899|3783981206|4437800128|5098205390|5764403103|6435770256|\n\n|$K$|10|15|20|25|30|35|40|45|50|\n|----|----|----|----|----|----|----|----|----|----|\n|Pdim|59319255|107887333|165114494|231061207|305746474|389199991|481459510|582566831|692565290|811498343|\n\n>  my minor comment is that I found the problem sizes too small (less then 2,000 variables for packing and 900 nodes for netflow).\n\nWe newly conducted experiments on larger LPs (packing problems with 100,000 variables). The results for a reduced dimension of $K=50$ and number of constraints $M=50$ are shown in the table below. Our method achieved a higher objective ratio than the other methods (Rand and PCA), and significantly reduced computational time compared to solving the original LPs (Full) on these larger instances.\n\nObjective ratio\n|Ours|Rand|PCA|SharedP|FCNN|\n|----|----|----|----|----|\n|0.924|0.230|0.066|0.070|0.257|\n\nComputational time in seconds\n|Full|Ours|Rand|PCA|SharedP|FCNN|\n|----|----|----|----|----|----|\n|23.487|0.055|0.013|0.029|0.063|0.049|\n\n> Could you please provide further interpretation of the generalization bound and training sizes that would be required for certain (carefully selected) LPs?\n\nAs mentioned above, if the training size $D$ is larger than $B^2/\\epsilon^2 Pdim$, the generalization error is approximately bounded by $\\epsilon$. Our theoretical analysis guarantees this decrease in the generalization error by increasing the training size, potentially bringing it arbitrarily close to zero.\n\n> the proof in the Appendix could be extended to be less obscure.\n\nWe will extend the proof in the Appendix to make the proof more accessible to readers.", "claims_and_evidence": "Experiments are thorough and the paper is well written and rigorously formalized.", "methods_and_evaluation_criteria": "In general, every optimization approach involving a heuristic component is suitable to learning, which has fostered several ICML submissions under this same spirit. However, the differential in this paper is the nice methodology to derive an appropriate embedding for the projection matrix (Section 4.2), which I found to be non-trivial and suitable to this application. I also appreciate the paper's theoretical analysis to assess how much data is needed to derive good results.  \n\nThe benchmarks were appropriately selected; in particular, they include recent work in column-randomized methods, which would be the primary methodological approach to consider within this context.", "theoretical_claims": "Theorem 5.1 (the key contribution). It is based on a few seminal results in the area and I believe it is correct to the best of my analysis. However, the text tends to overly summarize much of the theoretical claims, both in the main text as well as in the proofs (e.g., when applying Warren's theorem, or discussing the many assumptions of the theorem in the main text). Although there are space issues in the main text, the proof in the Appendix could be extended to be less obscure.\n\nMy major concern is that the authors have not interpreted much of the intricate generalization bound from Section 5.2, which can be difficult to understand. For example, the text could provide a table with a (rough) estimate of the bound for some notion of large-scale LPs, and discuss how it connects to the training sets used in the experimental analysis. That is, provide further evidence of how the bound can be useful to understand the required training set sizes.", "experimental_designs_or_analyses": "The experimental analysis is thorough. However, my minor comment is that I found the problem sizes too small (less then 2,000 variables for packing and 900 nodes for netflow). For example, state-of-the-art LP solvers can handle problems such as MaxFlow or MinCost-Flow with millions of nodes, especially as networks can be relatively sparse in many practical applications. \n\nAlthough one could always argue that the time limit to solve a problem can be small, the work could better highlight the benefit of projection methods (and learning) if showcasing LPs that could not even be represented in reasonably sized memory.", "relation_to_broader_scientific_literature": "Projection methods are very classical, and their use in multiple heuristic approaches has received growing attention in these last two years. The authors fundamentally improve heuristic performance by incorporating learning.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Could you please provide further interpretation of the generalization bound and training sizes that would be required for certain (carefully selected) LPs?", "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: This paper presents a learning-based method for dimensionality reduction in LPs by generating instance-specific projection matrices. The approach is well-motivated and leverages permutation-invariant neural network architectures to enhance generalization. The paper includes a solid theoretical analysis of the generalization. All reviewers appreciate this work. That being said, the authors should fully address the theoretical concern raised by Reviewer oitp in the revision. Overall, I recommend weak acceptance.
Decision: Accept (poster)