Class markov::Model

Interface for Markov models.

Implementations of the Markov model interface must provide

A calculate_cost (to calculate the cost of an entire state as well as the calculate_cost_difference incurred by a specific transition).
The means to generate the Monte Carlo chain (random_state, random_transition and apply_transition). The interface is templated for both the underlying Markov state and transition, such that users can decide how to represent each. The base classes markov::State and markov::Transition are provided as guidelines for designing these model-specifc types, but they are not enforced to be used. (That is, you may use Model<std::string, int> if a string is sufficient to represent your state and an int defines a transition. State

For initial testing, you may also opt to use the simplified classes markov::SimpleTransition and markov::SimpleModel. SimpleModel

SimpleTransition

Inheritance

model::BaseModel

markov::Model

Inherited Members

match_version

get_version

~BaseModel

configure

BaseModel

get_identifier

~Component

Component

get_status

param

get_class_name

Constructors

Model()

Create an uninitialized model.

Declaration

markov::Model<State, Transition, Cost>::Model()

Methods

set_step_limit()

Declaration

void markov::Model<State, Transition, Cost>::set_step_limit(uint64_t limit)

configure()

configure the object from input

Initialize the object's state from the input utils::Config. This is done by declaring which required and optional parameters are associated with the fields of this object. During initialization, they are checked for their presence, type and any matchers. Example:

MyClass : public Component {
 public:
  void configure(const utils::Json& json) override {
    this->param(json, "number", my_number)
        .description("some description")
        .matches(GreaterEquals(0))
        .required();
    this->param(json, "name", my_name)
        .description("some description")
        .matches(SizeIs(GreaterThan(0)))
        .default_value("no_name");
  }

 private:
  int my_number;
  std::string my_name;
}

MyClass my_object;
my_object.configure(utils::json_from_string(R"(
  {
    "number": 42,
    "name": "hello"
  }
)"));

Note

By default, nothing is configured from input. You need to overload this method if you want to use this functionality. Don't forget to call the configure method of the parent class if it also needs to be configured (this is not the case for utils::Component itself). HINT: Parameters are not limited to scalars and strings; Any component can be a parameter; in which case it is initialized using its own configure method. utils::Json

Declaration

void markov::Model<State, Transition, Cost>::configure(const utils::Json&json) override

configure()

Declaration

void markov::Model<State, Transition, Cost>::configure(model::BaseModelConfiguration&configuration)

init()

Initializes internal data structures (guaranteed to be called after configure()).

Declaration

void markov::Model<State, Transition, Cost>::init() override

calculate_cost()

Definition of the cost function.

Evaluate the entire cost function for the state being passed. For instance, in the case of a model from statistical mechanics, this would be the Hamiltonian.

Declaration

virtual Cost_T markov::Model<State, Transition, Cost>::calculate_cost(const State_T&state) const =0

calculate_cost_difference()

Partial evaluation of the cost function.

This method should calculate the difference in cost if we move from state (=before) to the one resulting from applying transition to state (=after):

 \Delta_{C} = C_{\mathrm{after}} - C_{\mathrm{before}}

In code: State state = get_random_state(rng); Transition transition = get_random_transition(rng); double cost_before = calculate_cost(state); double cost_diff = calculate_cost_difference(state, transition); apply_transition(transition, state); // modify state double cost_after = calculate_cost(state); // before + diff should correspond to after (up to double precision) assert(cost_before + cost_diff == cost_after);

Declaration

virtual Cost_T markov::Model<State, Transition, Cost>::calculate_cost_difference(const State_T&state, const Transition_T&transition) const =0

get_random_state()

Return a valid random state for the model.

The various algorithms don't know how to initialize a valid state; this allows them to start with a random one. NOTE: The rng being passed should be used for randomness (as opposed to creating one for the model), as multiple threads can potentially use the same underlying model (albeit with separate rngs).

Declaration

virtual State_T markov::Model<State, Transition, Cost>::get_random_state(utils::RandomGenerator&rng) const =0

has_initial_configuration()

Check if model has initial configuration.

Declaration

virtual bool markov::Model<State, Transition, Cost>::has_initial_configuration() const

get_initial_configuration_state()

Return a state from initial configuration.

Declaration

virtual State_T markov::Model<State, Transition, Cost>::get_initial_configuration_state() const

get_random_transition()

Return a random transition starting at state.

The various algorithms don't know how to move throuhg markov space; this allows them to pick a random direction given a starting point.

By definition, the next markov state should only depend on the current one, so only the last one is passed to this function.
"random" does not necessitate equi-distributed here (you may choose a different distribution if your model dictates it). However, the the typical choise is to pick randomly from all possible moves at state with equal probability.

Declaration

virtual Transition_T markov::Model<State, Transition, Cost>::get_random_transition(const State_T&state, utils::RandomGenerator&rng) const =0

apply_transition()

Apply a transition to a state.

This changes the configuration represented by *state. Depending on the optimization algorithm, transition can either be applied conditionally or alaways (e.g., population dynamics). Separating the functionality into the three interfaces random_transition, calculate_cost_difference, apply_transition leaves control over the strategy with the optimization method.

Declaration

virtual void markov::Model<State, Transition, Cost>::apply_transition(const Transition&transition, State&state) const =0

render_state()

Render a state of this model.

Default implementation of how a state of this model is rendered (by' invoking the state's proper rendering mechanic). Overloading this method allows a model implementation to customize how a state is printed. This is relevant if the rendering needs to depend on model parameters in addition to the state.

Declaration

virtual utils::Structure markov::Model<State, Transition, Cost>::render_state(const State_T&state) const

get_sweep_size()

Return the number of (attempted) transition to consider one sweep.

This number is expected to scale roughly with the number of variables in the model such that, on average, each variable is selected once per sweep (if selected randomly).

Declaration

virtual size_t markov::Model<State, Transition, Cost>::get_sweep_size() const

get_term_count()

Declaration

virtual size_t markov::Model<State, Transition, Cost>::get_term_count() const

get_benchmark_properties()

Collect statistics about the model being simulated.

The output of this method will appear in the Response.benchmark.input_data field. By default, we do not collect any model statistics implementations of this interface must override this method to fill the output.

Declaration

virtual utils::Structure markov::Model<State, Transition, Cost>::get_benchmark_properties() const

render()

render the object in structured form

Return a structured representation of the object. This is intended for output purposes. For instance, the solution your solver finds should have a render method which allows it to be returned as part of the result. Example:

{c++}
 MySolution : public Component {
  public:
   // Represent the internal bool vector as +-1 output.
   utils::Structure render() const override {
     utils::Structure rendered;
     for (bool item : solution_) rendered.push_back(item ? 1 : -1);
     return rendered;
   }

  private:
   std::vector<bool> solution_;
 }

 MySolution solution;
 std::cout << solution.render().to_string() << std::endl;

utils::Structure

Declaration

utils::Structure markov::Model<State, Transition, Cost>::render() const override

is_rescaled()

Declaration

virtual bool markov::Model<State, Transition, Cost>::is_rescaled() const

rescale()

Declaration

virtual void markov::Model<State, Transition, Cost>::rescale()

get_scale_factor()

Declaration

virtual Cost_T markov::Model<State, Transition, Cost>::get_scale_factor() const

get_const_cost()

Declaration

virtual Cost_T markov::Model<State, Transition, Cost>::get_const_cost() const

is_empty()

Declaration

virtual bool markov::Model<State, Transition, Cost>::is_empty() const =0

state_memory_estimate()

Estimate memory consumption of model state and lowest state in bytes, using paramters known by model. Numerous states will be created by solvers. Estimation of memory consumption is needed to avoid memory overflow. States may have complex nature, so knowledge of model parameters should be used for accurate estimation. For prototype models return 0 could be used.

Declaration

virtual size_t markov::Model<State, Transition, Cost>::state_memory_estimate() const =0

state_only_memory_estimate()

Declaration

virtual size_t markov::Model<State, Transition, Cost>::state_only_memory_estimate() const =0

estimate_max_cost_diff()

Declaration

virtual double markov::Model<State, Transition, Cost>::estimate_max_cost_diff() const

estimate_min_cost_diff()

Declaration

virtual double markov::Model<State, Transition, Cost>::estimate_min_cost_diff() const