ILP模型预处理及构建阶段内存优化技术问询

Hey there! Let's tackle your two ILP questions with the example model you shared to make things clear and practical.

Absolutely! Preprocessing is a standard, highly recommended step for ILP models—it can drastically reduce model size, speed up solving, and even reveal infeasibility early. Let's use your example to walk through this:

min 2x1 - 5x2 + 3x3 + 10x4
s.t.
x1 + x2 + x3 = 15 (1)
x1 ≤ 7 (2)
x2 ≤ 3 (3)
x3 ≤ 5 (4)
x4 > 1 (5)

Looking at constraints (1)-(4):

• The sum of the upper bounds for x1, x2, x3 is 7+3+5=15, which exactly matches the right-hand side of the equality constraint (1).
• This means the only feasible values for these variables are fixed: x1=7, x2=3, x3=5. Any deviation would break either the equality or one of the upper-bound constraints.

For constraint (5): Since we're dealing with an ILP (integer variables), x4 > 1 translates directly to x4 ≥ 2 (strict inequalities aren't typically supported by ILP solvers, and integers can't be between 1 and 2 anyway).

After preprocessing, your model simplifies drastically:

• Fixed variables are substituted into the objective function: 2*7 -5*3 +3*5 +10*x4 = 14 -15 +15 +10x4 = 14 +10x4
• Only one variable (x4) remains, with a single constraint: x4 ≥ 2 (integer)
• The optimal solution is immediately obvious: x4=2, with an objective value of 14 + 20 = 34.

Yes, there are both manual and tool-based ways to simplify your model while building it, which will cut down on memory usage. Here are key strategies, again using your example:

• Fix variables early: As we saw in the preprocessing step, if you can identify variables that have only one feasible value during model construction, substitute them directly into the objective and constraints instead of keeping them as variables. This reduces the number of variables and constraints in your model.
• Remove redundant constraints: After substituting fixed variables, constraints like (2), (3), (4) in your example become redundant (they're now equalities that are already satisfied), so you can omit them entirely.
• Avoid strict inequalities: Convert constraints like x4 >1 to x4 ≥2 during construction—this aligns with ILP solver capabilities and avoids unnecessary complexity.
• Leverage sparse matrix best practices: You mentioned using sparse matrices, so make sure you're only storing non-zero coefficients when building the model. Dense matrices waste memory by storing zeros, which are irrelevant for most ILP models.
• Use built-in solver preprocessing: Most modern ILP solvers (e.g., Gurobi, CPLEX, PuLP) include automatic preprocessing routines that run before solving. These tools can automatically fix variables, remove redundancies, merge constraints, and more. You can enable these options in your code (often by setting a parameter like Preprocessing=1 or similar) to let the solver handle simplification during the build/solve pipeline.

By applying these steps, you'll reduce the model's memory footprint significantly, which should resolve out-of-memory issues.

内容的提问来源于stack exchange，提问作者Christoph