MaxInfluence

class ioh.iohcpp.problem.MaxInfluence

Bases: GraphProblem

Max-Influence problems

The maximum influence problem in social networks is an important submodular optimization problem that has been widely studied in the literature from various perspectives. Let a directed graph G(V, E) represent a social network, where each node is a user and each edge (u, v) ∈ E has a probability pu,v representing the strength of influence from user u to v.

A fundamental propagation model is independence cascade. Starting from a seed set X, it uses a set At to record the nodes activated at time t, and at time t + 1, each inactive neighbor v of u ∈ At becomes active with probability pu,v. This process is repeated until no nodes get activated at some time. The set of nodes activated by propagating from X is denoted as IC(X), which is a random variable.

The goal is to maximize the expected value of IC(X). Note that the computation of the expected value is done by running a simulation of the influence process several times and averaging its results. In this sense, the computation of the objective function value is stochastic.

For a given search point x ∈ {0, 1}^n where n = |V|, we have V’(x) = {vi | xi = 1} and c(x) = SUM_{v∈V 0(x)} c(v).

Reference

[Neumann23] Neumann, Frank, Aneta Neumann, Chao Qian, Viet Anh Do, Jacob de Nobel, Diederick Vermetten, Saba Sadeghi Ahouei, Furong Ye, Hao Wang, and Thomas Bäck. “Benchmarking Algorithms for Submodular Optimization Problems Using IOHProfiler.” arXiv preprint arXiv:2302.01464 (2023).

Attributes Summary

bounds	The bounds of the problem.
constraints	The constraints of the problem.
create
graph	The underlying graph structure
load_instances
log_info	The data is that being sent to the logger.
meta_data	The static meta-data of the problem containing, e.g., problem id, instance id, and problem's dimensionality
optimum	The optimum and its objective value for a problem instance
problems	All registered problems
state	The current state of the optimization process containing, e.g., the current solution and the number of function evaluated consumed so far

Methods Summary

__call__([order, device])	Overloaded function.
add_constraint(self, arg, /)	add a constraint
attach_logger(self, arg, /)	Attach a logger to the problem to allow performance tracking.
detach_logger(self)	Remove the specified logger from the problem.
enforce_bounds(self[, weight, how, exponent])	Enforced the bounds (box-constraints) as constraint :param weight: :type weight: The weight for computing the penalty (can be infinity to have strict box-constraints) :param how: :type how: The enforcement strategy, should be one of the 'ioh.ConstraintEnforcement' options :param exponent: :type exponent: The exponent for scaling the contraint
invert(self)
remove_constraint(self, arg, /)	remove a constraint
reset(self)	Reset all state variables of the problem.
set_final_target(self, new_target)	update the final target
set_id(self, new_problem_id)	update the problem id
set_instance(self, new_instance)	update the problem instance
set_name(self, new_name)	update the problem name

Attributes Documentation

bounds

The bounds of the problem.

constraints

The constraints of the problem.

create = <nanobind.nb_func object>

graph

The underlying graph structure

load_instances = <nanobind.nb_func object>

log_info

The data is that being sent to the logger.

meta_data

The static meta-data of the problem containing, e.g., problem id, instance id, and problem’s dimensionality

optimum

The optimum and its objective value for a problem instance

problems

All registered problems

state

The current state of the optimization process containing, e.g., the current solution and the number of function evaluated consumed so far

Methods Documentation

__call__(self, arg: ndarray[shape=(*), order='C', device='cpu'], /) → float

__call__(self, arg: collections.abc.Sequence[int], /) → float

__call__(self, arg: ndarray[shape=(*, *), order='C', device='cpu'], /) → numpy.ndarray[dtype=float64, shape=(*)]

__call__(self, arg: collections.abc.Sequence[collections.abc.Sequence[int]], /) → numpy.ndarray[dtype=float64, shape=(*)]

Overloaded function.

1. __call__(self, arg: ndarray[shape=(*), order='C', device='cpu'], /) -> float

2. __call__(self, arg: collections.abc.Sequence[int], /) -> float

   Evaluate the problem.

   x: list

   the search point to evaluate. It must be a 1-dimensional array/list whose length matches search space’s dimensionality

   float

   The evaluated search point

3. __call__(self, arg: ndarray[shape=(*, *), order='C', device='cpu'], /) -> numpy.ndarray[dtype=float64, shape=(*)]

4. __call__(self, arg: collections.abc.Sequence[collections.abc.Sequence[int]], /) -> numpy.ndarray[dtype=float64, shape=(*)]

   Evaluate the problem at several search points.

   x: list[list]

   the search points to evaluate, one per row. It must be a 2-dimensional array/list whose rows’ length matches search space’s dimensionality

   numpy.ndarray

   The objective values of the search points: a new float64 array with one value per row

add_constraint(self, arg: ioh.iohcpp.AbstractIntegerConstraint, /) → None

add a constraint

attach_logger(self, arg: ioh.iohcpp.logger.Logger, /) → None

Attach a logger to the problem to allow performance tracking.

Parameters:

logger (Logger) – A logger-object from the IOHexperimenter logger module.

detach_logger(self) → None

Remove the specified logger from the problem.

enforce_bounds(self, weight: float = 1.0, how: ioh.iohcpp.ConstraintEnforcement = ConstraintEnforcement.SOFT, exponent: float = 1.0) → None

Enforced the bounds (box-constraints) as constraint :param weight: :type weight: The weight for computing the penalty (can be infinity to have strict box-constraints) :param how: :type how: The enforcement strategy, should be one of the ‘ioh.ConstraintEnforcement’ options :param exponent: :type exponent: The exponent for scaling the contraint

invert(self) → None

remove_constraint(self, arg: ioh.iohcpp.AbstractIntegerConstraint, /) → None

remove a constraint

reset(self) → None

Reset all state variables of the problem.

set_final_target(self, new_target: float) → None

update the final target

set_id(self, new_problem_id: int) → None

update the problem id

set_instance(self, new_instance: int) → None

update the problem instance

set_name(self, new_name: str) → None

update the problem name