pydcop generate ising

Ising benchmark problem generator

pydcop generate ising
              --row_count <row_count>
              [--col_count <col_count>]
              [--bin_range <bin_range>]
              {--un_range <un_range>]
              [-intentional]
              [--fg_dist]

Description

This command generates a DCOP modelling an ising problem [CEPRA18].

The Ising model is a widely used benchmark in statistical physics ; constraint graphs are rectangular grids where each binary variable is connected to its four closer neighbors (with toroidal links which connect opposite sides of the grid), and is constrained by a unary cost \(r_i\).

The weight of each binary constraint \(r_{ij}\) is determined by first sampling a value \(k_{ij}\) from a uniform distribution \(U[−\beta,\beta]\) and then assigning \(r_{ij}(x_i,x_j) = k_{ij}\) if \(x_i = x_j, −κ_{ij}\) otherwise. The \(\beta\) parameter controls the average strength of interactions.

The weight for each unary constraint \(r_i\) is determined by sampling \(k_i\) from a uniform distribution \(U[-\rho, \rho]\) and then assigning \(r_i (0) = k_i\) and \(r_i(1) = −k_i\).

When using --var_dist, this generator produces one agent for each variable and a distribution file that maps each variable to one agent. When using a factor-graph based algorithm, you can use the --fg_dist flag in order to generate a distribution that maps one variable and 3 constraints to each agents. Each unary constraint is mapped to the agent holding the corresponding variable. This agent also takes responsibility for the binary constraints on the right and bellow this variable in the grid. Both options can be used simultaneously, in which case both distributions will be generated.

Note: the generated DCOP and distribution(s) are written to the standard output. To write them in files, you can use the --output <file> global option.

Options

--row_count <row_count>

Number of rows in the grid, must be >= 2.

--col_count <col_count>

Number of columns in the grid, optional. If col_count is not given, the generated will be a square of size row_count. If given, col_count must be >= 2.

--bin_range <bin_range>

\(\beta\) value used for binary constraints. Defaults to 1.6.

--un_range <un_range>

\(\rho\) value used for unary constraints. Defaults to 0.05.

--intentional

When using this flag, constraints are generated in the intentional form (default is extensive).

--fg_dist

When using this flag, the agents and distribution are generated for factor-graph based algorithms where computations are needed for variables and constraints. When outputting (with the --output global option) the dcop in a file <dcop_name.yaml>, the distribution is automatically written to a file <dcop_name>_fgdist.yaml.

--var_dist

When using this flag, the agents and distribution are generated for a classic constraint graph where computations are needed for variables and each agent is responsible one variable. When outputting (with the --output global option) the dcop in a file <dcop_name.yaml>, the distribution is automatically written to a file <dcop_name>_vardist.yaml.

Examples

Generate a DCOP representing a 3x4 ising problem, in extensive form:

pydcop generate ising --row_count 3 --col_count 4

Generate a DCOP representing a 3x4 ising problem, in intentional form and written to disk:

pydcop --output ising.yaml  generate ising --row_count 3 --col_count 4 \
         --bin_range 1.6 --un_range 0.05 --intentional --fg_dist --var_dist