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.

News

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


Back to Ke Xu's homepage.

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