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 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 propose a simple 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 (Step 2), 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). Recently, it has been shown (both experimentally and theoretically) that unlike random 3-SAT, it is quite natural and easy to hide solutions in random CSP and SAT instances of Model RB. For more details, please see an IJCAI-05 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
In 2005, according to weblog statistics, this webpage was visited 4330 times (by people from 46 countries) and the above benchmarks were downloaded 445 times. Most visitors were from USA, China, Canada, UK, India, France, Germany, Australia, Italy and Spain (about 1/3 of them came through Google).
The above benchmarks were used for Pseudo Boolean Evaluation 2005 (8 solvers) and Pseudo Boolean Evaluation 2006 (14 solvers). The results are summarized in following table where the "Best Value (2005)" and "Best Value (2006)" respectively represent the best values obtained in the competition by the competing solvers in 2005 (the timeout is 20 minutes) and in 2006 (the timeout is 30 minutes).
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 (2005) | 30 | 30 | 30 | 30 | 30 |
Best Value (2006) | 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 (2005) | 34 | 33 | 34 | 35 | 33 |
Best Value (2006) | 35 | 35 | 35 | 35 | 35 |
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 (2005) | 38 | 38 | 38 | 37 | 38 |
Best Value (2006) | 40 | 39 | 40 | 40 | 39 |
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 (2005) | 41 | 41 | 41 | 42 | 41 |
Best Value (2006) | 44 | 44 | 44 | 45 | 44 |
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 (2005) | 46 | 45 | 45 | 46 | 46 |
Best Value (2006) | 49 | 49 | 49 | 49 | 49 |
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 (2005) | 49 | 48 | 49 | 48 | 48 |
Best Value (2006) | 52 | 52 | 51 | 51 | 51 |
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 (2005) | 49 | 49 | 50 | 50 | 49 |
Best Value (2006) | 54 | 54 | 54 | 54 | 54 |
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 (2005) | 52 | 52 | 51 | 52 | 53 |
Best Value (2006) | 57 | 57 | 57 | 57 | 57 |
List
of Papers That Use PB Benchmarks Based on Model RB
(Updated:
Mar. 4, 2009)
Other Benchmarks Based on Model RB
Forced Satisfiable CSP and SAT
Benchmarks of Model RB
Benchmarks with Hidden Optimum Solutions for Graph Problems
Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination
Weighted Max-2-SAT Benchmarks with
Hidden Optimum Solutions (New!)
Date Created: May 11, 2004. Last Updated: Aug. 30, 2006.