Pseudo-Boolean (0-1 Integer Programming) Benchmarks with Hidden Optimum Solutions

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:

1. 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;

2. 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);

3. 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.

• frb30-15-opb.tar.gz (  447 KB):   450 variables (30 disjoint sets) - 5 instances, with the optimum value  = 30
• frb35-17-opb.tar.gz (  693 KB):   595 variables (35 disjoint sets) - 5 instances, with the optimum value  = 35
• frb40-19-opb.tar.gz (1029 KB):   760 variables (40 disjoint sets) - 5 instances, with the optimum value  = 40
• frb45-21-opb.tar.gz (1459 KB):   945 variables (45 disjoint sets) - 5 instances, with the optimum value  = 45
• frb50-23-opb.tar.gz (2021 KB): 1150 variables (50 disjoint sets) - 5 instances, with the optimum value  = 50
• frb53-24-opb.tar.gz (2381 KB): 1272 variables (53 disjoint sets) - 5 instances, with the optimum value  = 53
• frb56-25-opb.tar.gz (2774 KB): 1400 variables (56 disjoint sets) - 5 instances, with the optimum value  = 56
• frb59-26-opb.tar.gz (3211 KB): 1534 variables (59 disjoint sets) - 5 instances, with the optimum value  = 59

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).

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!)
 

Back to Ke Xu's homepage.

Date Created: May 11, 2004. Last Updated: Aug. 30, 2006.