Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Soundness bug in QF_LIA #2871

Closed
numairmansur opened this issue Jan 20, 2020 · 14 comments
Closed

Soundness bug in QF_LIA #2871

numairmansur opened this issue Jan 20, 2020 · 14 comments

Comments

@numairmansur
Copy link

Hi,
Z3 returns wrong answer on the following files.
1.smt2
2.smt2.zip
3.smt2.zip
4.smt2.zip
5.smt2.zip
6.smt2.zip
7.smt2.zip
8.smt2.zip
9.smt2.zip
10.smt2.zip

Every formula at each level in the assertion stack is satisfiable. But z3 would return unsat at some level. For example for file 1.smt2, i get:

sat
sat
sat
sat
sat
sat
unsat
sat
sat
sat
sat

CVC4 gives me:

sat
sat
sat
sat
sat
sat
sat
sat
sat
sat
sat

OS:
NAME="Ubuntu"
VERSION="16.04.5 LTS (Xenial Xerus)"

$ git log -1
commit 321bad2
Author: Christoph M. Wintersteiger cwinter@microsoft.com
Date: Mon Jan 20 17:06:35 2020 +0000
Fix for implicit consts in FPA models. Fixes #2865.

@NikolajBjorner
Copy link
Contributor

Are these the smallest repros possible?

@numairmansur
Copy link
Author

I am sorry they actually aren't. I can run the minimiser and edit the PR with smaller files.

@numairmansur
Copy link
Author

Here are some relatively small examples:

small1.smt2
small2.smt2
small3.smt2
small4.smt2

@NikolajBjorner
Copy link
Contributor

@levnach The master branch creates a lia conflict with empty explanation. This seems to have been fixed in the levnach branch, or at least I don't easily repro.

@NikolajBjorner
Copy link
Contributor

in the gomory cut code, the case where a non-basic variable has integer assignment there is no tracking of the explanations on the bounds of that variable. Seems it is necessary to add explanations, as sketched below.

 if (p.coeff().is_int()) {
                    // m_fj will be zero and no monomial will be added
                    if (at_lower(j)) {
                        m_ex.push_justification(column_lower_bound_constraint(j));            
                    }
                    if (at_upper(j)) {
                        m_ex.push_justification(column_upper_bound_constraint(j));
                    }
                    continue;
                }

@levnach
Copy link
Contributor

levnach commented Jan 21, 2020

Integrated to levnach fork.

@NikolajBjorner
Copy link
Contributor

not really, it is #if 0'ed out at the moment. Can you check if just one bound is required and otherwise check correctness?

@levnach
Copy link
Contributor

levnach commented Jan 21, 2020

The Gomory cut is based on a precondition, as https://lara.epfl.ch/w/_media/projects:simplexdplltreport.pdf points out, that each non-basic variable is not free and has a value at its lower or upper bound. Therefore, at least one of the bound constraints needs to be provided; and the new code does it.
I also ran a performance test on QF_LIA: it did quite well.

@NikolajBjorner
Copy link
Contributor

I am not sure about this being the real issue. The legacy solver also skips this case and integral columns shouldn't contribute to non-integrality of the base variables.

Running on small1.smt2 it looks like the offending row does not have the property that the basic variable is the sum of non-basic variables. This is an assumption for applying the cut.
What is a quick way to check this pre-condition (check that the row evaluates to 0).

@levnach
Copy link
Contributor

levnach commented Jan 22, 2020

lar_solver::row_is_correct(unsigned i), where i is the index of the row.

@NikolajBjorner
Copy link
Contributor

Right, the rows are not correct and this is why gomory provides the wrong result. It assumes the rows are correct. I pushed a filter on incorrect rows, but a root cause understanding of whether this is legal would be useful.

@NikolajBjorner
Copy link
Contributor

ad965ac

@levnach
Copy link
Contributor

levnach commented Jan 23, 2020

The row becomes incorrect during the "find_cube()" column shifting. Currently there is no indication in lar_solver that this has happened. I should track it and restore the tableau in this case.

@levnach levnach reopened this Jan 23, 2020
@NikolajBjorner
Copy link
Contributor

we should be good now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants