Joint Generation

The input to joint generation is an oracle, describing a monotone property, over an integral box. The output consists of two subsets, F and G, containing respectively all minimal satisfying and maximal non-satisfying integral vectors for the input monotone property.

Below is a detailed description of the parameters, input and output files, together with some examples and downloadable executables.

---

Calling the program

"C:\> gen     OracleFileName    PrimalFileName    DualFileName" where

• gen is the name of the joint generation code, prepared to understand the particular oracle (see examples below).
• OracleFileName is the name of the file containing the oracle description. The format of this file depends on the particular oracle (see examples below).
• PrimalFileName is the name of the (output) file to contain the set of minimal satisfying vectors F.
• DualFileName is the name of the (output) file to contain the set of maximal non-satisfying vectors G.

The primal and dual files contain the output vectors one per line, with components separated by spaces.

As a demonstration of joint generation, we prepared examples with three different oracles, and provide below the compiled executables under different names.

Important remarks

• All files must be in the same directory where the program is to be run.
• If the code finds one or both of the output files PrimalFileName and DualFileName in the same directory, containing partial (possibly empty) lists of minimal satisfying and maximal non-satisfying elements for the input monotone property, then it will proceed to complete these partial lists, and generates the rest in both files.
• These codes are provided as "research ware", and in particular, the usually tedious and oracle dependent data consistency checks are not included. Please make sure that the input files adhere to the syntax we describe below (and if you provide partial lists also as input, those must indeed include minimal/maximal elements for the specified monotone property).

---

Example 1 - Linear Systems of Monotone Inequalities:

"C:\> sys     sys.o    sys.p    sys.d"


The oracle is this case is described by an r x n non-negative matrix A, and an r-dimensional real vector b. The families F and G correspond, respectively, to minimal feasible and maximal infeasible integral vectors x for the system Ax³b. The first line of the oracle file sys.o should contain the 3 values n,r and c, where:

• n is the number of variables,
• r is the number of constraints, and
• c is an upper bound on each variable (i.e variables can take integer values between 0 and c).

The next lines of the oracle file specify the rows of the matrix [A | b], one per line, with entries sperated by spaces.

The output files sys.p and sys.d contain respectively the families F and G.

Example 1(a):   3 constraints within [0,5]²:

	Sytem of inequalities	Input file	Output files
		sys1.o	sys1.p	sys1.d
	2x1+2x2³5   x1+4x2³5 3x1+  x2³4	2   3   5 2   2   5 1   4   5 3   1   4	0   4 1   2 2   1 5   0	4   0 1   1 0   3

Example 1(b):   4 constraints within [0,2]⁵:

	Sytem of inequalities	Input file	Output files
		sys2.o	sys2.p	sys2.d
	x1 +x3 +2x4 +4x5 ³11 x1 +2x2 +3x5 ³5 3x1 +2x2 +2x3 +x4 ³14 x1 +2x3 +x5 ³3	5   4   2 1   0   1   2   4   11 1   2   0   0   3   5 3   2   2   1   0   14 1   0   2   0   1   3	2   1   2   2   1 2   2   1   2   1 2   2   2   0   2	1   2   2   2   2 2   0   2   2   2 2   1   1   2   2 2   1   2   1   2 2   2   0   2   2 2   2   1   1   2 2   2   2   1   1 2   2   2   2   0

Download the program

• Win32 executable
• Linux executable

---

Example2 - Minimal Infrequent and Maximal Frequent Sets Sets:

"C:\> inf     inf.o    inf.p    inf.d"

The oracle is this case is described by an r x n 0-1 matrix D, that represents a database, and an integer threshold t. The families F and G correspond, respectively, to minimal infrequent and maximal frequnet sets, that is subsets of columns contined in at most t-1 and at least t of the rows, respectively.

The first line of the oracle file inf.o should contain the 3 values n,r and t. The next lines of the oracle file specify the rows of the matrix D, one per line, with entries sperated by spaces.

The output files inf.p and inf.d contain respectively the families F and G.

	Input File	Output Files
	inf.o	inf.p	inf.d
	8   6   2 0   0   1   0   1   0   1   1 1   1   0   0   0   1   1   0 1   0   1   1   0   0   1   1 0   1   1   1   1   1   0   0 1   1   0   1   1   1   0   0 1   0   1   1   1   1   1   0	0   0   0   0   0   1   0   1 0   0   0   0   1   0   0   1 0   0   0   0   1   1   1   0 0   0   0   1   1   0   1   0 1   1   0   0   1   0   0   0 0   1   0   0   0   0   1   0 0   1   1   0   0   0   0   0 1   0   1   0   1   0   0   0 1   0   1   0   0   1   0   0 0   0   1   0   0   1   1   0 1   0   0   0   1   0   1   0 1   1   0   1   0   0   0   0 0   0   0   1   0   1   1   0 1   0   0   0   0   0   0   1 0   1   0   0   0   0   0   1 0   0   0   1   0   0   0   1	1   1   0   0   0   1   0   0 0   1   0   1   1   1   0   0 1   0   0   1   1   1   0   0 1   0   1   1   0   0   1   0 0   0   1   1   1   1   0   0 1   0   0   0   0   1   1   0 0   0   1   0   1   0   1   0 0   0   1   0   0   0   1   1

Download the program

• Win32 executable
• Linux executable

---

Example 3- Perfect Matchings and Minimal Blockers in Bipartite Graphs:

"C:\> pmatch     pmatch.o    pmatch.p    pmatch.d"

The oracle is this case is described by a bipartite graph D on 2n vertices AÈB. The families F and G correspond, respectively, to perfect matchings and maximal subgraphs of D not containing a perfect matching (i.e complements to minimal blockers of perfect matchings in D). The vertices in D are assumed to be numbered from 0 to 2n-1, with even numbers assigned to the vertices in A and odd numbers assigned to the vertices of B.

The number of lines in the oracle file pmatch.o is n, where the ith line contains the vertices adjacent to vertex number 2(i-1), separated by spaces and terminated by -1.

Each element in F and G represents a subgraph as a 0-1 vector, which is the characteristic vector of the corresponding edge set. Edges of D are numbered according to their occurence in the oracle file. The output files pmatch.p and pmatch.d contain respectively the families F and G, i.e., the lists of perfect matchings and complements of minimal blockers of D, represented by the characteristic vectors of these edge subsets.

In the example below the graph D is the complete 3 x 3 bipartite graph, where A={1,3,5} and B={0,2,4}, and where the edges are labeled in the order (0,1),(0,3),(0,5),(2,1),(2,3),(2,5),(4,1),(4,3),(4,5).

	Input File	Output Files
	pmatch.o	pmatch.p	pmatch.d
	1   3   5   -1 1   3   5   -1 1   3   5   -1	0   0   1   0   1   0   1   0   0 0   0   1   1   0   0   0   1   0 0   1   0   0   0   1   1   0   0 0   1   0   1   0   0   0   0   1 1   0   0   0   0   1   0   1   0 1   0   0   0   1   0   0   0   1	0   0   0   1   1   1   1   1   1 0   0   1   0   0   1   1   1   1 0   0   1   1   1   1   0   0   1 0   1   0   0   1   0   1   1   1 0   1   0   1   1   1   0   1   0 0   1   1   0   1   1   0   1   1 1   0   0   1   0   0   1   1   1 1   0   0   1   1   1   1   0   0 1   0   1   1   0   1   1   0   1 1   1   0   1   1   0   1   1   0 1   1   1   0   0   0   1   1   1 1   1   1   0   0   1   0   0   1 1   1   1   0   1   0   0   1   0 1   1   1   1   0   0   1   0   0 1   1   1   1   1   1   0   0   0

Thus, e.g., the first line in pmatch.p represents the perfect matching {(0,5),(2,3),(4,1)}, while the first line of pmatch.d is the complement of the minimal blocker {(0,1),(0,3),(0,5)}.

Download the program

• Win32 executable
• Linux executable

The following demo is an interactive graphical illustration of the joint generation of perfect matchings and minimal blockers of bipartite graphs.

Download Demo (Windows):

• Demo package

---