Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems

We appreciate your positive and constructive comments.

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.

Thank 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.

For 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$.

my minor comment is that I found the problem sizes too small (less then 2,000 variables for packing and 900 nodes for netflow).

We 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.

Objective ratio

Computational time in seconds

Could you please provide further interpretation of the generalization bound and training sizes that would be required for certain (carefully selected) LPs?

As 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.

the proof in the Appendix could be extended to be less obscure.

We will extend the proof in the Appendix to make the proof more accessible to readers.

We appreciate your positive and constructive comments.

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.

We compared with the proposed NN with random initialization and no training. The 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.

Packing: Objective ratio

MaxFlow: Objective ratio

MinCostFlow: Objective ratio

Figure 3 is not very clear

We will make the figure more clearly.

Some comments on the mathematical optimization side do not seem entirely accurate

We will revise the sentences according to your comments.

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?

Thank 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.

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?

We 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.

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?

In 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.

We appreciate your constructive comments.

it lacks a clear comparison with existing MILP generation methods to highlight its distinct advantages.

Since 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.

MILP 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.

proofs appear correct, though their practical implications could be further clarified.

If 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.

Additionally, the practical robustness of the learned projection matrices, especially when encountering out-of-distribution LP instances, could have been further analyzed.

We have analyzed the robustness of our learned neural network-based model in Figure 5 (p.8) and Table 1 (p.14 in the appendix) when encountering out-of-distribution LP instances.

In 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. In 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).

Table 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.

included more discussions on practical deployment

On 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.

Potentially, we may be able to use (MI)LP instance generation techniques for synthesizing LPs. We will add discussions on practical deployment.

generalization to MILPs

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. We will add discussions on generalization to MILPs.

We appreciate your constructive comments.

the authors only show the generalization bound but do not show the optimality of this model.

Since 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.

Our 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.

It would be better to apply this new method to some problems for the competition of commercial solvers.

We 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).

Objective ratio

Computational time in seconds

I am not familiar with using NN to reduce dimensionality for optimization problems.

To our knowledge, there is no existing work that uses NN to reduce dimensionality for optimization problems.

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.

We 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.

Column 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.