SCIP求解ILP时整数变量结果偏差远超e-06的问题咨询

I’ve run into similar precision issues with SCIP when solving integer linear programs, so let’s break down why this might be happening and how to boost your model’s robustness:

Possible Causes #

• Poor Numerical Scaling: If your model has coefficients, variable bounds, or constraint right-hand sides with wildly varying magnitudes (e.g., some values are 1e9 while others are 1e-9), SCIP’s floating-point calculations can accumulate significant errors. This is one of the most common culprits for large deviations in integer solutions.
• Loose Default Tolerances: SCIP’s default feasibility thresholds (like int/feastol) work for most cases, but models with extreme numerical characteristics might need tighter bounds to enforce integer correctness.
• Model Definition Oversights: Accidentally defining an integer variable as continuous, or using unnecessary floating-point values in constraints, can introduce avoidable precision drift.

Fixes to Improve Robustness #

1. Rescale Your Model
   The most impactful fix is to normalize all values to a consistent magnitude. For example, if your constraints use values in the range 1e-3, multiply all coefficients, bounds, and right-hand sides by 1000 to work with integers. After solving, divide the results back by 1000. This eliminates tiny floating-point increments that add up over complex calculations.

2. Tighten SCIP’s Precision Parameters
   Adjust key solver settings to enforce stricter checks for integer feasibility. Add these lines after initializing your model in Python:

   from pyscipopt import Model
   model = Model()
   # Tighten tolerance for integer feasibility
   model.setRealParam("int/feastol", 1e-9)
   # Adjust general numerical epsilon for solver calculations
   model.setRealParam("numerics/epsilon", 1e-10)
   

   Note: Tighter tolerances may increase solve time, so test to balance performance and precision.

3. Explicitly Round Results (With Validation)
   After retrieving the solution, manually round integer variable values to the nearest integer, then verify the rounded values still satisfy all constraints. Example:

   sol = model.getBestSol()
   x_val = sol.getVal(x)
   # Round to nearest integer
   x_int = round(x_val)
   # Optional: Validate the rounded value doesn't deviate excessively
   assert abs(x_int - x_val) < 1e-3, "Rounded value is too far from solver output"
   

4. Audit Your Model Definition

   • Double-check that all integer variables are defined with vtype="I" (or "B" for binary):

     x = model.addVar(name="x", vtype="I")
     

   • Use integer values in constraints where possible (e.g., x + y <= 5 instead of x + y <= 5.0) to avoid floating-point representation errors.

5. Enable Numerical Stabilization Features
   SCIP has built-in settings to handle numerical instability. Try enabling these:

   model.setBoolParam("numerics/stallingdetect", True)
   model.setBoolParam("numerics/preferbinary", True)
   

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