ojAlgo thinks infeasible solution is feasible

[voun]

I have a binary problem (similar to the assignment problem) with a lot of equal 1 constraints which I am trying to maximize using ExpressionBasedModel. The solver generates an integer solution in which none of the variables for a certain constraint is chosen, when in fact it should choose exactly one of these. Increasing the precision and scale in model.options.feasibility seems to solve the problem but I have a feeling that this is not a good idea. What confuses me is why ojAlgo thinks the generated solution is feasible when in fact it clearly is not.

Thanks in advance

[apete]

If you get a Result with state OPTIMAL but a solution that is in fact infeasible, then that's a problem. If possible please construct a junit test that reproduce the problem.

However, model.options.feasibility is a configurable options because it's been anticipated that in some cases this is something you may have to control. Not sure why/how it affects the behaviour in your case. It is primarily used in the presolve functionality of ExpressionsBasedModel.

[voun]

Thanks for the quick response. Here is an example:

`
val model = ExpressionsBasedModel()

    val varA1 = model.addVariable().weight(-4836.0).binary()
    val varA2 = model.addVariable().weight(-4824.0).binary()
    val varB1 = model.addVariable().weight(1921.0).binary()
    val varB2 = model.addVariable().weight(1929.9).binary()
    val varC1 = model.addVariable().weight(2517.0).binary()
    val varC2 = model.addVariable().weight(2526.51).binary()
    val varD1 = model.addVariable().weight(270.0).binary()
    val varD2 = model.addVariable().weight(267.5).binary()

    varA1.setValue(0)
    varA2.setValue(1)
    varB1.setValue(0)
    varB2.setValue(1)
    varC1.setValue(0)
    varC2.setValue(1)
    varD1.setValue(1)
    varD2.setValue(0)

    val constraintA = model.addExpression().level(1)
    constraintA.set(varA1, 1)
    constraintA.set(varA2, 1)
    val constraintB = model.addExpression().level(1)
    constraintB.set(varB1, 1)
    constraintB.set(varB2, 1)
    val constraintC = model.addExpression().level(1)
    constraintC.set(varC1, 1)
    constraintC.set(varC2, 1)
    val constraintD = model.addExpression().level(1)
    constraintD.set(varD1, 1)
    constraintD.set(varD2, 1)

    val res = model.maximise()
    println(res)
    println(model.validate(res))`

[voun]

The state is OPTIMAL but the validation says that the solution is not valid, which is true since none of A1 and A2 are chosen. I am using version 51.0.0

[apete]

Great that you were able to reproduce the problem with a small model, but next time give me Java code (including junit assertions). An alternative way to supply a model is with a model file model.writeTo(File);

The key problem seems to be that the MIP solver generates a slightly infeasible subproblem for the LP solver, and the LP solver fails to handle this. Some sort of numerical bug in the LP solver. It ends up with a solution that is completely wrong, but it is an integer solution. (The MIP accepts that the LP states the solution to be optimal and only checks if it is an integer solution or not.)

The optimal solutions to the MIP and the relaxed LP are the same, and it is also that solution that is given as the initial solution. This is part of what's causing the problem (because of how ojAlgo works).

To work around the problem you can either:

1. Don't set the initial solution
2. Change the MIP gap configuration:
   IntegerStrategy.DEFAULT.withGapTolerance(...);
   It seems any value other than what happens to be the default avoids the problem.

[voun]

Your suggestions indeed seem to solve the problem for this test case. However, I am solving the same type of problem multiple times with different parameter values. If I don't set the initial solution or change the gap tolerance, I guess there is no guarantee that this problem will never occur again?

My current approach is to validate the final solution and if it is not valid then just use the initial solution.

[apete]

By all means, validate the solutions you get. Configuring the MIP strategy is generally a good idea. You should do it.