If you have any comments or need more instances for the following benchmarks, please send me an email.
The Pseudo-Boolean (0-1 integer programming) problem is a linear integer programming problem where all variables are restricted to take values of either 0 or 1. This problem is NP-hard, and as such, it is considered unlikely that there exists an efficient algorithm for solving it. The Pseudo-Boolean (0-1 Integer Programming) benchmarks presented here are directly transformed from forced satisfiable SAT benchmarks of Model RB, with the set of variables and the set of constraints respectively corresponding to the set of variables and the set of binary clauses in SAT instances. In fact, based on Model RB and this transformation, we can get a random Pseudo-Boolean model as follows:
First generate n disjoint sets of variables, each of which has cardinality nα (where α>0 is a constant), and then for every two variables x and y in the same set, generate a constraint x + y <= 1;
Randomly select two different disjoint sets and then generate without repetitions pn2α constraints of the form x + z <= 1 where x and z are two variables selected at random from these two sets respectively (where 0<p<1 is a constant);
Run Step 2 (with repetitions) for another rnlnn-1 times (where r>0 is a constant).
The objective function is to maximize the sum of all variables. It is easy to see that for the Pseudo-Boolean model above, the value of the objective function is at most n. Interestingly, determining if such a upper bound can be reached is equivalent to determining the satisfiability of the corresponding CSP and SAT instances of Model RB, and there is a one-to-one mapping between the solutions of these two problems. To hide an optimum solution of value n in the instances of this Pseudo-Boolean model, we first select a variable at random from each disjoint set to form a set of n variables which take value 1, and then in the above process of generating random constraints, no constraint is allowed to violate this hidden optimum solution. From the results of the paper "Many Hard Examples in Exact Phase Transitions with Application to Generating Hard Satisfiable Instances", it is expected that Model RB can also be used to generate hard instances for Pseudo-Boolean algorithms (by use of the above Pseudo-Boolean model and the hardness of phase transitions, i.e. choosing appropriate values of α, p and r). For the experimental results of Model RB with respect to CSP instances, please see a recent paper entitled "A Simple Model to Generate Hard Satisfiable Instances".
Note: The following Pseudo-Boolean (0-1 Integer Programming) benchmarks are expressed in the opb format which can be found on PBLIB.
News: The above benchmarks were used for Pseudo Boolean Evaluation 2005. The results are summarized in following table where the Best Value represents the best value obtained in the competition by the competing solvers.
| frb30-15-1.opb | frb30-15-2.opb | frb30-15-3.opb | frb30-15-4.opb | frb30-15-5.opb | |
| Optimum Value | 30 | 30 | 30 | 30 | 30 |
| Best Value | 30 | 30 | 30 | 30 | 30 |
| frb35-17-1.opb | frb35-17-2.opb | frb35-17-3.opb | frb35-17-4.opb | frb35-17-5.opb | |
| Optimum Value | 35 | 35 | 35 | 35 | 35 |
| Best Value | 34 | 33 | 34 | 35 | 33 |
| frb40-19-1.opb | frb40-19-2.opb | frb40-19-3.opb | frb40-19-4.opb | frb40-19-5.opb | |
| Optimum Value | 40 | 40 | 40 | 40 | 40 |
| Best Value | 38 | 38 | 38 | 37 | 38 |
| frb45-21-1.opb | frb45-21-2.opb | frb45-21-3.opb | frb45-21-4.opb | frb45-21-5.opb | |
| Optimum Value | 45 | 45 | 45 | 45 | 45 |
| Best Value | 41 | 41 | 41 | 42 | 41 |
| frb50-23-1.opb | frb50-23-2.opb | frb50-23-3.opb | frb50-23-4.opb | frb50-23-5.opb | |
| Optimum Value | 50 | 50 | 50 | 50 | 50 |
| Best Value | 46 | 45 | 45 | 46 | 46 |
| frb53-24-1.opb | frb53-24-2.opb | frb53-24-3.opb | frb53-24-4.opb | frb53-24-5.opb | |
| Optimum Value | 53 | 53 | 53 | 53 | 53 |
| Best Value | 49 | 48 | 49 | 48 | 48 |
| frb56-25-1.opb | frb56-25-2.opb | frb56-25-3.opb | frb56-25-4.opb | frb56-25-5.opb | |
| Optimum Value | 56 | 56 | 56 | 56 | 56 |
| Best Value | 49 | 49 | 50 | 50 | 49 |
| frb59-26-1.opb | frb59-26-2.opb | frb59-26-3.opb | frb59-26-4.opb | frb59-26-5.opb | |
| Optimum Value | 59 | 59 | 59 | 59 | 59 |
| Best Value | 52 | 52 | 51 | 52 | 53 |
Remark: As mentioned before, finding optimum solutions to the above Pseudo-Boolean (0-1 Integer Programming) instances is equivalent to finding solutions to the corresponding forced satisfiable CSP and SAT instances of Model RB. It is worth noting that some corresponding SAT benchmarks of the above instances were used for SAT Competition 2004 (55 solvers). The results are summarized as follows (Note: Instances differing only in the suffix are equivalent, e.g. frb40-19-1.opb and frb40-19-1.cnf):
Forced Satisfiable CSP and SAT Benchmarks of Model RB
Benchmarks with Hidden Optimum Solutions for Graph Problems
Date Created: May 11, 2004. Last Updated: Jul. 7, 2005.