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 sizerow_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