Presolver Error: Quadratic Constraints Marked INFEASIBLE

Dec 2, 2025 by Alex Johnson 57 views

Presolver Incorrectly Marks Feasible Quadratic Constraints as INFEASIBLE

Introduction

In the realm of optimization, presolvers play a crucial role in simplifying models before they are handed over to the main solver. These presolvers aim to reduce the size and complexity of the problem, potentially leading to faster solution times. However, sometimes, the logic within a presolver can lead to unexpected behavior, such as incorrectly identifying a feasible model as infeasible. This article delves into a specific scenario where the presolver in an optimization library, likely ojAlgo, flags a model with quadratic constraints as infeasible, even though a feasible solution exists. We will explore the root cause of this issue, the code snippet that demonstrates the problem, and the implications for optimization practitioners.

The Problem: Feasible Quadratic Constraints Marked as INFEASIBLE

A user encountered a perplexing issue: a model containing quadratic expressions (both quadratic and linear terms) was being incorrectly marked as INFEASIBLE during the presolve phase. This meant that the presolver, instead of simplifying the model, was prematurely concluding that no solution could satisfy the constraints. The interesting part was that when the presolver was disabled, the model solved correctly, indicating that a feasible solution indeed existed. This discrepancy pointed towards a bug or a flaw in the presolver's logic related to quadratic constraints. Specifically, the issue seems to stem from the way the presolver handles the interplay between quadratic and linear terms within the constraints.

Root Cause Analysis: Unveiling the `doCaseN` Method

To pinpoint the exact location of the issue, the user delved into the source code of the optimization library. Through careful examination, they suspected that the problem resided within the doCaseN method and its helper methods, particularly isNegativeOn and isPositiveOn. These methods likely play a role in determining the feasibility of constraints based on the signs of the coefficients and variables involved. The core of the problem seems to lie in how the isNegativeOn method handles expressions with quadratic factors. Let's dissect the relevant code snippet to understand the issue:

boolean isNegativeOn(final Set<IntIndex> subset) {
    if (!this.isAnyQuadraticFactorNonZero()) {
        // ... logic checking linear factors ...
    }
    // If there ARE quadratic factors, the loop is skipped and it returns TRUE
    return true;
}

In this snippet, the isNegativeOn method checks if an expression is negative over a given subset of variables. The logic is designed to handle both linear and quadratic factors. However, the critical flaw lies in the conditional statement. If the expression contains any quadratic factors (i.e., isAnyQuadraticFactorNonZero() returns true), the method skips the checks for linear factors and immediately returns true. This premature return can lead to incorrect conclusions about the feasibility of the constraint. The intention was likely to perform more rigorous checks when quadratic factors are present, but the current implementation effectively bypasses crucial feasibility checks. For instance, consider a constraint like x^2 - x <= 0. The quadratic term x^2 is always non-negative, but the linear term -x can be negative. The feasibility of this constraint depends on the interplay between these terms. By skipping the linear checks, the presolver might incorrectly flag this constraint (and the model) as infeasible.

Demonstrating the Issue: A Standalone Test Case

To further illustrate the problem, the user provided a standalone test case. This test case is invaluable as it allows others to reproduce the issue and verify the fix. The test case involves solving a simple quadratic problem twice: once with the default presolvers enabled and once with them disabled. This side-by-side comparison clearly demonstrates the discrepancy in the results. When the presolver is enabled, the model is incorrectly marked as INFEASIBLE. However, when the presolver is disabled, the model is solved correctly, yielding an OPTIMAL solution. This difference underscores the fact that the presolver is the root cause of the infeasibility issue.

The test case code snippet is as follows:

package org.ojalgo.optimisation;

import java.math.BigDecimal;
import org.ojalgo.optimisation.solver.cplex.SolverCPLEX;


public class OJPresolveTest {

    public static void main(String[] args) {
        // Run with presolver
        System.out.println("--- Run WITH Presolver ---");
        caseN();
    }

    static void caseN() {
        ExpressionsBasedModel model = getModel();

        // 1. Solve with default settings (Presolver enabled)
        Optimisation.Result result = model.minimise();
        System.out.println("State with presolver: " + result.getState());

        // 2. Clear presolvers and solve again
        ExpressionsBasedModel.clearPresolvers();
        // Re-create model to ensure clean state
        model = getModel(); 
        
        Optimisation.Result resultNoPre = model.minimise();
        System.out.println("State without presolver: " + resultNoPre.getState());
    }

    private static ExpressionsBasedModel getModel() {
        ExpressionsBasedModel model = new ExpressionsBasedModel();
        Variable x1 = model.addVariable("x1");
        Variable x2 = model.addVariable("x2");
        Variable x3 = model.addVariable("x3");

        x1.upper(1).lower(0);
        x2.upper(1).lower(0);
        x3.upper(1).lower(0);

        // Create the quadratic expression
        Expression quadExpr = model.addExpression("QuadraticExpression");
        quadExpr.set(x1, x1, 0.1);
        quadExpr.set(x2, x2, 0.1);
        quadExpr.set(x3, x3, 0.1);
        quadExpr.set(x1, -0.0649319296487038);
        quadExpr.set(x2, -0.035049269354063314);
        quadExpr.set(x3, -0.054569655903981634);

        // This constraint causes the issue during presolve
        quadExpr.upper(new BigDecimal("-0.02"));
        
        return model;
    }
}

This code defines a simple optimization model with three variables (x1, x2, x3) and a quadratic constraint. The constraint involves quadratic terms (e.g., x1*x1) and linear terms (e.g., x1). The upper bound of the quadratic expression is set to -0.02. When this model is solved with the presolver enabled, it incorrectly reports an infeasible state. However, when the presolver is disabled, the solver finds an optimal solution.

Implications and Mitigation Strategies

This issue has significant implications for users of the optimization library. If the presolver incorrectly flags feasible models as infeasible, it can lead to wasted time and effort in debugging the model. Users might mistakenly believe that their model has inherent issues when the problem lies within the presolver itself. To mitigate this issue, users can adopt the following strategies:

Disable the presolver: If you suspect that the presolver is causing issues, try disabling it and solving the model directly. This can help you determine if the problem lies within the presolver or the model itself.
Carefully examine quadratic constraints: Pay close attention to constraints involving quadratic expressions, especially those with both quadratic and linear terms. These constraints are more susceptible to issues with presolver logic.
Report the issue: If you encounter this problem, report it to the developers of the optimization library. Providing a minimal reproducible example (like the test case in this article) can greatly assist in debugging and fixing the issue.
Check for updates: Regularly check for updates to the optimization library. Bug fixes and improvements to presolver logic are often included in new releases.

Conclusion

The case of the presolver incorrectly marking feasible quadratic constraints as infeasible highlights the importance of rigorous testing and debugging in optimization software. Presolvers, while valuable for improving performance, can sometimes introduce subtle bugs that lead to incorrect results. By understanding the potential pitfalls and adopting appropriate mitigation strategies, users can minimize the impact of such issues. The detailed analysis and the standalone test case provided in this article serve as a valuable resource for both users and developers of optimization libraries. It underscores the need for careful consideration of the interplay between linear and quadratic terms in constraints and the potential for presolver logic to misinterpret these relationships. Remember to always validate your optimization results and be prepared to investigate further if you encounter unexpected behavior. For further reading on optimization and constraint programming, consider exploring resources from trusted websites such as NEOS Guide.