PB06: Input Format

This is an archived description of the PB06 input format. For the PB07 evaluation, this format is maintained for linear pseudo-Boolean instances.

The input file format is a  stricter variant of the OPB format (see the end of the README file in http://www.mpi-sb.mpg.de/units/ag2/software/opbdp/opbdp1.1.1.tar.gz). Here is an example:

* #variable= 5 #constraint= 4
*
* comments
*
*
min: 1 x2 -1 x3 ;
1 x1 +4 x2 -2 x5 >= 2;
-1 x1 +4 x2 -2 x5 >= +3;
12345678901234567890 x4 +4 x3 >= 10;
* an equality constraint
2 x2 +3 x4 +2 x1 +3 x5 = 5 ;
Most of the syntax of this file can be described by a simple BNF grammar (see http://en.wikipedia.org/wiki/Backus-Naur_form). <formula> is the start symbol of this grammar.
<formula>::= <sequence_of_comments>
[<objective>]
<sequence_of_comments_or_constraints>

<sequence_of_comments>::= <comment> [<sequence_of_comments>]
<comment>::= "*" <any_sequence_of_characters_other_than_EOL> <EOL>

<sequence_of_comments_or_constraints>::=<comment_or_constraint> [<sequence_of_comments_or_constraints>]
<comment_or_constraint>::=<comment>|<constraint>

<objective>::= "min:" <zeroOrMoreSpace> <linearfunction> ";"
<constraint>::= <linearfunction> <relational_operator> <zeroOrMoreSpace> <integer> <zeroOrMoreSpace> ";"

<linearfunction>::= <product> | <product><linearfunction>
<product>::= <integer> <oneOrMoreSpace> <variablename> <oneOrMoreSpace>

<integer>::= <unsigned_integer> | "+" <unsigned_integer> | "-" <unsigned_integer>
<unsigned_integer>::= <digit> | <digit><unsigned_integer>

<relational_operator>::= ">=" | "="

<variablename>::= "x" <unsigned_integer>

<oneOrMoreSpace>::= " " [<oneOrMoreSpace>]
<zeroOrMoreSpace>::= [" " <zeroOrMoreSpace>]
Some comments and details:
Notice that integers may be of arbitrary size in the file. See here for a rationale.

The rules let us write a very simple parser and avoid some ambiguities present in the original description of the OPB format. At the same time, the format remains easily human readable and is compatible with solvers using the OPB format.