sat4j issueshttps://gitlab.ow2.org/sat4j/sat4j/-/issues2018-07-07T05:11:54Zhttps://gitlab.ow2.org/sat4j/sat4j/-/issues/138Fix WBO issue found during PB 20162018-07-07T05:11:54ZDaniel Le BerreFix WBO issue found during PB 2016A problem with WBO has been discovered during PB16. It seems that the top costs are ignored.A problem with WBO has been discovered during PB16. It seems that the top costs are ignored.2.3.6https://gitlab.ow2.org/sat4j/sat4j/-/issues/136Incorrect answer with PB Solver2018-07-07T05:11:54ZAnithaIncorrect answer with PB SolverI am seeing a strange issue with solving a PBO problem using SAT4J: version NIGHTLY.v20151101
Attached are 2 opb files: min-nonbuggy.opb and min.opb
Differences between the files: Both files differ from line 18 onwards. "min.opb" is an extension of min-nonbuggy.opb. Note that both files have same objective function that needs to be minimized.
The first file ("min-nonbuggy.opb") returns correct answer with optimum value as "4" with x12=0, x14 = 0 and x17=0. I agree with this answer. I also verified this by manually solving the constraints and objective function.
The second file ("min.opb") returns answer with optimum value as "5" with x12=1, x14=0 and x17=0. I think this is wrong.
(I am interested in values that appear in objective function only)
This is quite surprising given that - no additional constraint involving "x12" appears in "min.opb". So x12 should be 0 regardless of value of x17. Isn't it? Why is the answer returned as x12=1?
I am seeing a strange issue with solving a PBO problem using SAT4J: version NIGHTLY.v20151101
Attached are 2 opb files: min-nonbuggy.opb and min.opb
Differences between the files: Both files differ from line 18 onwards. "min.opb" is an extension of min-nonbuggy.opb. Note that both files have same objective function that needs to be minimized.
The first file ("min-nonbuggy.opb") returns correct answer with optimum value as "4" with x12=0, x14 = 0 and x17=0. I agree with this answer. I also verified this by manually solving the constraints and objective function.
The second file ("min.opb") returns answer with optimum value as "5" with x12=1, x14=0 and x17=0. I think this is wrong.
(I am interested in values that appear in objective function only)
This is quite surprising given that - no additional constraint involving "x12" appears in "min.opb". So x12 should be 0 regardless of value of x17. Isn't it? Why is the answer returned as x12=1?
https://gitlab.ow2.org/sat4j/sat4j/-/issues/128PB solver finds wrong optimal solution when a unit clause appears in the inpu...2018-07-07T05:11:53ZDaniel Le BerrePB solver finds wrong optimal solution when a unit clause appears in the input fileWhen running the functional tests on PB12 benchmarks, the solvers return incorrectly on a few benchmarks, e.g. normalized-PB06/OPT-SMALLINT/submitted-PB06/manquiho/bounded_golomb_rulers/normalized-bogr_7.opb.
Those benchmarks contain unit clauses.
It might be the case that a propagation by one learned constraint is removed incorrectly (e.g. a PB constraint propagates x which is also a unit clause).
We may need to check in the PB constraint when we remove it if the literals are not propagated by a unit clause, or simply to remove that literal from the PB constraint.When running the functional tests on PB12 benchmarks, the solvers return incorrectly on a few benchmarks, e.g. normalized-PB06/OPT-SMALLINT/submitted-PB06/manquiho/bounded_golomb_rulers/normalized-bogr_7.opb.
Those benchmarks contain unit clauses.
It might be the case that a propagation by one learned constraint is removed incorrectly (e.g. a PB constraint propagates x which is also a unit clause).
We may need to check in the PB constraint when we remove it if the literals are not propagated by a unit clause, or simply to remove that literal from the PB constraint.https://gitlab.ow2.org/sat4j/sat4j/-/issues/127OPBSolver exports files with empty objectives2018-11-12T16:07:10ZGhost UserOPBSolver exports files with empty objectivesI tried the OPBSolverDecorator for exporting .opb files. In some cases, my objective function is empty because I am solving a pure SAT instance (using the PB solver because of "at most 1"-constraints).
In these cases, the OPBSolverDecorator outputs a .opb format that the command line sat4j-pb.jar does not understand. The text opb file then contains the following line:
min: ;
This is because the "toString()" method does a null-check on the objective function, but it does no empty-check on it. I think my fix for it is suboptimal:
```
if (this.obj != null) {
String objStr = obj.toString();
if (objStr.trim().length() > 0) {
tmp.append("\n");
tmp.append("min: ");
tmp.append(this.obj);
tmp.append(";");
}
}
```I tried the OPBSolverDecorator for exporting .opb files. In some cases, my objective function is empty because I am solving a pure SAT instance (using the PB solver because of "at most 1"-constraints).
In these cases, the OPBSolverDecorator outputs a .opb format that the command line sat4j-pb.jar does not understand. The text opb file then contains the following line:
min: ;
This is because the "toString()" method does a null-check on the objective function, but it does no empty-check on it. I think my fix for it is suboptimal:
```
if (this.obj != null) {
String objStr = obj.toString();
if (objStr.trim().length() > 0) {
tmp.append("\n");
tmp.append("min: ");
tmp.append(this.obj);
tmp.append(";");
}
}
```https://gitlab.ow2.org/sat4j/sat4j/-/issues/126How do I do an industry standard export for Partial Weighted MaxSat problems?2018-07-07T05:11:53ZGhost UserHow do I do an industry standard export for Partial Weighted MaxSat problems?I have filed this as question, but it might result in a change request:
I am using the WeightedMaxSatDecorator for solving Partial Weighted MaxSat problems. Most constraints are in (weighted) cnf, but there are some cardinality constraints. If I do not want to convert them to CNF constraints, I cannot export a wcnf file but must export something other.
I think the .opb format is suitable for that case. Am I right?
I tried to create .opb output using the OPBStringSolver or the LPStringSolver. Both have the same problem:
The WeightedMaxSatDecorator calls the method "registerLiteral(int p)" on the decorated solver. Since both the OPBStringSolver and the LPStringSolver extend the DimacsStringSolver, the method DimacsStringSolver.registerLiteral(int p) is called, which throws an UnsupportedOperationException.
So, if one of these StringSolvers is suitable for my problem: Would it be a solution to override the method in that suitable solver so that it does not do anything?
An, if none of these StringSolvers is suitable: Is there another way of exporting all input that the WeightedMaxSatDecorator got into a standard file format?I have filed this as question, but it might result in a change request:
I am using the WeightedMaxSatDecorator for solving Partial Weighted MaxSat problems. Most constraints are in (weighted) cnf, but there are some cardinality constraints. If I do not want to convert them to CNF constraints, I cannot export a wcnf file but must export something other.
I think the .opb format is suitable for that case. Am I right?
I tried to create .opb output using the OPBStringSolver or the LPStringSolver. Both have the same problem:
The WeightedMaxSatDecorator calls the method "registerLiteral(int p)" on the decorated solver. Since both the OPBStringSolver and the LPStringSolver extend the DimacsStringSolver, the method DimacsStringSolver.registerLiteral(int p) is called, which throws an UnsupportedOperationException.
So, if one of these StringSolvers is suitable for my problem: Would it be a solution to override the method in that suitable solver so that it does not do anything?
An, if none of these StringSolvers is suitable: Is there another way of exporting all input that the WeightedMaxSatDecorator got into a standard file format?https://gitlab.ow2.org/sat4j/sat4j/-/issues/125CP solver provides incorrect results when performing Lexico-optimization2018-07-07T05:11:53ZDaniel Le BerreCP solver provides incorrect results when performing Lexico-optimizationOnce issue #124 has been fixed, the parallel solver res+cp solver still provides a wrong solution (ignore unit clauses in 3 cases) or wrong optimum (in 10 cases) out of the 2688 benchmarks.
It is likely that such issue is related to former #113 issue, i.e. incorrect handling of unit clause removal in case of unsatisfiability.Once issue #124 has been fixed, the parallel solver res+cp solver still provides a wrong solution (ignore unit clauses in 3 cases) or wrong optimum (in 10 cases) out of the 2688 benchmarks.
It is likely that such issue is related to former #113 issue, i.e. incorrect handling of unit clause removal in case of unsatisfiability.https://gitlab.ow2.org/sat4j/sat4j/-/issues/122Allow the definitions of levels of the heuristic2018-07-07T05:11:53ZDaniel Le BerreAllow the definitions of levels of the heuristicIn some cases, domain knowledge allow the user of the solver to rank the variables to guide the solver.
It would be nice to provide a way to provide such information to Sat4j users.In some cases, domain knowledge allow the user of the solver to rank the variables to guide the solver.
It would be nice to provide a way to provide such information to Sat4j users.3.0https://gitlab.ow2.org/sat4j/sat4j/-/issues/102API for using an OPB string spec2018-07-07T05:11:52ZMihai BarbuceanuAPI for using an OPB string specHi Daniel,
Is there any API available that would allow me to read an OPB spec as a string (which I have stored previously in a database, for example) and run the PB solvers to get a solution? I would like to do this without going through the command line.
Many Thanks,
MihaiHi Daniel,
Is there any API available that would allow me to read an OPB spec as a string (which I have stored previously in a database, for example) and run the PB solvers to get a solution? I would like to do this without going through the command line.
Many Thanks,
Mihaihttps://gitlab.ow2.org/sat4j/sat4j/-/issues/93Find a way to factorize the various settings for the solvers2018-07-07T05:11:52ZDaniel Le BerreFind a way to factorize the various settings for the solversThe PB, MAXSAT and SAT launchers have their own code for configuring the solvers.
As such, it is quite tedious to update all the launchers when a new feature is added to the library (e.g. internal optimization).
The PB launcher does not have any dependency to commons CLI, so is a bit different from the two others.
However, we need to find a central class to perform the configuration of solvers: note that in sat package, the configuration of the solvers is done twice, one in DetailedCommandPanel and one in Launcher.
The PB, MAXSAT and SAT launchers have their own code for configuring the solvers.
As such, it is quite tedious to update all the launchers when a new feature is added to the library (e.g. internal optimization).
The PB launcher does not have any dependency to commons CLI, so is a bit different from the two others.
However, we need to find a central class to perform the configuration of solvers: note that in sat package, the configuration of the solvers is done twice, one in DetailedCommandPanel and one in Launcher.
https://gitlab.ow2.org/sat4j/sat4j/-/issues/92Add documents on Sat4j web site to conform with OW2 mature project requirements2018-07-07T05:11:52ZDaniel Le BerreAdd documents on Sat4j web site to conform with OW2 mature project requirementsA few documents are mandatory according to the Ow2 mature project requirements:
- code convention guidelines
- SVN guidelines
- Ow2 dashboardA few documents are mandatory according to the Ow2 mature project requirements:
- code convention guidelines
- SVN guidelines
- Ow2 dashboardhttps://gitlab.ow2.org/sat4j/sat4j/-/issues/74Make Sat4j easily usable in Scala2018-05-11T12:15:13ZDaniel Le BerreMake Sat4j easily usable in ScalaScala has some conventions for methods and fields that are different from usual Java ones.
It might be a good idea to complete the current API to make the integration of Sat4j inside scala programs seemingless.
Scala has some conventions for methods and fields that are different from usual Java ones.
It might be a good idea to complete the current API to make the integration of Sat4j inside scala programs seemingless.
3.0https://gitlab.ow2.org/sat4j/sat4j/-/issues/73Make Sat4j easily embeddable with JVM language2018-05-11T12:15:13ZDaniel Le BerreMake Sat4j easily embeddable with JVM languageWe use the Java code conventions in Sat4j.
Those conventions are not necessarily used in other JVM languages (such as Scala and Groovy for instance).
We would like to make Sat4j the library of choice for all JVM languages.
Such it might be needed to add/rename some methods of the api to make them easily usably in those languages.We use the Java code conventions in Sat4j.
Those conventions are not necessarily used in other JVM languages (such as Scala and Groovy for instance).
We would like to make Sat4j the library of choice for all JVM languages.
Such it might be needed to add/rename some methods of the api to make them easily usably in those languages.3.0https://gitlab.ow2.org/sat4j/sat4j/-/issues/54Dispatch lower bounding to all parts of Sat4j2018-05-11T12:15:13ZDaniel Le BerreDispatch lower bounding to all parts of Sat4jLower bounding is available in the API of Sat4j 2.3.1.
The next step is now to provide that feature on the command line of all optimization tools.Lower bounding is available in the API of Sat4j 2.3.1.
The next step is now to provide that feature on the command line of all optimization tools.https://gitlab.ow2.org/sat4j/sat4j/-/issues/53Allow both lower and upper bounding on the ManyCore solvers.2018-05-11T12:15:13ZDaniel Le BerreAllow both lower and upper bounding on the ManyCore solvers.We already shipped parallel solvers with both Resolution and Cutting Planes. It would be nice to have both Lower Bound and Upper Bounding done in parallel. This is not possible currently, since parallel optimizers do cooperate to compute the best upper bound currently. The parallelization need to move to a higher level to allow this.
We already shipped parallel solvers with both Resolution and Cutting Planes. It would be nice to have both Lower Bound and Upper Bounding done in parallel. This is not possible currently, since parallel optimizers do cooperate to compute the best upper bound currently. The parallelization need to move to a higher level to allow this.
https://gitlab.ow2.org/sat4j/sat4j/-/issues/46Add an API to reduce the value of the objective function in case of optimization2018-05-11T12:15:13ZDaniel Le BerreAdd an API to reduce the value of the objective function in case of optimizationWhen we do optimization using strengthening, we decrease the value of an atMostK constraint, corresponding to the best upper bound of the objective function.
When using CNF translation of AtMostK, this is done only by setting some boolean variables.
It is currently not easy to know when that value is reduced, thus it is not possible to take advantage of the CNF translation.
When we do optimization using strengthening, we decrease the value of an atMostK constraint, corresponding to the best upper bound of the objective function.
When using CNF translation of AtMostK, this is done only by setting some boolean variables.
It is currently not easy to know when that value is reduced, thus it is not possible to take advantage of the CNF translation.
https://gitlab.ow2.org/sat4j/sat4j/-/issues/28Allow easy explanation for OPB file2018-05-11T12:15:13ZDaniel Le BerreAllow easy explanation for OPB fileCurrently, using ExplainPB on an opb file does not provide an explanation of inconsistency with the explain method because there are no "names" associated with the constraints.
One should allow to use constraint numbers in that case, to easily display the unsat core in terms of constraints number (might not be that good because an equality constraint is splitted into 2 constraints).Currently, using ExplainPB on an opb file does not provide an explanation of inconsistency with the explain method because there are no "names" associated with the constraints.
One should allow to use constraint numbers in that case, to easily display the unsat core in terms of constraints number (might not be that good because an equality constraint is splitted into 2 constraints).https://gitlab.ow2.org/sat4j/sat4j/-/issues/24Add statistics about SAT/UNSAT calls2018-05-11T12:15:13ZDaniel Le BerreAdd statistics about SAT/UNSAT callsWhen doing optimization, it is sometimes useful to be able to get some statistics about the number of calls to the SAT solver, and how much time is spent for SAT and UNSAT.When doing optimization, it is sometimes useful to be able to get some statistics about the number of calls to the SAT solver, and how much time is spent for SAT and UNSAT.https://gitlab.ow2.org/sat4j/sat4j/-/issues/22DependencyHelper (the solvers in general) behave differently when units are s...2018-05-11T12:15:13ZDaniel Le BerreDependencyHelper (the solvers in general) behave differently when units are set first or set lastThe DependencyHelper behavior can look strange to newcomer since its behavior depends of the order of the constraints.
SAT power users use that order to let the solver perform as much simplification as possible.
Here, we receive an exception when the constraints are simplified.
Several options are available:
- do not fix, its a feature, not a bug
- fix be ignoring simplified constraints => no more control of what's going on in the helper, might be error prone
- fix by delegating unit to be the last thing added to the solver: the helper acts as a proxy here. => no more power user control of the helper.
Need to think about it.The DependencyHelper behavior can look strange to newcomer since its behavior depends of the order of the constraints.
SAT power users use that order to let the solver perform as much simplification as possible.
Here, we receive an exception when the constraints are simplified.
Several options are available:
- do not fix, its a feature, not a bug
- fix be ignoring simplified constraints => no more control of what's going on in the helper, might be error prone
- fix by delegating unit to be the last thing added to the solver: the helper acts as a proxy here. => no more power user control of the helper.
Need to think about it.https://gitlab.ow2.org/sat4j/sat4j/-/issues/19Allow creation of clauses, cardinality and pseudo boolean constraints using a...2018-05-11T12:15:13ZDaniel Le BerreAllow creation of clauses, cardinality and pseudo boolean constraints using arrays of primitive typeWhen creating test cases, it is painful for many users to create feed VecInt to create new clauses.
It would be much simpler to simply use arrays of integers in addClause for instance.When creating test cases, it is painful for many users to create feed VecInt to create new clauses.
It would be much simpler to simply use arrays of integers in addClause for instance.