Solver falsely finds solution to problem with impossible constraints

[Terence Lam]

Hi,

I'm running into an issue with GLOP where one of my solutions being returned is not possible given the constraints I entered. I am using the python library. My hypothesis was the solver was returning a bad solution, so I isolated the constraints of the linear problem that I knew were being violated, and added a third constraint which set the value of the variable in question to the bad solution that was found. The result was the solver was not failing as expected. 

from ortools.linear_solver import pywraplp

import math

def main():

    solver = pywraplp.Solver('SolveStigler',

                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

    objective = solver.Objective()

    objective.SetMaximization()

    indicator = solver.IntVar(0.0, 1.0, 'indicator')

    value = solver.NumVar(0.0, math.inf, 'value')

    M = 10000000

    m = 1

    bad_value = 0.5

    # Constraint is value >= m - M * (1 - indicator)

    # Equivalent to value - M * indicator >= m - M

    constraint1 = solver.Constraint(m - M, math.inf)

    constraint1.SetCoefficient(value, 1.0)

    constraint1.SetCoefficient(indicator, -M)

    # Constraint is value <= M * indicator or value - M * indicator <= 0

    constraint2 = solver.Constraint(-math.inf, 0.0)

    constraint2.SetCoefficient(value, 1.0)

    constraint2.SetCoefficient(indicator, -M)

    # Constraint is we'll set value to have to equal to 0.5

    constraint3 = solver.Constraint(bad_value, bad_value)

    constraint3.SetCoefficient(value, 1.0)

    status = solver.Solve()

    if status == solver.OPTIMAL:

        print("{} >= {} - {} * (1 - {})".format(value.solution_value(), m, M, indicator.solution_value()))

        left_side = value.solution_value()

        right_side = m - M * (1 - indicator.solution_value())

        print(left_side >= right_side)

    else:

        print('expectedly failed')

if __name__ == '__main__':

  main()

In this problem I was leveraging the technique of setting up an indicator function as a constraint (https://math.stackexchange.com/questions/2220355/involving-indicator-function-as-a-constraint-in-a-lp-problem). Since I am setting up the constraint such that the indicator should be set to 0 if value is less than m, as well as the second constraint that the value is bound by the indicator * M, then the solution value of 0.5 should not be possible. However, GLOP sets value to 0.5 as the solution. When I print out the results of the first constraint, it is clearly wrong, as the output is

0.5 >= 1 - 10000000 * (1 - 1.0)

This appears to be a bug in the linear solver when the value of m and bad_value are small because if I set bad_value to 99 and m to 100, the solver correctly fails to find a solution that satisfies the constraints. The margin for this error seems to diminish as I set the numbers larger and larger.

I am using the following version of or tools:

https://pypi.python.org/packages/11/a9/1dbed7a593e3aa9164f079afa27528c58bfa17dc3fdc22c1ee46a5a26d8d/ortools-6.6.4656-cp36-cp36m-manylinux1_x86_64.whl#md5=9a9d679069b38735ea18eb17ee181c18; sys_platform == 'linux'

Is this a known issue? If not, can this be looked at? Currently we have to work around this issue by filtering out these cases as bad output.

Thanks,

Terence

[Laurent Perron]

Glop is not a MIP solver, just a simplex. 

It completely ignore the integrality constraints of variables.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Terence Lam]

Hi Laurent,

I am a little confused now, as the documentation https://developers.google.com/optimization/mip/integer_opt describes CBC_MIXED_INTEGER_PROGRAMMING as mixed integer programming. I am defining the indicator variable as an integer variable, from 0 to 1, and it is being solved as such. The issue is the value cannot be 1 in this case. 

Are you saying the implementation (simplex) means it is not actually mixed integer programming? Why is the behavior working in some cases (the constraints are not ignored), but not others?

Thanks,

Terence

[Laurent Perron]

You said GLOP at the beginning of your mail :-)

CBC is a MIP solver.

I will have a look.

--

--Laurent

[Terence Lam]

Oh yes, sorry about that typo! Thank you, that's much appreciated.

Terence

[Laurent Perron]

Just to be clear, 

MIP solver have an internal precision of 1e-4 to 1e-6.

so 100000 * x + 1 == 100000 accepts a valid solution x == 1.

Is it what you are seing?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Terence Lam]

The problem doesn't seem to be precision based, because the invalid solution is off by much more than the implied tolerance of the precision of 1e-4 to 1e-6. Setting x to 0.5 should not be a valid solution for this problem, but the solver thinks it is. Here, x needs to be either 0, or >= 1.

As mentioned, if I change the numerical values of the parameters, then the solver behaves as expected. For example if I set m to 100 and x to 99, then the solver correctly fails to find a solution.

[Terence Lam]

Hi Laurent,

Were you able to find anything on this?

Thanks,

Terence

[Laurent Perron]

I am on vacation. I will look into it next week.

[Laurent Perron]

Once again, 

MIP solvers checks solutions with an epsilon on each variable.

Thus

 value >= m - M * (1 - indicator)

is actually 

value >= 1 - 10000000(1 - indicator)

so imagine indicator is 1 - epsilon

this translate to value >= 1 - 10000000 * epsilon.

In practise, epsilon <= 1e-4 to 1e-6

This is perfectly valid.

Furthermore, we have additional code that checks all solutions against the constraint of the model with this epsilon tolerance.

So, even if I do not trust CBC, I do trust the checker code.

To conclude, this is working as intended w.r.t MIP solvers.

If you want exact arithmetic, you need to use only integer variables, and the CP-SAT solver.

--Laurent

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00